Advertisement

automatic waypoints placing

Started by November 11, 2007 09:31 AM
2 comments, last by Gagyi 17 years ago
Hi all. I have a problem with waypoints generation in 3d world. I was build a grid-based representation like this: http://img148.imageshack.us/img148/8663/samplefk6.jpg Anyone know good algorithm for waypoints generation, which avoids to place waypoints in toltally isolated areas?
you need to write a small function to peek locations in all possible movement directions. aka peek (location)to(origin) +(loop tracking all directions 100*adjust to needs* cubits from most direct route) last time i wrote an algorythm for such a thing was in A-basic lol.. been a while.. hope i helped even a little. dont know much about the engine your using.
Advertisement
Just spawn bots in random places (e.g. from objects) and get them to use a wandering behavior. Then as they wander, search for the nearest neighbour waypoint p in a graph, and add a new point if p is too far.

It's surprisingly effective!

Join us in Vienna for the nucl.ai Conference 2015, on July 20-22... Don't miss it!

I found this paper a few days ago and I was amazed how easy it was to implement:
http://www.nps.navy.mil/cs/cjdarken/levelexploration-3page.pdf
This is the same wandering behaviour, but a bit more detailed.

This is some pascal code, that does the job (surprisingly small):

// Twaypoints is the wapoints class// Generates about 10K waypoints in a minuteprocedure Twaypoints.generate;varSimulatedPos:TVector3;i,j:integer;addtable:array [0..5] of TVector3;onground:boolean;begin //Initializing the 6 angles, needed for physics for i:=0 to 5 do begin  addtable.x:=sin(i*2*pi/6)*0.06; // Running speed  addtable.y:=-gravity;           // 0.001 here  addtable.z:=cos(i*2*pi/6)*0.06; end; //fisrt waypoint... Set this yourself AddWP(0,0,First); i:=0; repeat  //for all angles, process the current (i) waypoint  for j:=0 to 5 do  begin    // Physics simulation of the bot going forward 1 unit    // from the waypoint towards the direction we set,    // and stop when it's on the ground and travelled the 1 m.    // This should be easy.   // Add the waypoint... If it is close to another, simply set   // a connection between the two waypoints (poins and the simulated one).   // If not, an other waypoint is added to the list    AddWP(i,j,SimulatedPos);  end;  inc(i); //Next!  // Maximum of 50K Waypoints  // We finish if there's no unprocessed waypoints until (i>50000) or (high(points)<i);end;//Add WayPoint//NOTE: points[].Connections[] is the one-way connection to another waypointprocedure Twaypoints.AddWP(current,direction:word;place:TVector3);vari:integer;begin //If this place is close to an existing waypoint, for i:=0 to high(points) do          //sqrt(3)/3  if DstPointPointSq(points.hol,place)<0.7*0.7 then  begin   points[current].Connections[direction]:=i;  //set the index   exit;  end;  setlength(points,length(points)+1); //If not, create a waypoint and  points[high(points)].hol:=place;     //set the index pointing there.  for i:=0 to 5 do   points[high(points)].Connections:=high(word); //Not connected... Processed later  points[current]..Connections[direction]:=high(points); //Set the indexend;


P.S.: The code may be noobish, but the idea is great.
P.S.2: My english is weird too. Hope you understand most of it.
-----------------------------------"After you finish the first 90% of a project, you have to finish the other 90%." - Michael Abrashstickman.hu <=my game (please tell me your opinion about it)

This topic is closed to new replies.

Advertisement