3d dynamic pathfinding

I would like to implement some method of dynamic pathfinding.

Say I have EntityX and I want this entity to navigate to PointXYZ - the path created should be totally dynamic, as my scenery is liable to change at all times. Also, my level mesh is treated as one big object, so it has polygonal collision, so the pathfinding needs to take this into account (to navigate succesfully around objects such as furniture).

Ideally I would like to be create a linked-list of nodes for the character to follow as the shortest path from their present position to the target.

What is the best way to go about this? I know absolutely nothing about this stuff!

if this is what you mean:

http://www.blitzbasic.com/Community/posts.php?topic=43014

I suggest you to have a look at A* pathfinding,
basically the above demo works the same as in A*.
There are some good tutorials about A* in Blitzcoder ... (or all over the internet too, of course :)

Paolo.

Nice demo of A*

Ok I've looked at some stuff on A* - it's half of what I need, but it relies on having a grid of possible / non-possible squares to move to, or as your demo shows, a set of linked nodes...

What if I know nothing about the geometry of the level?

Maybe there is a way of running a mini-simulation of the possible routes? This could test multiple routes, whilst checking for collisions, and the fastest route is chosen?

I would like to get my hands on a free 3D* Library. I've coded one for PPF, but, it was riddled with bugs. The community could definately benefit from one.

I see Bouncer has done dynamic node generation on his Nano project - hopefully he can point me in the right direction :)

I think you always must have some kind of nodes system around, in my demo I took out the "grid" because if was difficult to implement on an already made level, therefore I use nodes, but the code to find the path is the same (it use the F=G+H thing...)

if not, how could the character decide its next move if it doesn't know what is the shortest path??? ... I think in that way you could have a character moving randomly around the level but only that ..

Paolo.

Hi Eurythmia -

Thanks for the replies. Yes after having tried a few things, it definitely seems better to have nodes.

I like your editor - but it crashes a lot when I try to create and link nodes. Would you be willing to release the source to the editor? I would be interested in helping fix any problems - if not I will probably write one myself :)

As I said above,... learn A* because it is the same thing I'm using ...

In A* code, you have to select the quads that are not going to be taken into the calculations, those quads are the walls and so.
So the A* code then search the path within the rest of the nodes.

But, in my way, I do not select the walls, I just give the code a list of nodes that are always actives, and you don't need to check for "walls".
So the code then calculate the nodes F, G, and H the same way than in A* and then select the lowest F, and keep searching ...

Also, please if you found a nodes combinations where the demo crash, please post the txt info here so I can check it.

Paolo.

I prefer your solution of creating linked list of nodes, as it will be more accurate.

Also yes I do understand how A* works.

I have started to work on a similar node editor.

I was hoping you might release the source to yours as it would save me time, but I understand if you want to keep it to yourself.

I will hopefully post the source to my pathfinder editor soon.

were using a mesh floorplan in Blitzmax for our dynamic AI, works pretty well and you can paint level behaviours with vertex colours that influence the NPC AI's behaviour in interesting ways.

vertex colours act as varaiables, dangerous scary areas to avoid if possible unless you abslutely have to go there to evade something, good areas that are recommended if it's clear, stuff like that. or you can set a specific colour to determine cover, or where you can safely drop off a ledge without killing yourself etc

Still work in progress with our sports game, might be a bit CPU intensive for 11 AI NPC players and a Pentium 2 350, but good for other types of games.

one benefit of this method is that you don't need collision for characters, as they will only walk on the floormap and will not pass over open edges, so they will create paths around static obstacles where there is a hole in the floormap, and you can close off a door etc by dynamicly colouring verts across a doorway, or in theory seperating a few verts creating a open edge along the door.

might be able to do something similar in B3d too.

Sounds interesting - that's proper weighted A* where you make decisions not just based on the shortest route.

I just need a basic 'find way around simple obstacles' technique, which is why I've opted for the node-based approach as Eurythmia has adopted.

This is 2d code which I have posted before but I am sure you can do somethign with it. Look at binding for clues on how to navigate towards a certain area/point. My code is well ropey I only did it to get my head around how to go about doing arbitrary obstacle avoidance and Ive never taken it further. (I get bored easily)

basically for 3d you need to extend the transformation to local space to cope with 3 dimentions. You need 2 calculations 1 for the pitch plane of your object and one for the yaw.. other than that its going to be much the same as for 2d

Const NORMAL =0
Const ALERT = 1
Const COLLIDED = 2
Global drawn ;a global variable simply to determine if the territorial "bind" area has been drawn

