VBfx / Tile tutorial / Step 4

Node checking

The following part is getting a little harder and you have to watch carefully what is explained.

The AddOpen function takes the Position, Score and Parent node as parameters. I'll explain the parts in-code for you:

Private Sub AddOpen( X as Long, Y as Long, Score as Long, iParent as cNode )
Dim TempNode as cNode
Dim TempScore as Long

'Check position
If X < 0 Then: Exit Sub
If Y < 0 Then: Exit Sub
If X > ( Map.W - 1 ) Then: Exit Sub
If Y > ( Map.H - 1 ) Then: Exit Sub

First it confirms the position if it's still inside the map.

'Check unit collisions
If Map.Units( Y * Map.W + X ) > 0 Then: Exit Sub

'Check map friction (score)
TempScore = Tile( Map.Floor( Y * Map.W + X ) ).Friction
If TempScore < 0 Then: Exit Sub

Now that we're inside the map for sure we can perform the collision checks. The first line checks if there's unit standing at the requested position. If so we can't pass here and the tile is left-out.

The next line gets the Friction of the specified tile. This value is added to the score making sure the algorithm tries to avoid tiles with high friction. If the friction is less than 0 the tile is blocked and we can leave it out.

TempScore = TempScore + Score

'Check done list
For Each TempNode in DoneList
If TempNode.X = X And TempNode.Y = Y Then: Exit Sub
Next

This loop checks if the specified tile is already on the done list. If so we can leave it out.

'Check open list
For Each TempNode in OpenList
If ( TempNode.X = X ) And ( TempNode.Y = Y ) Then
'Check new path
If TempNode.Score >= TempScore Then
'Found a nearer path
Set TempNode.Parent = iParent
TempNode.Score = TempScore
End If

Exit Sub
End If
Next

Now this is getting a little harder. As mentioned in the theory we have to check for shorter paths if the tile is on the open list already. In case we found one we have to update the tile's parent and score appending it to the current path. Because the tile don't needs to be added again we can leave the function then.

'Create node
Set TempNode = New cNode

The two lines create the new node and add it to the open list.

'Setup node
With TempNode
.X = X
.Y = Y
.Dist = ( Abs( Destination.X - X ) + Abs( Destination.Y - Y ) ) * 10
'        .Dist = Sqr((Destination.X - X) ^ 2 + (Destination.Y - Y) ^ 2) * 10
.Score = TempScore
Set .Parent = iParent
End With
End Sub

Here the properties are set. Since we're using objects we can set the node properties no matter the it was already added to the open list. As you can see the estimated target distance is calculated here. I used the Manhattan formula and commented Pythagoras out, feel free to try both.

CheckNextItem

This is probably the hardest function because of scanning the list. Again I'll guide you through the code:

Private Sub CheckNextItem()
Dim A as Long

Dim Min as Long
Dim Index as Long

Dim TempNode as cNode

This is the set of variables we need to perform the search.

'Check open list
If OpenList.Count = 0 Then: Exit Sub

First of all we check if there's any item in the open list. If not we didn't find the goal and have to cancel the search.

'Setup
Index = 1
Set TempNode = OpenList.Item( 1 )
Min = TempNode.Dist + TempNode.Score

Here we get the first node and calculate the estimated distance (regarding the score) for this node. Now this is a littly tricky because there are 3 possible situations we can get into:

• The open list contains only 1 item
• No item has a shorter distance to the target
• Another item has a shorter distance to the target

In the first and second case the code works just fine because the item we picked luckily was the nearest tile.

Now if the last case happens we have to find the nearest tile first, this is done in the following loop:

'Find nearest itemNode.Score
For A = 2 To OpenList.Count
'Get node from collection
Set TempNode = OpenList.Item( A )

'Compare distance
If ( TempNode.Dist + TempNode.Score ) <= Min Then
Index = A
Min = TempNode.Dist
End If
Next

The loop goes from 2 because we already picked the first item just before.

Since we're using a Collection to store the nodes we have to get the item from it's list first. After that we can compare the estimated distances and if the current item is any nearer we store it's index into the Index variable. Also we have to store the new minimum distance in the Min variable.

'Get nearest item
Set TempNode = OpenList( Index )

'Move to done list
OpenList.Remove Index

'Check that item
CheckNode TempNode
End Sub

Now that we found the nearest item we can move it to the done list and continue the search from there by calling CheckNode again.

Conclusion

What we have now is a fully-working path finding. The 3 functions work together adding tiles to the open list, checking the list for the nearest node and continuing the search from there.

The only thing left is re-constructing the way and add the waypoints to the unit we want to move. This is explained in the next step so keep on reading!