A* Pathfinding In Game

I wrote a post on implementing a simple A* Pathfinding algorithm a couple months ago. When I went to add it to my game I ran into some interesting differences I wanted to write an update on.

Here is the algorithm working on my game server. Both player and NPC are red blocks. When the player is within viewable range of the NPC, the NPC will start chasing it.

The pathfinding algorithm allows the NPC to maneuver around blocked tiles.

Coordinate to Tile Mapping

One thing I discovered while incorporating it into my game was my simple example had a 1:1 coordinates to tile ratio. Coordinates 0,0 was the first tile, and 0,1 was the second tile. When tiles were 16×16 pixels, the coordinate to index mapping broke.

To address this, I needed to pass  map width and map height in tiles, as well as the tile size so it was known when a new row started and the bounds of the map.

I did this by creating a map struct that contained the width, height, size, and pointer to the tile vector.

Getting the mapping information into the pathfinder class was a small challenge due to circular dependencies between my GameState class and GameMob (GameState already include GameMob). A forward declaration can be used to address this, but I decided I would split out the Map into its own code unit (different cpp file).

The pathfinding functions were altered to take the map width and height (in tiles, not pixels) and the tile size.

coords_to_index and index_to_coords only needs the tiles per row (map width) in order to know when a tile drops to a new row.

Coding Aggro

The NPC engaging the player is outside of the pathfinding algorithm. It uses a very rudimentary raycasting algorithm (if it can be called that) that only looks up, down, left, and right.

This can be improved by only looking int the direction the player is and only checking tiles that are in that line of sight.

Moving Forward

One thing I realized from this implementation is the pathfinding quickly became proprietary to tile based maps. I would like to generalize it and just make it coordinates.

I ran into some bugs early on when the NPC wasn’t standing precisely on a tile. I think moving to coordinates would help here.

I would also like to move to interpolating the movement between coordinates so it is more precise.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.