Rewriting in C of a pedagogical program allowing to understand the functioning of path-finding algorithms in graphs.
Hexagons allows you to test path-finding algorithms on a 2D hexagonal map.
Algorithms should try to find a path from the starting point (the magenta-colored hexagon) to the ending point (the red colored hexagon).
You can complicate their task by adding impassable or difficult to cross obstacles, you have walls (black), water (blue), grass (green) and sand (yellow).
The walls are totally impassable, but the others only slow down by having a higher cost to move from one neighbour to the other. The costs are as follows:
| Type of tile | Cost |
|---|---|
| Wall | impassable |
| Nothing | 1 |
| Water | 10 |
| Grass | 5 |
| Sand | 2 |
Here is the list of algorithms that have been implemented:
- Depth-first search
- Breadth-first search
- Connected components (This algorithm is an exception, it only displays the connected components.)
- Bellman-Ford
- Dijkstra
- A*
To be able to compile the project, you must first have the GTK 3 graphics library.
On Debian/Unbuntu distributions you can install it via the command
$ sudo apt-get install libgtk-3-devFirst of all you have to recover the sources. To do this you can either download a release from the release page, or clone the repository via the command
$ git clone https://github.com/Astropilot/Hexagones.gitOnce the sources are recovered, you can compile the project under UNIX with the make command:
$ cd Hexagones
$ makeFinally, all you have to do is launch Hexagons!
$ ./hexagonesThis project is a rewrite of an already existing project originally written in Python by Mr. David Auger, professor-researcher at the University Institute of Technology in Vélizy, France.