Advertisement

Vehicle obstacle avoidance

Started by February 05, 2009 06:52 AM
7 comments, last by MGB 15 years, 9 months ago
Hi all, I'm trying to write generalised obstacle avoidance for my wheeled vehicles and having umm... mixed success. It needs to avoid any shape obstruction including concavities/dead ends etc. I've managed to write something that quite successfully seeks out the concave parts and gets stuck in them ;) Are there any good strategies for handling this sort of environment? I've looked at robotics stuff and the Red3D stuff many times but that seems tailored to really simple environments (e.g. I can't really use 'wall normals' & wall following due to the concavities). I cast one probe ray per frame in front of the vehicle at random x offset then process any hits that would cause collision. Maybe I need to store more state over time - maybe maintain some representation of the immediate environment? That sounds like it could be quite a bit of work, so I'd be interested to hear from anyone with experience here... [ed] Also interested in strategies for handling impassable/dangerous terrain too. cheers, Aph
Assuming your environment is static, the simplest method would be to overlay a grid and just find a path. A downside is that the square bounding volumes required to fill a grid doesn't exactly fill some areas (like rounded obstacles for instance).

You could try to represent the environment in a number of other ways if that doesn't suit, including nav meshes, roadmaps or even hand-crafted waypoint graphs. The same problem as before exists but the coverage is usually better.
There was also an OKish paper at AIIDE'08 by Youngblood et al describing DEACCON, a system they built to create structures that exactly fill an environment. I say OKish because I found it hard to read in places but it should be enough to get you started.
Advertisement
Hi Pithlit,

The environment is mostly static structures, but pre-authoring waypoints & nav meshes isn't practical as the world is huge and procedurally generated.
Some sort of scrolling grid sounds interesting... I'll have a think about that one.
Woah - that paper does look rather complex. I'll see if it gives me any ideas though - like you say, a bit hard to read...
Well if it's procedurally generated that should actually be easier since you can just procedurally generate the navmesh simultaneously.

-me
This is the sort of environment to be navigated. The user could leave the vehicle anywhere they like, then request it to autonomously go home at some later point. The structures are chosen & placed semi-randomly, which could obfuscate navmesh calcs?
Quote: Original post by Aph3x
This is the sort of environment to be navigated. The user could leave the vehicle anywhere they like, then request it to autonomously go home at some later point. The structures are chosen & placed semi-randomly, which could obfuscate navmesh calcs?


Are the structures fixed or dynamically placed during the game? In the latter case, you might be able to do local repair of the nav mesh. With a grid it's even more trivial.
Advertisement
One thing I did learn in my robotics class last year (never thought I would use actually use this again) was pathfinding. You mentioned you tried robotics stuff - did you try the potential field method? I don't remember the exact equations, but basically, imagine your entire environment as one of those "infinite rubber sheets". Tilt it downward from the start to the finish, so if you were to place a ball at the start, it would roll down toward the goal. Now poke a well down at the goal so the object gets more drawn in and stuck there. At each obstacle, create a hump in the field to repel it. When you place the ball at the start, it will tend to roll down, around the obstacles, and fall into the goal.

The bumps and well are some sort of quadratic. The tilt of the field is linear. Just sum up all the individual equations of the tilt, goal, and obstacles to get the total field, then find the gradient at your current location to decide where to go next. You can also add weights (coefficients) to each obstacle to encourage more or less avoidance.

Not sure if this is quite what you were asking for, but I hope it helps at least a little.
Although not a full solution, for vehicle turning issues, look at Chris Jurney's article in AI Game Programming Wisdom 4. It shows some of the stuff they did in Company of Heroes.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

Tesserex: that sounds quite an interesting approach. Might mix well with terrain data to avoid steep slopes & large drops...

Fox: I'll try and find that article.

This topic is closed to new replies.

Advertisement