Example - Breath First grid search.monkey

'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