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.