   2d shooter ai - damage avoidance
  I am making a 2d game in which two spaceships orbit the moon and try to shoot each other down. (One player controlled, the other ai controlled). Going off the side of the screen wraps you around to the other side, and touching the moon is instant death.So far I've got everything working, except for the ai, which fails miserably.My first goal is to make it able to avoid bullets. Since the physics are perfectly deterministic, my idea was to have the ai simulate the game a second or so in advance (It won't know what the player will do, but avoiding the existing bullets should be good enough)and try to find a path to avoid the damage.On each tick, there are 6 possible steering inputs. Either you can accelerate forward, or not, and rotate to either side or stay going straight.My first try was a brute force search, but the possibilities grow exponentially. It can only search 4 ticks ahead in a reasonable amount of time, even with no bullets on the screen, but I need it to search at least 30. (My game runs at 62.5fps) So obviously, I need to find some way to redesign my ai. What can I do? Is what I'm attempting to do even possible?#include <vector>#include <bitset>#include "PSpaceduel/psdmanager.h"#include "utilityheaders/timer.h"typedef uint inputtype;bool Accel(inputtype i) {return i/3 > 0;}int Rot(inputtype i) {return ((i+1)%3)-1;}class TrajectoryProjection{    std::vector<std::vector<BulletData> > trajectories;    public:    TrajectoryProjection(const std::vector<BulletData>& bullets)    {   trajectories.push_back(bullets);    }    const std::vector<BulletData>& GetBullets(uint time)    {   assert(time<=1000);   assert(trajectories.size()>0);   while (time >= trajectories.size())   {  uint i = trajectories.size() - 1;  std::vector<BulletData> newtrajectory;  BOOST_FOREACH(const BulletData& b, trajectories.at(i))  { assert(b.p.active); BulletData newbullet = b; if (newbullet.life == 0) {newbullet.p.active = false; } else {--newbullet.life;MoveAndGravity(newbullet.p, BulletRad()); } if (newbullet.p.active) {newtrajectory.push_back(newbullet);}  }  assert(newtrajectory.size() <= trajectories.at(i).size());  trajectories.push_back(newtrajectory);   }   return trajectories.at(time);    }};ShipData StepShip(const ShipData& oldstate, inputtype i){    ShipData newstate(oldstate);    MoveAndGravity(newstate.p, ShipRad());    if (Accel(i)) {newstate.p.vel += ShipAccel() * newstate.Dir();}    newstate.angle += RotSpeed() * Rot(i);    return newstate;}//Returns 2 if we die instantly and 1 if we hit at least one bulletuint TakesDamage(TrajectoryProjection& trajs, const ShipData& shipstate, uint time, uint recursedepth){    if (!shipstate.p.active) {return 2;}    BOOST_FOREACH(const BulletData& b, trajs.GetBullets(time))    {   if (Norm(b.p.pos - shipstate.p.pos) < (ShipRad() + BulletRad()))   {  return 1;   }    }    if (recursedepth>0)    {   uint mindmg = 2;   for (inputtype i = 0; i < 6; ++i)   {  uint leafdmg = TakesDamage(trajs, StepShip(shipstate, i), time + 1, recursedepth - 1);  if (leafdmg < mindmg) {mindmg = leafdmg;}   }   return mindmg;    }    return 0;}ShipInput psdManager::DoAI() const{    Timer mytimer;    const uint SEARCHDEPTH = 4;    const ShipData& player = ship.at(0);    const ShipData& me = ship.at(1);    ShipInput newinput;    TrajectoryProjection trajs(bullets);    //Determine whether we are going to be hurt soon    uint mindmg = 2;    std::bitset<6> safeinputs;    for (inputtype i = 0; i < 6; ++i)    {   uint leafdmg = TakesDamage(trajs, me, 1, SEARCHDEPTH);   if (leafdmg < mindmg)   {  mindmg = leafdmg;  safeinputs.reset();   }   //This branch may be taken after the branch above. DO NOT MERGE INTO ELSE IF   if (leafdmg == mindmg)   {  safeinputs.set(i, true);   }    }    assert(safeinputs.any());    //find the first acceptable outcome. The inputs are already ordered from best to worst, so this is just the first 1 bit of the bitset    for (inputtype i = 0; i < 6; ++i)    {   if (safeinputs.test(i))   {  newinput.engine = Accel(i);  newinput.rotation = Rot(i);  Debug(mytimer.milliseconds());  return newinput;   }    }    assert(false);    return newinput;}
  Running a full simulation when the AI thinks is not "realistic" anyway (unless the AI represents some godly genius).I would go with using projections (ray casting ?) : calculate linear trajectories for obstacles, projectiles, other players. Supposing that no collision occurs, or the players do not change directions (this is false of course, but you can add tweaks later, when the AI seems too dumb).Keep us posted, I'm interested in the subject, making a similar game !   ;  I managed to speed it up considerably by using the heuristic that you usually want to do the same input for multiple consecutive ticks. It can now dodge the moon with a fairly high success rate. It's still not perfect due to horizon effects and the shortcuts I took in the searching, but it's pretty good.Unfortunately, it completely refuses to dodge bullets.   ;  You could probably achieve the same effect using influence maps. Give any targets a positive one, give bullets and the moon negative ones, maybe adjust for velocity...It should seem quite intelligent, when it's just blindly following.   ;  The problem is that a static influence map isn't terribly useful when all of the obstacles are fast moving, and accelerating in different directions. (Yeah, the bullets follow gravity too)I figured out why it was failing to dodge bullets, and fixed it. The new problem is that once again, the ai takes way too long, although it's much better then before.I tried adding a hash set to cache positions already known to be safe, and the time required went up!Without it, the search took 1530ms, while with the hash set it took 5430ms!Any idea what the problem might be? Do you think the overhead of hashing or searching the set is too high?std::size_t hash_value(ShipData const& arg){    assert(arg.p.active);    std::size_t seed = 0;    boost::hash_combine(seed, arg.p.pos.x);    boost::hash_combine(seed, arg.p.pos.y);    boost::hash_combine(seed, arg.p.vel.x);    boost::hash_combine(seed, arg.p.vel.y);    boost::hash_combine(seed, arg.angle);    return seed;}class HashMap{    boost::hash<ShipData> myhasher;    std::set<std::size_t> hashset;    public:    void Insert(const ShipData& newdata)    {   hashset.insert( myhasher(newdata) );    }    bool Contains(const ShipData& newdata) const    {   return hashset.count( myhasher(newdata) ) > 0;    }};;  Can you/Are you ignoring projected inputs which couldn't possibly collide with the bullets? And how many bullets are we talking about here? Do bullets wrap around the screen edges? Disapear? or get sucked into the moon?For example, if the bullets are moving in an arc due to the gravitational effects, then moving counterwise to the direction of the arc won't collide (save wrapping around), and you can assume no collision with that bullet. Similar assumptions could possibly be made for forward and backward movement.Another approach might be to take the tangent to the projectile path and assume that locations on the outside of this line (the half-space furthest from the moon) are safe -- though multiple projectiles will complicate this.   ;  You don't need a static influence map. In fact, technically, you don't need a map at all. Just have your AI call an "InfluenceCheck" on a reasonable number of points in a circle around it - Eight should work well. Take the best one, lerp between it and its best neighbor based their relative scores...In InfluenceCheck, just get each "InfluenceProvider" to calculate the influence for that point only. Iterate and add. Since the calculation for any point is just a velocity-modified distance fall-off, the check will be very quick.   ;  There can be up to 10 bullets at once. They warp around the screen and disappear when they hit the moon, a player, or they run out of timed life.I just don't understand how crude measures like linear interpolation are going to help.[Edited by - Storyyeller on April 19, 2010 7:57:36 PM];  The linear interpolation is to keep it from heading in only 45 degree directions. Anything else, you'd have to ask a specific question, rather than "I don't think it'll work".   ;  Ok, specific question: How do I make the AI not crash into the moon, dodge all bullets if possible, and take less then 16ms to think?   