pathfinding help

Blitz3D Forums/Blitz3D Beginners Area/pathfinding help

chwaga

(Posted 2008) [#1]

Hi, i'm back, with an even more naive question than ever before!

I've tackled A* already, and failed miserably ( see below ).

Graphics3D 1280, 1024, 32, 2

Const gridscale = 1
Global goalx, goaly, startx, starty
Global currentx, currenty

Global lf = 10000000000

startx = 300
starty = 300
currentx = startx
currenty = starty
goalx = 800
goaly = 600


Type goodnode
	Field x
	Field y
	Field open = False 

End Type

Type badnode
	Field x
	Field y
End Type

Type potentialnode
	Field x
	Field y
	Field g
	Field h
	Field lf
End Type

Type hlnode
	Field x
	Field y
End Type


setupgrid()


While Not KeyHit(1)

	Cls()
	RenderWorld()
	drawgrid()
	

	
	If KeyDown(29) Then
		Stop 
	EndIf
	
	If KeyHit(57) Then updatepath()
	Flip()

Wend


End

Function setupgrid()
	For w = 0 To GraphicsWidth()-(gridscale*100) Step gridscale*100
		For h = 0 To GraphicsHeight()-(gridscale*100) Step gridscale*100
			node.goodnode = New goodnode
			node\x = w
			node\y = h 
		Next
	Next
End Function

Function drawgrid()
	Color 0, 0, 200
	For node.goodnode = Each goodnode
		Rect node\x, node\y, gridscale*100, gridscale*100, 0
	Next
	Color 0, 200, 0
	For hnode.hlnode = Each hlnode
		Rect hnode\x, hnode\y, gridscale*100, gridscale*100, 0
	Next
	Color 255, 255, 255
End Function 

;g = 10 if vertical or horizontal
;g = 14 if diagonal

;h = 10*(abs(currentx - goalx) + abs(currenty - goaly))


Function updatepath()
	Repeat
	Cls
	RenderWorld()
	 
		If KeyHit(29) Then Stop 
		Text 0, 0, currentx + ", " + currenty

		;find the surrounding 8 nodes and replace them with potentialnodes (closing the normal ones)
		For node.goodnode = Each goodnode
			If ((node\x = currentx - (gridscale*100)) And (node\y = currenty)) Or ((node\x = currentx) + (gridscale*100) And (node\y = currenty)) Or ((node\y = currenty - (gridscale*100)) And (node\x = currentx)) Or ((node\y = currenty + (gridscale*100)) And (node\x = currentx)) Then 
				pnode.potentialnode = New potentialnode
				pnode\x = node\x
				pnode\y = node\y
				pnode\g = 10
				node\open = False  
			EndIf
			If ((node\x = currentx + (gridscale*100)) And (node\y = currenty + (gridscale*100))) Or ((node\x = currentx + (gridscale*100)) And (node\y = currenty - (gridscale*100))) Or ((node\x = currentx - (gridscale*100)) And (node\y = currenty + (gridscale*100))) Or ((node\x = currentx - (gridscale*100)) And (node\y = currenty - (gridscale*100))) Then 
				pnode.potentialnode = New potentialnode
				pnode\x = node\x
				pnode\y = node\y
				pnode\g = 14
				node\open = False
			EndIf	
		Next
		;determine h, f (g was found above), and lf(lowest f)
		For pnode.potentialnode = Each potentialnode
			pnode\h = 10 * (Abs(currentx - goalx) + Abs(currenty - goaly))
			If pnode\h + pnode\g < lf Then 
				lf = pnode\h + pnode\g
				pnode\lf = True
			EndIf
			n = n + 1
		Next
		Text 0, 20, n
		n=0
		;delete all potentialnodes, open up the closed nodes, and set currentx and y to the location of the lowest f
		For node.goodnode = Each goodnode
			If ((node\x = currentx - (gridscale*100)) And (node\y = currenty)) Or ((node\x = currentx) + (gridscale*100) And (node\y = currenty)) Or ((node\y = currenty - (gridscale*100)) And (node\x = currentx)) Or ((node\y = currenty + (gridscale*100)) And (node\x = currentx)) Then node\open = True 
		Next 
		For pnode.potentialnode = Each potentialnode
			
			If pnode\lf = True Then
				currentx = pnode\x
				currenty = pnode\y
				lf = 10000000
				hnode.hlnode = New hlnode
				hnode\x = pnode\x
				hnode\y = pnode\y
			EndIf
			Delete pnode
			
		Next
		 
		
	Until currentx = goalx And currenty = goaly Or KeyHit(1)
End Function

I was wondering if there's any file somewhere with a simple plug-in-and-use pathfinding system. It doesn't need to be extremely fast, just usable. I want to be able to set up a grid of given dimensions, and send an object from point A to point B, A* style. It seems that all the easy ones are 3D node-based and are way too slow for an interpolated grid. A simple 2D that i could translate into 3D (relative to the terrain, or whatever) would do nicely. That or tell me what's wrong with the above code.

thanks!! (i send a thank-you-cookie-program to whoever solves either of my problems)

Ross C

(Posted 2008) [#2]

You really are best learning it yourself :o) When you get it ( i swear it just CLICKS on day), you'll see it's not that hard at all. I can't be of more help though, sorry ^_^

chwaga

(Posted 2008) [#3]

well, i took another shot at coding it, but I'm getting killed (on step 1 here on a MAV for doing this:

for node.nodes = each nodes
     for node.nodes = each nodes

     next
next

anybody wanna fix this for me? I'm kinda perplexed how to work around the above thing. code down below!

Graphics 800, 600, 32, 2

Global StartX = 0
Global StartY = 0
Global EndX = 15
Global EndY = 11

;Self explanatory
Type nodes

	Field x
	Field y
	Field open = False
	Field closed = False
	Field parentx
	Field parenty
	Field StartNode = False
	Field EndNode = False 

End Type

CreateGrid(15, 11)
FindPath()
Repeat

	DrawNodes()
	Flip()

Until KeyHit(1)

End


Function CreateGrid(w, h)
	
	;Create the nodes, position them according to the grid, and determine if they're Start or End nodes
	For n = 0 To w
		For m = 0 To h
			node.nodes = New nodes
			node\x = n
			node\y = m
			If node\x = StartX And node\y = StartY Then node\StartNode = True
			If node\x = EndX And node\y = EndY Then node\EndNode = True
		Next
	Next

End Function


Function DrawNodes()
	
	;Check for what type of node it is, and draw it accordingly
	For node.nodes = Each nodes
		If node\StartNode = False And node\EndNode = False Then 
			Color 0, 0, 255
			Rect node\x * 50, node\y * 50, 50, 50, 0
		EndIf
		If node\open = True Then 
			Color 0, 255, 0
			Rect node\x * 50, node\y * 50, 50, 50, 0
		EndIf
		If node\closed = True Then 
			Color 255, 0, 0
			Rect node\x * 50, node\y * 50, 50, 50, 0
		EndIf
		If node\StartNode = True Then
			Color 0, 255, 0
			Rect node\x * 50, node\y * 50, 50, 50, 1
		EndIf
		If node\EndNode = True Then
			Color 255, 0, 0
			Rect node\x * 50, node\y * 50, 50, 50, 1
		EndIf
	Next

End Function


Function FindPath()

	;Find the starting node
	For node.nodes = Each nodes
		If node\StartNode = True Then 
			;Open up the starting node
			node\open = False
			;Find the adjacent 8 nodes
			For node.nodes = Each nodes
				If node\x = StartX + 1 Or node\x = StartX Or node\x = StartX-1 Then
					If node\y = StartY + 1 Or node\y = StartY Or node\y = StartY - 1 And (node\x <> StartX And node\y <> StartY) Then 
						;Open the adjacent nodes up and parent them to the starting node
						node\open = True
						node\parentx = StartX
						node\parenty = StartY
					EndIf
				EndIf
			Next
			;close the starting node
			node\open = False
			node\closed = True 
		EndIf
	Next

End Function

And Ross, I totally understand the logic of A*, just I keep screwing up on the code for it. I drew out a grid and A-starred my way from point A to point B around obstacles to prove to myself I knew it. I tend to have trouble translating logic into code when it's complex and random MAV-involving...

Naughty Alien

(Posted 2008) [#4]

..have you try to setup network of nodes where each connected node is a child or parent of previous one? On that way you can simply get closest path/node to the desired location by just checking parented nodes ..thats what I did, and its really simple to use and working just fine for me..

Ross C

(Posted 2008) [#5]

for node.nodes = each nodes
     for node.nodes = each nodes

     next
next

I'm certain that will fail. You have the same varaible assigned to both loops.

for node1.nodes = each nodes
     for node2.nodes = each nodes

     next
next

That should work.

andy_mc

(Posted 2008) [#6]

is a node just a predefined set of coords on a map? i.e with pacman it would be all square, but with 3d maps like quake maps, would it just be the corners of rooms and doorways?

chwaga

(Posted 2008) [#7]

I'll try that naughty alien, thanks (andy_mc, each node is a coordinate on a grid, I hope to just use 2D graphics and translate it into 3D using a heightmap or whatever I do)

chwaga

(Posted 2008) [#8]

why do I get an error saying "Variable must be a type" on these lines:

If NodeID(n * m)\x = StartX And node\y = StartY Then NodeID(n * m)\StartNode = True
			If NodeID(n * m)\x = EndX And node\y = EndY Then NodeID(n * m)\EndNode = True

in this code:

Graphics 800, 600, 32, 2

Global StartX = 0
Global StartY = 0
Global EndX = 15
Global EndY = 11



;Self explanatory
Type nodes

	Field x
	Field y
	Field open = False
	Field closed = False
	Field ID$
	Field parentID$
	Field parentx
	Field parenty
	Field StartNode = False
	Field EndNode = False 

End Type

Type links

	Field node1
	Field node2

End Type

Dim ClosedList(15 * 11)
Dim OpenList(15 * 11)
Dim NodeID.nodes(15 * 11)
CreateGrid(15, 11)

;FindPath()
Repeat

	DrawNodes()
	Flip()

Until KeyHit(1)

End


Function CreateGrid(w, h)
	
	;Create the nodes, position them according to the grid, and determine if they're Start or End nodes
	For n = 0 To w
		For m = 0 To h
		
			NodeID(n * m) = New nodes
			NodeID(n * m)\x = n
			NodeID(n * m)\y = m
			If NodeID(n * m)\x = StartX And node\y = StartY Then NodeID(n * m)\StartNode = True
			If NodeID(n * m)\x = EndX And node\y = EndY Then NodeID(n * m)\EndNode = True
			
			
		Next
	Next
	
End Function


Function DrawNodes()
	
	;Check for what type of node it is, and draw it accordingly
	For node.nodes = Each nodes
		If node\StartNode = False And node\EndNode = False Then 
			Color 0, 0, 255
			Rect node\x * 50, node\y * 50, 50, 50, 0
		EndIf
		If node\open = True Then 
			Color 0, 255, 0
			Rect node\x * 50, node\y * 50, 50, 50, 0
		EndIf
		If node\closed = True Then 
			Color 255, 0, 0
			Rect node\x * 50, node\y * 50, 50, 50, 0
		EndIf
		If node\StartNode = True Then
			Color 0, 255, 0
			Rect node\x * 50, node\y * 50, 50, 50, 1
		EndIf
		If node\EndNode = True Then
			Color 255, 0, 0
			Rect node\x * 50, node\y * 50, 50, 50, 1
		EndIf
	Next

End Function


Function FindPath()

	;Find the starting node
	For node.nodes = Each nodes
		If node\StartNode = True Then 
			;Open up the starting node
			node\open = False
			;Find the adjacent 8 nodes
			For node.nodes = Each nodes
				If node\x = StartX + 1 Or node\x = StartX Or node\x = StartX-1 Then
					If node\y = StartY + 1 Or node\y = StartY Or node\y = StartY - 1 And (node\x <> StartX And node\y <> StartY) Then 
						;Open the adjacent nodes up and parent them to the starting node
						node\open = True
						node\parentx = StartX
						node\parenty = StartY
					EndIf
				EndIf
			Next
			;close the starting node
			node\open = False
			node\closed = True 
		EndIf
	Next

End Function

chwaga

(Posted 2008) [#9]

really guys, something like this for b3d would be FREAKING AWESOME. If you have one, find one, make one, get it to me :D

I'm about to explode, I can't reverse engineer anybody else's, I can't code my own because stupid syntax errors keep getting me and it takes about a day to figure out why for EACH, and all the good ones that are SIMPLY TOO PERFECT for my purposes are bmax!!!

GAH!!!!!!!!!!!
(I think I need to go play some TF2 to blow off some steam by blowing off some heads...)

....FYI: I've been at this for two hours straight today and gotten absolutely nowhere, I have the right, no, the DUTY to be ticked off :)

stayne

(Posted 2008) [#10]

Hope this is what you're after. I'm sure it'll make sense to ya.

If NodeID(n * m)\x = StartX And NodeID(n * m)\y = StartY Then NodeID(n * m)\StartNode = True
If NodeID(n * m)\x = EndX And NodeID(n * m)\y = EndY Then NodeID(n * m)\EndNode = True

chwaga

(Posted 2008) [#11]

dang, typo, I feel like an idiot now :(

chwaga

(Posted 2008) [#12]

ok, bram translated this for me to b3d, and it works kinda fine. Except it's SLOW. Up to 50m/s per loop on a 256 x 192 grid. Check this out:

pathinc.bb:

Const FLAG1% = $01
Const FLAG2% = $02
Const FLAG4% = $04
Const FLAG8% = $08
Const FLAG16% = $10
Const FLAG32% = $20
Const FLAG64% = $40
Const FLAG128% = $80

Function CheckFlag%(flags%, flag%)
	If flags And flag Then Return True Else Return False
End Function

Const PATH_TOP% = FLAG1
Const PATH_BOTTOM% = FLAG2
Const PATH_LEFT% = FLAG4
Const PATH_RIGHT% = FLAG8
Const PATH_CEIL% = FLAG16
Const PATH_FLOOR% = FLAG32
Const PATH_ALL% = FLAG64

; Pathmap Type
Type TPathmap
	Field width, height, depth
	Field map
End Type

Type TPath
	Field x, y, z
	Field path$
End Type

; Create a New pathmap
Function CreatePathmap.TPathmap(width, height, depth = 1)
	 this.TPathmap = New TPathmap
		this\width = width
		this\height = height
		this\depth = depth
		
		this\map = CreateBank(this\width * this\height * this\depth)
		
	Return this
End Function

; Insert flags To pathmap slot
Function PathmapSlot(this.TPathmap, flags%, x, y, z = 0)
	 offset = (z * this\width * this\height) + (y * this\width) + x
	PokeByte(this\map, offset, flags)
End Function

; Search For a path within pathmap; 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down
Function FindPath$(this.TPathmap, x1, y1, z1, x2, y2, z2)
	 Local offset, offset_top, offset_bottom, offset_left, offset_right, offset_ceil, offset_floor
	
	 Local temp_bank = CreateBank(BankSize(this\map))
	CopyBank(this\map, 0, temp_bank, 0, BankSize(this\map))
	
	Delete Each TPath
	 that.TPath = New TPath
		that\x = x1
		that\y = y1
		that\z = z1
		that\path = ""
		Insert that Before First TPath
		Insert that Before First TPath
	
	For that.TPath = Each TPath
		offset = (that\z * this\width * this\height) + (that\y * this\width) + that\x
		
		; TOP
		If that\y > 0
			offset_top = (that\z * this\width * this\height) + ((that\y - 1) * this\width) + that\x
			If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_TOP)) And (Not CheckFlag(PeekByte(temp_bank, offset_top), PATH_BOTTOM)) And (Not CheckFlag(PeekByte(temp_bank, offset_top), PATH_ALL))
				 pth.TPath = New TPath
					pth\x = that\x
					pth\y = that\y - 1
					pth\z = that\z
					pth\path = that\path + "1"
					Insert pth After Last TPath
					PokeByte(temp_bank, offset_top, PATH_ALL)
			EndIf
		EndIf
		; Left
		If that\x > 0
			offset_left = (that\z * this\width * this\height) + (that\y * this\width) + that\x - 1
			If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_LEFT)) And (Not CheckFlag(PeekByte(temp_bank, offset_left), PATH_RIGHT)) And (Not CheckFlag(PeekByte(temp_bank, offset_left), PATH_ALL))
				pth.TPath = New TPath
					pth\x = that\x - 1
					pth\y = that\y
					pth\z = that\z
					pth\path = that\path + "3"
					Insert pth After Last TPath
					PokeByte(temp_bank, offset_left, PATH_ALL)
			EndIf
		EndIf
		; BOTTOM
		If that\y + 1 < this\height
			offset_bottom = (that\z * this\width * this\height) + ((that\y + 1) * this\width) + that\x
			If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_BOTTOM)) And ((Not CheckFlag(PeekByte(temp_bank, offset_bottom), PATH_TOP)) And (Not CheckFlag(PeekByte(temp_bank, offset_bottom), PATH_ALL)))
				 pth.TPath = New TPath
					pth\x = that\x
					pth\y = that\y + 1
					pth\z = that\z
					pth\path = that\path + "2"
					Insert pth After Last TPath
					PokeByte(temp_bank, offset_bottom, PATH_ALL)
			EndIf
		EndIf
		; Right
		If that\x + 1 < this\width
			offset_right = (that\z * this\width * this\height) + (that\y * this\width) + that\x + 1
			If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_RIGHT)) And (Not CheckFlag(PeekByte(temp_bank, offset_right), PATH_LEFT)) And (Not CheckFlag(PeekByte(temp_bank, offset_right), PATH_ALL))
				 pth.TPath = New TPath
					pth\x = that\x + 1
					pth\y = that\y
					pth\z = that\z
					pth\path = that\path + "4"
					Insert pth After Last TPath
					PokeByte(temp_bank, offset_right, PATH_ALL)
			EndIf
		EndIf
		
		; If the pathmap has 3 dimensions
		If this\depth > 1
			If that\z > 0
				offset_ceil = ((that\z - 1) * this\width * this\height) + (that\y * this\width) + that\x
				If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_CEIL)) And (Not CheckFlag(PeekByte(temp_bank, offset_ceil), PATH_FLOOR)) And (Not CheckFlag(PeekByte(temp_bank, offset_ceil), PATH_ALL))
					 pth.TPath = New TPath
						pth\x = that\x
						pth\y = that\y - 1
						pth\z = that\z
						pth\path = that\path + "5"
						Insert pth After Last TPath
						PokeByte(temp_bank, offset_ceil, PATH_ALL)
				EndIf
			EndIf
			If that\z + 1< this\depth
				offset_floor = ((that\z + 1) * this\width * this\height) + (that\y * this\width) + that\x
				If Not CheckFlag(PeekByte(temp_bank, offset), PATH_FLOOR) And (Not CheckFlag(PeekByte(temp_bank, offset_floor), PATH_CEIL)) And (Not CheckFlag(PeekByte(temp_bank, offset_floor), PATH_ALL))
					 pth.TPath = New TPath
						pth\x = that\x
						pth\y = that\y + 1
						pth\z = that\z
						pth\path = that\path + "6"
						Insert pth After Last TPath
						PokeByte(temp_bank, offset_floor, PATH_ALL)
				EndIf
			EndIf
		EndIf
		
		; CORRECT PATH FOUND
		If that\x = x2 And that\y = y2 And that\z = z2
			 path$ = that\path
			Delete Each TPath
			FreeBank temp_bank
			Return path
		EndIf
		
		; Return False If there is no solution
		If First TPath = Null Then
			FreeBank temp_bank
			Return "[ERROR]"
		EndIf
				
		; Remove the parent
		Delete that
	Next
	Return "FAILED"
End Function

; Remove pathmap from memory
Function FreePathmap(this.TPathmap)
	FreeBank this\map
End Function

test.bb:

Include "pathinc.bb"

Graphics 1024, 768, 32, 1
SetBuffer BackBuffer()

Global map_width = 256
Global map_height = 192

Type Dudes

	Field x
	Field y

End Type


; Create level
Dim map(map_width, map_height)
For y = 0 To map_height -1
	For x = 0 To map_width - 1
		If Rand(0, 5) < 1 Then map(x, y) = PATH_ALL
	Next
Next

; Create pathmap
Global pathmap.TPathmap = CreatePathmap(map_width, map_height)
Global path$ = ""

; Copy level To pathmap
For y = 0 To map_height -1
	For x = 0 To map_width - 1
		PathmapSlot(pathmap, map(x, y), x, y)
	Next
Next

;make FOUR dudes (dun dun dun!!)

For n = 1 To 20
	Dude.Dudes = New Dudes
	Dude\x = Rnd(1, map_width)
	Dude\y = Rnd(1, map_height)
Next

While Not KeyHit(1)
	Cls()
	
	; Draw level
	For  y = 0 To map_height -1
		For  x = 0 To map_width - 1
			If CheckFlag(map(x, y), PATH_ALL)
				Color(255, 0, 0)
			Else
				Color(255, 255, 255)
			EndIf
			Rect x * 4, y * 4, 4, 4
		Next
	Next
	
	Color 0, 0, 0
	Oval MouseX() - 5, MouseY() - 5, 10, 10, 1
	
	; 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down
	
	For Dude.Dudes = Each Dudes
		path = FindPath(pathmap, dude\x, dude\y, 0, MouseX() / 4.0, MouseY() / 4.0, 0)
		; Draw the PATH
		If Len(path) > 0
			Color(0, 0, 255)
				Select Mid(path, 1, 1)
					Case "1"
						dude\y  = dude\y - 1
					Case "2"
						dude\y = dude\y + 1
					Case "3"
						dude\x = dude\x - 1
					Case "4"
						dude\x = dude\x + 1
				End Select
				Oval dude\x * 4, dude\y * 4, 4, 4, 1
		EndIf
	Next 
	
	Flip()
Wend

FreePathmap(pathmap)

does anybody have some ideas to speed thing along? (I need speed, at least 100 or so "dudes", 20 "dudes" is around 0.5FPS!!)

chwaga

(Posted 2008) [#13]

well, I didn't quite fix the speed problem, but I made it look nonexistant. I just use an interpolation of positions, but the stupid "dudes" keep getting stuck on walls....

test.bb:

Include "pathinc.bb"

Graphics 1024, 768, 32, 2
SetBuffer BackBuffer()

Global map_width = 102
Global map_height = 76

Type Dudes

	Field x#
	Field y#
	Field destinationx#
	Field destinationy#

End Type


; Create level
Dim map(map_width, map_height)
For y = 0 To map_height -1
	For x = 0 To map_width - 1
		If Rand(0, 5) < 1 Then map(x, y) = PATH_ALL
	Next
Next

; Create pathmap
Global pathmap.TPathmap = CreatePathmap(map_width, map_height)
Global path$ = ""

; Copy level To pathmap
For y = 0 To map_height -1
	For x = 0 To map_width - 1
		PathmapSlot(pathmap, map(x, y), x, y)
	Next
Next

;make the dudes

For n = 1 To 20
	Dude.Dudes = New Dudes
	Dude\x = Rnd(1, map_width)
	Dude\y = Rnd(1, map_height)
	Dude\destinationx = dude\x
	Dude\destinationy = dude\y
Next

While Not KeyHit(1)
	Cls()
	
	; Draw level
	For  y = 0 To map_height -1
		For  x = 0 To map_width - 1
			If CheckFlag(map(x, y), PATH_ALL)
				Color(255, 0, 0)
			Else
				Color(255, 255, 255)
			EndIf
			Rect x * 10, y * 10, 10, 10
		Next
	Next
	
	Color 0, 0, 0
	Oval MouseX() - 5, MouseY() - 5, 10, 10, 1
	
	; 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down
	t1 = MilliSecs()
	For Dude.Dudes = Each Dudes
		If Int Dude\x# = Int Dude\destinationx# And Int Dude\y# = Int Dude\destinationy# Then 
			path = FindPath(pathmap, dude\x, dude\y, 0, MouseX() / 10, MouseY() / 10, 0)
			; Move the DUDE
			Select Mid(path, 1, 1)
				Case "1"
					dude\destinationy  = dude\destinationy - 1
				Case "2"
					dude\destinationy = dude\destinationy + 1
				Case "3"
					dude\destinationx = dude\destinationx - 1
				Case "4"
					dude\destinationx = dude\destinationx + 1
			End Select
		Else
			If dude\x < dude\destinationx Then dude\x = dude\x + .1
			If dude\x > dude\destinationx Then dude\x = dude\x - .1
			If dude\y < dude\destinationy Then dude\y = dude\y + .1
			If dude\y > dude\destinationy Then dude\y = dude\y - .1
		EndIf
		;Draw the DUDE
		Color(0, 0, 255)
		Oval dude\x * 10, dude\y * 10, 10, 10, 1
	Next 
	t2 = MilliSecs()
	Text 0, 0, t2 - t1
	Flip()
	
	If KeyHit(57) Then Stop 
Wend

FreePathmap(pathmap)

chwaga

(Posted 2008) [#14]

hmm...fixed that, now I guess I just kinda...well, unless anybody can speed up the code, it's my problem now. Thanks for the help, guys!

chwaga

(Posted 2008) [#15]

dun dun dun....

this doesn't plug into a 3d FPS too well, as soon as I raise the grid to 100 x 100, it's SLOW... I may have to chunk the pathfinding grids....would it be practical to give each npc a grid of it's own, and if the player invaded the grid, it would chase the player??