3d dynamic pathfinding
Blitz3D Forums/Blitz3D Programming/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. |
   |