A* For Tiles

Well, this is seriously kicking it old-school :)  I mentioned in the prior post on A* for waypoints that I would add A* for tiles in the library.  In fact, this is the typical application thought of by most people when mentioning pathfinding.

Just as A* for waypoints is driven by a 2D Graph structure of waypoints, the tiles version is driven by a 2D grid of tile nodes.  There is also a view component that is written on top of EaselJS in the library.  Define a Grid2D instance and a GridView instance.  Assign the GridView instance to the Grid2D instance and any updates to the grid automatically update the view.    This is a great way to debug and compare the behavior of different heuristics.

Speaking of heuristics, the A* heuristic is injectable; it can be Euclidean, Manhattan, or anything that suits your interest or a very particular application.  A diagonal heuristic is applied by default that is ideal for a lot of up-and-down movement, especially to move around barriers or avoid high-cost regions.  If it were a chess piece, the heuristic would generally move like a Bishop, like a Rook only if absolutely required, and then like a Knight.

The example below shows the path around a barrier.  The red region is a region of high-cost tiles.



Nothing really new here, but I wanted to show the breadth of the pathfinding algorithms in the library.  With luck, I’ll announce the project this coming Friday.

Comments are closed.