I'm working on a brand new grid based game, and I need some help. I'm searching for algorithm (or code) that can iterate through all possible paths between point A and point B on a 6x6 grid (taking into account to not walk through empty squares). So this isn't a shortest path pathfinding problem, but an all paths pathfinding problem.
Is this the solution to my problem? http://en.wikipedia.org/wiki/Breadth-first_search
If yes, then how to apply this algorithm to 2D grid?
Here is a little code snippet showing my problem:
Code: Select all
#include "fbgfx.bi"
Using FB
Randomize Timer
Const As Integer gridSize = 50
Const As Integer gridSizeHalf = gridSize / 2
Const As Integer gridX = 6
Const As Integer gridY = 6
Const As Integer xres = gridSize * gridX
Const As Integer yres = gridSize * gridY
Const As Integer midx = xres / 2
Const As Integer midy = yres / 2
Const As Single Pi = Atn(1) * 4
Const As Single TwoPi = Atn(1) * 8
Const As Single RAD = Pi / 180
Const As Single DEG = 180 / Pi
Dim Shared As Integer valueGrid(gridX, gridY)
Dim Shared As Integer x1, y1, x2, y2
Function randINT(first As Integer, last As Integer) As Integer
Function = Cint(Rnd * (last - first) + first)
End Function
Sub CenterText(text As String, xx As Integer, yy As Integer)
Dim As Integer xOff = Len(text) * 4
Draw String ((xx - xOff) + 2, yy - 3), text, Rgb(0, 0, 0)
End Sub
Sub InitGrid()
For x As Integer = 0 To gridX - 1
For y As Integer = 0 To gridY - 1
valueGrid(x, y) = 1
Next
Next
For i As Integer = 1 To 5
valueGrid(randINT(0, gridX - 1), randINT(0, gridY - 1)) = 0
Next
Do
x1 = randINT(0, gridX - 1)
y1 = randINT(0, gridY - 1)
x2 = randINT(0, gridX - 1)
y2 = randINT(0, gridY - 1)
Loop Until ((x1 <> x2) Or (y1 <> y2)) And valueGrid(x1, y1) = 1 And valueGrid(x2, y2) = 1
End Sub
Sub RenderGrid()
Dim As Integer xx, yy
For x As Integer = 0 To gridX - 1
xx = x * gridSize
For y As Integer = 0 To gridY - 1
yy = y * gridSize
If valueGrid(x, y) = 1 Then Line(xx, yy)-(xx + gridSize, yy + gridSize), Rgb(255, 255, 255), bf
Line(xx, yy)-(xx + gridSize, yy + gridSize), Rgb(200, 200, 200), b
Next
Next
CenterText("A", x1 * gridSize + gridSizeHalf, y1 * gridSize + gridSizeHalf)
CenterText("B", x2 * gridSize + gridSizeHalf, y2 * gridSize + gridSizeHalf)
End Sub
Screenres xres, yres, 32
Color Rgb(255, 255, 255), Rgb(100, 100, 100)
InitGrid()
Do
Screenlock
Cls
RenderGrid()
Screenunlock
Sleep 5
Loop Until Multikey(SC_ESCAPE)