For the 3D RTS I would like to experiment with making, high speed jets will be attacking ground targets. It will be a terrain-intensive game, so there will be some careful maneuvering necessary. I plan to use a heightmap for the terrain to start out with. I figured the best way for the jets to avoid the terrain is to simply predict a collision ahead of time. If within a few seconds they would strike the terrain, they will prioritize adjusting their travel path to avoid a collision. Now, it's easy to predict a collision within a few seconds. I can just extend a ray out and look for an intersection with the terrain within a certain distance based on the speed of the craft. The problem comes in with how the trajectory should be adjusted. If the jet is heading for a small spire, it can adjust itself slightly to avoid it. For a huge side of a mountain, the jet will naturally have to perform a serious adjustment to avoid a collision. The trick comes in with how to model the collision detection such that I can quickly determine how the jet needs to adjust itself to avoid a collision. The solution I propose for myself involves pre-parsing the terrain and making an approximate model out of it, basically making the polygons much larger. The flat side of a hill would be for the most part one polygon, for example. That way, I could quickly determine based on the size of the collision polygon and the orientations and positions of the adjacent polygons exactly what to do in the short term to avoid a collision. Does this make any sense? Are there any methods out there that help solved this kind of problem? Books or links to articles would be appreciated! Anything that helps me represent a data parse of the terrain that quickly leads to an optimum avoidance path would be wonderful. Thanks! [edited by - Waverider on February 14, 2003 8:03:19 PM]

You might find the obstacle avoidance steering behavior that is discussed at http://www.red3d.com/cwr/steer/ to be worth reviewing as a possible solution.

Eric

Excellent start, thanks!

You should also do a little reading on TFR (Terrain Following Radar), the automated system used in aircraft like the F111.

Cheers,

Timkin

I would also like to throw in the possibility of using a Neural Network to determine steering behavior, trained by a Genetic Algorithm. There a great series of articles on it over at Ai-Depot. Neat stuff and its always good to have options The articles are Bot Navigation : Using Neural Networks for Obstacle Avoidance. Its applied to Quake Bots but the technique can be adapted to other types of games too.
www.ai-depot.com

[edited by - Eudaemon69 on February 20, 2003 11:37:44 AM]

The problem with adapting such an approach to a TFR application is in the size of the state space. A bot wandering around a Quake level (or similar) may only come across a few tens of objects... maybe a few thousand if you include wall shapes as obstacles. However, an aircraft flying highspeed over a variable terrain is going to need to know how to avoid a very broad spectrum of terrain shapes. Flying over the same place from different directions will give a completely different obstacle to avoid. So, there are conceivably an infinite number of shapes you would have to train the network on. Not a good starting point.

If you were to take this approach, you would hope that you could broadly classify terrain into a handful of distinct sets. This would require preprocessing of the terrain data and ultimately I doubt it would perform much better than a hand-crafted, rule based system, which would take a lot less effort to produce.

Cheers,

Timkin

I'm thinking about just tracing along the abbreviated polygons (radiating out from the polygon that would be collided with) until I find the first polygon that actually faces away from the jet, and have the jet fly towards that position. Before I obligate the jet to trying that maneuver, though, I would need to make sure there isn't more terrain past that peak that it would collide with. Sometimes it's better to swerve sideways than to try to take it vertically (but I imagine a vertical avoidance would work most of the time)

Then again, I would like the craft to follow a low path as much as possible to avoid vulnerability to missile emplacements. Jets hopping over hills could be easy targets.

It's a challenge, to say the least!

[edited by - Waverider on February 20, 2003 10:03:19 PM]

If I were approaching this problem, I would convert the height information into a low-resolution boolean grid, where "true" in the grid means "you might crash into something flying into this square at your current altitude" and "false" is "there is nothing in this grid to hit at your altitude". Then do an easy pathfinding search through the grid.

Timkin: Actually a NN is ideal for it, you do train the net with a wide varity instances but if trained properly then the NN can react generally, its kinda the point of using a NN over a more discrete way of catagorizing something.

Plus using a Genetic Algorithm to evolve the NN you wouldn't have to write a rule at all, just let the GA figure it out for you.
Atleast that my view But I will look into TFR more, it sounds interesting.

[edited by - eudaemon69 on February 20, 2003 12:36:50 AM]

quote: Original post by Eudaemon69
Timkin: Actually a NN is ideal for it, you do train the net with a wide varity instances but if trained properly then the NN can react generally, its kinda the point of using a NN over a more discrete way of catagorizing something.

It's not an issue of whether the network could learn a useful representation of the function mapping, but how much data you would need to cover enough of the state space to make the network useful. In a domain such as this (without preprocessing) there is simply too much variability in the state space to be able to train a practical network in reasonable time.

Personally, I think that the AP's suggested solution (the boolean grid) is the best so far.

Cheers,

Timkin

[edited by - Timkin on February 23, 2003 6:17:09 PM]