1 – Concepts And Facts

Introduction

So, I’m going to start by saying that this is probably my favorite algorithm to implement for Artificial Intelligence. I really have 3 that make up the basic composition of AI in games:

  1. A* PathfindingWhat is the best way to get there from here?
  2. Finite State MachineHow do I behave under these conditions, and what conditions change my behavior?
  3. Flocking Behavior How do I handle what’s around me, and how do I take part in a group?

The combination of these 3 in games, along with the various areas we are able to play with the variables, can create some unique behavior, from dastardly and clever, to outright dumb as bricks.

Think of the ghosts from Pac-Man. Many of you might think the ghosts where just adversarial with just basic maze-following behavior. Actually, the ghosts all have their own unique AI in how they react to the player. “Blinky,” for instance, would target the tile that Pac-Man was currently occupying. This gave the effect that he would “chase” the player. As you collected more pellets, Blinky would speed up, and, as you got up to the higher levels, Blinky would actually become faster than Pac-Man (AKA “Cruise Elroy” Mode). “Pinky” is an interesting one, because she tries to end up in front of Pac-Man by 2 tiles (or 16 pixels). I say she’s interesting because her logic actually has a few bugs in it. Due to an overflow error, if Pac-Man is facing up, Pinky will target the space 4 tiles in front and 4 tiles to the left of Pac-Man. You can also work it out in such a way that Pac-Man will actually be able to chase Pinky instead. “Inky” is probably my favorite to analyze, because you can tell the developers had fun with this one.  Inky is considered “Bashful” because his movements are erratic. He is like Pinky in that he tries to be 2 tiles ahead of Pac-Man (while also suffering the “Pac-Man facing Up” bug), and then doubling that by the distance Blinky is away from Pac-Man. Inky typically will close in when Blinky is closing in as well – and this algorithm is why. Then we have “Clyde.” Clyde is a different one. When Clyde is 8+ tiles away from Pac-Man, he will chase Pac-Man like Blinky. However, when Clyde is <8 tiles away, he'll flee from Pac-Man and run to the bottom-left tile of the screen.

All these behaviors are combinations of switching states, following a path, and being aware of the surroundings. Today, I'm covering how to get from point A to B in the most efficient way possible.

Note: The code I’ll be writing for this will be for Unity in C#, but I’m keeping the concepts and math independent, so smart and beautiful people like you can translate it to other languages.

A* Is Born

Every programmer dealing with data structures and complex algorithms should pour one out for Dr. Edsger Wybe Dijkstra. The man was a brilliant computer scientist, mathematician, professor, and wizard (probably). I could go on all day about his accomplishments, all the algorithms he’s helped create, but he’s, unfortunately, not the entire focus for this article. We’re going to focus briefly on just one algorithm of his: the adequately-named Dijkstra’s Algorithm.

In the early years of programming, circa 1956, Dijkstra wanted to come up with a problem that could be both easily understood by normal people, and show off the computing power of a new computer called the ARMAC. He created a “map” of 64 cities in the Netherlands, and calculated the shortest transportation path between different cities. 3 years after tackling the problem and optimizations, he published Dijkstra’s Algorithm. This algorithm found the “best” path for traveling through a graph, if both the start and end points are known. This is done by, starting with the “Start” point, adding all adjacent points (referred to as Nodes) to a queue, checking to see if we’ve reached the end, and repeating the process with each node in the queue until we reach the end. Once we reach the end, we build backwards from the visited nodes all the way back to the start, and that gives us our path.

This animation from Wikipedia shows how this is accomplished, visually:

dijkstra_animation
From Dijkstra’s Algorithm’s Wikipedia page.

“Now hold on, Keith,” The skeptical reader might say, “What are all those numbers between the nodes?” And that’s a great question, because that is the power behind Dijkstra’s Algorithm. Those values are the Heuristic. The heuristic is the cost of traveling between the nodes. In Mathematics, a heuristic is a value that can be used in place of a more complicated calculation, sacrificing precision for speed. The heuristic can be a number of things (terrain, difficulty, etc.) that can effect the cost for traveling to that node. When we pop a node off our queue, we prioritize the nodes with the lowest heuristic, so we get the “shortest”, or least-costly, path. We’re essentially playing pathfinding minigolf – you want the lowest score possible (while avoiding windmills).

