# Fastest pathfinding for static node matrix

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

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.

## migrated from stackoverflow.comJun 19 '12 at 15:54

This question came from our site for professional and enthusiast programmers.

• This might do better on the game development stack – Clara Onager Jun 19 '12 at 15:37
• A few thoughts without digging too deep into your code. Are you checking the same node twice if you come across it again during the search? Also, does your profiler say anything about your LINQ structures? I'm not very familiar with LINQ but I suspect it adds some overhead, especially since you're using it on every node. In addition, I also noticed that you're using for each statements only to assign variables which means those variables will only take on the last value in the list. Why are you doing this? – Richard Marskell - Drackir Jun 19 '12 at 16:53
• @RichardMarskell-Drackir: In regards to use of LINQ, I found that the overhead of using it in my hex-grid path-finding (see below) was less than * 2. It really only had an effect on the PrioirtyQueue, where a hand-rolled MinHeap was somewhat faster than a DictionaryQueue as inspired by Eric Lippert (at the cost of not providing a stable sort, so I use one at short range, and the other at long range.). – Pieter Geerkens Apr 29 '13 at 1:27
• I don't know if would be viable but you can get a lot of performance by precalculating the routes and caching for each system the best path to each other. probably would use a lot of space. – petervaz May 29 '13 at 3:22