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:
'Vars
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.
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
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
'Done
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
CheckNextItem
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.