Posts RSS Comments RSS Del.icio.us Digg Technorati Blinklist Furl reddit 73 Posts and Comments till now
This wordpress theme is downloaded from wordpress themes website.

Pathfinding with A* (A Star)

Labor Day weekend gave me an opportunity to implement pathfinding.  Here’s notes on some of what I read.  BFS (breadth first search) explores equally in all directions.  Dijkstra favors lower cost paths.  A* is modified Dijkstra optimized for a single dst (uses heuristic to search towards dst).  A* is the standard pathfinding for games (I also used it in college game projects ~12-14 years ago), so it’s easy to find pseudocode, articles, tutorials, and videos about it.  A* can be further optimized a number of ways – use more efficient data structures, bidirectionoal search, jump point search can optimize uniform cost grids (like HeroQuest).

My HeroQuest map is an array of 26×19 square spaces, but pathfinding works on nodes in a graph.  So before I implemented pathfinding, I added C++ code to generate the graph.  Each space has a list of 0 to 4 neighbor nodes that are valid moves.  The graph is for monster AI, so a hero is a blocker.  When a space is revealed for the first time, we generate neighbors for that space.  When a hero moves a space, we update neighbor list for src node, dst node, src’s neighbors, and dst’s neighbors.  Once I got that working, I moved on to actual pathfinding.

To keep things simple, I just implemented A*.  Two references I used were Vincent Cogne’s 2010 blog post ( http://bit.ly/2c6vTnF ) and wikipedia pseudocode ( http://bit.ly/2cimKrr ).

A* uses an open list and a closed list (open list means we will visit it later, closed list means we already visited it).  When a node is visited, its neighbors are added to the open list (unless it’s already in the open list or closed list).  Each node has an F, G, and H value.  The way A* searches towards the goal is that each iteration, we visit the node in the open list with the lowest F value.  F = G + H.  G is the lowest cost path we’ve found so far to the node.  When we visit a node, we update it’s G value and the parent node used to get that G value (unless the node already has a lower G value using a different parent) (parent node aka “came from” node).  H is a heuristic function to estimate the remaining cost to the goal.  For HeroQuest, I used the manhattan distance as my heuristic.  The heuristic function needs to be equal to or less than the actual cost (HeroQuest only allows orthogonal movement).

The following is a simple example that I used as a test case.  The numbers are just x, y, and the order that A* visited each node (in terms of the current node).  Overall it was pretty straightforward.

image

In the above example, the Orc searches for the hero with the lowest Body (eg Wizard), then he runs A* towards the wizard.  However, the Wizard is actually a blocking node, so A* never visits the Wizard’s node.  So we end our search when when the Orc is in range to attack the Wizard (ie the Oric is orthogonally adjacent to the Wizard without a wall blocking his attack).

Here’s a screen shot:

image

And here’s an example where no path was found:

image

Aside – I added the “Back” button to the UI as part of an effort to enable the interface to work without a keyboard (eg Android tablet mode) (I also enabled finger tapping to move or attack eg on an Android tablet).

Pathfinding is a fundamental building block for a HeroQuest Zargon AI that will be required to enable a single-player campaign mode.

I’ll close with a video that shows some examples of monster pathfinding to reach the Wizard:

Update: here’s a photo of pathfinding on my Android (technically Kindle Fire) tablet

IMG_20160906_2144484

Trackback this post | Feed on Comments to this post

Leave a Reply