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. |