Grid Based Raycast

Monkey Forums/Monkey Code/Grid Based Raycast
NoOdle
(Posted 2012) [#1]
Will check if tile is visible from start to end by performing a ray cast.

Controls:

MouseLeft places start
MouseRight places goal
Import mojo


Class GridMap


	Const FREE : Int = 0
	Const OCCUPIED : Int = 1
	Const BOOKED : Int = 2
	Const RESERVED : Int = 3
	
	
	Global MAP_SIZE : Int = 8	
	Global MAP_RESOLUTION : Int = 480 / MAP_SIZE
	
	
	Global markerDiameter : Int = 12
	Global mapMarkerDiameter : Int = 26


	'map arrays
	Field map : Int[ MAP_SIZE ][]
	Field markedMap : Int[ MAP_SIZE ][]

	
	'start position of ray
	Field startX : Int
	Field startY : Int
	
	'end position of ray
	Field endX : Int
	Field endY : Int
	
	

	'setup map
	Method New()
	
		'init arrays
		For Local i : Int = 0 To MAP_SIZE - 1
			Self.map[ i ] = New Int[ MAP_SIZE ]
			Self.markedMap[ i ] = New Int[ MAP_SIZE ]
		Next


	End Method




	'creates our map
	Function Create : GridMap()
		Local this : GridMap = New GridMap
		
		Return this
	End Function




	' init the map
	Method InitMap()
		For Local x : Int = 0 To MAP_SIZE - 1
			For Local y : Int = 0 To MAP_SIZE - 1
				If (Rnd(0.0, 1.0) > 0.2)
					map[ x ][ y ] = FREE
				Else
					map[ x ][ y ] = OCCUPIED
				Endif
			Next
		Next
	End Method






	'paints the map
	Method Draw()
	
		Local x : Int
		Local y : Int
	
		'draws grid color if solid
		SetColor( 128, 128, 128 )
		For x = 0  To MAP_SIZE - 1
			For y = 0 To MAP_SIZE - 1
				If ( map[ x ][ y ] = OCCUPIED )
					DrawRect( x * MAP_RESOLUTION + 1, y * MAP_RESOLUTION + 1, MAP_RESOLUTION - 1, MAP_RESOLUTION - 1)
				Endif
			Next
		Next
	
	
		'draws grid lines
		SetColor( 96, 96, 96 )
		For x = 0 To MAP_SIZE
			DrawLine( x * MAP_RESOLUTION, 0, x * MAP_RESOLUTION, MAP_SIZE * MAP_RESOLUTION )
		Next
		For y = 0 To MAP_SIZE
			DrawLine( 0, y * MAP_RESOLUTION, MAP_SIZE * MAP_RESOLUTION, y * MAP_RESOLUTION )
		Next
	
	
		'draws travelled path
		For x = 0  To MAP_SIZE - 1
			For y = 0 To MAP_SIZE - 1
				If markedMap[ x ][ y ] = 1
					DrawOval(( x * MAP_RESOLUTION ) - ( mapMarkerDiameter / 2 ) + ( MAP_RESOLUTION / 2 ), y * MAP_RESOLUTION - ( mapMarkerDiameter / 2 ) + ( MAP_RESOLUTION / 2 ), mapMarkerDiameter, mapMarkerDiameter )
				Endif
			Next
		Next
	
	
		' links markers
		SetColor( 0, 0, 0 )
		DrawLine( Self.startX, Self.startY, Self.endX, Self.endY )	
		
		' draw start marker
		SetColor( 0, 255, 0 )
		DrawOval( Self.startX - ( markerDiameter / 2 ), startY - ( markerDiameter / 2 ), markerDiameter, markerDiameter )
	 
		' draw End marker
		SetColor( 255, 0, 0 )
		DrawOval( Self.endX - markerDiameter / 2, endY - markerDiameter / 2, markerDiameter, markerDiameter)
	 
	
	End Method



	'draw stats
	Method DrawStats()
		
		SetColor( 255, 255, 255 )
		DrawText( "Start: (" + Self.startX + "," + Self.startY + ")", MAP_SIZE * MAP_RESOLUTION + 16, 30 )
		DrawText( "End: (" + Self.endX + "," + Self.endY + ")", MAP_SIZE * MAP_RESOLUTION + 16, 50 )
	
		DrawText("Map Start: (" + Int( worldCoordToMapCoord( Self.startX )) + "," + Int( worldCoordToMapCoord( Self.startY )) + ")", MAP_SIZE * MAP_RESOLUTION + 16, 100 )
		DrawText("Map End: (" + Int( worldCoordToMapCoord( Self.endX )) + "," + Int( worldCoordToMapCoord( Self.endY )) + ")", MAP_SIZE * MAP_RESOLUTION + 16, 120 )

	End Method



	'convert coord
	Method mapToWorld : Float( coord : Int )
		Return Float( coord * MAP_RESOLUTION )
	End Method
	
	
	'convert coord
	Method worldCoordToMapCoord : Float( coord : Float )
		Return Float( coord / MAP_RESOLUTION )
	End Method
	 
	
	'sets position to occupies
	Method isMapPositionOccupied : Int( x : Int, y : Int )
		If (x < 0 Or y < 0 Or x > MAP_SIZE - 1 Or y > MAP_SIZE - 1 )
			Return True
		Endif
		Self.markedMap[ x ][ y ] = OCCUPIED
		Return Self.map[ x ][ y ] = OCCUPIED
	End Method


	'resets marked map
	Method ResetMarkedMap()
		For Local x : Int = 0 To  MAP_SIZE - 1
			For Local y : Int = 0 To MAP_SIZE - 1
				Self.markedMap[ x ][ y ] = 0
			Next
		Next
	End Method


	
	Method CheckPath : Int()
	
		' calculate the direction of the ray (linear algebra)
		Local dirX : Float = (Self.endX - Self.startX)
		Local dirY : Float = (Self.endY - Self.startY)
		Local length : Float = Float( Sqrt(dirX * dirX + dirY * dirY))
		
		' normalize the direction vector
		dirX = ( dirX / length ) + 0.001
		dirY = ( dirY / length ) + 0.001
	 
		' how far we must move in the ray direction before we encounter a New voxel in x-direction
		Local tDeltaX : Float = MAP_RESOLUTION / Abs(dirX)
	
		' same but y-direction
		Local tDeltaY : Float = MAP_RESOLUTION / Abs(dirY)
	 
		' decide which direction To start walking in
		'signum will return -1 if less than 0 otherwise 1
		Local stepX : Int = Signum( dirX )
		Local stepY : Int = Signum( dirY )
		
		
		' start voxel coordinates
		' use your transformer Function here
		Local x : Int = Int( worldCoordToMapCoord( Self.startX ))
		Local y : Int = Int( worldCoordToMapCoord( Self.startY ))
	
		' End voxel coordinates
		Local endX1 : Int = Int(worldCoordToMapCoord( Self.endX ))
		Local endY1 : Int = Int(worldCoordToMapCoord( Self.endY ))	
		
		
	
		' calculate distance To first intersection in the voxel we start from
		Local tMaxX : Float
		If dirX < 0
			tMaxX = ( mapToWorld( x ) - Self.startX ) / dirX
	      Else
			tMaxX = ( mapToWorld( x + 1 ) - Self.startX ) / dirX
		Endif
	 	Local tMaxY : Float
		If dirY < 0
			tMaxY = ( mapToWorld( y ) - Self.startY ) / dirY
		Else
			tMaxY = ( mapToWorld( y + 1 ) - Self.startY ) / dirY
		Endif
	
	
	    Local reachedX : Int = False
		Local reachedY : Int = False

	
	      ' check If first is occupied
		If isMapPositionOccupied(x, y)
			Return False
		Else
			'check if start and end are the same
			If x = endX1 And y = endY1
				Return True	
			Endif
		Endif
		
	
		While True
			If (tMaxX < tMaxY)
				tMaxX = tMaxX + tDeltaX
				x = x + stepX
			Else
				tMaxY = tMaxY + tDeltaY
				y = y + stepY
			Endif
			If stepX > 0.0
				If x >= endX1
					reachedX = True
				Endif
			Elseif x <= endX1
				reachedX = True
			Endif
			If stepY > 0.0
				If y >= endY1
					reachedY = True
				Endif
			Elseif y <= endY1
				reachedY = True
			Endif
			If (isMapPositionOccupied(x, y))
				Return False
			Endif
			If (reachedX = True And reachedY = True)
				Exit
			Endif
		Wend

		Return True
	End Method


End Class









Class MyApp Extends App


	'store our map
	Field myMap : GridMap
	Field pathStatus : String


	Method OnCreate()

		SetUpdateRate 60
		
		
		'create a new map
		myMap = GridMap.Create()
		myMap.InitMap()
		
		
		
	End Method
	




	Method OnUpdate()

		If MouseDown( MOUSE_LEFT )
			myMap.startX = MouseX()
			myMap.startY = MouseY()	
			If myMap.startX >= GridMap.MAP_SIZE * GridMap.MAP_RESOLUTION Then myMap.startX = ( GridMap.MAP_SIZE * GridMap.MAP_RESOLUTION ) - 1
			If myMap.startY >= GridMap.MAP_SIZE * GridMap.MAP_RESOLUTION Then myMap.startY = ( GridMap.MAP_SIZE * GridMap.MAP_RESOLUTION ) - 1
			If myMap.startX < 0 Then myMap.startX = 0
			If myMap.startY < 0 Then myMap.startY = 0
		 	myMap.ResetMarkedMap()
			Local result : Int = myMap.CheckPath()
			If result Then pathStatus = "True" Else pathStatus = "False"
		Endif
		
		
		'set end position and check path
		If MouseDown( MOUSE_RIGHT )
			myMap.endX = MouseX()
			myMap.endY = MouseY()
			If myMap.endX >= GridMap.MAP_SIZE * GridMap.MAP_RESOLUTION Then myMap.endX = ( GridMap.MAP_SIZE * GridMap.MAP_RESOLUTION ) - 1
			If myMap.endY >= GridMap.MAP_SIZE * GridMap.MAP_RESOLUTION Then myMap.endY = ( GridMap.MAP_SIZE * GridMap.MAP_RESOLUTION ) - 1
			If myMap.endX < 0 Then myMap.endX = 0
			If myMap.endY < 0 Then myMap.endY = 0
			myMap.ResetMarkedMap()
			Local result : Int = myMap.CheckPath()
			If result Then pathStatus = "True" Else pathStatus = "False"
		Endif
				

	End Method
	



	Method OnRender()
		Cls 232, 232, 232
		
		
		'draws map
		myMap.Draw()
		myMap.DrawStats()
		DrawText( "Free Path: " + pathStatus, GridMap.MAP_SIZE * GridMap.MAP_RESOLUTION + 16, 170 )
	
	
	End Method
	

End Class



Function Main()
	New MyApp()
End Function




Function Signum : Int( value : Float )
	If value < 0.0 Then Return -1
	Return 1
End Function