Pathfinding Help

BlitzMax Forums/BlitzMax Programming/Pathfinding Help

FBEpyon (Posted 2015) [#1]

Hello, Can someone please run this code, and help me figure out where my pathfinding is broken please?? SuperStrict SeedRnd MilliSecs() Const Infinity:Int = 2^31-1 Const MaxSX:Int = 24 Const MaxSY:Int = 24 Global g:Node[,] = New Node[MaxSX,MaxSy] Type Node Field walkable:Int Field parent:Node Field G:Int Field H:Int Field x:Int, y:Int Field list:TList Field nlist:TList = New TList Method New() list = New TList 'Parent = New Node End Method Method F:Int() Return G + H End Method Method Init:Node(_x:Int, _y:Int, _walkable:Int) x = _x y = _y walkable = _walkable End Method End Type Function GetNieghbours:TList(n:Node) Local t:TList = New TList For Local x:Int = -1 To 1 For Local y:Int = -1 To 1 If x = 0 And y = 0 Continue EndIf Local checkx:Int = n.x + x Local checky:Int = n.y + y If checkx < MaxSX And checky < MaxSY And checky >= 0 And checkx >= 0 t.AddLast(g[checkx,checky]) EndIf Next Next Return t End Function For Local x:Int = 0 Until MaxSX For Local y:Int = 0 Until MaxSY g[x,y] = New Node g[x,y].Init(x,y,Rnd(10)>6) Next Next Function CloneNode:Node(s:Node) Local n:Node = New Node n.x = s.x n.y = s.y n.walkable = s.walkable n.G = s.g n.H = s.h Return n End Function Function GenPath(px:Int, py:Int, tx:Int, ty:Int) Path.Clear() Local start:Node = g[px,py] Local target:Node = g[tx,ty] Local open:TList = New TList Local close:TList = New TList Local tmpOpen:Node[] open.AddLast(start) Local curNode:Node While open.Count() > 0 tmpOpen = Node[](open.ToArray()) curNode = tmpOpen[0] For Local i:Int = 0 Until open.Count() If tmpOpen[i].f() < curNode.f() Or tmpOpen[i].f() = curNode.f() And tmpOpen[i].H < curNode.H curNode = tmpOpen[i] EndIf Next open.Remove(curNode) close.AddLast(curNode) If curNode = target RetracePath(start,target) Return EndIf For Local i:Node = EachIn GetNieghbours(curNode) If Not i.walkable Or close.Contains(i) Continue EndIf Local newMove:Int = curNode.G + Distance(curNode, i) If newMove < i.G Or Not open.Contains(i) i.G = newMove i.H = Distance(i, target) i.Parent = curNode If Not open.Contains(i) open.AddLast(i) EndIf EndIf Next Wend open.Clear() close.Clear() End Function Function RetracePath(s:Node, e:Node) Local curNode:Node = e While curNode <> s Path.AddLast(curNode) curNode = curNode.Parent Wend Path.Reverse() End Function Function Distance:Int(n1:Node, n2:Node) Local x:Int = Abs(n1.x - n2.x) '* (n1.x - n2.x)) Local y:Int = Abs(n1.y - n2.y) '* (n1.y - n2.y)) If x > y Return 14 * y + 10 * (x - y) EndIf Return 14 * x + 10 * (y - x) End Function 'end Graphics 640,480 Global px:Int = 5, py:Int =5 Global tx:Int = 15, ty:Int = 15 Global Path:TList = New TList GenPath(px,py,tx,ty) While Not KeyHit(KEY_ESCAPE) If MouseHit(MOUSE_LEFT) px = MouseX()/16 py = MouseY()/16 GenPath(px,py,tx,ty) EndIf If MouseHit(MOUSE_RIGHT) tx = MouseX()/16 ty = MouseY()/16 GenPath(px,py,tx,ty) EndIf Cls 'Rem For Local n:Node = EachIn g If n.walkable = True SetColor 255,255,255 Else SetColor 0,0,0 EndIf If Path.Contains(n) SetColor 0,255,0 EndIf DrawRect n.x*16,n.y*16,16,16 Next 'End Rem SetColor 255,0,255 DrawRect px*16, py*16, 16, 16 SetColor 255,0,0 DrawRect tx*16, ty*16, 16, 16 SetColor 255,255,255 Flip Wend EndGraphics End *Updated Code a bit, NOW IT WORKS!!!* Thanks,

zoqfotpik (Posted 2015) [#2]

Read my code archive entry on Dijkstra map pathfinding. You may find it somewhat easier to conceptualize.

Matty (Posted 2015) [#3]

Yep dijkstra pathfinding is easy to implement. ... I second that idea.

FBEpyon (Posted 2015) [#4]

Yeah I looked at the Dijkstra and its good, but I'm working on my Dwarf mining game, and notices performance issues with it. I came up with my own path finding that seems to work for the most part, but then things start to get stuck with they are directly to the left of the target or top of the target. I will look at the Dijkstra again because it doesn't seem to require as much. Thanks, FBEpyon

Pineapple (Posted 2015) [#5]

For the love of god, don't use Djikstra's if a heuristic is available. Try checking this out: http://www.policyalmanac.org/games/aStarTutorial.htm

Henri (Posted 2015) [#6]

Hi, there is also Astar demo in blitmax / samples folder. -Henri

FBEpyon (Posted 2015) [#7]

@Pineapple@ Thanks for the information I will go over it a bit more.. :P I have most of what I need in the above code, but I'm not sure were the path is getting messed up at.. :( **UPDATED** THIS IS FULLY WORKING NOW!! Thanks for all the help!!

zoqfotpik (Posted 2015) [#8]

Pineapple you can precache Dijkstra maps :) Don't discount them if you don't know what they are, they're different from the Dijkstra algorithm. They also allow INCREDIBLY simple AI that can look extremely lifelike. Really if you use the maps it's closer to potential fields than it is to A* or the Dijkstra algorithm.