VBfx / Tile tutorial / Step 3

Implementing A*

I already mentioned the open and done lists we need. Each item of these lists needs a position, parent and pre-calculated values for score and estimated target distance. To make things easier we'll use a class (class module) called cNode here instead of a Type. However the class will only hold some values for us:

    Public X as Long
    Public Y as Long
    Public Score as Long
    Public Dist as Long
    Public Parent as cNode

Furthermore we need a new Module called mPathFinding where we put in the necessary functions and lists. First of all we need a new Type that represents a position in 2D space:

Public Type tCoord2D
    X as Long
    Y as Long
End Type

We can use this for storing map positions or even waypoint positions.

And here are the declarations we need in the path finding Module:

Private OpenList as Collection
Private DoneList as Collection

Private TargetUnit as Long
Private Destination as tCoord2D

The two lists you already know from the theory.

TargetUnit points to the unit we're going to move, we need this so we can directly add the waypoints to that unit when done.

For performance reasons the destination will be stored in Destination, don't bother about it yet.

Extending the units

Now that each unit needs individual waypoints we have to extend the tUnit by a list of waypoints, just insert this somewhere in the Type:

        'Path finding
        WayPointCount as Long
        WayPoint() as tCoord2D

That's it already. The units have nothing to do with path finding, they'll just move towards the waypoints we set. We'll get back to this at the end of this tutorial

Adding the functions

Now where to start? The Module has nothing more to do than find a path and adding the waypoints to the specified unit. Tha interface I would except looks something like this:

FindPath( Unit, Destination )

Agree with me? That's all the module needs to know to perform the search. The start position it can get from the unit directly and the map to scan is also accessible from everywhere. Always try to keep the interface as simple as possible.

Well behind this simple interface there's a little more work to do. As mentioned in the theory we'll have to add a tile to the open list, then check the whole open list to find the nearest tile and continue the search from there. I splitted these steps up into 3 functions called AddOpen, CheckNextItem and CheckNode. The functions are explained in the following, but first let's have a look at the initial function I named FindPath:

Public Sub FindPath( iTargetUnit as Long, iDestination as tCoord2D )
    Dim Temp as New cNode
    'Setup target
    TargetUnit = iTargetUnit
    Destination = iDestination
    'Setup unit
    Unit( TargetUnit ).WayPointCount = -1
    'Reset lists
    Set OpenList = New Collection
    Set DoneList = New Collection
    'Setup start
    Temp.X = CLng( Unit( TargetUnit ).X / TileSize )
    Temp.Y = CLng( Unit( TargetUnit ).Y / TileSize )
    'Start path finding
    DoneList.Add Temp
    CheckNode Temp
End Sub

As you can see the function provides exactly the interface we wanted. First it clears the waypoint list of the specified unit and saves the destination point for later checks. in the second part the start position is gathered from the unit, note that path finding happens on the map directly and therefore uses tile-based positions.

In the last part we add the start tile to the done list because there's no need to check it again. In the last line we start the search by calling the CheckNode function.


This function checks a specified node (tile) if it's the goal and if not adds the surrounding tiles to the open list. Note that this means 4 tiles in a 4-way system and 8 tiles in a 8-way system. Finally the function calls CheckNextItem to continue the search.

Private Sub CheckNode( iNode as cNode )
    Dim X as Long
    Dim Y as Long
    Dim Score as Long
    Dim Index as Long
    'Get values
    X = iNode.X
    Y = iNode.Y
    Score = iNode.Score
    'Check for goal
    If X = Destination.X And Y = Destination.Y Then
        CheckBack iNode
        Exit Sub
    End If

If the current node matches the destination we found the goal. In this case we can re-construct the path from here by calling the CheckBack function (explainatin follows) and exit.

    'Add straight nodes
    AddOpen X + 1, Y, Score + 10, iNode
    AddOpen X, Y + 1, Score + 10, iNode
    AddOpen X - 1, Y, Score + 10, iNode
    AddOpen X, Y - 1, Score + 10, iNode
    'Add diagonal nodes
    AddOpen X + 1, Y + 1, Score + 14, iNode
    AddOpen X + 1, Y - 1, Score + 14, iNode
    AddOpen X - 1, Y + 1, Score + 14, iNode
    AddOpen X - 1, Y - 1, Score + 14, iNode
    'Check open list
End Sub

Watch for the Score there which is 10 for straight tiles and 14 for diagonal tiles.

Now this was the easier part and we're getting into the essence in the next step.