Pathfinding with A*

For Null Op I needed some sort of path finding so that the enemy viruses would attack your base and your towers. In order to do so I implemented the A* algorithm with a simple modification. This post will explain how to implement A* and go onto describe how to make the algorithm aware of additional metadata. First off, please check out the debug version of Null Op which let’s you watch the A* algorithm in action and visualize the metadata underlying the whole process:

Debug Op

You can see all the paths A* explored in blue. The optimal path to the target is in purple. Each cell evaluated has two numbers the first is the cost to get to that tile and the second is the weight of that tile. This will mean more by the end of this post. Finally, the tile metdata is overlaid on the map. Tiles can be:

  • Vacant (no color)
  • Blocked (black)
  • Dangerous (yellow)
  • Very danger (orange)
  • Extremely danger (red)

If you place buildings down you should see two things. First, that new tiles will become “dangerous” and second that you can impact the path A* will take!

What it means to be A*

The algorithm behind A* is very simple. It is built on three concepts:

  1. Each node has a cost to travel to it
  2. Each node has a weighted value indicating how good it is
  3. You explore the node which has the lowest cost + weight

A* itself is a very simple algorithm best outlined in pseudocode:

create priority queue of open nodes, initially contains starting node
create a set of closed nodes, initially empty
while (open nodes is not empty) {
    current node = best node from open nodes
    add current node to closed set
    if (current node == target node) break

    for (neighbor in current node) {
        if (neighbor node is in closed set 
                and current cost to neighbor < cached cost to neighbor) {
            remove neighbor from closed
        }
        if (neighbor node is in open queue 
                and current cost to neighbor < cached cost to neighbor) {
            remove neighbor from open
        }
        if (neighbor is not in open or closed) {
            neighbor.parent = current
            neighbor.cached cost = current cost
            neighbor.weight = calculateWeight(neighbor, target)
            add neighbor to open queue
        }
    }
}

As might be apparent this algorithm is really all about the Node data structure. There are few key points to remember when implementing this class:

  1. To use in a PriorityQueue implement the Comparable interface
  2. Be careful when using sets such that equals and hashCode return the correct value
  3. Keep a back pointer to your parent so you can trace back the optimal path

Be especially wary of number 2. I got caught by that when using a HashSet and ended up having many nodes which pointed to the same cell in a grid!

So, a careful reader noticed that there are two variables which have not been defined. current cost represents the cost to reach a given node from the starting point. If you are working with a tilemap then an easy way to start is to make the cost from moving to any neighboring tile one. This means that the current cost is always:

current cost = 1 + current.cached cost

The second, and arguably more important, variable is the weight. The usual approach is to calculate either the Manhattan distance or Euclidean distance between the current node and target node.

For Null Op I combined the Euclidean distance with a weighted value determined by how dangerous a cell was. With this modification A* will try to avoid moving through dangerous zones if possible! In order to accomplish this I generated metadata about each square in the grid with the values outlined above. Whenever I calculated the distance from the target I would also calculate a value based on the metadata for that square. By combining the two I was able to influence the path A* explored.

Conclusion

Alright, time’s up! So far I’ve covered a lot of ground pretty quickly but I hope things remained clear. Be sure to run the demo above if you are confused as I think it’s especially easy to see how things work visually.

With A* you can quickly find the shortest path to a given destination, and with the modification I outlined you can create better informed path finders. In the future I’ll cover how you can generate the necessary metadata by leveraging the Grid data structure I’ve written about before.

I hope you enjoyed this post and found it to be a useful demonstration of A* and how it can apply to your next game!

Comments

8 Responses to “Pathfinding with A*”
  1. Marte says:

    Opensource this code :D

  2. aschearer says:

    Hahaha, which code do you mean? Null Op’s? I’m still figuring out what I want to do with that codebase. I’ll probably get around to tidying it up and releasing it sometime soon.

  3. Firstly, I linked to your Fluent FX article on my website, as I think it will grow to be quite useful to people. :)

    Secondly, I’ve been waiting for an article on AI stuff for a while, and this is great; but where can I find the debug version of null op?

    Thanks, Ashley.

  4. aschearer says:

    Well the debug version and the real version are identical minus a couple commented out lines of code. It sounds like people would like to see the source for Null Op so I’ll make it available later this week.

    Thanks for linking to Fluent Fx and I’m glad you found this post useful!

  5. Alex, I think you misunderstood what I was saying a little.

    Is there somewhere I can play the debug mode online? or is there a key in the normal game I can press to enable debug mode?

    Anyhow, I’ve been meaning to ask, where is it you get the music for your games? It always seems to be of great quality. :) (That’s music, not sound..)

    Thanks. :)

  6. aschearer says:

    Aha I did misunderstand you. To play the debug version just click on the image above and it should launch the appropriate webstart. As for my music I have been using Mod Archive and generally just sifting through “featured” or “popular” tracks. I highly recommend the site!

  7. Eddie says:

    The real question is: can A* find a path to a woman’s heart?

Trackbacks

Check out what others are saying...
  1. [...] Pathfinding With A* [...]



Leave A Comment