Pathing Problem (Recursion)

[The Frugal Gourmet]

Here's a bit of a puzzle I've been working on the past day or so. I imagine it's not as difficult as I'm making it to be, so I thought someone here might be able to help me out. It's basically a "pathing" routine.

In this particular application (in my case, it's a board game), I have 500 different "sectors" or units where a player could be located. Unfortunately, the board is not really set up in a system with coordinates and it has no definite shape. The playing field is set up randomly each game and the only rule in how the game is set up is that one sector must border between 1 and 5 other sectors.

My goal is to create a routine which will generate the shortest path between "sectors" (which sectors the user must traverse).

So far, I have come up with the following, but it is so slow and unwieldy that it craps out if the sectors are more than 12 or so spaces from one another.

[The Frugal Gourmet]

Type A_Sector
    exits(1 To 6) As Integer
    sector_number
End Type

Dim path(1 To 30) As Integer
Dim all_sectors(1 To 500) As A_Sector

Function adjacent_sector()
'Determines whether one sector is adjacent to another.  Code not included.

End Function

Public Sub compute_shortest_path(Source As Integer, destination As Integer, step As Integer, max_depth As Integer, start As Boolean)
Dim z As Integer

While found_it = False


        If adjacent_sector(Source, destination) = True Then
                path(step + 1) = destination
                found_it = True
        Else
            If step < max_depth Then
            For i = 1 To Num_Exits
                If Source <> 0 Then
                    If all_sectors(Source).exits(i) <> 0 Then
                            compute_shortest_path all_sectors(Source).exits(i), destination, step + 1, max_depth - 1, False
                    End If
                End If
            Next i
            End If
        End If
        If start = True Then
            max_depth = max_depth + 1
           If max_depth > Max_Distance_Possible Then
                x = MsgBox("There is currently no path to that destination sector!", vbOKOnly, "No path!")
                Exit Sub
           End If
        Else
             If found_it = True Then
                    path(step) = Source
            End If
            Exit Sub
        End If
Wend
If found_it = True And start = True Then
    path(step) = Source
End If

End Sub 

[seaweed]

I didn't read your code too carefully because I don't really understand your situation, but if I understand what you are doing it's this:

Given a start and a destination, find all possible paths between them and return the shortest path.

Is that what you are doing?

If it is, this may be a little faster:

Create two global variable that contain 1)the number of steps used in a complete path from start to destination, and 2) an array of those steps that represent the path.

Find the first path from Start to Dest, and put number of steps it took in the first variable and the path itself in the array.

When searching the next path, along the way (for each step you take) compare the number of steps used so far to the number of steps in the global variable. As soon as the number of steps used in the current path equals the number of steps in the global variable, you can quit searching the current path and start searching the next path. If, however, you reach the destination before the steps equal the number in the variable, you have found a shorter path! So save the new number of steps in the variable and the path in the array. As you find shorter paths, the function will take less time to run (will quit when steps = GlobalSteps).

[The Frugal Gourmet]

Type A_Sector
    exits(1 To 6) As Integer
    sector_number
End Type

Dim path(1 To 30) As Integer
Dim all_sectors(1 To 500) As A_Sector
Dim found_it as Boolean

Function adjacent_sector()
'Determines whether one sector is adjacent to another.  Code not included.

End Function

'To call the Subroutine
compute_shortest_path x, y, 1, 1, True

Public Sub compute_shortest_path(Source As Integer, destination As Integer, step As Integer, max_depth As Integer, start As Boolean)
Dim z As Integer

While found_it = False


        If adjacent_sector(Source, destination) = True Then
                path(step + 1) = destination
                found_it = True
        Else
            If step < max_depth Then
            For i = 1 To Num_Exits
                If Source <> 0 Then
                    If all_sectors(Source).exits(i) <> 0 Then
                            compute_shortest_path all_sectors(Source).exits(i), destination, step + 1, max_depth - 1, False
                    End If
                End If
            Next i
            End If
        End If
        If start = True Then
            max_depth = max_depth + 1
           If max_depth > Max_Distance_Possible Then
                x = MsgBox("There is currently no path to that destination sector!", vbOKOnly, "No path!")
                Exit Sub
           End If
        Else
             If found_it = True Then
                    path(step) = Source
            End If
            Exit Sub
        End If
Wend
If found_it = True And start = True Then
    path(step) = Source
End If

End Sub 

[The Frugal Gourmet]

Seaweed,

Hmm.. let me think about that for a bit..

Mine already computes the shortest path by only looking one sector deeper in an iteration until it finds the target sector. So, its redundancy (and probably slowness) occurs because every new time it must go through the entire process again and THEN go one level deeper.

You might be on to something there... Thanks for the new angle...