Path-Finding

[SLH]

Hi all, here's the situation: (if you just want to get to my problem scroll down to the code listing)

I'm making a 2d tile-based game. All is going well, i have inhabited it with various monsters, created lots of maps etc. I'm now trying to expand the possibilities by adding a general path finding function to get from A to B in my map.

I have managed to use the A* algorythm in one type of my monsters fine. The only trouble is that on big maps it noticably slows down my game.

What i thought i could do is pre-calculate the direction to move to get from A to B.

This I have also managed to do, using the A* algorythm. However, as each calculation of a path is independent of the other this creates a huge pause when calculating all the paths (as the # of calculations required is GridWidth^2*gridheight^2).

My thought was that i could adapt the A* algorythm so that i didn't need to do similar calculations more than once.

Below is the algorythm i devised.

Create a closed list and an open list, for storing nodes

Loop through each node that the destination can see, adding them onto the open list

While the open list is not empty:
    Get a node from the open list, then remove it from that list
    If this node is in the closed list ignore it
    For each node that this node can see:
        If it's not on the open list then calculate it's distance from the destination via 'thisnode'
        If it is on the open list check it's distance, and if it's better to go via 'thisnode' then update the distance

'At this point each node as its distance from the destination (i hope)

For each possible position on the grid:
    Loop through each node that this position can see, finding the one with the shortest distance to the destination
    Once we have the best node (shortest distance), store the direction we need to move in to get from our position to that node and store it

I hope you're still with me here. The implimentation i've put below doesn't work. I was just wondering if anyone could see anything wrong with the above algorythm, or my implimentation. FYI, everything is syntactically correct and the algorythm runs, it just doesn't work correctly.

[SLH]

The overall function

frmProgress.ProgressBar.Width = 0
For i = 2 To GridWidth - 1
    For j = 2 To GridHeight - 1
        If Not ThinkGrid(i, j).Type = harddirto Then
            NodeNetwork.ResetNodeData
            GetMovePathsUsingNodes i, j
            frmProgress.ProgressBar.Width = frmProgress.Width * (((i - 1) / (GridWidth - 2)) + ((j - 1) / (GridHeight - 2)) / (GridWidth - 2)) 'Update the progress bar
            DoEvents
        End If
    Next j
Next i

[SLH]

The function that given a destination, gets all directions for all possible source positions

Public Sub GetMovePathsUsingNodes(DestX As Integer, DestY As Integer)
    Dim i As Integer
    Dim j As Integer
    Dim BestNode As TPathNode
    Dim CurrentNode As New TNodeListElement
    Dim TempNode As TPathNode
    Dim NodesNRDest As New TNodeList
    Dim NodesToCheck As New TNodeList
    Dim CheckedNodes As New TNodeList
    'This routine uses a method similar to that of the other one,
    'except that it gets lots of paths from the same data (and so is faster)
    
    Set CurrentNode = NodeNetwork.Nodes.Start
    
    If IsVisible(DestX, DestY, CurrentNode.Data.X, CurrentNode.Data.Y) Then
        Set TempNode = New TPathNode
        TempNode.X = DestX
        TempNode.Y = DestY
        CurrentNode.Data.Distance = GetDistance(TempNode, CurrentNode.Data)
        NodesNRDest.Add CurrentNode.Data
        NodesToCheck.Add CurrentNode.Data
    End If
    Do
        If Not Exists(CurrentNode.NextLE) Then Exit Do
        Set CurrentNode = CurrentNode.NextLE
        
        If IsVisible(DestX, DestY, CurrentNode.Data.X, CurrentNode.Data.Y) Then
            Set TempNode = New TPathNode
            TempNode.X = DestX
            TempNode.Y = DestY
            CurrentNode.Data.Distance = GetDistance(TempNode, CurrentNode.Data)
            NodesNRDest.Add CurrentNode.Data
            NodesToCheck.Add CurrentNode.Data
        End If
    Loop Until Not Exists(CurrentNode.NextLE)
    
    'NodesNRDest now contains a list of all nodes that can see the destination as does NodesToCheck
    
        While Not NodesToCheck.IsEmpty
        Set TempNode = NodesToCheck.GetTop
        NodesToCheck.RemoveTop
        CheckedNodes.Add TempNode
        
        'Check Up
        If Exists(TempNode.UpLink) Then
            If Not CheckedNodes.AlreadyExists(TempNode.UpLink) Then
                If NodesToCheck.AlreadyExists(TempNode.UpLink) And (TempNode.UpLink.Distance > 0 Or (TempNode.UpLink.X = DestX And TempNode.UpLink.Y = DestY)) Then
                    If TempNode.Distance + GetDistance(TempNode, TempNode.UpLink) < TempNode.UpLink.Distance Then
                        TempNode.UpLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.UpLink)
                        'Possibly reorder the list
                    End If
                Else
                    NodesToCheck.Add TempNode.UpLink
                    TempNode.UpLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.UpLink)
                End If
            Else
                'If TempNode.Distance + GetDistance(TempNode, TempNode.UpLink) < TempNode.UpLink.Distance Then
                '    TempNode.UpLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.UpLink)
                '    'Possibly reorder the list
                'End If
            End If
        End If
        
        'Check Down
        If Exists(TempNode.DownLink) Then
            If Not CheckedNodes.AlreadyExists(TempNode.DownLink) Then
                If NodesToCheck.AlreadyExists(TempNode.DownLink) And (TempNode.DownLink.Distance > 0 Or (TempNode.DownLink.X = DestX And TempNode.DownLink.Y = DestY)) Then
                    If TempNode.Distance + GetDistance(TempNode, TempNode.DownLink) < TempNode.DownLink.Distance Then
                        TempNode.DownLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.DownLink)
                        'Possibly reorder the list
                    End If
                Else
                    NodesToCheck.Add TempNode.DownLink
                    TempNode.DownLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.DownLink)
                End If
            Else
                'If TempNode.Distance + GetDistance(TempNode, TempNode.DownLink) < TempNode.DownLink.Distance Then
                '    TempNode.DownLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.DownLink)
                '    'Possibly reorder the list
                'End If
            End If
        End If
        
        'Check Left
        If Exists(TempNode.LeftLink) Then
            If Not CheckedNodes.AlreadyExists(TempNode.LeftLink) Then
                If NodesToCheck.AlreadyExists(TempNode.LeftLink) And (TempNode.LeftLink.Distance > 0 Or (TempNode.LeftLink.X = DestX And TempNode.LeftLink.Y = DestY)) Then
                    If TempNode.Distance + GetDistance(TempNode, TempNode.LeftLink) < TempNode.LeftLink.Distance Then
                        TempNode.LeftLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.LeftLink)
                        'Possibly reorder the list
                    End If
                Else
                    NodesToCheck.Add TempNode.LeftLink
                    TempNode.LeftLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.LeftLink)
                End If
            Else
                'If TempNode.Distance + GetDistance(TempNode, TempNode.LeftLink) < TempNode.LeftLink.Distance Then
                '    TempNode.LeftLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.LeftLink)
                '    'Possibly reorder the list
                'End If
            End If
        End If
        
        'Check Right
        If Exists(TempNode.RightLink) Then
            If Not CheckedNodes.AlreadyExists(TempNode.RightLink) Then
                If NodesToCheck.AlreadyExists(TempNode.RightLink) And (TempNode.RightLink.Distance > 0 Or (TempNode.RightLink.X = DestX And TempNode.RightLink.Y = DestY)) Then
                    If TempNode.Distance + GetDistance(TempNode, TempNode.RightLink) < TempNode.RightLink.Distance Then
                        TempNode.RightLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.RightLink)
                        'Possibly reorder the list
                    End If
                Else
                    NodesToCheck.Add TempNode.RightLink
                    TempNode.RightLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.RightLink)
                End If
            Else
                'If TempNode.Distance + GetDistance(TempNode, TempNode.RightLink) < TempNode.RightLink.Distance Then
                '    TempNode.RightLink.Distance = TempNode.Distance + GetDistance(TempNode, TempNode.RightLink)
                '    'Possibly reorder the list
                'End If
            End If
        End If
    Wend
    
    'Now every node has its distance from the destination associated with it.
    
    'Loop through every possible place that could get to the destination
    For i = 2 To GridWidth - 1
        For j = 2 To GridHeight - 1
            If ThinkGrid(i, j).Type = harddirto Or NodeNetwork.Nodes.IsEmpty Then
                RouteData(i, j, DestX, DestY).PathExists = False
            Else
                If IsVisible(i, j, DestX, DestY) Then
                    'There is a direct route between the monster and this node
                    RouteData(i, j, DestX, DestY).Direction = GetDirection(i, j, DestX, DestY)
                    RouteData(i, j, DestX, DestY).PathExists = True
                Else
                    If Not (i = DestX And j = DestY) Then
                        'The src isn't the dest, and the src is an open tile
                        'Loop through each node that the monster can see, and find the one with the shortest distance to the player, and workout how to get to it (a direction)
                        Set CurrentNode = CheckedNodes.Start
                        
                        If IsVisible(i, j, CurrentNode.Data.X, CurrentNode.Data.Y) And Not (i = CurrentNode.Data.X And j = CurrentNode.Data.Y) Then
                            If Exists(BestNode) Then
                                Set TempNode = New TPathNode
                                TempNode.X = i
                                TempNode.Y = j
                                If BestNode.Distance + GetDistance(BestNode, TempNode) > CurrentNode.Data.Distance + GetDistance(CurrentNode.Data, TempNode) Then
                                    Set BestNode = CurrentNode.Data
                                End If
                            Else
                                Set BestNode = CurrentNode.Data
                            End If
                        End If
                        Do
                            If Not Exists(CurrentNode.NextLE) Then Exit Do
                            Set CurrentNode = CurrentNode.NextLE
                            
                            If IsVisible(i, j, CurrentNode.Data.X, CurrentNode.Data.Y) And Not (i = CurrentNode.Data.X And j = CurrentNode.Data.Y) Then
                                If Exists(BestNode) Then
                                    If BestNode.Distance + GetDistance(BestNode, TempNode) > CurrentNode.Data.Distance + GetDistance(CurrentNode.Data, TempNode) Then
                                        Set BestNode = CurrentNode.Data
                                    End If
                                Else
                                    Set BestNode = CurrentNode.Data
                                End If
                            End If
                        Loop Until Not Exists(CurrentNode.NextLE)
                        
                        If Exists(BestNode) Then
                            RouteData(i, j, DestX, DestY).PathExists = True
                            RouteData(i, j, DestX, DestY).Direction = GetDirection(i, j, BestNode.X, BestNode.Y)
                            Set BestNode = Nothing
                        End If
                    End If
                End If
            End If
        Next j
    Next i