;meet bob - a behavioural object
Type bob
	Field x#
	Field y#
	Field heading#
	Field rotation#
	Field speed#
	Field state
	Field wander
	Field Bind
	Field avoid
End Type

;draw a bob to the screen
Function drawbob(abob.bob)
	Local x#=abob\x
	Local y#=abob\y
	Local heading=abob\heading
	Local sh#=10*Sin(heading)
	Local ch#=10*Cos(heading)
	If abob\state=ALERT Then
		Color 255,255,100
	Else If abob\state = NORMAL
		Color 0,255,0
	Else If	abob\state=COLLIDED
		Color 255,0,0
	End If
	Oval( x-10,y-10,20,20,1)
	Color 255,255,255
	Line x,y,x+1*sh,y-1*ch
	;left side of sensor box
	sx1=x-1*ch
	sy1=y-1*sh
	
	sx2=sx1+6*sh
	sy2=sy1-6*ch
	;right side of sensorbox
	sx3=x+1*ch
	sy3=y+1*sh

	sx4=sx3+6*Sh
	sy4=sy3-6*Ch
	
	Line sx1,sy1,sx2,sy2
	Line sx2,sy2,sx4,sy4
	Line sx4,sy4,sx3,sy3
	Oval x-15,y-15,30,30,0
End Function

