Fastest pathfinding for static node matrix
- by Sean Martin
I'm programming a route finding routine in VB.NET for an online game I play, and I'm searching for the fastest route finding algorithm for my map type.
The game takes place in space, with thousands of solar systems connected by jump gates. The game devs have provided a DB dump containing a list of every system and the systems it can jump to. The map isn't quite a node tree, since some branches can jump to other branches - more of a matrix.
What I need is a fast pathfinding algorithm. I have already implemented an A* routine and a Dijkstra's, both find the best path but are too slow for my purposes - a search that considers about 5000 nodes takes over 20 seconds to compute. A similar program on a website can do the same search in less than a second.
This website claims to use D*, which I have looked into. That algorithm seems more appropriate for dynamic maps rather than one that does not change - unless I misunderstand it's premise.
So is there something faster I can use for a map that is not your typical tile/polygon base? GBFS? Perhaps a DFS? Or have I likely got some problem with my A* - maybe poorly chosen heuristics or movement cost? Currently my movement cost is the length of the jump (the DB dump has solar system coordinates as well), and the heuristic is a quick euclidean calculation from the node to the goal.
In case anyone has some optimizations for my A*, here is the routine that consumes about 60% of my processing time, according to my profiler. The coordinateData table contains a list of every system's coordinates, and neighborNode.distance is the distance of the jump.
Private Function findDistance(ByVal startSystem As Integer, ByVal endSystem As Integer) As Integer
'hCount += 1
'If hCount Mod 0 = 0 Then
'Return hCache
'End If
'Initialize variables to be filled
Dim x1, x2, y1, y2, z1, z2 As Integer
'LINQ queries for solar system data
Dim systemFromData = From result In jumpDataDB.coordinateDatas
Where result.systemId = startSystem
Select result.x, result.y, result.z
Dim systemToData = From result In jumpDataDB.coordinateDatas
Where result.systemId = endSystem
Select result.x, result.y, result.z
'LINQ execute
'Fill variables with solar system data for from and to system
For Each solarSystem In systemFromData
x1 = (solarSystem.x)
y1 = (solarSystem.y)
z1 = (solarSystem.z)
Next
For Each solarSystem In systemToData
x2 = (solarSystem.x)
y2 = (solarSystem.y)
z2 = (solarSystem.z)
Next
Dim x3 = Math.Abs(x1 - x2)
Dim y3 = Math.Abs(y1 - y2)
Dim z3 = Math.Abs(z1 - z2)
'Calculate distance and round
'Dim distance = Math.Round(Math.Sqrt(Math.Abs((x1 - x2) ^ 2) + Math.Abs((y1 - y2) ^ 2) + Math.Abs((z1 - z2) ^ 2)))
Dim distance = firstConstant * Math.Min(secondConstant * (x3 + y3 + z3), Math.Max(x3, Math.Max(y3, z3)))
'Dim distance = Math.Abs(x1 - x2) + Math.Abs(z1 - z2) + Math.Abs(y1 - y2)
'hCache = distance
Return distance
End Function
And the main loop, the other 30%
'Begin search
While openList.Count() != 0
'Set current system and move node to closed
currentNode = lowestF()
move(currentNode.id)
For Each neighborNode In neighborNodes
If Not onList(neighborNode.toSystem, 0) Then
If Not onList(neighborNode.toSystem, 1) Then
Dim newNode As New nodeData()
newNode.id = neighborNode.toSystem
newNode.parent = currentNode.id
newNode.g = currentNode.g + neighborNode.distance
newNode.h = findDistance(newNode.id, endSystem)
newNode.f = newNode.g + newNode.h
newNode.security = neighborNode.security
openList.Add(newNode)
shortOpenList(OLindex) = newNode.id
OLindex += 1
Else
Dim proposedG As Integer = currentNode.g + neighborNode.distance
If proposedG < gValue(neighborNode.toSystem) Then
changeParent(neighborNode.toSystem, currentNode.id, proposedG)
End If
End If
End If
Next
'Check to see if done
If currentNode.id = endSystem Then
Exit While
End If
End While
If clarification is needed on my spaghetti code, I'll try to explain.
