Ok, I have read all there is about AI and object avoidance/steering, but it all seems to work in a "Car Driving" environment. As in when you turn left you immediatly change your direction to that turn angle, or whatever. ANYWAY, I was hoping someone could help me with perhaps a resource I missed pertaining to this, or you math whizzes could help me personally - I''m sure there is huge trigonometry involved. My movement system works like the classic ASTEROIDS system: You turn to a specific angle and then you can accellerate at that angle. To slow down you turn 180dgs and accellerate in the other direction. You can see how the standard car simulation object avoidance doesn''t quite apply here. SO, I was hoping someone could help me out in any way with some object avoidance ideas/equations/theories based on THIS movement system. Thanks for any help in advance BTW: I posted this on accident in the Game Programming Forum and tried to delete the post, but its like it''s still there... just the contents were removed Oh well, maybe a mod will delete it for real

It''s simply a matter of determining the appropriate velocity vector that would enable your craft to avoid the object and then finding an appropriate thrust vector to achieve that velocity vector, given the current velocity of the craft.

What is specificially important is the impulse applied to the craft by the engines. The same impulse can be achieved by a long burn at low thrust or a short burn at high thrust. You will need a way to choose this combination... perhaps by preferring longer, weaker thrusts. Obviously though the length of burn is governed by the time to impact!

Cheers,

Timkin

gahhh!

Well, for further information, there is no choice as to what to thrust at beyond what you''ve researched to. For example, 1 player''s thrust could be 100 while another might be 57, but they will ALWAYS thrust at 100 and 57; basically, full thrust is on or off. Thanks for the response, but I''m looking for something a little more specific.

For example, should I mix the car steering method and create a long line extending out in the direction the object is moving and test collisions with? Hmm... it''s got me thinking. Maybe perpendicular corrections (thrusts) to that line could achieve the dodging effect..? We''ll see, but any additional help is obviously still welcome

I just can't resist, sorry Timkin . The obstacle avoidance articles at www.Ai-Depot.com have an article about this, using a Neural Network to process the inputs (probably distance censors) and a Genetic Algorithm to evolve the NN to react appropriately. Of course in this case it might get more interesing. I'm going to have to do the same thing for my space game and right now I'm thinking a combination or a few linked Neural Networks to control the various forces (in my case acceleration and torque). Now NNs are not the end all be all but from what I've seen so far NNs have the best chance of learning when to start an impulse and when to stop it. There are downsides of course, I haven't quite figured out how to set up the sensors yet since in space the main thing to avoid are small objects and not walls. But I think with a combination of distance and angle sensors you might be able to train it correctly. Other than that it will come down to some math though it shouldn't be too bad (though some calculas will probably have to come into play . If you did incorporate side thrusters you might be able to to something like a walk-ahead simulation to see how long you have to thrust to get out of the way.
Also is it real thrust? i.e. is the thrust an acceleration or a constant velocity?

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

I once wrote a game with asteroids style (that is, inertial) movement. For enemy ship movement I used heuristic state space search and the results were impressive. Actually enemy ships navigated better than human players. The idea is that if at any point enemy ship has three choices - turn left (LEFT), turn right (RIGHT) and not turn at all (FORWARD) then you can find the best trajectory by searching all possible subsequent combinations of those choices up to some depht by simulating ship positions in the future (using the same function that updates actual ships). That gives you O(3^n) complexity (very bad), but the complexity can be greatly reduced (actually made polynomical) by analyzing only sensible trajectories. I searched only trajectories in form

zero or more FORWARD followed by zero or more LEFT followed by zero or more FORWARD (up to fixed depth)

and

zero or more FORWARD followed by zero or more RIGHT followed by zero or more FORWARD (up to fixed depth)

(that is, I''m not searching trajectories like RIGHT LEFT RIGHT LEFT RIGHT LEFT - sudden, chaotic turns in both directions)

that gave me about O(n^2) complexity, which means few hundred steps per ship per frame. And it allowed me to handle obstacle avoiding, other ship avoiding, and attacking/retreating from player ship through a single utility function. The whole AI code was about 350 lines of code.

Advanced Bug: You didn''t mention thrust. Did you assume full power was always on?

(a fun approach to solving that particular problem btw! Proving that overkill is fine so long as your machine can handle it...)



ai-junkie.com

quote: Original post by fup
Advanced Bug: You didn''t mention thrust. Did you assume full power was always on?

At first I tried a more complex system, which allowed enemies to switch thrust on/off, but for some reason 95% of all time they flied with thrust on (probably because they could reach they goal faster), so I threw that part of the code away. Though that caused some rare problems with stucking at the obstacles.

In response to Eudaemon69 - Yeah, it''s real thrust, where the thrust is a constant accelleration applied to the ship.

Hmm, thanks for the replies guys - got me thinking. In between posting and this reponse I quick did a modified version of the "car steering" i mentioned before... it actually seems to be working really well.

I use the velocity of the ship to determine the direction to extend the "collision prediction" line, not the looking direction. I then do some simple "Closest Point to Line" tests to tell if a collision is imminent.
Then based on this, comparing a few angles and stuff I can tell them to thrust the way of, err, "least resistance" to avoid collisions.
It also works really nice because since the collision detection line is based on current velocity, I can also derive the best slowdown angle (collision detection line angle + 180 dgs), which I also use as well.
And on TOP of that, it''s simple multiplication to increase or decrease the length of the collision detection line. As of now I''m using a simple "MASS/THRUST" type deal, so the more mass and less thrust power the longer the line gets, which is good because something that has more mass and/or less thrust should get a warning and should start "avoiding" earlier than normal.

I''m still having trouble, however, in determining the best avoidance angle for a nice, smooth, flyby of the object. If you are at all interested in helping me out, here is what has been helping me think of the most basic calculations to hopefully pull off the effect... I just can''t think of the math behind it.

Ok, picture this - your ship is moving head on towards and object it should avoid. The angle to it is 0dgs. In this situation, it doesn''t take a rocket scientist to know that the best avoidance & thrust angle is 90dgs, perpendicular to the angle you are moving at it - this will get you out of the way of this object fastest. BUT, as you move around/past the object, that avoidance angle gets smaller, to the point where when you are flying by it, the avoidance angle will be 0dgs when the direction angle is now perpendicular to your movement angle. I also think that the distance to the object and the object''s size will also scale the amount of change needed... but I can''t think of an EQ that will encompass this all ;|.

It could be a little work so I don''t blame anyone for not wasting time on this, BUT, if you can think of any advice off the top of your head, that''d be kickin Thanks for any help again and your responses already.