;rotate a bob by an specified ammount
Function rotatebob(abob.bob,ammount#)
	abob\heading = abob\heading + ammount
	If abob\heading>=360 Then abob\heading=abob\heading-360
	If abob\heading<0 Then abob\heading = 360+abob\heading
End Function

;move a bob by its speed relative to its current heading
Function movebob(abob.bob)
	rotatebob(abob,abob\rotation)
	x#=abob\x
	y#=abob\y
	heading = abob\heading
	x=x+abob\speed*Sin(heading)
	y=y-abob\speed*Cos(heading)
	abob\x=x
	abob\y=y
End Function

;randomly alter the bobs turn rate to change its heading periodicaly
Function wanderbob(abob.bob)
	If Not abob\wander Then Return
	a=Rand(10)
	If a<=3 Then abob\rotation=abob\rotation+1
	If a>=8 Then abob\rotation=abob\rotation-1
	If abob\rotation>3 Then abob\rotation=3
	If abob\rotation<-3 Then abob\rotation=-3
	
End Function

;"bind" a bob to a rectangular area
;this simulates a desire for a bob to remain close to or within this area
Function Bindbob (abob.bob,ox,oy,width,height)
	
	Local x#=abob\x
	Local y#=abob\y
	Local heading = abob\heading
	Local rotation#= abob\rotation
	If Not drawn Then
		Color 128,128,128
		Rect ox,oy,width,height,0
		Color 255,255,255
		drawn=1
	End If
	If Not abob\Bind Then Return
	b_left=ox
	b_right=ox+width
	b_top=oy+height
	b_bottom=oy
	If x<b_left Then
		If y<b_bottom Then
			If heading <=90 rotation=rotation +1
			If heading >315 rotation=rotation+1
			If heading >180 And heading <=315 Then rotation = rotation -1
		Else If y>b_top Then
			If heading >90 And heading <225 Then rotation = rotation -1
			If heading >225  Then rotation = rotation +1
		Else 
			If heading>180 And heading <270 Then rotation=rotation-1
			If heading>=270 Then rotation = rotation +1
		End If
	End If

	If x>b_right Then
		
		If y<b_bottom Then
			If heading <45 Or heading >=270 Then rotation = rotation -1
			If heading >=45 And heading <=180 Then rotation = rotation +1
		Else If y>b_top Then
			If heading <135 Then rotation = rotation -1
			If heading >=135 And heading <270 Then rotation = rotation +1
		Else
			If heading >90 And heading <=180 Then rotation = rotation +1
			If heading <=90 Then rotation =rotation -1
		End If
	End If

	If x<b_right And x>b_left Then
		If y>b_top Then
			If heading >45 And heading <=180 Then rotation = rotation -1
			If heading >180 And heading <=315 Then rotation =rotation +1
		End If

		If y<b_bottom Then
			If heading <135 Then rotation = rotation +1
			If heading >225 Then rotation = rotation -1
		End If
	End If

	
	If rotation<-3 Then rotation=-3
	If rotation>3 Then rotation=3
	abob\rotation=rotation
End Function

;bobs want to travel in a straight line so
;if they are not continually steered they will "straighten up"
Function dampbob(abob.bob)
	rot#=abob\rotation
	If abob\speed>1.5 Then abob\speed=1.5
	If abob\speed>1 Then abob\speed=abob\speed-0.1
	If abob\speed<0.1 Then abob\speed=0.1
	If rot <0 Then rot=rot+0.1
	If rot >0 Then rot=rot-0.1
	If Abs(rot)<0.1 Then rot = 0
	abob\rotation=rot
	
End Function

;make a bob follow another bob
Function seekBob(predator.bob, prey.bob)
	Local x#=predator\x
	Local y#=predator\y
	Local heading#=predator\heading
	Local rotation#=predator\rotation
	Local tx#,ty#

	tx=prey\x-x
	ty=prey\y-y
	tx2=tx*Cos(180-heading)-ty*Sin(180-heading)
	ty2=tx*Sin(180-heading)+ty*Cos(180-heading)
	If tx2<0 Then rotation=rotation+1
	If tx2>0 Then rotation=rotation-1

	If (tx2^2+ty2^2)>900 Then
		predator\speed=predator\speed +0.1
	Else
		predator\speed=predator\speed -0.1
	End If


	predator\rotation=rotation

End Function

;bobs hate running into other bobs as it gives them a red face
Function avoidbob(abob.bob)

	Local x#=abob\x
	Local y#=abob\y
	Local heading#=abob\heading
	Local rotation#=abob\rotation
	Local tx#,ty#
	Local avoiding.bob
	;transform the coords of each bob in to local bobspace
	avoiding=Null
	count=count+1
	For a.bob=Each bob
		If a<>abob Then
			
			tx#=(a\x-x)
			ty#=(a\y-y)
			;tx and ty now represent "a.bob" relative to abob (abobs position is now the origin)
			;rotate this point around the origin
			tx2=tx*Cos(180-heading)-ty*Sin(180-heading)
			ty2=tx*Sin(180-heading)+ty*Cos(180-heading)
			
			If tx2>=-30 And tx2<=30 And ty2>=-30 And ty2<=70 Then
				
				abob\state=ALERT
				If Sqr(tx2^2+ty2^2) <20 Then abob\state=COLLIDED
				If tx2<0 And ty2>0 Then rotation =rotation-1
				If tx2>=0 And ty2>0 Then rotation = rotation +1
				;if a bob is avoiding another bob it is focused on its task
				;and ignores all other stimulii
				abob\wander=0
				abob\Bind=0
				;abob\seek=0
				avoiding=a
				If ty2>0 Then
					abob\speed=abob\speed-0.1
				Else
					abob\speed=abob\speed+0.1
				End If
			End If
		End If
		;left alone a bob will continue to wander around its territory
		If  avoiding=Null Then
			abob\wander=1
			abob\Bind=1
			;abob\seek=1
			abob\state=NORMAL
			If abob\speed<1 abob\speed=abob\speed+0.1
			
		End If

		abob\rotation=rotation
		Next
	

End Function

Graphics 800,600,32,2

SetBuffer BackBuffer()
SeedRnd(MilliSecs())

;create one or more bobs
While numbobs=0
	numbobs=Input ("number of bobs?:")
	If numbobs=0 Then Print" 0 is not allowed"
Wend
Local hunter.bob
Local hunted.bob
target=1
While numbobs>1 And target = 1
	target = Rand (numbobs)	
Wend
For f=1 To numbobs
	a.bob=New bob
	a\x=Rand(600)+100
	a\y=Rand(400)+100
	a\heading=Rand (360)
	a\speed=1
	a\wander=1
	If f=1 Then hunter = a
	If f=target Then hunted = a

Next

Bind = 1
wander = 1
avoid = 1
height = 100
width=100
t1=MilliSecs()
t2=MilliSecs()
timer=0
While Not KeyHit(1)
	Cls
	count=0
	Local huntx,hunty
	Local preyx,preyy
	For a.bob =Each bob
		movebob(a)
		
		If wander Then wanderbob(a)
;		If a = hunter Then
;			seekbob(hunter,hunted)
;			huntx=a\x
;			hunty=a\y
;		Else If a= hunted Then
;			preyx=a\x
;			preyy=a\y
;		End If
		If bind Then Bindbob(a,400-width/2,300-height/2,width,height)

		If avoid Then avoidbob(a)
		
		dampbob(a)
		drawbob(a)
	Next
	;Text huntx,hunty,"Hunter"
	;Text preyx,preyy,"Prey"
	drawn=0
	If KeyHit(48) Then Bind=Not Bind
	If KeyHit(17) Then wander=Not wander
	If KeyHit(30) Then avoid=Not avoid
	If KeyHit(203) Then width=width+50
	If KeyHit(205) Then width=width-50
	If KeyHit(200) Then height=height+50
	If KeyHit(208) Then height=height-50
	If height<=0 Then height = 2
	If width<=0 Then width =2
	Text 10,10,"(W)Wandering:"+wander
	Text 10,25,"(B)Territory Binding:"+Bind
	Text 10,40,"(A)Avoidance:"+avoid
	Text 10,55,"(Arrow keys)Change Territory size"
	Text 10,70,"(Esc)Quit"
	t1=t2
	t2=MilliSecs()
	
	timer=timer+(t2-t1)
	If timer>100 FPS#=1000/Float(t2-t1): timer=0
	Text 10,95,FPS
	Flip 0
	
Wend

What I have posted is known as reactive behaviour and is the oposite end of the AI pathfinding spectrum to A* which is deliberative behaviour. A* relies on the entity having knowlege of the terrain/map/area so it can plan the best route through it. Reacive behaviour instead relies on localised information about the surroundings gathered from virtual sensors(or real ones in the case of robots - maze solving robot mice for example). Reactive behaviour is very good at coping with dynamic environments where the position of obstacles (eg players or other AI entities) cannot be predicted, only observed. A* is superb at working with complex static enviroments eg terrain maps.

Typically a more sophisticated AI will use a hybrid system of both systems where possible. The entity will deliberatively plan its path from tile to tile choosing the best route to get to its destination but also use reactive control to cope with the "how" to get from tile to tile (assuming that each tile must be traversed over a period of time)

Thus if you had a starship moving between saturn and jupiter you would break the space down into 3d blocks use A* to plan the path of least resistance through the asteroid field (find the best density / distance compromise) and set up a series of waypoints and then use reactive behaviour to traverse between waypoints while avoiding asteroids space invaders pirates etc.. or whatever you care to throw into the mix.

Hey that looks interesting Luke! Thanks for posting, I'll have a look later today.

In the meantime, I've written a visual 3d node placement editor and a basic algorithm for finding the shortest route (not based upon A* or heuristics, so VERY basic!) - it seems fairly quick, but I've only tested with a low node count of less than 20 or so pre-defined nodes.

I'll post this up too if anyone is interested in a free node editor? The code is pretty sloppy so I'm a bit embarassed to do so (I've a feeling it will grind to a halt on slow machines!).

(I've a feeling it will grind to a halt on slow machines!).
Let me try it I,ll let you know.

well it grinds to around 5pfs on my machine if I use say 100 bobs.. Im using 2 ghz 1gb ram and a radeon 9600 pro 256

however if I tell it not to draw to the screen it runs fine so its my card thats crap at drawing 2d

my friend gets a good framerate at 100 bobs on an almost identical machine except he's using an nVidia 5600 card

but yes.. theres lots of optimisation in there you can do
the first one I can think of is do and entity distance on each object and discard objects which are considered "out of the way" rather than doing the whole calc on every object which is what it does now.

if you dont draw the sensor box and use images for the bobs instead of the oval command it will be a lot faster Im sure. its not the algorithm that slows things down its drawing to the screen.

ok sorry its 11fps with 100 bobs.. and I just commented out the 4 lines of code that draw the sensor box and the proximity sensor (circle) and the prog jumped to 40fps..

its the rendering thats slow :D

oh and the reason I did it like that (knowing it would be slow) was so that it would at least run on any system with the code "as is" without having the annoyance of dling or creating extra graphics files :) and so I could post the code straight into a board and not have to provide a link

I get between 16-18 fps as is on pentium 4, win xp,256 mb,P4VMM2 with prosavage.

that doesnt surprise me :) how many bobs? and see what the improvement is if you coment out the bit that draws the lines for the sensor box

mostly I use 5 bobs.. I just included the option to have more because I could.

I had 100 bobs. With 200 I had 8 fps.
Without the lines and ovel I got 35-40 fps.
Without the the lines and ovel on back down to 20 fps

100 bob at 16-18 fps is better than my system does.

Try turning ALL the graphics off so all thats runnign is the simulation :)

@100 bobs with the rendering on I get 30 fps (lines off)
with all the rendering turned off I get 250fps

so its the rendering thats slow not the simulation even tho its doing at least n^2 calculations per program loop.. FP calcs at that too. but I never claimed it to be efficient.. only effective. :P

With all graphics turned off I get between 60 to 100 fps with 100 bobs.

By the way I find that Bill's are normaly faster than Bobs, but not faster than John's.

Thats because Bill comes earlier in the alphabet than Bobs

@Caff,
Have a look at my other topic for the source to the editor,
although it is still a dirty code ...

Paolo.