Part VI.   Pathfinding

This will be confusing!  It's time for hardest part of all!  Yes, that evil element of pathfinding . . . . beware, there's a lot of code in this final chapter.

 

With the use of our node system, pathfinding won't be too hard to tackle.  If our world was completely 3D, pathfinding would extremely challenging, but we are instead using a 2D grid system, so it's not that bad.  The first thing we have to do is come up with an algorithm that we can understand.  The idea behind pathfinding involves defining two nodes, the start node and the goal node.  The algorithm then needs to generate a list which will tell us which nodes to move through to get from the start node to the goal node.  The list should give us the shortest possible route, of course, and should be blank if a path is impossible.  What algorithm should we use?

 

The A* algorithm!  Actually, no!  The A* algorithm (pronounces 'A-star') is very effecient, but it's difficult to program with c-script.  There is an easier way with . . . the Hannifin algorithm!  This pathfinding algorithm works great with c-script, and with our node system.  Here's a graphic representation of the steps my beautiful algorithm goes through to generate a movement list.  Then all we'll have to do is code it!  Here it is:

 

img1.gif

FIGURE 6.1

 

That's a pretty nice way to look at it, huh?  Let's discuss the algorithm's elements.  As you can see from above, it starts by initiating the arrays.  What arrays?  There are three arrays we will need: one to store information about whether or not a node is open (the OpenList array), one that will be the list of movements to get from the start node to the goal node (the MoveList array), and finally one to store the 'NodeValues', which is a value given to each node to show how close it is to the goal node (the smaller the value, the closer the node is).  Let's go ahead and begin coding while we go through the algorithm.  I have created a new script to hold all the new code, and called it paths.wdl.  Don't forget to include the file in the main script!  At the beginning, I have declared all the vars and arrays we will need:

 

var OpenList[400];

var MoveList[400];

var NodeValues[400];

 

var CurrentNode = 0;

var BestNode = 0;

var OpenNodes = 0;

 

Notice I have declared 400 elements of the arrays.  That is, of course, because with a 20 by 20 grid there are 400 nodes.  If you are working with a larger grid, be sure to increase these values.  Now we must write two simple functions that will initiate the arrays by going through the members of the arrays and setting them to -1.  The functions are rather simple:

 

function InitOpenList()

{

        var num = 0;

        

        while (num < (GridLength * GridWidth))

        {

                OpenList[num] = -1;

                num += 1;

        }

}

 

function InitMoveList()

{

        var num = 0;

        

        while (num < (GridLength * GridWidth))

        {

                MoveList[num] = -1;

                num += 1;

        }

}

 

Easy enough, right?  Simple while loops do the trick.  The next step is to 'calculate the node values'.  This involves going through all the nodes (in the NodeValues array) and giving a numerical value based on far away the are from the goal node.  Remember the distance formula from high school?  Perhaps you're still in high school, in which case I feel sorry for you.  Homework stinks, doesn't it?  We can use the distance formula to calculate how far away a node is from the goal node.  Here is the distance formula:

 

 

Oh, an equation!  Fancy, huh?  All we have to do is plug in the given node's x and y coordinates and the goal's x and y coordinates in the proper place, and give that value to the given node.  Ready for the function?

 

function CalcValues(goal)

{

        var num = 0;

        var tempx;

        var tempy;

        

        var goalx;

        var goaly;

        

        while (num < (GridLength * GridWidth))

        {

                if (Nodes[num] == 1)

                {

                        tempx = int(num / GridLength);

                        tempy = num - (tempx * GridWidth);

                        

                        goalx = int(goal / GridLength);

                        goaly = goal - (goalx * GridWidth);

                

                        NodeValues[num] = sqrt(pow((goalx - tempx),2)+pow((goaly - tempy),2));

                        

                        OpenList[num] = 1;

                }

                

                num += 1;

        }

}

 

As you can see in the function, a while loop is used to go through all the members of the array.  The tempx and tempy values are used to help find the x and y coordinates based on the nodes' index value.  A bit confusing, isn't it?  Notice how that the function makes sure a path is on the node before doing any calculating (look at the if statement).  It's pointless to calculate the value of a node if the node is on the grass, since the entity can't go there anyway.  Also, notice that the OpenList array is also prepared in this function, by setting a node with a path on it to 'open' by giving it a value of 1.

 

Most of the rest of the algorithm is contained in the LookAround() function and the PathFind(start, goal) function.  Before we get to those, there are some other functions we must first create that will be called in those larger functions.  We need to write the AddToMoveList(num) and the TakeFromMoveList(num) functions.  These functions have a pretty simple task.  AddToMoveList(num) adds the value num to the end of the list.  Remember how we initialized all the MoveList array members to -1?  -1 means that that spot in the array is blank, so when we add a new value to the list, all we really have to do is place it at the first instance we find of -1.  Here is the function:

 

function AddToMoveList(num)

{

        var loop = 0;

        

        while (loop < (GridLength * GridWidth))

        {

                if (MoveList[loop] == -1)

                {

                        MoveList[loop] = num;

                        break;

                }               

                loop += 1;

        }

}

 