Now, lets take a moment to break down the steps in Dijkstra’s Algorithm:

  1. Create a Node data structure, with a coordinate field (x, y, z), a Heuristic Cost field, and a From Node field.
  2. Create 3 data structures: a priority queue for Open Nodes,  and a normal list for Closed Nodes.
  3. Enqueue the Start Node into the Open Queue. Its From Node will be Null.
  4. Pop the lowest Heuristic Cost Node off the Open Queue. Call this the Current Node.
  5. Check if the Current Node is the End Node. If it is, go to Step 6. Else, go to 9. (Nice)
  6. Create a Path List and add the End Node.
  7. Traverse through the From Node field in End Node, and add each visited node to the Path List.
  8. Reverse the Path List (From “End -> Start” to “Start -> End”) and return it. DONE.
  9. Add the Current Node to the Closed list, and add all adjacent nodes to the Open Queue, setting their From Nodes to the Current Node.
  10. Return to Step 4.

That’s pretty much it. 10 steps for finding the shortest path. But… can we do better?

yesitis2

All we need to do is a slight modification to go from Dijkstra’s to A*. See, the problem with Dijkstra’s algorithm is that Dijkstra is going to check all adjacent nodes from the current node, and then all adjacent nodes to those, and then all adjacent nodes from those, etc. But, what if we prioritized a “straight line” to our goal? What we’re going to do is take the Heuristic from the Current Node from the Open Queue and add the distance from that Node to the Goal.

  1. Create a Node data structure, with a coordinate field, a Heuristic Cost field, and a From Node field.
  2. Create 3 data structures: a priority queue for Open Nodes,  and a normal list for Closed Nodes.
  3. Enqueue the Start Node into the Open Queue. Its From Node will be Null.
  4. Pop the lowest (Distance between Node & Goal + Heuristic Cost) Node off the Open Queue. Call this the Current Node.
  5. Check if the Current Node is the End Node. If it is, go to Step 6. Else, go to 9. (Nice)
  6. Create a Path List and add the End Node.
  7. Traverse through the From Node field in End Node, and add each visited node to the Path List.
  8. Reverse the Path List (From “End -> Start” to “Start -> End”) and return it. DONE.
  9. Add the Current Node to the Closed list, and add all adjacent nodes to the Open Queue, setting their From Nodes to the Current Node.
  10. Return to Step 4.

And that’s it! That’s the big change! Here’s a few gifs to detail what the difference is:

dijkstras_progress_animation
Dijkstra’s – Notice that the node traversal is in a very “Breadth-First” sort of fashion. Every adjacent node is visited, even if it’s not really helpful in finding the goal.
astar_progress_animation
A* – First thing you’ll notice is the algorithm makes a B-line straight to the goal before ramming into the wall. This one finds the goal faster, but notice the differences in the paths.

A* does the job with just one small modification. Though, it may not be the best path. But what it does afford us, besides faster processing, is something that’s very…. exploitable…

Oh Jeez, Here We Go…

Mathematically speaking, our nodes exist as structures comprised of a 3D Point (x, y, z), a Heuristic Cost, and a Distance to the goal (which is just a Vector Distance calculation). In a way, this is our AI’s Though Process, its Logic. Our Pathfinding AI says “I have this Node from the Open Queue, and now, I need to figure out it’s Cost, by…” and that “…” is where we get to have fun.

That Heuristic Cost can mean a number of things. Lets say it’s Terrain, right? So, if it was a grassy field, which is easy to traverse, it’s Heuristic Cost is 0. However, Rock, which is tougher, can be, lets say, 10. BUT! What if your AI Agent can fly!? Then it’s just a matter of Distance, and no Heuristic Cost at all!

Lets do some more! Maybe we want to make our AI Agent have some randomness? So lets multiply the Heuristic Cost by, I dunno, by (Delta Time multiplied by 10)? What’ll happen then? That’s up to you. This is your place to play.

So that’s it! I think everyone should now have a fundamental idea on how A* works.

everybody_got_that_spaceballs

Now, lets actually start putting this together!

>>> Next, Implementation >>>

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s