Ever since I started to code I wanted to have a game character move from one place to another intelligently, no pre-canned paths.

The A* search algorithm allows you to do this, but due to my age/indifference/attention span I never got round to understanding how it worked ("Heuristics? Weightings? I don't... I... I could just make more particle blood...")

Now that we live in a world filled with free and easily accessible information such as Wikipedia, I could finally find an example that would make sense to me.

With the information on Wikipedia and this article, I gave myself one day to implement the algorithm myself (that last link was the "I can actually do this!" turning point for me, the images with values on were the part that finally made sense to me).

Impatience and Tools

As I didn't have much time to do this, I thought I'd stick with the basics I knew:
Visual Studio Express to develop in C++
SDL and SDL_image for graphics
Tiled for map creation
Paint.NET for tile creation

Seeing as I had absolutely no desire whatsoever to mess around with an XML or JSON library in C++, I made a quick Python script to convert Tiled's native .TMX format into a C++ .H header file containing a class that I could use to get the tile and collision properties of an X,Y co-ordinate.

Using Tiled, tiles in the tileset were given values relating to how costly they were to travel over. I guess this is what they call "weighting". For me it worked out as a multiplier where roads where a multiplier of 1, grass is a multiplier of 20, and sea is a multiplier of 100 (a pure obstacle then really).

So in the end I made diagonal tiles cost just a bit more than travelling across two tiles so it would prefer to keep to the road, and "G" and "H" values would end up being multiplied by the preference value of the current tile.
Tile_Weight = 10,
Tile_Weight_Diagonal = Tile_Weight * 2 + 1,

openTile->G = CostSoFar;
openTile->H = (abs(DestinationX - openTile->X) + abs(DestinationY - openTile->Y)) * Tile_Weight;

openTile->G *= world->map.Cost(openTile->X, openTile->Y);
openTile->H *= world->map.Cost(openTile->X, openTile->Y);


Not too crappy actually.

I had several criteria I wanted a path to follow:
  • A car should prefer to drive on a road
  • A car may drive on grass if it's the only option
  • A car should not take a shortcut by travelling diagonally across a corner tile, i.e., skipping a curved round turn by crossing grass
  • A car can take a shortcut diagonally across grass if it means getting back to the road quicker

As this was all done in a day, I have no doubt that there are issues I haven't found, but I finally understand how it all works and for a small amount of time I felt good about myself.

permalink print article