End Sub

[mark113]

I have no clue what the A* is but here is what you should do. Dijkstra's Algo. Here is why. You have a modern computer with tons of disk space. You could create a data map of the PERFECT optimal route from every space on your map to every other space on your map. You do all this processing before your game runs and store the data as a text file. It'll be big; maybe 10 to 100mb depending on the size of your maps. Then you read this data into a multi demensional array and every time a monster needs to move you pass the monsters current XY and the target XY into a function you wrote and it returns the next XY for your critter. The time involved is a simple array lookup.

This will work because everytime you run DA for a specific target node it weighs every posible nodes proximitly to the target node based on the PERFECT optimal routes. So pick any other node on the map and that node has only one node that represents the optimal path to the target. You store one array for each target node. The 2D array uses the maps X,Y to corespond to another X,Y. TheTargetArray(MonsterX, MonsterY) = Next MonsterX,Y

This is some work up front and alot of storage space but you will not find a faster or more acurate pathfinding solution.

Feel free to contact me for more details.

[Illuminator]

I have a few questions about the data set, not the method you are using, that might lead to a possible solution.

1. What dimensions are these maps? 100x100? 1000X1000?

2. When the map is created do walls or otherwise impassible
areas use one full tile or do they border the edges of the
tiles?

3. Are the nodes you referred to in the first post adjacent tiles
another or are they only at points such as intersections.

