Hey there, I have a hobby project for a dungeon exploring game, the game is a grid based one (each graphic is an orxOBJECT base on a 64x64 png).
To move the players and monsters around I implemented the A* algorithm. I made it so it would be really easy to interface with other applications.
I published the code, as well an explanation on how to interface it and its limitations
here.
You may find a zip with the code
here.
In this file you may find a file main.c, it is a very simple example that will read a text file with a map in a specific format and print the path found.
The map file should contain:
- '0' is a non-walkable area.
- '.' is a walkable area.
- 's' is the starting point.
- 'e' is the goal.
Here is an example of a map file:
.........
.....0...
s....0...
0000000.0
e....0...
.00..0...
.....0.00
.........
The output is:
....xxx..
...x.0x..
xxx..0.x.
0000000x0
xxxx.0.x.
.00x.0x..
...x.0x00
....xxx..
If you need any help, please feel free to post here, in the blog or mail me.
Edit: Updated the file with a bugfix.
Comments
Thanks for your post and contribution, I'm sure it'll be useful to others.
Two improvements that could be worth considering would be:
- decouple your algorithm from the underlying data organization (in your case, the grid)
- or propose more free movements/costs by using Chanfrein masks/distances if you'd rather keep the grid.
Here's a (very old) example of chanfrein use for pathfinding: http://code.orx-project.org/orx/src/c591b2fbab2e/orx/src/utils/pathfinder.c
Sorry for the not-so-pretty code, I like thinking I improved over the last 10 years!
Don't really got this, the grid is a void* given by the user, it doesn't matter to my algorithm how the user implemented it. My algorithm receives a function (that must be implemented by the user) that tell if a cell is walkable by parameter and uses it with the user given grid.
In my first post, the text file that is converted to a int** is just one example of possible grid. I just used this one because it is simple, fast to code and very easy for any user to change the input file and test the algorithm.
- or propose more free movements/costs by using Chanfrein masks/distances if you'd rather keep the grid.
Both the g and h functions are overloadable, so the user may replace then for another. Also the costs are defines and can be replaced. Maybe you meant something else?
From it:
This part assumes your representation is a grid (moving diagonally wouldn't mean anything if you were using a navmesh, for example). Using a (x, y) integer as input also brings a similar limitation, ie. a 2D discrete space only.
In the same way, I assume you can only move in a 4- or 8-connex way: no option to move like the knight on a chessboard for example, or did I miss something? That's were Chanfrein masks come in.
Maybe your code is more generic than your post let imagine, in which case you can disregard all my comments.
So I assumed it'd work for grids and not for navmesh, quadtrees, octrees or any other space representation.
I have made some 3d projects in the past (including a client-server arena game that was pretty big), but right now I am focusing on 2D, so I don't think I will expand it to navimeshes so soon