request for code: simple A*

BlitzMax Forums/BlitzMax Programming/request for code: simple A*

CS_TBL

(Posted 2007) [#1]

I'd like to request some A* methods/functions that:
1: don't come with 54 terabyte of comments between the code that make it unreadable, and for me, unusable. See, I don't want to know how the code works, I only want to know how the algo should be used.
2: are completely local, no globals, global arrays, wasted consts etc.
3: are clear about what the input and output formats are.
4: come *only* as one type with methods/functions, I don't want to see any examples that mess the whole thing up, also I don't want any external game-depended stuff in the core pathfinding algo. Only its own startX/Y and endX/Y fields. In fact, who's talking games anyway?

Actually what I'd like to see is a type that looks as follows:

Type TPathfinder

	Field status:Int ' 0: no possible path, 1:path found
	Field startX:Int, startY:Int, endX:Int, endY:Int

	Field diagonals:Int=1 ' true: use diagonal routes in pathfinding
	
	Field mapwidth:Int
	Field mapheight:Int
	
	Field map:TBank ' representing a 2d map where 0=walkable and 1=wall
	
	Field route:Int[]
	
	Method Setmapwidth(width:Int)
		' all kinda bounds checks here
		' ..
		' ..
		If mapwidth<1 RuntimeError "mapwidth<1"
		mapwidth=width
		Mapdimensions
	End Method
	
	Method Setstart(x:Int,y:Int)
		Assert x>=0 And x<mapwidth "start X out ot range"
		Assert y>=0 And y<mapheight "start Y out ot range"
		startx=x; starty=y
	End Method

	Method Setend(x:Int,y:Int)
		Assert x>=0 And x<mapwidth "end X out ot range"
		Assert y>=0 And y<mapheight "end Y out ot range"
		endx=x; endy=y
	End Method
	
	Method Mapdimensions()
		mapheight=BankSize(map)/mapwidth
		If mapheight<1 RuntimeError "mapheight<1"	
	End Method
	
	Method Setmap(bank:TBank=Null)
		Assert bank<>Null "bank=null"
		Assert BankSize(bank)>=1 "no dimension in bank"
		map=bank
		Mapdimensions
	End Method
	
	Method Findpath()
	
	
	' resulting path in a 'resliced' route[].
	' as [x0, y0, x1, y1, x2, y2, x3, y3, ..etc. .. xn,yn]
	'     ^ start                                   ^ end
	'
	End Method
	
	
End Type

' to use:
' make some bank
' make a pathfind instance
' add bank to instance
' set width and start/emd coords
' find path
' read out path from array
' yay \o/

If it's easy to adjust the A* code in the archives to this format then I'd be grateful to the one who does so. :-)

Curtastic

