64x64 icon dark hosting
Deploy New Relic now and get $135 off your Tuts+ subscription.
Advertisement

Artificial Intelligence Series - Part 1: Path Finding

by

This tutorial is the first of three which discuss how to give some Artificial Intelligence (AI) to games and apps you create. In this first tutorial we are going to learn about path finding.


Final Result Preview

Let's take a look at the final result we will be working towards:

Click a point, then another point and the AI will figure out a shortest possible path to get between them. You can use the drop-down list to select the AI algorithm to use.


Step 1: AI Series Overview

This tutorial will be the first of three which will discuss giving Artificial Intelligence (AI) to games and apps you create. You might think that this sounds just too hard, but it is actually pretty simple! I will explain two key aspects of the AI in games and then create a cool game using what we learn. I hope you enjoy following this short series!


Step 2: Introduction

In games, one of the most important aspects is to make it very efficient, to do what it has to do using minimal resources. There's a whole science just for that.

In this tutorial we are going to cover a key aspect in game development: pathfinding. We will discuss the 2 best methods, how they work, how we make them work in AS3, then last but not least, when to use them. Let's start..


Step 3: So What's Pathfinding About?

Suppose you are in the middle of a forest with 50 different potential routes in front of you, you have almost no energy and need to find the best way out, how would you do it?

One option would be to follow each of the 50 routes; a trial and error method. You will certainly get out but that would take too much time. This isn't a new problem and many people have come up with ideas of how to solve it. One of them was Edsger W. Dijkstra who developed an algorithm to get the shortest path given a graph, a source and a target.

Before we can start solving the problem, we must create those elements, the graph which contains all the information, the nodes which are the waypoint of the graph, and the edges that connect the nodes. Think of it as the graph being a map: the nodes are the cities and the edges the highways that connect them.


Step 4: Setting up the Project

Before we start coding, let's first set up our workspace. Create a new folder and name it "PathFinding". Inside it create another folder and name it "Graph". Then in the PathFinding folder create a new Flash (AS3) FLA file and call it "PathFinding".


Step 5: Creating the Node Symbol

In the "PathFinding.fla" file, go to Insert > New Symbol and create a new MovieClip called Node. Select "export for actionscript" and as the class write "Graph.Node"


Step 6: Drawing the Node

Inside the Node Movieclip, create a new Circle with a radius of 25 and place it in the center. Then add a new text box, make it Dynamic and give it an instance name of "idx_txt" and position it at the center of the stage.


Step 7: Creating the Node

Each node is composed of 2 main elements; an index in order to identify it, and its position on the graph. With this in mind create a new class inside the Graph folder/package and name it "Node". Make it extend the sprite class, then just add two variables: one int for the index, and a Vector3D for the position. Also, add their corresponding set and get methods:


Step 8: Creating the Edge

The edge contains three elements: the indices of the two nodes that it connects, and its "cost" (or distance between nodes in this case). Again in the Graph package/folder create a new class and call it "Edge"; make it extend the Sprite class again.

Now add two ints for the nodes, and one Number for the cost, then add the corresponding set and get methods:


Step 9: Creating the Graph

The Graph is a more complex element since it must store all the information. In the Graph folder, create a new class and name it "Graph". Since it just contains data, there's no need to extend the Sprite class.

The graph will contain a Vector with all the nodes on the graph, another Vector with the edges that each node has and a static int in order to get the next index available for a node. This way, it will be easier to access all the elements in the graph, since the node index is the key of the edges vector, meaning that if you want to get the edges of a node with index 3, you access the edges vector at position 3 and you will get the edges for that node.

Now let's create these variables:

The graph also needs methods to add and get nodes, and edges:


Step 10: Building a Graph

So now that we have all the elements needed, let's go ahead and build a graph.

In the PathFinding folder, create a new class and call it "Main", this will be our main class:

Now we need to import the classes we just created since they are in the Graph folder. Then create two variables: one for the graph and another that is an array of the position of the nodes we want to add. After that just add those nodes and their edges:


Step 11: How to Choose the Right Path?

As I told you before there are many methods to obtain a path between two nodes, like the DFS(Deep First Search), or BFS(Broad First Search), but sometimes you don't just want to get a path that connect the nodes, you also want to get the "best" path, which most of the time will mean the one that takes less time or the closest, depending on what you want.

