Taking a Longer Path

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|25\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Concept/Design -> Taking a Longer Path
Thu, 21 Mar 2019, 05:22
spinal	anyone know how to do pathfinding where instead of the shortest path between a and b, you want to move an exact amount of moves without hitting any obstacles (including your own path)? -=-=- Check out my excellent homepage!
Thu, 21 Mar 2019, 05:22
cyangames	is it possible to use A* but set obstacles to have a crazy high value (thus negating them from the correct result) -=-=- Web / Game Dev, occasionally finishes off coding games also!
Thu, 21 Mar 2019, 05:30
Jayenkai	I was thinking something like "pick a random point which is equidistant between A and B, at half the intended number, then pathfind to that point, then from there to the end point".. It wouldn't be exact, though, so you'd probably need to do multiple iterations to find one that matches. -=-=- ''Load, Next List!''
Thu, 21 Mar 2019, 06:17
cyangames	Ohhh, so if you wanted to do mobile object avoidance you could hittest the object against the squares and change their movement cost accordingly... Now I kinda wanna do A* pathfinding on the NES....somehow...errrr -=-=- Web / Game Dev, occasionally finishes off coding games also!
Thu, 21 Mar 2019, 07:35
spinal	I was thinking something along these lines... Graphics 320,12,32,2 time1=MilliSecs() a0=0:a1=0:a2=0:a3=0:a4=0:a5=0:a6=0:a7=0:a8=0:a9=0 fileout=WriteFile("moves.txt") While a9<>3 a0=a0+1 If a0=4 Then a0=0:a1=a1+1 If a1=4 Then a1=0:a2=a2+1 If a2=4 Then a2=0:a3=a3+1 If a3=4 Then a3=0:a4=a4+1 If a4=4 Then a4=0:a5=a5+1 If a5=4 Then a5=0:a6=a6+1 If a6=4 Then a6=0:a7=a7+1 If a7=4 Then a7=0:a8=a8+1 If a8=4 Then a8=0:a9=a9+1 thing$= Str$(a9)+Str$(a8)+Str$(a7)+Str$(a6)+Str$(a5)+Str$(a4)+Str$(a3)+Str$(a2)+Str$(a1)+Str$(a0) WriteLine(fileout,thing$):ins=0 If KeyDown(1) Then End Wend CloseFile(fileout) WaitKey() End --v But only working out x number of moves while tracing each path and checking of obstacles. But I can't quick get my head around crating the path as an array of moves. Also, the end point isn't so important either. So from A to wherever in exactly X moves safely. -=-=- Check out my excellent homepage!
Thu, 21 Mar 2019, 07:39
Jayenkai	Eeek! Array that up!!!
Thu, 21 Mar 2019, 08:26
Jayenkai	Made a brute-force thing.. Graphics 512,512,0,2 SetBuffer BackBuffer() Global GridW=16 Global GridH=16 Global zx=512/GridW Global zy=512/GridH Global PlayerX,PlayerY,TargetX,TargetY,PathLength,Threshold Dim grid(GridW,GridH) Dim path(GridW,GridH) PlayerX=1 PlayerY=1 TargetX=GridW-2 TargetY=GridH-2 PathLength=32 Repeat mx=MouseX()/zx my=MouseY()/zy If MouseDown(1) Then grid(mx,my)=1 ; Left Mouse to draw a wall If MouseDown(2) Then grid(mx,my)=0 ; Right Mouse to remove a wall If KeyDown(2) Then PlayerX=mx:PlayerY=my ; [1] to move Player If KeyDown(3) Then TargetX=mx:TargetY=my ; [2] to move Target If KeyDown(57) Then PathFind() ; [Space] to find a new path Draw() Delay 5 Until KeyDown(1) Function Draw(withpath=0) ClsColor 80,80,80 Cls For x=0 To GridW-1 For y=0 To GridH-1 Color(0,0,0) If grid(x,y)=1 Then Color(255,255,255) If x=PlayerX And y=PlayerY Then Color(255,255,100) If x=TargetX And y=TargetY Then Color(100,128,255) Rect((xzx)+1,(yzy)+1,zx-2,zy-2) If path(x,y)>0 Then Color(0,180,0):Text((xzx)+(zx/2),(yzy)+(zy/2),path(x,y),1,1) Next Next If withpath=1 Then Color(255,255,255):Text(256,256,"Pathfinding",1,1) Flip End Function Function EnsureARoute() For x=0 To GridW-1 For y=0 To GridH-1 path(x,y)=0 Next Next path(TargetX,TargetY)=1 For n=2 To GridW*GridH For x=0 To GridW-1 For y=0 To GridH-1 If path(x,y)=0 If x>0 Then If grid(x-1,y)=0 And path(x-1,y)=n-1 Then path(x,y)=n If y>0 Then If grid(x,y-1)=0 And path(x,y-1)=n-1 Then path(x,y)=n If x<GridW-1 Then If grid(x+1,y)=0 And path(x+1,y)=n-1 Then path(x,y)=n If y<GridH-1 Then If grid(x,y+1)=0 And path(x,y+1)=n-1 Then path(x,y)=n EndIf Next Next If path(PlayerX,PlayerY)>0 Then Return 1 Next Return 0 End Function Function Pathfind() attempt=0 Threshold=0 If EnsureARoute()=0 Then Return fin=0 try=0 Repeat attempt=attempt+1 If attempt Mod 20=1 Then Draw(1) If attempt Mod 500=0 Then Threshold=Threshold+1 px=PlayerX py=PlayerY pd=Rand(1,4) For x=0 To GridW-1 For y=0 To GridH-1 path(x,y)=0 Next Next distance=0 try=0 Repeat moved=0 If pd=1 And px<GridW-1 Then If grid(px+1,py)=0 And path(px+1,py)=0 Then moved=1:px=px+1 If pd=2 And py<GridH-1 Then If grid(px,py+1)=0 And path(px,py+1)=0 Then moved=1:py=py+1 If pd=3 And px>0 Then If grid(px-1,py)=0 And path(px-1,py)=0 Then moved=1:px=px-1 If pd=4 And py>0 Then If grid(px,py-1)=0 And path(px,py-1)=0 Then moved=1:py=py-1 If moved=0 Or Rnd(0,20)<4 Then pd=Rand(1,4) If moved=1 distance=distance+1 path(px,py)=distance EndIf If px=TargetX And py=TargetY Then try=500 try=try+1 Until try>250 DebugLog distance If try>500 Then fin=1 If Abs(distance-PathLength)>Threshold Then fin=0 Until fin=1 End Function --v It starts off searching for the exact distance, but slowly expands the amount if it can't find one, every 500 attempts. -=-=- ''Load, Next List!''
Fri, 22 Mar 2019, 04:56
Pakz	Brute force can be very cpu intensitive with longer paths. A path more than 10 length is almost not doable I remember. Maybe use looped a* or floodfill pather and randomly block some tiles every now and then until you come with the exact amount ? Maybe find the best path and step into a random direction a number of times until you get to the right amount?
Fri, 22 Mar 2019, 05:41
spinal	What I'm looking to do, is check for valid moved in my game and giving a game over if there are none. The rules of the game are simply move a specific amount of moves without crossing your own path or hitting an obstacle. pathfinding sort of implies that there is a specific end point, which there isn't. Oh and a maximum of 10 moves, which may or may not make things easier. -=-=- Check out my excellent homepage!
Fri, 22 Mar 2019, 07:25
Jayenkai	Only 10 maximum? Yeah, you could definitely brute force that. -=-=- ''Load, Next List!''
Sat, 23 Mar 2019, 11:04
shroom_monk	I'd also vote for brute-forcing it. The requirement for an exact path length makes using any of the usual pathfinding algorithms unhelpful, but the lack of fixed destination writes them out entirely! With 10 moves your search space should be small enough to be feasible, but even if it is expensive, if the game is based on a limited number of moves by the player then you only need to run it once per move, rather than once per frame. Depth-first search will certainly be faster than breadth-first search for this, since you have a capped number of moves and you only care about whether a solution exists, not whether it's the 'best' solution. -=-=- A mushroom a day keeps the doctor away... Keep It Simple, Shroom!