Movhex is a Project which, given a Map of an Area, gives the path with the fewer cost possible in order to go from a point to another.
The Map has been represented as a 2D Matrix of Exagonal Tiles, each defined by an height attribute (symbolising its cost).
The Map can be modified adding Monodirectional Air Routes from one Tile to another and changing the heights of some areas, such as a real world Map being not flat.
This Project was born as an assigment from the "Algorithm and Data Structures" class I have followed during my Computer Science Engineering course at Politecnico di Milano.
All the notes I created wile working on this project have been published in this repository as well, all collected in the Movhex_notes.pdf file.
In order to obtain the wanted path, the Movhex program has to analyse a Map following some cost criteria.
The Map is represented by a Matrix of Exagonal Tiles, each one defined by a height attribute; when exiting from a Tile, you have to pay the given cost, and if it is equal to 0, the Tile cannot be exited.
Every Tile can have up to AIR_ROUTES_OUT_MAX (set to 5 from the assignement) outgoing Air Routes, which connects two Tiles regardless of their distance, using the same cost as the starting Tiles' height.
In order to find the Shortest Path, has been implemented the Dijkstra Search Algorithm (since the Air Routes presence makes impossibile to get an efficient euristic as in the A* Search Algorithm), adapted to the Matrix Map used instead of a Graph.
Has been also defined a flag VISIT_MODE, which allows to change implementation from Classic Dijkstra (VISIT_MODE = 0) to Backward Dijkstra (VISIT_MODE = 1).
This flag management system opens the way for including more Search Algorithms alongside the already implemented ones in the future.
Finally, in order to compare the various paths, has been used a Min-Heap Structure, which gives direct access to the shortest path; this way when the next Tile to visit is the wanted one, you have correctly found the cost of the shortest path possible.