During this tutorial I will just refer to it as the one that costs less to follow. (In our case, remember "cost" means distance. In a game, you may wish to find the least dangerous path, or the one that uses least fuel, or the least visible...)

There are algorithms that work depending on the cost, the most important ones being the Dijkstra Algorithm and the A* (A-Star) Algorithm. Lets talk first about the Dijkstra Algorithm


Step 12: Introduction to Dijkstra Algorithm

This algorithm was created by Edsger Dijkstra in 1959. It advances depending on the cost that each edge represents, the edges with lower cost will always be chosen first so when you reach the target, you will be sure that the path is the lowest costing path available.


Step 13: How the Dijkstra Algorithm Works

Because this algorithm works with costs, we must have a place where we will be storing the cost of moving to each node from the source (the starting node); call this a cost vector.

For example if the source is the node 0, when we access the cost vector at position 3, this will return the lowest cost until now of moving from 0 to 3. We will also need a way of storing the shortest path: I'll explain the Shortest Path Tree in the next step.

The basic steps of the algorithm are the following:

  1. Take the closest node not yet analyzed.
  2. Add its best edge to the Shortest Path Tree.
  3. If it is the target node, finish the search.
  4. Retrieve all the edges of this node.
  5. For each edge calculate the cost of moving from the source node to the arrival Node.
  6. If the total cost of this edge is less than the cost of the arrival node until now, then update the node cost with the new one.
  7. Take the next closest node not yet analyzed.
  8. Repeat this until the target is reached, or there are no more nodes available.

An animation will make more sense. Here we are trying to get from 1 to 6:


Step 14: Algorithm's Main Elements

This algorithm is composed of different vectors that will store all the information needed, for example the costs of the nodes, or the best path until now. I will explain this better:

  • The costs vector : Here we will store the best cost until now of reaching a certain node from the source. For example if the source node is 3 and we access element 6 of the cost vector, we will obtain the best cost found so far of moving from 3, the source node, to the node 6.
  • The Shortest Path Tree (SPT): This vector contains the lowest cost edge to get to a specific node. This means that if we access the element 7 of the SPT, it will return the best edge to access that node.
  • The Search Frontier (SF): This vector will store the best edge to get to a specific node, almost the same as the SPT, but this will have all the nodes that are not yet in the SPT. This means that the SF will work as a test area where we will test all the edges for one node, when all the edges are analyzed we will be sure that the SF contains the best one, so we can then add it to the SPT.
  • The Indexed Priority Queue (pq): A priority queue is a data structure which always keep its elements in an ordered way. As the algorithm needs to first get the lowest cost node, this structure will keep the nodes in a descending order depending on their cost, but because we want to retrieve the index of the node and not the cost itself, we use an indexed priority queue. For example, if the first element of the pq is node 4, this will mean that it is the one with the lowest cost.

Note: AS3 doesn't contain many data structures including the Indexed Priority Queue, so I coded one to use in this tutorial. To get it just download the source files and import the utils folder to the PathFinding folder. The class is utils.IndexPriorityQ.


Step 15: Create an Algorithm Folder

Before we start coding, in the PathFinding folder, create a new Folder and call it "Algorithms".

In this new folder, create a new AS3 class named "Dijkstra":


Step 16: The Dijkstra Algorithm in AS3

Now let's code the Algorithm. It will need three basic things: the graph itself, the source node and the target node; but we must also create the vectors we just talked about (Cost,SPT,SF). Remember to import the Graph classes:


Step 17: The Search Function

Once we have set up the class, we can start coding the algorithm which will be in the "Search" function. I will explain the code with comments, so If you still have some questions return to Steps 12 and 13 to remind yourself how this algorithm works:


Step 18: Getting the Path

When the function finishes searching we will have the path all messes up on the SPT, so it is up to us to retrieve it. Since the SPT has the best edge to get to a node, we can work backwards to obtain the best path. Take as a reference the following image which comes from the previous animation:

