A* (pathfinding) implementation for grids.

edited September 2012 in Projects - Tools
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

  • edited October 2012
    Hi Knolan!

    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! :)
  • edited October 2012
    - decouple your algorithm from the underlying data organization (in your case, the grid)

    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?
  • edited October 2012
    I haven't read your code, only your post.

    From it:
    4) How to Customize the Algorithm:

    The implementation offers some limited customization, if you look at the pathfinding.h file you will find the following defines:
    #define CONSTANT_STRAIGHT_COST 10
    #define CONSTANT_DIAGONAL_COST 14
    #define PATHFINDING_INFINITY 1000000000
    #define PATHFINDING_MAY_MOVE_DIAGONALLY 1
    #define PATHFINDING_MAX_ITER 1000

    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. :)
  • edited October 2012
    Also the title for your post is:
    A* implementation for grids in C

    So I assumed it'd work for grids and not for navmesh, quadtrees, octrees or any other space representation. :)
  • edited October 2012
    Ah, in that point you are correct, it is based on grids only, it doesn't support navmeshes.
    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 =)
Sign In or Register to comment.