From GPWiki

Turn based movement is used in many strategy games including Final Fantasy Tactics. Final Fantasy Tactics is a tactical roleplaying game where, turn by turn, you tell your various units to fight, move, casts spells and whatnot. When it's your turn you can choose to move your unit, but the unit cannot be moved anywhere on the map. Instead there is usually a circle where movement is allowed and this is calculated from the units agilty statistic (or something similar).

Here's a nice picture to show you what I mean.

How is that nice pixely circle created? That's the question we're here to answer.

Abstracting the map

Every map tile that we can walk on we'll call a node. So this discounts things like chasms, fire pits, trees, large walls and that type of thing. We're left with a big pile of unsorted nodes.

Next we'll imagine ourselves two lists - the open list, and the closed list. These are lists of nodes and currently they're both empty.

So we have two lists and all the map tiles we can walk on, which we are calling those the nodes. Our map might look a little like this.

So there are four nodes here. Our man is standing on the node ( 1 ,1 ) (assuming 0-based index). This makes this node very important, it's the start node. The other important thing to note is the mans movement statistic. It's currently 2. With all this noted we can get started.

The Algorithm

AddTheStartNode to the Open List.

    foreach node in the OpenList

         Check if we can walk to this node, if we can't add discard and break.

         Find all the nodes 'next to' the current node, add them to the start list.
         Don't add any nodes to the openList that are already in the closedList.
         Put the current node in the ClosedList.

Okay that's quite a lost of pseudo code to digest and you may not quiet get the picture yet but that's an overview of what's going to happen. There are are a few vague things notably what does "next to" mean and how do we know if we can walk to a current node or not.

In many tactical battle games "next to" means, all tiles touching the current tile apart from the diagonal ones. So in our example, the following tiles are defined as next to.

The above nodes are what we consider next to. So we take those four nodes and add them to the open list. Then we remove node 1,1 and put that into the closed list.

Open List     ClosedList               Open List       ClosedList        OpenList        ClosedList
---------     --------                 ---------        ----------   ->  ---------       ----------
( 1, 1 )        Empty                  ( 1, 1 )           Empty           ( 1, 0 )        +( 1, 1 )
                                      +( 1, 0 )                           ( 0, 1 )
                                      +( 0, 1 )                           ( 2, 1 )
                                      +( 2, 1 )                           ( 1, 2 )
                                      +( 1, 2 )                           
                                          

Now there are four new nodes in the open list. Of course, we've glossed over the can we walk to bit.

How did we know we could walk to these new four nodes?

Well each node is given a base value, in our example our our nodes have a cost of 1. This is the cost to move over the node, in a tactics style game we might make tiles that are taller cost more, shallow water might also cost more. For simplicity though everything today is one.

class WalkNode
{
    int TotalCost = 0;
    WalkNode parent = null;
    int base = 1;
    ...
}

Above is what a tile data structure might look like! The first thing that jumps out is parent, each walk node is given a parent, unless it's the start node. So our start node was node ( 1 ,1 ), it has a null parent, no node preceeded it. The four nodes we have in the open list at the moment, each one of those parents is node ( 1, 1). Parentage is assigned when we add all the next-to nodes into the open list.

Now each node also has a walk to cost. This is how we determine if we can walk to a node or not. How might such a cost be worked out? Well hopefully you can guess. It's the parents walkToCost plus the base cost of this node. It there's no parent then the we just say 0.

A function or method to work out such a thing would be like

public int CalculateTotalCost()
{
    int parentCost = 0;
 
    if(parent != null)
    {
        parentCost = parent.TotalCost;
    }
 
    return baseCost + parentTotalCost;
}

The cost to walk to any of the four tiles, currently in the open list is 2, we have 2 movement points, so we're okay. Now we set the TotalCost of the current node to the output of CalculateTotalCost.

if([current walking cost] < movement)
{
   TotalCost = [current walking cost];
}

Well the computer churns on, and it picks up all the neighbours of the four points in the openlist. Point 1,1 is ignored because it's in the closed list. The rest are added to the open list and our four points are moved to the closed list.

Once we process the openlist again - we see that all the current point's cost 3 to walk to therefore they're discarded and the openlist is empty. We've finished. All those nodes in the closed list are nodes we can walk to!

The one thing to watch out for here, it that it costs one movement point to stand still :D But apart from that, that's the base of how tactical movement works! (could be modified by having a null parent give a total cost of -1, rather than 0)

Here's what we'd get on the last iteration.