If we access the SPT at the target node, which in this case is 6, it will return the best edge to get there. That would be the 6 - 5 edge. Now if we repeat this process with the new node that comes with the edge, the 5 we would obtain the best edge to get to that node, which is the 5 - 2 edge. Repeating this process once again with the node 2, will give us the edge 2 - 1, so we finally get to the beginning, now joining al those edges we get the best path: 6 > 5 > 2 >1.

As you see we have to work backwards starting on the target and moving to the source to get the best path.


Step 19: The getPath Function

Create a new function that will return an Array with the nodes of the path, call it "getPath":


Step 20: The Complete Dijkstra Class

We have finished almost everything, we just now have to fill the constructor and call the search function, so the class will look like this:


Step 21: Creating a New Graph

In order to see a better result of the algorithm, I wrote a class that helps with the creating of graphs. It's called Grapher and can be found inside the utils folder that comes with the source files. This class creates a grid of nodes from where we can observe how the algorithm is moving through the graph.

With this class, open again the "Main.as" file and modify it. We will now have the following code:

Save and run the file and you will obtain this result:


Step 22: Using the Dijkstra Algorithm

Now let's go ahead and perform a search with the new algorithm we have just done. Import the Dijkstra class, create an instance of it and call the getPath function:

Save and run the file. You will see the edges that the algorithm analyzed as red lines, the best path found (from node 24 to node 35) appearing as a black line:


Step 23: Isn't There Something Better?

As we can see, the Dijkstra algorithm does find the shortest path between two nodes, but as the last image shows, there are a lot of red lines. This means that all those edges were analyzed, which isn't a big deal because we have a small graph, but imagine a bigger graph; that would be just too many edges to analyze. If we could just find a way to reduce this and make the algorithm even more efficient... well I present you the A* (A-Star) algorithm.


Step 24: The A* Algorithm

The A* algorithm is a modified version of Dijkstra. It takes into consideration a modified way of getting the cost of each node with an heuristic approach. This means that we provide a little "help" for the algorithm and tell him where to go, working as a compass and moving the algorithm directly to the target.

Instead of calculating the cost of a node by summing the edge cost to the stored node cost, it is now calculated by summing the stored node cost and an Heuristic cost, which is an estimation of how close to the target the node we are analyzing is. This new cost is called the F cost


Step 25: The F Cost

The F cost is calculated using the following formula: F = G + H, where G is the cost of the node and H is the heuristic cost of that node to the target. In this tutorial the H cost will be calculated using the Euclidean distance between the node and the target, which is the straight line distance between the two nodes.

What this does is that at the end, the nodes with a lower F cost will be the first ones tested and because the F cost will depend mostly on the H cost, at the end the algorithm will always prioritize the nodes closest to the target.


Step 26: The A* Algorithm in AS3

In the Algorithms folder, create a new class named "Astar". The variables inside the class will be almost the same as the Dijkstra class, but here we will have another vector to store the F cost of each node:

Step 27: The New Search Class

The only difference between the Dijkstra algorithm search function and this one will be that the nodes will be sorted (in the Indexed Priority Queue) depending on the F cost vector and that the F cost vector will be given by the calculated H cost and the stored G cost:


Step 28: The Complete A* Class

These are the only changes needed, since the getPath function is the same for both classes. At the end the class will be this one:


Step 29: Using the A* Algorithm

Once again open the "Main.as" file and import the Astar class, then erase the Dijkstra search we created, replacing it with an A* search:

Save and run the file. As you can see, the result is very impressive, there are no red lines meaning that the search went directly from the source to the target without analyzing extra edges:


Step 30: Which One is better?

Well, even though the A* algorithm is faster and better in getting a direct path from the source to the target, there will be some cases where Dijkstra will be the best option.

For example, imagine an RTS game, where you've instructed your villager to go and find some resources; with the A* algorithm you would have to do a search for every resource on the map and then analyze which one is closer. With a Dijkstra search, since it expands the same amount to all directions, the first resource it finds will be the best one to gather and you will have performed just one search versus the many searches of the A*.

Basically, you will want to use the Dijkstra algorithm when you are doing a general search and the A* algorithm when you are looking for a specific item.


Conclusion

That's it for this tutorial, I hope you liked it and will use it for your projects. Keep track of the next tutorial of this AI series and let me know what you think about it.

Thanks for reading! -Eduardo

Advertisement