Moving along a path

BlitzMax Forums/BlitzMax Programming/Moving along a path

therevills

(Posted 2008) [#1]

Hi All,

Im trying to move a sprite along a path found using a pathfinder routine, but having troubles.

I cant get my sprite to move along the path correctly.

Here is the pathfinder code:

'''''''''''''''''''''''''
'A General A* Pathfinder'
'Coded by Curtastic 2007'
'Coded in Lightning IDE.'
'''''''''''''''''''''''''
'Strict

Type TPathfinder Abstract
	'1 if diaognal movement is allowed. Cutting corners is allowed.
	'0 otherwise.
	Global Diagonals:Int
	
	'The higher this number, the more the path will randomly differ from what is optimum.
	Global Randomity:Float
	
	'Use SetMap() to set these.
	Global MapWidth:Int
	Global MapHeight:Int
	'Map is a float. The closer to 1 the harder it is to move into this tile.
	'All values 1 or greater are considered walls.
	Global Map:Float[, ]
	
	'The amount of steps in the route. (Read only)
	Global Paths:Int
	
	'The resulting path is a 'resliced' route[].
	' as [x0, y0, x1, y1, x2, y2, x3, y3, ..etc. .. xn,yn]
	' The size of this array is paths*2.
	Global Route:Int[]
	
	'Private
	Global PathMap:TPath[, ]
	Const Root2:Float = 1.4142
	
	
	Function SetMap(Array:Float[, ], Width:Int, Height:Int)
		Map = Array
		MapWidth = Width
		MapHeight = Height
	EndFunction
	
	'Returns 1 if successful and 0 if unseccessful.
	'Fills the route[] array if successful.
	Function FindPath:Int(StartX:Int, StartY:Int, EndX:Int, EndY:Int)
		
		Assert Not(StartX < 0 Or StartY < 0 Or StartX >= MapWidth Or StartY >= MapHeight), ..
		 "Starting point out of bounds: " + StartX + "," + StartY
		Assert Not(EndX < 0 Or EndY < 0 Or EndX >= MapWidth Or EndY >= MapHeight), ..
		 "End point out of bounds: " + EndX + "," + EndY
		Assert Map <> Null, ..
		 "SetMap() must be called before FindPath"
		
		Paths = 0
		
		'already on target
		If StartX = EndX And StartY = EndY Then Return 1
		'target is a wall.
		If Map[EndX, EndY] >= 1 Then Return 0
		
		
		Local P:TPath
		Local P2:TPath
		Local NewP:TPath
		Local NewX:Int
		Local NewY:Int
		Local Dir:Int
		Local DirMax:Int
		Local Done:Int
		Local PHead:TPath
		Local MapHere:Float
		
		PathMap = New TPath[MapWidth, MapHeight]
		
		'make first path node at start
		P = New TPath
		PHead = P
		P.X = StartX
		P.Y = StartY
		PathMap[StartX, StartY] = P
		
		If Diagonals Then
			DirMax = 7
		Else
			DirMax = 3
		EndIf
		
		Repeat
			
 			
			
			For Dir = 0 To DirMax
				
				'move based on direction
				Select Dir
				Case 0; NewX = P.X + 1; NewY = P.Y
				Case 1; NewX = P.X    ; NewY = P.Y + 1
				Case 2; NewX = P.X - 1; NewY = P.Y
				Case 3; NewX = P.X    ; NewY = P.Y - 1
				Case 4; NewX = P.X + 1; NewY = P.Y + 1
				Case 5; NewX = P.X - 1; NewY = P.Y + 1
				Case 6; NewX = P.X - 1; NewY = P.Y - 1
				Case 7; NewX = P.X + 1; NewY = P.Y - 1
				EndSelect
				
				'check if it is ok to make a new path node here.
				If NewX >= 0 And NewY >= 0 And NewX < MapWidth And NewY < MapHeight Then
					MapHere = Map[NewX, NewY]
					If MapHere < 1 Then
						
						If Diagonals = 2 And Dir > 3 Then
							If Map[NewX, P.Y] >= 1 Then Continue
							If Map[P.X, NewY] >= 1 Then Continue
						EndIf
						
						P2 = PathMap[NewX, NewY]
						
						'check if there already is a path here
						If P2 = Null Then
							
							'DrawRect newx*29,newy*29,29,29
							'Flip
							'If KeyHit(key_escape) Then End
							
							'make new node
							NewP = New TPath
							PathMap[NewX, NewY] = NewP
							NewP.Parent = P
							NewP.X = NewX
							NewP.Y = NewY
							
							'cost is slightly more for diagnols
							If Dir < 4 Then
								NewP.Cost = P.Cost + .1 + MapHere + Rnd(0, Randomity)
							Else
								NewP.Cost = P.Cost + (.1 + MapHere + Rnd(0, Randomity)) * Root2
							EndIf
							
							'set distance from end
							If Diagonals Then
								NewP.Dist = ((NewX - EndX) * (NewX - EndX) + (NewY - EndY) * (NewY - EndY)) / 240.0
							Else
								NewP.Dist = (Abs(NewX - EndX) + Abs(NewY - EndY)) / 8.0
							EndIf
							
							'insert node at appropriate spot in list
							P2 = P
							Repeat
								If P2.After = Null Then
									P2.After = NewP
									Exit
								EndIf
								If P2.After.Dist + P2.After.Cost > NewP.Dist + NewP.Cost Then
									NewP.After = P2.After
									P2.After = NewP
									Exit
								EndIf
								P2 = P2.After
							Forever
							
							'check if found end
							If NewX = EndX And NewY = EndY Then
								Done = 1
								Exit
							EndIf
						Else
							'overwrite existing path node if this way costs less.
							If P2.Cost > P.Cost + .1 + MapHere * Root2 + Randomity Then
								P2.Parent = P
								'cost is slightly more for diagnols
								If Dir < 4 Then
									P2.Cost = P.Cost + .1 + MapHere + Rnd(0, Randomity)
								Else
									P2.Cost = P.Cost + (.1 + MapHere + Rnd(0, Randomity)) * Root2
								EndIf
							EndIf
						EndIf
					EndIf
				EndIf
			Next
			
			If Done = 1 Then Exit
			
			P = P.After
			If P = Null Then Exit
			
		Forever
		
		
		If Done Then
			'count how many paths
			P2 = NewP
			Repeat
				Paths:+ 1
				P2 = P2.Parent
				If P2 = Null Then Exit
				'If KeyDown(key_space) Then DebugStop

			Forever
			
			'make route from end to start
			Route = New Int[Paths * 2]
			Local i:Int = 0
			P2 = NewP
			Repeat
				Route[i] = P2.X
				i:+ 1
				Route[i] = P2.Y
				i:+ 1
				P2 = P2.Parent
				If P2 = Null Then Exit
			Forever
		EndIf
		
		'nullify pointers so mem will be deallocated.
		P = PHead
		Repeat
			P.Parent = Null
			P = P.After
			If P = Null Then Exit
		Forever
		
		Return Done
	EndFunction
EndType


'Private
Type TPath
	Field X:Int
	Field Y:Int
	Field Parent:TPath
	Field Cost:Float
	Field Dist:Float
	Field After:TPath
EndType

Ive tried this:

If x < TPathfinder.Route[currentPath] * TILE_SIZE + 5
x:+1
endif
if x > TPathfinder.Route[currentPath] * TILE_SIZE + 5
x:-1
endif
if x = TPathfinder.Route[currentPath] * TILE_SIZE + 5
currentPath:-1
endif

But it doesnt work right!

Does any have a good solution for this? I have seen a lot of examples how to create paths but not how to move along them.

therevills

(Posted 2008) [#2]

Dont worry, Ive worked out what I was doing wrong...

I was setting the starting currentPath incorrectly, it should be this:

sprite.currentpath = (TPathfinder.Paths - 1) * 2

and with the movement code:

if x = TPathfinder.Route[currentPath] * TILE_SIZE + 5
 currentPath:-2 ' as it store x and y
endif

therevills

(Posted 2008) [#3]

Here is a quick example for anyone with the same problem:

Strict
Import "pathfind.bmx"

Graphics 640, 480, 0

Const TILE_SIZE = 16
Const MAX_WIDTH = 40
Const MAX_HEIGHT = 30

Local Grid:Float[MAX_WIDTH, MAX_HEIGHT]


' make random map
For Local x = 0 To MAX_WIDTH -1
	For Local y = 0 To MAX_HEIGHT - 1
		If Rand(0,5) > 4 Grid[x, y] = 1
	Next
Next


TPathfinder.Diagonals = 1
TPathfinder.Randomity = 0
TPathfinder.SetMap(Grid, MAX_WIDTH, MAX_HEIGHT)

Local startx = 1, starty = 1
Local endx = 1, endy = 1


Type Tsprite
	Field x#,y#
	Field currentPath 
	Field speed
	
	Function Create:Tsprite(x,y)
		Local s:Tsprite = New Tsprite
		s.x = x
		s.y = y
		s.speed = 1
		Return s
	End Function

	Method update()
		If pathset = True
			If currentPath >= 0
				If x < TPathfinder.Route[currentPath] * TILE_SIZE
					x:+speed 
				End If
				If x > TPathfinder.Route[currentPath] * TILE_SIZE
					x:-speed 
				End If
	
				If y < TPathfinder.Route[currentPath + 1] * TILE_SIZE 
					y:+speed 
				End If
				If y > TPathfinder.Route[currentPath + 1] * TILE_SIZE 
					y:-speed 
				End If
			
						
				If x = TPathfinder.Route[currentPath] * TILE_SIZE ..
				And y = TPathfinder.Route[currentPath + 1] * TILE_SIZE
					currentPath:-2
				EndIf
			Else
				pathset = False
			EndIf
		EndIf
	End Method
	
	Method draw()
		SetColor 0,255,255
		DrawOval x,y,16,16
		SetColor 255,255,255
	End Method
End Type

Local sprite:Tsprite = Tsprite.Create(startx,starty)

Global pathset = False

MoveMouse 320, 240

SetBlend alphablend

Repeat
	Local mx = MouseX() / TILE_SIZE
	Local my = MouseY() / TILE_SIZE
	mx=Max(mx,0); mx=Min(mx,MAX_WIDTH - 1)
	my=Max(my,0); my=Min(my,MAX_HEIGHT - 1)

	If MouseDown(1) Then 		
		endx = mx
		endy = my
		pathset = True
		
		startx = sprite.x / TILE_SIZE
		starty = sprite.y / TILE_SIZE
		
		TPathfinder.FindPath(startx, starty, endx , endy )
		sprite.currentPath = (TPathfinder.Paths - 1) * 2
	EndIf	
	
	If KeyHit(KEY_SPACE)
		If TPathfinder.Diagonals = 1
			TPathfinder.Diagonals = 0
		Else 
			TPathfinder.Diagonals = 1
		EndIf
	End If

	
	sprite.update()
	
	'Draw grid tiles
	For Local fy = 0 To MAX_HEIGHT - 1
		For Local fx = 0 To MAX_WIDTH - 1
			If Grid[fx, fy] > 0 Then
				SetColor Grid[fx, fy] * 255, 0, 0
				DrawRect fx *TILE_SIZE, fy *TILE_SIZE, TILE_SIZE, TILE_SIZE
			EndIf
		Next
	Next
	SetAlpha 0.2
	'Draw grid lines
	SetColor 255, 255, 255
	For Local fx = 0 To MAX_WIDTH - 1
		DrawRect fx *TILE_SIZE, 0, 1, MAX_WIDTH  * TILE_SIZE
		DrawRect 0, fx * TILE_SIZE, MAX_WIDTH * TILE_SIZE, 1
	Next
	SetAlpha 1
	'Draw path
	SetColor 0, 255, 0
	For Local i = 0 To (TPathfinder.Paths - 1) * 2 Step 2
		DrawRect TPathfinder.Route[i] * TILE_SIZE + 5, TPathfinder.Route[i + 1] * TILE_SIZE + 5, 5, 5
	Next
	
	sprite.draw()
	
	Flip
	Cls
	If KeyHit(key_escape) Then End
Forever

Thanks to Curtastic for the great pathfinding code!

therevills

(Posted 2008) [#4]

And here is a prototype that I have been working on using the platformer game as a basis:

You can see that I have added ladders, and now you control "Gripe" by using the mouse, just click just above the floor and if "he" can get there he will... Ive made it if you want him to fall you need to click over edge.

http://therevillsjunk.googlepages.com/pathfinderPlatformer.zip

Does any know how to make the pathfinder calculate a path including the fall?