4 way Flood Fill Pathfinding

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|618\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Snippet Home -> AI and Movement

Pakz	Created : 20 July 2017 Language : Monkey-X 4 way Flood Fill Pathfinding Move your monsters around the map.
Import mojo ' This is a class that holds x and y variables. Class pathnode Field x:Int,y:Int Method New(x:Int,y:Int) Self.x = x Self.y = y End Method End Class Class MyGame Extends App 'Our map. it holds the walls(-1) and the distance 'from the start to end position. Field cmap:Int[][] ' map width and height Field mw:Int=20,mh:Int=20 ' tile width and height Field tw:Float=22,th:Float=18 ' our start and end position Field sx:Int,sy:Int,ex:Int,ey:Int ' this holds our path Field path:List<pathnode> Method OnCreate() SetUpdateRate(1) ' create a new map array cmap = New Int[mw][] For Local i:=0 Until mw cmap[i] = New Int[mh] Next ' set the tile width and height. tw = DeviceWidth() / Float(mw) th = DeviceHeight() / Float(mh) ' get a random seed so every time we run ' this program we get a different result. Seed = GetDate[4] + GetDate[5] End Method Method OnUpdate() 'erase the map For Local y:=0 Until mh For Local x:=0 Until mw cmap[x][y] = 0 Next Next 'draw some contents on the map For Local x:=0 Until mw Step 5 For Local y:=2 Until mh-2 cmap[x][y] = -1 Next Next For Local i:=0 Until 5 Local x1:Int=Rnd(0,mw-4) Local y1:Int=Rnd(0,mh-4) For Local x2:=0 Until 4 For Local y2:=0 Until 4 cmap[x1+x2][y1+y2] = -1 Next Next Next For Local y:=0 Until mh Step 5 For Local x:=0 Until mw cmap[x][y] = 0 Next Next 'find start and end position Repeat sx = Rnd(0,mw) sy = Rnd(0,mh) ex = Rnd(0,mw) ey = Rnd(0,mh) If cmap[sx][sy] = 0 And cmap[ex][ey] = 0 If sx<>ex And sy<>ey Exit End If End If Forever 'flood the map with distance from 'sx and sy ' Create a list with a class inside it (the class has ' the x and y variables) Local ol:List<pathnode> = New List<pathnode> ' Add the start position on the list ol.AddLast(New pathnode(sx,sy)) ' set the cloes map at the start position to distance 1 cmap[sx][sy] = 1 ' some helper arrays. We can determine the top,right,and bottom ' and left position cells with these numbers. Local dx:Int[] = [0,1,0,-1] Local dy:Int[] = [-1,0,1,0] ' While there is contents in the list While ol.Count <> 0 ' Get the current location Local x1:Int=ol.First.x Local y1:Int=ol.First.y ' Remove the current location from the list ol.RemoveFirst ' Get 4 new positions around the current positions For Local i:=0 Until 4 ' Set new x and y Local nx:Int=x1+dx[i] Local ny:Int=y1+dy[i] ' If the coordinates are inside the map If nx>=0 And ny>=0 And nx<mw And ny<mh ' If the closedmap is not written to yet If cmap[nx][ny] = 0 ' Set the new distance based on the current distance cmap[nx][ny] = cmap[x1][y1] + 1 ' Add new position to the list ol.AddLast(New pathnode(nx,ny)) End If End If Next Wend ' Make the path. Here we start at the end position ' and find the lowest value around our current position ' and so on until we are at the start position. ' Get the current position Local x1:Int=ex,y1:Int=ey ' Reset our path list path = New List<pathnode> ' Set the first path contents(end x and y) path.AddLast(New pathnode(x1,y1)) ' Little counter for if we enter an infinite loop Local cnt:Int=0 ' While we are not near the map distance of 1 While cmap[x1][y1] > 1 ' Get tge current poditions distance Local lowest:Int=cmap[x1][y1] ' Create 2 new variables that hold the new location Local nx:Int,ny:Int ' If the position left of our current position is on the map ' and is not a wall and has a distance smaller that of our ' current position. If x1-1>=0 And cmap[x1-1][y1]>-1 And cmap[x1-1][y1] < lowest Then ' set new position nx=x1-1 ny=y1 ' set new lowest variable lowest = cmap[nx][ny] End If ' If the position right of our current position is on the map ' and is not a wall and has a distance smaller that of our ' current position. If x1+1<mw And cmap[x1+1][y1]>-1 And cmap[x1+1][y1] < lowest nx=x1+1 ny=y1 lowest = cmap[nx][ny] End If ' If the position top of our current position is on the map ' and is not a wall and has a distance smaller that of our ' current position. If y1-1>=0 And cmap[x1][y1-1]>-1 And cmap[x1][y1-1] < lowest nx=x1 ny=y1-1 lowest = cmap[nx][ny] End If ' If the position at the bottom of our current position is on the map ' and is not a wall and has a distance smaller that of our ' current position. If y1+1 < mh And cmap[x1][y1+1]>-1 And cmap[x1][y1+1] < lowest nx=x1 ny=y1+1 lowest = cmap[nx][ny] End If ' Here we should have a new position so we put it into ' our current position x1 = nx y1 = ny ' Add the next position to the bottom of our path list path.AddLast(New pathnode(x1,y1)) ' If we can not go anywhere then exit this loop if we have done ' a thousand loops. cnt+=1 If cnt>1000 Then Exit Wend End Method Method OnRender() Cls 0,0,0 SetColor 255,255,255 'draw the map For Local y:=0 Until mh For Local x:=0 Until mw If cmap[x][y] = -1 Then DrawRect xtw,yth,tw,th End If Next Next 'draw the path If path For Local i:=Eachin path SetColor 255,255,0 DrawRect i.xtw,i.yth,tw,th SetColor 255,255,255 DrawText cmap[i.x][i.y],i.xtw,i.yth Next End If 'Draw the end and start position SetColor 255,0,0 DrawRect sxtw,syth,tw,th DrawRect extw,eyth,tw,th SetColor 255,255,255 DrawText 'FloodFill pathfinding',0,0 End Method End Class Function Main() New MyGame() End Function --v
Latest Update Basic example showing random maps each with a path between 2 points.

Comments

4 way Flood Fill Pathfinding

Latest Update

Comments