Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
This might do better on the game development stack –  Clara Onager Jun 19 '12 at 15:37
1  
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
1  
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
add comment

migrated from stackoverflow.com Jun 19 '12 at 15:54

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

1 Answer

Without looking at your spaghetti code, I can say you are doing something drastcically wrong. I have adapted Eric Lippert's C# A-star algorithm to a hex map of ~ 420x750 hexes (~ 133,000 hexes total), and the longest diagonal path determination takes about 3 sec.

A profile analysis would almost certainly identify the performance culprit quickly, as you are off by at least an order of magnitude. Likely candidates are your closed list, so check your hashing algorithm. I used x<<16 ^ y.

Hmm! Where is your closed-list lookup? I can't find it. That wold explain poor performance.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.