I'm reading up on Craig Reynolds' steering algorithms and I'm still unclear on some of the underlying principles.

As far as I can tell, Reynolds' vehicle model has only position and velocity (and mass). It seems to be assumed that the vehicle's orientation is kept aligned to its velocity vector. The vehicle's direction changes by taking a steering vector, its magnitude truncated to a maximum steering force, and adds it to the vehicle's velocity. The vehicle's velocity is then truncated to a maximum speed. Steering behaviours are achieved by calculating different steering vectors and combining them into a single final vector. The vehicle has continually variable thrust and it is never "rotated" (say, Asteroids-style) per se.

That's pretty much it, right?

Quote:Original post by VideroBoy
That's pretty much it, right?

That sounds about right. Basically, with the model you described, the agents are treated as particles. How to handle orientation is up to you, but it's common simply to align the object with the velocity vector.

These methods are not typically the most appropriate for vehicles, for exactly that reason. Steering works purely by applying acceleration, and assumes that the entity can accelerate equally well in any direction. While this sort of works for bipeds and quadrapeds (and it works great for spaceships!), it doesn't really work very well at all for vehicles.

For an alternate approach, you might look into Chris Jurney's article in AI Game Programming Wisdom 4, "Postprocessing for High Quality Turns," for a starting point. I believe Nathan Sturtevant (http://webdocs.cs.ualberta.ca/~nathanst/) has also done some work in this area.

Quote:Original post by Kevin Dill
These methods are not typically the most appropriate for vehicles, for exactly that reason. Steering works purely by applying acceleration, and assumes that the entity can accelerate equally well in any direction. While this sort of works for bipeds and quadrapeds (and it works great for spaceships!), it doesn't really work very well at all for vehicles.

This might have caused my confusion. Reynold's work is so influential yet his assumed physics model doesn't seem to mesh with several vehicle control schemes common in games.

Reynold's original paper has steering through combining vectors and applying them to point masses. There's no explicit rotation, the implied rotation has variable speed, and the thrust speed is also variable. The control input with behaviour closest to AI's using Reynold's locomotion is an analog joystick.

For my specific case, I have games in mind where vehicles have forward/reverse thrust and rotation; Asteroids-style of course. I also have games in mind where movement is constrained along four or eight cardinal directions like in Zelda or Robotron. I'd like to apply Reynold's steering method to those schemes since his method allows complex behaviour for little effort, but I anticipate certain degrees of shoehorning.

Quote:For an alternate approach, you might look into Chris Jurney's article in AI Game Programming Wisdom 4, "Postprocessing for High Quality Turns," for a starting point. I believe Nathan Sturtevant (http://webdocs.cs.ualberta.ca/~nathanst/) has also done some work in this area.

I'll have to put off looking at Chris Jurney's article since I'd have to pay money for the journal. ;) Also, according to the abstract it just talks about smoothing out movement along a predefined path (in combination with pathfinding). Nathan Sturtevant also seems to deal mainly with pathfinding (though it's kind of cool he worked with Bioware :) ). I'm currently more interested in dynamic flocking, seeking, and evasion behaviours.

So for my money, I'd use a search-based solution for both of those. For the asteroids game, you're searching over the space of rotations and accelerations to find a series of steps that will transition from your starting position and velocity to your destination position and velocity. I'd recommend finding a copy of Russell & Norvig's "Artificial Intelligence: A Modern Approach," and reading chapters 3 and 4 (at least, those are the chapters in the third edition. The chapters on search, up to and including searching in continuous spaces). That's the standard text for AI classes, and has been for 15 years or so - I used the first edition back in '97. I expect that you will find a ton of ideas there.

For vehicles moving using cardinal directions - that sounds like simple A* path planning on a grid. Should be a no-brainer, unless you're doing something complicated that I'm not understanding. Again, Russell & Norvig will have the algorithm for A* - or you can look it up on the web, or in just about any other AI book out there.

Quote:Original post by Kevin Dill
For the asteroids game, you're searching over the space of rotations and accelerations to find a series of steps that will transition from your starting position and velocity to your destination position and velocity.

I honestly never thought of that. I guess you can throw graph traversals at anything. :)
I'm just worried A* might be a bit heavy for what I need. And about evasion steering? Would I just stick to the "go in the direction that maximizes the distance between me and the target" method?

Quote:For vehicles moving using cardinal directions - that sounds like simple A* path planning on a grid. Should be a no-brainer

Path planning is a no-brainer, at least when I have a tiled environment. But there are times when I want an NPC to navigate without following an actual path, like when wandering.

As a specific example, one of the games I'm working on (and not just planning ;) ) is a Spacewar-style game. The player is in a spaceship pitted against an AI opponent in empty space. Unlike Spacewar, I use WASD for movement and mouse for aim; ship movement is more like Robotron or Geometry Wars. I need the AI to (a) dodge the player's bullets and (b) get within firing range. This sound more suited to steering/flocking behaviour than to A* or other graph traversals, but I still want to constrain the AI's movement so that it follows the same rules as the player.

For the space game, a simple hill climbing algorithm, or maybe simulated annealing, might work well. Yes, it's heavyweight - but solving a search problem in a continuous space like this is a tricky problem, and TNSTAAFL (there's no such thing as a free lunch). The good news is, you can probably improve your solution each frame. So on the first frame, start your search with a good guess of a likely action (e.g. turn toward the destination, or accelerate if you're aiming the right general direction). Then on each frame, continue your search, and when you run out of time in that frame execute the best action you've found so far. You'll have to do some playing with it, and a lot depends on making sure that that initial guess doesn't do exactly the wrong thing, but I suspect something like that will work.

Collision avoidance definitely throws a wrinkle in. With that said, if you know the positions, velocities, and rotations of the other ships then you can reasonably predict the space that they're likely to enter (represented as a cone), and steer to avoid that (i.e. pick an intermediate position and velocity on the way to your destination that will try to keep you out of those cones).

Overall, this sounds like a really hard problem to solve perfectly. You'll probably still get the occasional collision. If that's not OK, then you might want to loosen the constraints and just use steering forces, although that means you'll have to change the game mechanics a bit. And even steering forces still sometimes result in collisions if you don't allow infinite acceleration. If you look at the little java apps on Craig Reynolds page, you'll see the occasional collisions on most of them. Ultimately, to get a perfect solution you may need to sacrifice some physical accuracy.

For wandering, a common trick is to pick a random point and move there, then pick another random point, and repeat. The trick is, when you pick subsequent points, you want to choose ones that don't have you doing anything obviously odd (like a u-turn in the middle of the street for no obvious reason). At least, if the player's watching you do - if the character's not on camera, you can do almost anything you want.