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.