All of these questions lead to one main idea.
* Is it possible to reduce your data set ? *

I have used dijkstra's implementation with VB in my own path fining program and it works fast on maps that are 20x20 tiles in size. I preprocess the maps and create a Decision Node Map.

These nodes are important because they dont bother with all of the possibilities of going to adjacent tiles. For example a node is placed at corridor intersections but NOT at any point in an open area (after all in an open area there are thousands of paths between two points) In open areas I only have nodes at the corners, at corridor entrances to the area, and at the destination within the open area. If I ever have to cross the open area then all I did was calculate the tile path of a straight line.

As a last resort you may want to think about writing a c++ DLL file that will perform the algorithm. Feed it an adjacency matrix and return an array of consecutive nodes.

[SLH]

Thanks for your replys.

Re Mark:

I have heard of Dykstra's algorythm and did concider using it. However, the trouble with this algorythm, (and the A*) is that it has no memory of previous searches. I know you pre-proces the map to make a graph, but the actual tracing of the graph is the bit that takes the time.

I have already done exactly what you've described using the A* algorythm, and so i think i'll stick to adapting it, as i already have a full understanding of it.

FYI the A* algorythm also projuces the best path, and is recognised by most academics as the fastest (according to numerus sources).


Re Illuminator:

1: Absolute max dimensions are 100x100

So the saved file size is about tops 15MB

2: The wals are 1 tile each.

3:Nodes are not at all tiles, just ones of note, i.e. entrances to areas, exits to areas, corners of passageways etc. All nodes can 'see' eachother in a straight line.


I have thought of most of the obvious optimization methods (such as using nodes, not every open tile in the algorythm). I have already completed a working algorythm as you both describe. I don't have problems with the speed, i just need to spot the error(s) in the algorythm. (I've been stareing at it for so long i can't see anything i've done wrong).

If i do manage to fix it, i'll post my game with source thus far if anyone's interested.


Any more help would by much appreciated (as was the help thus far).

[NotLKH]

Originally posted by SLH
FYI the A* algorythm also projuces the best path, and is recognised by most academics as the fastest (according to numerus sources).

perhaps you could post some links to sites describing this?

[SLH]

Originally posted by NotLKH
perhaps you could post some links to sites describing this?

Certainly.

This Page has lots of links about the A* algorythm (as well as a few others).

[SLH]

I found the error with my distance-calculating part of my algorythm, so you can assume that part of the algorythm works correctly.

However i'm still having trouble with the final calculation though...

[SLH]

Well, after a lot of searching, i found the problem.

If you want to see it in useClick Here