(Posted 2007) [#2]

I think the problem is that most A* here is blitzbasic code. I'll be happy to code one in blitzmax.
Why is the map a bank and not a 2d array though?

CS_TBL

(Posted 2007) [#3]

Well, dunno. Perhaps because a bank is a bank, and not an int? :P

If I add a bank to this type instance then map references to this bank, so I won't loose any more mem. Ints/bytes/floats etc. are copied to a new var instance afaik, so I figure the same counts for arrays of those basic vars.

If you do, please try to fill in those methods/functions in my framework.. ^_^ For I think that's a clean/open way to do all this.

Jesse

(Posted 2007) [#4]

http://www.blitzmax.com/Community/posts.php?topic=62388#697498

CS_TBL

(Posted 2007) [#5]

Too much noise in it.

It's what I meant with 'game depending', in that code there's this Tunit stuff everywhere. Unit? What unit? sprite:timage? What image? Speed? Who needs speed? Who says pathfinding is exclusively for games? Tnode, oh really.. so that costs yet another (global) type, and do I actually care, for only 2 int fields? Tilesize? What tiles? As far as I'm concerned, a tile is a visual property, not a functional property. Etc. etc., that whole thing is almost a game already, it's far from neutral and sterile.

The minimum required for pathfinding is a start location and an end location, and a 2d map with walkable/nonwalkable states. I suggest keeping these kind of solutions as minimal as possible, in order to be as flexible and modular as possible.

Dreamora

(Posted 2007) [#6]

Check the german blitzbasic forum. There is a working and very good A* ressource in the codearchive of the blitzmax categorie (there is one for regular blitz as well if you do not like the BM one)

CS_TBL

(Posted 2007) [#7]

Curtastic: so .. you're up to do it (in the way I proposed)? :P

Curtastic

(Posted 2007) [#8]

ya!!!111:):):):

I think I can do it this weekend

Curtastic

(Posted 2007) [#9]

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

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
			
 			If KeyDown(key_space) Then DebugStop
			
			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

Example of how to use:

'Click to make walls.
'Rightclick to change starting point.


Strict
Import "pathfinder.bmx"



Graphics 800, 600

Local Grid:Float[20, 20]

TPathfinder.Diagonals = 2
TPathfinder.Randomity = 0
TPathfinder.SetMap(Grid, 20, 20)

Const TS = 29

Local fx, fy
Local my, mx
Local startx = 1, starty = 1
Local i
Local z, g:Float

MoveMouse 111, 111

Repeat
	mx = MouseX() / TS
	my = MouseY() / TS
	mx=Max(mx,0); mx=Min(mx,19)
	my=Max(my,0); my=Min(my,19)

	If MouseDown(1) Then Grid[mx, my] = 1
	
	If MouseHit(2) Then
		startx = mx
		starty = my
	EndIf
	
	
	TPathfinder.FindPath(startx, starty, mx, my)
	
	'use mousewheel to change tile speeds
	g = Grid[mx, my] + (MouseZ() - z) / 10.0
	z = MouseZ()
	If g < 0 Then g = 0
	If g > 1 Then g = 1
	Grid[mx, my] = g
	
	
	'Draw grid tiles
	For fy = 0 To 19
		For fx = 0 To 19
			If Grid[fx, fy] > 0 Then
				SetColor Grid[fx, fy] * 255, 0, 0
				DrawRect fx * TS, fy * TS, TS, TS
			EndIf
		Next
	Next
	'Draw grid lines
	SetColor 255, 255, 255
	For fx = 0 To 20
		DrawRect fx * TS, 0, 1, 20 * TS
		DrawRect 0, fx * TS, 20 * TS, 1
	Next
	'Draw path
	SetColor 0, 255, 0
	For i = 0 To (TPathfinder.Paths - 1) * 2 Step 2
		DrawRect TPathfinder.Route[i] * TS + 5, TPathfinder.Route[i + 1] * TS + 5, 5, 5
	Next
	
	DrawText TPathfinder.Paths, 0, 0
	Flip
	Cls
	If KeyHit(key_escape) Then End
Forever

CS_TBL

(Posted 2007) [#10]

I want your babies!

Curtastic

(Posted 2007) [#11]

You're welcome, let me know if any improvements are needed, for the code archives or anything.

And my seed will conquer the world!

CS_TBL

(Posted 2007) [#12]

^_^
Why the 'abstract' btw?

Curtastic

(Posted 2007) [#13]

Well I don't see the need to make new instances, since all you need is the route. I could easily change it though.

Right now if you want to keep 2 separate paths you have to do:

local myroute[]
local blahroute[]

tpathfinder.findpath(x1,y1,x2,y2)
myroute=tpathfinder.route

tpathfinder.findpath(blahx,blahy,targetx,targety)
blahroute=tpathfinder.route

Curtastic

(Posted 2007) [#14]

Oops there was a big memory leak because of cyclic refrences, I just edited and fixed it.

TartanTangerine (was Indiepath)

(Posted 2007) [#15]

Here's some code I borrowed from somewhere and ported, I've restricted to 4 directions but it's easy to change back.

Strict

Rem
bbdoc: 4 Direction Restricted aStar Module
End Rem
Module Indiepath.indie_astar

ModuleInfo "Version: 1.0"
ModuleInfo "Author: Tim Fisher"
ModuleInfo "License: Public Domain"
ModuleInfo "Modserver: BRL"

Import brl.linkedlist
Import brl.basic

Const	NOTFINISHED		= 0
Const	NOTSTARTED		= 0
Const	FOUND			= 1
Const	NONEXISTENT		= 2
Const	WALKABLE		= 0
Const	UNWALKABLE		= 1


' ***********************************************************************

Type aStar

	Global aStarList:TList

	Field MapWidth		: Int
	Field MapHeight		: Int
	Field Walkability	: Int[0,0]
	Field OpenList		: Int[0]
	Field WhichList		: Int[0,0]
	Field OpenX			: Int[0]
	Field OpenY			: Int[0]
	Field ParentX		: Int[0,0]
	Field ParentY		: Int[0,0]
	Field fCost			: Int[0]
	Field gCost			: Int[0,0]
	Field hCost			: Int[0]
	Field onClosedList	: Int
	Field pathStatus	: Int
	Field pathLength	: Int
	Field pathLocation	: Int
	Field pathBank		: TBank
	Field TargetX		: Int
	Field TargetY		: Int
	
		Method New ()
            	If aStarList = Null Then aStarList = New TList
            	aStarList.AddLast Self
	   	End Method	

		'----------------------------------------------------------------
		
		Function KillAll()
				While (Not aStarList.IsEmpty())
					aStarList.RemoveLast()
				Wend
		End Function
			
		'----------------------------------------------------------------
		
		Function Destroy(g:aStar)
				g.pathBank = Null
		     	aStarList.Remove g
				g = Null
        End Function
	
		'----------------------------------------------------------------
		
		Function Intitialise:aStar(width:Int,Height:Int)
			Local a:aStar = New aStar
			a.pathBank = CreateBank(0)
			a.MapWidth 		= width
			a.MapHeight 	= Height
			a.OpenList 		= New Int[a.MapWidth * a.MapHeight + 2]
			a.OpenX			= New Int[a.MapWidth * a.MapHeight + 2]
			a.OpenY			= New Int[a.MapWidth * a.MapHeight + 2]
			a.fCost			= New Int[a.MapWidth * a.MapHeight + 2]
			a.hCost			= New Int[a.MapWidth * a.MapHeight + 2]
			a.Walkability 	= New Int[a.MapWidth + 1 , a.MapHeight + 1]
			a.WhichList		= New Int[a.MapWidth + 1 , a.MapHeight + 1]
			a.ParentX		= New Int[a.MapWidth + 1 , a.MapHeight + 1]
			a.ParentY		= New Int[a.MapWidth + 1 , a.MapHeight + 1]
			a.gCost			= New Int[a.MapWidth + 1 , a.MapHeight + 1]
			Return a
		End Function
	
		'----------------------------------------------------------------
		
		Method FindPath(StartX:Int,StartY:Int,TargetX:Int,TargetY:Int) ' grid based co-ords
				
				Local NumberofOpenListItems:Int
				Local NewOpenListItemID:Int
				Local ParentXval:Int
				Local ParentYval:Int
				Local v:Int, u:Int, temp:Int, a:Int, b:Int, m:Int, x:Int, TempX:Int
				Local Direction:Int
				Local OnOpenList:Int
				Local TempGcost:Int
				Local Path:Int, PathX:Int, PathY:Int
				Local CellPosition:Int
				Local dx1#,dy1#,dx2#,dy2#,cross#,heuristic#
				
				
				self.TargetX = TargetX
				self.TargetY = TargetY
				If StartX = TargetX And StartY = TargetY And self.pathLocation > 0 Then Return FOUND
				If StartX = TargetX And StartY = TargetY And self.pathLocation = 0 Then Return NONEXISTENT
				If self.Walkability[self.TargetX,self.TargetY] = UNWALKABLE Then	Return NONEXISTENT

				If self.onClosedList > 1000000
					self.Whichlist = New Int[self.MapWidth,self.MapHeight]
					self.onClosedList = 10
				EndIf
				self.onClosedList:+2
				onOpenList = self.onClosedList - 1
				self.pathLength 	 = NOTSTARTED
				self.pathLocation 	 = NOTSTARTED
				self.gCost[StartX,StartY] = 0
				NumberofOpenListItems = 1
				self.OpenList[1] = 1
				self.OpenX[1] = StartX
				self.OpenY[1] = StartY
				
				Repeat			' Find Route Loop
				
					If NumberofOpenListItems <> 0 Then
						ParentXval = self.OpenX[self.OpenList[1]]
						ParentYval = self.OpenY[self.OpenList[1]]
						self.WhichList[ParentXval,ParentYval] = self.onClosedList
						self.OpenList[1] = self.OpenList[NumberofOpenListItems]
						NumberOfOpenListItems:-1
						v = 1				
						Repeat
							u = v
							If 2 * U + 1 <= NumberofOpenListItems
								If self.fCost[self.OpenList[u]] >= self.fCost[self.OpenList[2 * u]] Then v = 2 * u
								If self.fCost[self.OpenList[v]] >= self.fCost[self.OpenList[2 * u + 1]] Then v = 2 * u + 1
							Else
								If 2 * u <= NumberofOpenListItems
									If self.fCost[self.openList[u]] >= self.fCost[self.OpenList[2 * u]] Then v = 2 * u
								EndIf
							EndIf
							If u <> v Then
								temp = self.OpenList[u]
								self.OpenList[u] = self.OpenList[v]
								self.OpenList[v] = temp
							Else
								Exit
							EndIf
						Forever
						
						For Direction = 1 To 4
							Select Direction
								Case 3
									a = ParentXval
									b = ParentYval - 1
								Case 4
									a = ParentXval - 1
									b = ParentYval
								Case 1
									a = ParentXval + 1
									b = ParentYval
								Case 2
									a = ParentXval
									b = ParentYval + 1
							End Select
							If a <> - 1 And b <> -1 And a <> Self.MapWidth And b <> Self.MapHeight
								If self.WhichList[a,b] <> self.OnClosedList
									If Self.Walkability[a,b] <> UNWALKABLE
										If self.WhichList[a,b] <> onOpenList
											NewOpenListItemID:+1
											m = NumberofOpenListItems + 1
											self.OpenList[m] = NewOpenListItemID
											self.OpenX[newOpenListItemID] = a
											self.OpenY[newOpenListItemID] = b
											self.gCost[a,b] = self.gCost[ParentXval,ParentYval] + 10
											
											self.hCost[self.OpenList[m]] = 10 * (Abs(a - self.TargetX) + Abs(b - Self.TargetY))
											
										'	dx1 = a - self.TargetX
										'	dy1 = b - self.TargetY
										'	dx2 = startX - self.TargetX
										'	dy2 = startY - self.TargetY
										'	cross = Abs(dx1*dy2 - dx2*dy1)
										'	heuristic :+ cross*0.001
										'	self.hCost[self.OpenList[m]] = 0'heuristic
											
											
											self.fCost[self.OpenList[m]] = self.gCost[a,b] + self.hCost[self.OpenList[m]]
											self.ParentX[a,b] = ParentXval
											self.ParentY[a,b] = ParentYval
											While m <> 1
												If self.fCost[self.OpenList[m]] <= self.fCost[self.OpenList[m/2]] Then
													temp = self.OpenList[m/2]
													self.OpenList[m/2] = self.OpenList[m]
													self.OpenList[m] = temp
													m:/2
												Else
													Exit
												EndIf
											Wend
											NumberOfOpenListItems:+1
											self.WhichList[a,b] = onOpenList
										Else
											tempGcost = self.gCost[ParentXval,ParentYval]+10
											If tempGcost < self.gCost[a,b] Then
												self.ParentX[a,b] = ParentXval
												self.ParentY[a,b] = ParentYval
												self.gCost[a,b] = tempGCost
												For x = 1 To NumberofOpenListItems
													If self.OpenX[self.OpenList[x]] = a And self.OpenY[self.OpenList[x]] = b Then
														self.fCost[self.OpenList[x]] = self.gCost[a,b] + self.hCost[self.OpenList[x]]
														m = x
														While m <> 1
															If self.fCost[self.OpenList[m]] < self.fCost[self.openList[m/2]]
																Temp = self.OpenList[m/2]
																self.OpenList[m/2] = self.OpenList[m]
																self.OpenList[m] = temp
																m:/2
															Else
																Exit
															EndIf
														Wend
														Exit
													EndIf
												Next
											EndIf
										EndIf
									EndIf
								EndIf
							EndIf
						Next
					Else
						path = NONEXISTENT
						Exit
					EndIf
					
					If self.WhichList[self.TargetX,self.TargetY] = onOpenList Then
						Path = FOUND
						Exit
					EndIf					
				Forever
														
				If Path = FOUND
					PathX = Self.TargetX
					PathY = Self.TargetY
					Repeat
						tempx = self.ParentX[pathx,pathy]
						PathY = self.ParentY[pathx,pathy]
						PathX = tempX								
						self.PathLength:+1
					Until PathX = StartX And PathY = StartY
					
					ResizeBank(Self.PathBank,(self.pathLength+1) * 4)
									
					PathX = self.TargetX
					PathY = self.TargetY
					cellPosition = self.Pathlength * 4
					While Not (pathX = StartX And pathY = StartY)
						PokeShort (self.pathBank,cellPosition,PathX)
						PokeShort (self.pathBank,cellPosition+2,PathY)
						cellPosition:-4
						tempx = self.ParentX[pathX,pathY]
						pathY = self.ParentY[pathX,pathY]
						pathX = Tempx
					Wend
					PokeShort (self.pathBank,0,StartX)
					PokeShort (self.pathBank,2,StartY)
				EndIf
				Return Path
		End Method
		
		'----------------------------------------------------------------
		
		Method ReadPathX(PathLocation:Int)
			Return PeekShort(self.pathBank,PathLocation * 4)
		End Method
		
		'----------------------------------------------------------------
		
		Method ReadPathY(PathLocation:Int)
			Return PeekShort(self.pathBank,PathLocation * 4 + 2)
		End Method
		
			
End Type

Diordna

(Posted 2007) [#16]

Awesome Curtastic, thanks! Couple of things:
-You misspelled "diagonal."
-If I put a value >1 into the map, will it count it as being twice as slow to walk over? If not, what part of the code should I change to make it do this? This is essential for games with varying terrian. (I think it also means that Map[] should be changed to something with decimals, not an int, so I can say, for example, 1.5.)

Curtastic

(Posted 2007) [#17]

-You misspelled "diagonal."

wow. How can I even be smart enough to code this? lol.
I seriously didnt know how to spell that. fixed.

-If I put a value >1 into the map, will it count it as being twice as slow to walk over? If not, what part of the code should I change to make it do this? This is essential for games with varying terrian. (I think it also means that Map[] should be changed to something with decimals, not an int, so I can say, for example, 1.5.)

I could add support for that. Theoretically all you have to do is something like this:

'cost is slightly more for diagnols
If Dir < 4 Then
	NewP.Cost = P.Cost + CostOfTile
Else
	NewP.Cost = P.Cost + CostOfTile*Root2
EndIf

CS_TBL

(Posted 2007) [#18]

I think it needs something like being able to walk in diagonals while not cutting corners when there's a non-walkable thing to cross. Another option for the diagonals field perhaps?
0 no diagonals
1 diagonals + cutting
2 diagonals, no cutting

I keep seeing Warcraft in front of me where figures are walking in all 8 directions but aren't cutting corners at buildings/trees etc.

CS_TBL

(Posted 2007) [#19]

Actually I think we should expand this pathfinder with all kinda extra functionality, without loosing its neutrality of course.

Apart from the walk/wall and the said ramping there could also be floors (used in cobination with ramping), meaning that from floor a you can't directly move to floor b, only via a ramp.

Also, there could be walkable tiles with priorities, high priority is to choose over low priority.

What about legal random errors in a path to simulate human errors? (otherwise you get straight marching of units). These errors could be simulated by analyzing the found path: for each step in the route check the surrounding tiles, if they are walkable then the route could add this to the route.

What about another route[] to store enviromental properties for each step? Like how many rings of directly walkable tiles are around the position of the step?

etc. all these things keep the thing neutral but could greatly enhance the functionality!

Damien Sturdy

(Posted 2007) [#20]

Wow, nice bit of code! :)

Curtastic

(Posted 2007) [#21]

Ya I'll add that. I just didn't know if anyone wanted it.

I keep seeing Warcraft in front of me where figures are walking in all 8 directions but aren't cutting corners at buildings/trees etc.

Actually in warcraft (and most games I've seen) you can cut corners. Notice the footman is cutting a corner between farms. Most games have corners rounded, so there is room to cut inbetween.

What about legal random errors in a path to simulate human errors? (otherwise you get straight marching of units). These errors could be simulated by analyzing the found path: for each step in the route check the surrounding tiles, if they are walkable then the route could add this to the route.

Done!

What about another route[] to store enviromental properties for each step? Like how many rings of directly walkable tiles are around the position of the step?

Well once the route is found you can always do that, it shouldn't be be the pathfinder's job.

Now lets say the object is larger than one tile, the pathfinder will need to find a path that the large object can fit through. That's something that I can add.

Also, there could be walkable tiles with priorities, high priority is to choose over low priority.

Ya I'll do that except the tiles will store how long it takes to move into it. So a high number is slower and 0 is the fastest. [edit: done]

Wow, nice bit of code! :)

thanks!

CS_TBL

(Posted 2007) [#22]

^_^ babies, more babies! ^_^

But one baby needs a new diper: try to move along the edges of the map with this randomness (place a wall next to it orso) and you'll get an assert exception (coords out of bounds).

[edit] hm.. or maybe not.. oO

CS_TBL

(Posted 2007) [#23]

the example could use this, under the:

mx = MouseX() / TS
my = MouseY() / TS

	mx=Max(mx,0); mx=Min(mx,19)
	my=Max(my,0); my=Min(my,19)

Curtastic

(Posted 2007) [#24]

ok, I added the no cuting corners option. Any more ideas?

GW	(Posted 2007) [#25]

nice!
perhaps the option to specify a variable width for moving agents as an argument, So the pathfinder could exclude paths that are to narrow for anything with a width greater than 1 cell. For example, a width=3 would represent a unit that occupies a 3x3 area.

CS_TBL

(Posted 2007) [#26]

well, those floors I mentioned perhaps, with ramps 'n stuff (like in Starcraft). Tho I wouldn't know how to include that in one single 2d array.