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.