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