I hope you think it is simple.  Notice the nice usage of the break command, which gets us out of the while loop after we have changed the first instance of -1 to the given value num.  We will use the break command again, so look for it!  Alright, let's move on to the other function, TakeFromMoveList(num).  If our pathfinding function hits a dead end, we will need this function to delete the last entry of our MoveList array, since we'll need to go back.  The function can basically work like the AddToMoveList(num) function, but by going through the MoveList array backwards, and changing the first occurrence of the num value to -1.  So here is the function.  Again, notice the use of the break command:

 

function TakeFromMoveList(num)

{

        var loop;

        loop = (GridLength * GridWidth) - 1;

        

        while (loop > -1)

        {

                if (MoveList[loop] == num)

                {

                        MoveList[loop] = -1;

                        break;

                }

                loop -= 1;

        }

}

 

Again, I hope you think it is simple!  That's because it is!  One more function to create before we tackle the bigger ones.  We'll need the FindLastMove() function when we hit a dead end and need to go backwards.  This function will allow us to find the last move on the MoveList array, and set the CurrentNode to it.  It is also a very simple function, so here it is (I'm anxious to get to those larger ones!):

 

function FindLastMove()

{

        var loop;

        loop = (GridLength * GridWidth) - 1;

        

        while (loop > -1)

        {

                if (MoveList[loop] != -1)

                {

                        CurrentNode = MoveList[loop];

                        break;

                }               

                loop -= 1;

        }

}

 

And that's it for the little functions!

 

Now let's get to the hardest function . . . LookAround().  This function needs to look at it four neighboring nodes and see if there is anything there.  It needs to check whether or not a node is there, then check whether or not that node is 'open'.  Then, of all the 'open' nodes it finds, it needs to set the BestNode to the CurrentNode.  The BestNode is, of course, an 'open' node with the smallest NodeValue, since that means it is closest to the goal node.  As you can probably guess, there will be a lot of if statements in this function!  Take a look at the following picture to get an idea of how we can look at the neighboring nodes:

 

img1.gif

FIGURE 6.2

 

The value of 20 comes, of course, from the grid's dimensions.  Here is the long evil function:

 

function LookAround()

{       

        OpenNodes = 0;

        

        BestNode = CurrentNode;

        

        // Check Nodes

        if (((CurrentNode + GridLength) < (GridLength * GridWidth)) && ((CurrentNode + GridLength) > -1))

        {

                if (OpenList[CurrentNode + GridLength] == 1)

                {

                        OpenNodes += 1;

                        BestNode = (CurrentNode + GridLength);

                        beep();

                }

        }

        if (((CurrentNode - GridLength) < (GridLength * GridWidth)) && ((CurrentNode - GridLength) > -1))

        {       if (OpenList[CurrentNode - GridLength] == 1)

                {

                        OpenNodes += 1;

                        if (NodeValues[BestNode] > NodeValues[CurrentNode - GridLength])

                        {

                                BestNode = CurrentNode - GridLength;

                                beep();

                        }

                        if (BestNode == CurrentNode)

                        {

                                BestNode = CurrentNode - GridLength;

                                beep();

                        }

                }

        }

        if (((CurrentNode + 1) < (GridLength * GridWidth)) && ((CurrentNode + 1) > -1))

        {       if (OpenList[CurrentNode + 1] == 1)

                {

                        OpenNodes += 1;

                        if (NodeValues[BestNode] > NodeValues[CurrentNode + 1])

                        {

                                BestNode = CurrentNode + 1;

                                beep();

                        }

                        if (BestNode == CurrentNode)

                        {

                                BestNode = CurrentNode + 1;

                                beep();

                        }

                }

        }

        if (((CurrentNode - 1) < (GridLength * GridWidth)) && ((CurrentNode - 1) > -1))

        {       if (OpenList[CurrentNode - 1] == 1)

                {

                        OpenNodes += 1;

                        if (NodeValues[BestNode] > NodeValues[CurrentNode - 1])

                        {

                                BestNode = CurrentNode - 1;

                                beep();

                        }

                        if (BestNode == CurrentNode)

                        {

                                BestNode = CurrentNode - 1;

                                beep();

                        }

                }

        }

}

 

Isn't that nice?  Luckily, it will work like a charm.  I added calls to the beep function, so that when we create a test we can hear the function as it calculates.  After the function is called, the OpenNodes value will represent how many 'open' nodes the function found.  If it doesn't find any, it means we're at a dead end, and need to go back.  If the function does find some 'open' nodes, the CurrentNode will be set to the BestNode that was found.  It has a lot of if statements, and it's a bit hard to follow, but it works!

 

Lastly, before we create a test to see the wonderful source code in action, we need to create the main function: PathFind(start, goal).  start is the node index of the node that we want to start on, and it goes without saying that goal is the node index of our target node.  The PathFind function will basically go through the steps given by the algorithm illustration (Figure 6.1), so it's not too hard to follow.  It's certainly not as intensive as the LookAround() function!  So here it is, take a look, my friend:

 

function PathFind(start, goal)

{

        InitOpenList();

        InitMoveList();

        

        CalcValues(goal);

        

        wait(100);

        

        CurrentNode = start;

        

        while (CurrentNode != goal)

        {

                LookAround();

                if (OpenNodes == 0)

                {

                        if (CurrentNode == start)

                        {

                                break;

                        }

                        

                        OpenList[CurrentNode] = -1;

                        FindLastMove();

                        TakeFromMoveList(CurrentNode);

                }

                if (OpenNodes > 0)

                {

                        OpenList[CurrentNode] = -1;

                        AddToMoveList(CurrentNode);

                        CurrentNode = BestNode;

                }

                

                if (CurrentNode == goal)

                {

                        beep();

                        AddToMoveList(CurrentNode);

                        break;

                }

                wait(1);

        }

}

 

Okay, it's a little long, but hopefully it's not too confusing.  You can follow through it with the help of Figure 6.1, which makes it pretty self-explanatory.

 

That's all there is to pathfinding!  Well, not quite.  After you call this function, the MoveList array will be generated, and then you'll have to create a function that will move an entity through the nodes given in the list.  To do this, let's first put a model in our map (I added the warlock) and create a pointer to it near the top of the script:

 

entity* tester;

 

And here is the action for it.  It attaches the pointer to itself.  In WED, remember to give this action to the entity and rebuild the level to update the entities.

 

action IMTester

{

        tester = me;

        my.z = 10;

}

 

Now all we need is the function for this tester entity to move through the members of the MoveList array, so here it is:

 

function MoveIt(start, goal)

{

        var tempx;

        var tempy;

        

        var loop = 0;

        

        var MyNode;

        var MoveTo;

        

        MyNode = start;

        

        tempx = int(start / GridLength);

        tempy = start - (tempx * GridLength);

        

        tempx = (tempx * TileSize) - ((GridLength / 2) * TileSize - (TileSize / 2));

        tempy = (tempy * TileSize) - ((GridLength / 2) * TileSize - (TileSize / 2));

        

        tester.x = tempx;

        tester.y = tempy;

        

        while ((loop < (GridLength * GridWidth)) && (MyNode != goal))

        {

                wait(32);

                

                if (MoveList[loop] != -1)

                {

                        MoveTo = MoveList[loop];

                }

                

                tempx = int(MoveTo / GridLength);

                tempy = MoveTo - (tempx * GridLength);

                

                tempx = (tempx * TileSize) - ((GridLength / 2) * TileSize - (TileSize / 2));

                tempy = (tempy * TileSize) - ((GridLength / 2) * TileSize - (TileSize / 2));

                

                tester.x = tempx;

                tester.y = tempy;

                

                MyNode = MoveTo;

                

                loop += 1;

                wait(1);

        }       

}

 

Again, the tempx and tempy values are used to translate the node index into the x and y coordinates.  The wait(32); will allow us some time to view entity moving along the path.  Lastly, to create the demo, I added the following code at the very end:

 

function test()

{

        PathFind(0,2);

}

 

function test2()

{

        MoveIt(0,2);

}

 

on_q = test();

on_w = test2();

 

Of course, if you're coding along with this tutorial, you can test the functions freely by yourself.  But the demo included with this tutorial uses these functions.  The demo can be found at Demos / Part 6 - Pathfinding / isometric.exe  So, to test the pathfinding, run isometric.exe and immediately scroll the camera to the upper left corner.  You'll have to build some kind of path between node 0 and node 2, as shown below (if you don't put a path at 0 or 2, it won't work):

 

img2.gif

FIGURE 6.3

 

After you make sure you have those to paths, you can build any link between them you can think of!  For example, here's mine:

 

img3.gif

FIGURE 6.4

 

Then, press the Q on the keyboard, and listen for all the beeps!  When the beeps stop, press the W key, and watch the warlock go from node 0 to node 2.  Hopefully it will work as well for you as it did for me.  Here is my warlock traveling on through the path:

 

img4.gif

FIGURE 6.5

 

There he goes!  How exciting!  And we didn't even have to use A*

 

Back

 

Well, that conlcudes the Tile-based programming tutorial, and I hope you learned a lot about how to get started creating a tile-base game.  We sure covered a lot --  the mouse, the camera, the nodes, the paths, and the pathfinding.  There are many elements that go into a well-designed game, and no tutorial can cover every single element.  However, I believe the most important aspects of tile-based game programming have been discussed in this tutorial, and I believe many of the issues newbies tend to have trouble with have been taught.  Try to stick with any game you start planning, and never give up.  There is always a solution to every game programming problem.  I also hope game programming never stops being so fun!  It is truly a wonderful hobby.

 

If you have any questions, or are having problems with something, feel free to e-mail me at: sean@wizardwalk.com and I will try to respond in a decent amount of time.  Also, visit my website at http://www.wizardwalk.com

 

Have a wonderful time programming the games of tomorrow!

 

Over and out,

Sean Patrick Hannifin