VBfx / Tile tutorial / Step 4

Node checking

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

AddOpen

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 skipped.

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 skip it.

    'Add score offset
    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 skip it.

    '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
    OpenList.Add TempNode

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:

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
    DoneList.Add TempNode
    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!

Navigation