Monday, October 23, 2017

Monkey-X - Breath First Search(bfs) - code example


 'Is this the breath first search? Not to familiar with it.  
   
 Import mojo  
   
 Class search  
      Field screenwidth:Int,screenheight:Int  
      Field mapwidth:Int,mapheight:Int  
      Field tilewidth:Float,tileheight:Float  
      Field sx:Int,sy:Int  
      Field ex:Int,ey:Int  
      Field map:Int[][]  
      Field myopenlist:List<node>  
      Field myclosedlist:List<node>  
      Field mypath:List<path>  
      Field mx:Int[]=[0,-1,1,0]  
      Field my:Int[]=[-1,0,0,1]  
      Method New(screenwidth:Int,screenheight:Int,mapwidth:Int,mapheight:Int)  
           Self.screenwidth = screenwidth  
           Self.screenheight = screenheight  
           Self.mapwidth = mapwidth  
           Self.mapheight = mapheight  
           Self.tilewidth = Float(screenwidth) / Float(mapwidth)  
           Self.tileheight = Float(screenheight) / Float(mapheight)  
           map = New Int[mapwidth][]  
           For Local i:Int=0 Until mapwidth  
                map[i] = New Int[mapheight]  
           Next  
           makemap()  
      End Method  
      Method makemap:Void()  
           For Local i:Int=0 Until mapwidth/3  
                Local x1:Float=Rnd(0,mapwidth)  
                Local y1:Float=Rnd(0,mapheight)  
                Local angle:Int=Rnd(360)  
                Local dist:Int=Rnd(3,7)  
                For Local ii:Int=0 Until dist  
                     x1+=Cos(angle)*1  
                     y1+=Sin(angle)*1  
                     If x1<0 Or y1<0 Or x1>=mapwidth Or y1>=mapheight Then Exit  
                     map[x1][y1] = 1  
                Next  
           Next  
      End Method  
      Method search:Bool(sx:Int,sy:Int,ex:Int,ey:Int)  
           If sx=ex And sy=ey Then Return False  
           If map[sx][sy] <> 0 Or map[ex][ey] <> 0 Then Return False  
           Self.sx = sx  
           Self.sy = sy  
           Self.ex = ex  
           Self.ey = ey  
           myopenlist = New List<node>  
           myclosedlist = New List<node>  
           mypath = New List<path>  
           myopenlist.AddFirst(New node(sx,sy,sx,sy))  
           ' the search  
           While Not myopenlist.IsEmpty  
                Local cx:Int=myopenlist.First.x  
                Local cy:Int=myopenlist.First.y  
                Local px:Int=myopenlist.First.parentx  
                Local py:Int=myopenlist.First.parenty  
                myclosedlist.AddFirst(New node(cx,cy,px,py))  
                If cx = ex And cy = ey Then   
                     findpathback()  
                     Return True  
                End If  
                myopenlist.RemoveFirst()  
                For Local i:Int=0 Until mx.Length  
                     Local nx:Int=cx+mx[i]  
                     Local ny:Int=cy+my[i]  
                     If nx<0 Or ny<0 Or nx>=mapwidth Or ny>=mapheight Then Continue  
                     If map[nx][ny] = 0 'if the map is not obstructed  
                     If isonclosedlist(nx,ny) = False And isonopenlist(nx,ny) = False  
                     myopenlist.AddLast(New node(nx,ny,cx,cy))                      
                     End If  
                     End If  
                Next  
           Wend  
           Return False  
      End Method  
        
   ' Here we calculate back from the end back to the  
   ' start and create the path list.  
   Method findpathback:Bool()  
     Local x:Int=ex  
     Local y:Int=ey  
     mypath.AddFirst(New path(x,y))  
     Repeat  
       For Local i:=Eachin myclosedlist  
         If i.x = x And i.y = y  
           x = i.parentx  
           y = i.parenty  
           mypath.AddFirst(New path(x,y))  
         End If  
       Next  
       If x = sx And y = sy Then Return True  
     Forever    
   End Method  
   
      Method drawpath()  
           If Not mypath Then Return  
           For Local i:=Eachin mypath  
                SetColor 255,0,0  
                DrawOval i.x*tilewidth+(tilewidth/4),i.y*tileheight,tilewidth/4,tileheight/2  
           Next  
      End Method  
        
      Method drawclosedlist()  
           If Not myclosedlist Then Return  
           For Local i:=Eachin myclosedlist  
                DrawText "loc:"+i.x+","+i.y,                    i.x*tilewidth,i.y*tileheight+15  
                DrawText "par:"+i.parentx+","+i.parenty,     i.x*tilewidth,i.y*tileheight+30  
           Next  
      End Method  
   
      Method isonopenlist:Bool(x:Int,y:Int)  
           For Local i:=Eachin myopenlist  
                If x = i.x And y = i.y Then   
                Return True  
                End If  
           Next  
           Return False  
      End Method  
   
      Method isonclosedlist:Bool(x:Int,y:Int)  
           For Local i:=Eachin myclosedlist  
                If x = i.x And y = i.y Then   
                Return True  
                End If  
           Next  
           Return False  
      End Method  
      Method draw()  
           SetColor 255,255,255  
           For Local y:Int = 0 Until mapheight  
           For Local x:Int = 0 Until mapheight  
                  
                If map[x][y] = 1  
                     SetColor 155,155,155  
                     DrawRect x*tilewidth,y*tileheight,tilewidth,tileheight       
                End If  
                If sx = x And sy = y  
                     SetColor 255,0,0  
                     DrawOval x*tilewidth+10,y*tileheight,10,10  
                End If  
                If ex = x And ey = y  
                     SetColor 255,255,0  
                     DrawOval x*tilewidth+10,y*tileheight,10,10  
                End If  
           Next  
           Next  
      End Method  
 End Class  
   
 Class node  
      Field x:Int  
      Field y:Int  
      Field parentx:Int  
      Field parenty:Int  
      Method New(x:Int,y:Int,parentx:Int,parenty:Int)  
           Self.x = x  
           Self.y = y  
           Self.parentx = parentx  
           Self.parenty = parenty  
      End Method  
 End Class  
   
 Class path  
      Field x:Int  
      Field y:Int  
      Method New(x:Int,y:Int)  
           Self.x = x  
           Self.y = y  
      End Method  
 End Class  
   
 Class MyGame Extends App  
      Field pathfound:Bool=False  
      Field mysearch:search  
      Field cnt:Int=0  
   Method OnCreate()  
        Seed = GetDate[5] * GetDate[4]  
     SetUpdateRate(10)  
     mysearch = New search(DeviceWidth,DeviceHeight,10,10)  
     pathfound = mysearch.search(2,2,6,6)  
   End Method  
   Method OnUpdate()   
        cnt+=1  
        If KeyHit(KEY_SPACE) Or cnt>15  
             pathfound=False  
             cnt=0  
             Local w:Int=Rnd(10,50)  
             mysearch = New search(DeviceWidth,DeviceHeight,w,w)  
             pathfound = mysearch.search(Rnd(w),Rnd(w),Rnd(w),Rnd(w))  
        End If   
   End Method  
   Method OnRender()  
     Cls 0,0,0   
     mysearch.drawclosedlist  
     mysearch.draw  
     mysearch.drawpath  
     SetColor 255,255,255  
           If pathfound  
                DrawText "Path Found",0,0  
           End If  
   End Method  
 End Class  
   
   
 Function Main()  
   New MyGame()  
 End Function  

No comments:

Post a Comment