Mercurial > projects > openmelee
changeset 24:441eb7672404
impleneted steer to avoid
| author | zzzzrrr <mason.green@gmail.com> |
|---|---|
| date | Fri, 27 Mar 2009 16:05:24 -0400 |
| parents | e79347dd38a3 |
| children | 2bf818f8b005 |
| files | ai/ai.d ai/steer.d melee/melee.d render/render.d ships/asteroids.d ships/orz.d ships/planet.d ships/ship.d ships/urQuan.d |
| diffstat | 9 files changed, 144 insertions(+), 285 deletions(-) [+] |
line wrap: on
line diff
--- a/ai/ai.d Thu Mar 26 20:35:58 2009 -0400 +++ b/ai/ai.d Fri Mar 27 16:05:24 2009 -0400 @@ -30,8 +30,9 @@ */ module openmelee.ai.ai; +import tango.util.container.LinkedList : LinkedList; import tango.io.Stdout : Stdout; -import tango.math.Math : atan2, abs, PI; +import tango.math.Math : atan2, abs, PI, isNaN; import blaze.common.bzMath: bzVec2, bzClamp; import blaze.bzWorld : bzWorld; @@ -39,40 +40,57 @@ import openmelee.ai.steer : Steer; import openmelee.ships.ship : Ship; +alias LinkedList!(Ship) ObjectList; + +struct Threat { + Ship target; + bzVec2 steering; + float distance = 0.0f; + float collisionTime = 0.0f; + float minSeparation = float.max; + bzVec2 relativePos; + bzVec2 relativeVel; +} + class AI { - Steer steer; Ship ship; float maxPredictionTime = 0.1f; - bzWorld m_world; bzVec2 st; - bool avoidTurn; + bool avoidRight; + bool avoidLeft; - this(Ship ship, bzWorld world) { - m_world = world; + this(Ship ship, ObjectList objectList) { this.ship = ship; - steer = new Steer(ship); + steer = new Steer(ship, objectList); } void move(Ship enemy) { - - st = bzVec2.zeroVect; + + Threat threat; // Elementary steering AI steer.update(); - //st = steer.steerToAvoidObstacles(0.25, m_world.bodyList); - //st = steer.avoid(10.0, m_world.bodyList); - //st = steer.getSteering(m_world.bodyList); + steer.collisionThreat(threat); + st = threat.steering; if(st == bzVec2.zeroVect) { - avoidTurn = false; - st = steer.steerForPursuit(enemy.state, maxPredictionTime); + if(avoidLeft || avoidRight) { + avoidLeft = avoidRight = false; + ship.rBody.angularVelocity = 0.0f; + } + st = steer.targetEnemy(enemy.state, maxPredictionTime); chase(enemy); + return; } else { + ship.state.turn = false; avoid(); + return; } + + assert(0); } void chase(Ship enemy) { @@ -80,10 +98,12 @@ ship.state.target = st; st = ship.rBody.localPoint(st); float x = st.x; - float y = st.y; + float y = st.y; st = -bzVec2(y,-x); + // Because ship's heading is 90 off rigid body's heading + //st = st.rotate(-90); float angle = atan2(st.x, st.y); - + if(abs(angle) > 0.05) { if(!ship.state.turn) { if(st.x >= 0) { @@ -108,18 +128,25 @@ void avoid() { st = ship.rBody.localPoint(st); + // Because ship's heading is 90 off rigid body's heading + //st = st.rotate(-90); float x = st.x; - float y = st.y; + float y = st.y; st = -bzVec2(y,-x); float angle = atan2(st.x, st.y); - if(!avoidTurn) { - if(st.x >= 0) { + if(st.x <= 0) { + if(!avoidRight) { ship.turnRight(); - } else { + avoidRight = true; + avoidLeft = false; + } + } else { + if(!avoidLeft) { ship.turnLeft(); + avoidLeft = true; + avoidRight = false; } - avoidTurn = true; } ship.thrust();
--- a/ai/steer.d Thu Mar 26 20:35:58 2009 -0400 +++ b/ai/steer.d Fri Mar 27 16:05:24 2009 -0400 @@ -33,6 +33,7 @@ module openmelee.ai.steer; import tango.io.Stdout : Stdout; +import tango.util.container.LinkedList : LinkedList; import blaze.common.bzMath: bzDot, bzClamp, bzVec2; import blaze.collision.shapes.bzShape : bzShape; @@ -41,12 +42,19 @@ import openmelee.ships.ship : Ship, State; import openmelee.ai.utilities; +import openmelee.ai.ai : Threat; + +alias LinkedList!(Ship) ObjectList; class Steer -{ +{ + + ObjectList objectList; + // Constructor: initializes state - this (Ship ship) - { + this (Ship ship, ObjectList objectList) + { + this.objectList = objectList; m_ship = ship; m_body = ship.rBody; } @@ -132,250 +140,79 @@ bzVec2 avoidance = obstacle.steerToAvoid (this, minTimeToCollision); return avoidance; } - - // avoids all obstacles in an ObstacleGroup */ - - bzVec2 steerToAvoidObstacles (float minTimeToCollision, bzBody obstacles) { - - bzVec2 avoidance; - PathIntersection nearest, next; - float minDistanceToCollision = 10; //minTimeToCollision * m_speed; - - next.intersect = false; - nearest.intersect = false; - - // test all obstacles for intersection with my forward axis, - // select the one whose point of intersection is nearest - for (bzBody o = obstacles; o; o = o.next) { - - if(o is m_body) continue; - - // This code which presumes the obstacle is spherical - findNextIntersectionWithSphere(o, next); - - if (!nearest.intersect || (next.intersect && next.distance < nearest.distance)) { - nearest = next; - } - } - - // when a nearest intersection was found - if (nearest.intersect && (nearest.distance < minDistanceToCollision)) { - // compute avoidance steering force: take offset from obstacle to me, - // take the component of that which is lateral (perpendicular to my - // forward direction), set length to maxForce, add a bit of forward - // component (in capture the flag, we never want to slow down) - bzVec2 offset = m_position - nearest.obstacle.position; - avoidance = perpendicularComponent(offset, m_forward); - avoidance.normalize; - avoidance = m_body.localPoint(avoidance); - ///avoidance *= m_maxForce; - //avoidance += m_forward * m_maxForce * 0.75f; - } - - auto state = cast(State) m_body.userData; - state.avoid = avoidance; - return avoidance; - } - bzVec2 getSteering(bzBody obstacles) { + // Steer to avoid + void collisionThreat(inout Threat threat, float maxLookAhead = 10.0f) { // 1. Find the target that’s closest to collision - + float radius = m_radius; - float rad; - // Store the first collision time - float shortestTime = 0.5; + float rad = 0.0f; + float shortestTime = float.max; + + // Loop through each target + foreach(obstacle; objectList) { - // Store the target that collides then, and other data - // that we will need and can avoid recalculating - bzBody firstTarget = null; - float firstMinSeparation = 0; - float firstDistance = 0; - bzVec2 firstRelativePos; - bzVec2 firstRelativeVel; - bzVec2 relativePos; - - // Loop through each target - for (bzBody target = obstacles; target; target = target.next) { - + bzBody target = obstacle.rBody; + if(target is m_body) continue; // Calculate the time to collision - relativePos = m_body.localPoint(target.position); // - m_position; - bzVec2 relativeVel = target.linearVelocity - m_velocity; + bzVec2 relativePos = target.position - m_position; + bzVec2 relativeVel = m_velocity - target.linearVelocity; float relativeSpeed = relativeVel.length; - float timeToCollision = bzDot(relativePos, relativeVel) / + // Time to closest point of approach + float timeToCPA = bzDot(relativePos, relativeVel) / (relativeSpeed * relativeSpeed); - - // Check if it is going to be a collision at all + + // Threat is separating + if(timeToCPA < 0) { + continue; + } + float distance = relativePos.length; - float minSeparation = distance - relativeSpeed * shortestTime; + + // Clamp look ahead time + timeToCPA = bzClamp(timeToCPA, 0, maxLookAhead); - float eRad; - for (bzShape s = target.shapeList; s; s = s.next) { - if(s.sweepRadius > eRad) { - eRad = s.sweepRadius; - } - } + // Calculate closest point of approach + bzVec2 cpa = m_position + m_velocity * timeToCPA; + bzVec2 eCpa = target.position + target.linearVelocity * timeToCPA; + relativePos = (eCpa - cpa); + float dCPA = relativePos.length; - if (minSeparation > radius + eRad) continue; + // No collision + if (dCPA > radius + obstacle.state.radius) continue; - // Check if it is the shortest - if (timeToCollision > 0 && timeToCollision < shortestTime) { - - // Store the time, target and other data - shortestTime = timeToCollision; - firstTarget = target; - firstMinSeparation = minSeparation; - firstDistance = distance; - firstRelativePos = relativePos; - firstRelativeVel = relativeVel; - rad = eRad; + // Check if it's the closest collision threat + if (timeToCPA < shortestTime && dCPA < threat.minSeparation) { + shortestTime = timeToCPA; + threat.target = obstacle; + threat.distance = distance; + threat.relativePos = relativePos; + threat.relativeVel = relativeVel; + threat.minSeparation = dCPA; + rad = obstacle.state.radius; } } // 2. Calculate the steering // If we have no target, then exit - if(!firstTarget) return bzVec2.zeroVect; - - Stdout(shortestTime).newline; + if(!threat.target) return; // If we’re going to hit exactly, or if we’re already // colliding, then do the steering based on current // position. - if(firstMinSeparation <= 0 || firstDistance < radius + rad) { - relativePos = firstTarget.position - m_position; - } else { + //if(threat.minSeparation < m_radius || threat.distance < radius + rad) { + //threat.steering = m_position - threat.target.state.position; + //} else { // Otherwise calculate the future relative position: - relativePos = firstRelativePos + - firstRelativeVel * shortestTime; - } - - // Avoid the target - bzVec2 steering = relativePos; - steering.normalize(); - //steering.linear = relativePos * maxAcceleration - - return steering; + threat.steering = threat.relativePos; + //} } - bzVec2 avoid(float maxLookAhead, bzBody obstacles) { - - float avoidMargin = 1.0f; - float maxLookahead = maxLookAhead * m_speed; - - // Make sure we're moving - if (m_velocity.length > 0) - { - for (bzBody o = obstacles; o; o = o.next) { - - if(o is m_body) continue; - - // Find the distance from the line we're moving along to the obstacle. - bzVec2 movementNormal = m_velocity; - movementNormal.normalize(); - bzVec2 characterToObstacle = o.position - m_position; - - real distanceSquared = bzDot(characterToObstacle, movementNormal); - distanceSquared = characterToObstacle.lengthSquared - distanceSquared*distanceSquared; - - // Check for collision - float oRad = 0; - for (bzShape s = o.shapeList; s; s = s.next) { - if(s.sweepRadius > oRad) { - oRad = s.sweepRadius; - } - } - - real radius = oRad + avoidMargin; - if (distanceSquared < radius*radius) - { - // Find how far along our movement vector the closest pass is - real distanceToClosest = bzDot(characterToObstacle, movementNormal); - - // Make sure this isn't behind us and is closer than our lookahead. - if (distanceToClosest > 0 && distanceToClosest < maxLookahead) - { - // Find the closest point - bzVec2 closestPoint = o.position + movementNormal * distanceToClosest; - - // Find the point of avoidance - bzVec2 target = o.position + (closestPoint - o.position).length * radius; - - target -= m_position; - - auto state = cast(State) m_body.userData; - state.avoid = m_body.localPoint(target); - - return target; - } - } - } - } - - auto state = cast(State) m_body.userData; - state.avoid = bzVec2.zeroVect; - - return bzVec2.zeroVect; - - } - - void findNextIntersectionWithSphere(bzBody obs, - inout PathIntersection intersection) { - - // This routine is based on the Paul Bourke's derivation in: - // Intersection of a Line and a Sphere (or circle) - // http://local.wasp.uwa.edu.au/~pbourke/geometry/sphereline/raysphere.c - - float b, c, d, p, q, s; - bzVec2 lc; - - // initialize pathIntersection object - intersection.intersect = false; - intersection.obstacle = obs; - - // find "local center" (lc) of sphere in coordinate space - lc = m_body.localPoint(obs.position); - - // computer line-sphere intersection parameters - b = 0; - - // Find radius of obstacle - float obsRadius = 0; - for (bzShape shape = obs.shapeList; shape; shape = shape.next) { - if(shape.sweepRadius > obsRadius) { - obsRadius = shape.sweepRadius; - } - } - - c = square(lc.x) + square(lc.y) - square(obsRadius + m_radius); - d = (b * b) - (4 * c); - - // when the path does not intersect the sphere - if (d < 0) return; - - // otherwise, the path intersects the sphere in two points with - // parametric coordinates of "p" and "q". - // (If "d" is zero the two points are coincident, the path is tangent) - s = sqrt(d); - p = (-b + s) * 0.5f; - q = (-b - s) * 0.5f; - - // both intersections are behind us, so no potential collisions - if ((p < 0) && (q < 0)) return; - - // at least one intersection is in front of us - intersection.intersect = true; - intersection.distance = - ((p > 0) && (q > 0)) ? - // both intersections are in front of us, find nearest one - ((p < q) ? p : q) : - // otherwise only one intersections is in front, select it - ((p > 0) ? p : q); - } - /* // ------------------------------------------------------------------------ // Unaligned collision avoidance behavior: avoid colliding with other @@ -522,14 +359,7 @@ return (myFinal - otherFinal).length; } - // ------------------------------------------------------------------------ - // pursuit of another vehicle ( version with ceiling on prediction time) - - bzVec2 steerForPursuit (State quarry) { - return steerForPursuit (quarry, float.max); - } - - bzVec2 steerForPursuit (State quarry, float maxPredictionTime) { + bzVec2 targetEnemy (State quarry, float maxPredictionTime) { // offset from this to quarry, that distance, unit vector toward quarry bzVec2 offset = quarry.position - m_position;
--- a/melee/melee.d Thu Mar 26 20:35:58 2009 -0400 +++ b/melee/melee.d Fri Mar 27 16:05:24 2009 -0400 @@ -31,6 +31,7 @@ module openmelee.melee.melee; import tango.io.Stdout; +import tango.util.container.LinkedList : LinkedList; version(distrib) import tango.io.vfs.ZipFolder; import tango.time.StopWatch; @@ -58,6 +59,8 @@ const ITERS_PER_SECOND = 100; const k_maxContactPoints = 100; +alias LinkedList!(Ship) ObjectList; + // Melee settings struct Settings { float hz = 60; @@ -92,6 +95,7 @@ class Melee { + ObjectList objectList; Settings settings; float timeStep; const bzVec2 gravity = bzVec2(0.0f, 0.0f); @@ -100,9 +104,10 @@ AI ai; Human human; + Ship ship1; Ship ship2; - Planet planet; + Ship planet; bool running; @@ -115,6 +120,8 @@ int pointCount; this() { + + objectList = new ObjectList; } void init() { @@ -125,14 +132,18 @@ scope renderer = new Renderer; m_boundaryListener = new BoundaryListener(this); - m_contactListener = new ContactListener(this); initWorld(); running = true; draw = new Render(world, ship1, ship2, settings); human = new Human(ship1); - ai = new AI(ship2, world); - + + objectList.add(planet); + objectList.add(ship1); + objectList.add(ship2); + + ai = new AI(ship2, objectList); + gui.begin(cfg).retained; gui.push(`main`); GLViewport(`glview`).renderingHandler(&draw.draw) @@ -190,13 +201,12 @@ void initWorld() { // Define world boundaries - worldAABB.lowerBound.set(-100.0f, -150.0f); - worldAABB.upperBound.set(100.0f, 150.0f); + worldAABB.lowerBound.set(-400.0f, -250.0f); + worldAABB.upperBound.set(400.0f, 250.0f); world = new bzWorld(worldAABB, gravity, allowSleep); world.boundaryListener = m_boundaryListener; - world.contactListener = m_contactListener; - ship1 = new UrQuan(world); - ship2 = new Orz(world); + ship2 = new UrQuan(world); + ship1 = new Orz(world); ship2.rBody.angle = 3.14159265/4; planet = new Planet(world); //auto asteroids = new Asteroid(world);
--- a/render/render.d Thu Mar 26 20:35:58 2009 -0400 +++ b/render/render.d Fri Mar 27 16:05:24 2009 -0400 @@ -386,16 +386,7 @@ // Draw dynamic bodies if (settings.drawShapes) { for (bzBody b = world.bodyList; b; b = b.next) { - - if(b.userData) { - bzVec2 center = b.position; - auto state = cast(State) b.userData; - vec2 avoid = vec2.from(state.avoid); - gl.drawCircle(vec2.from(center), state.radius); - if(avoid != vec2(0,0)) { - gl.drawSegment(vec2.from(b.position), avoid, Color(0, 1, 0)); - } - } + for (bzShape shape = b.shapeList; shape; shape = shape.next) {
--- a/ships/asteroids.d Thu Mar 26 20:35:58 2009 -0400 +++ b/ships/asteroids.d Fri Mar 27 16:05:24 2009 -0400 @@ -75,13 +75,15 @@ bzVec2 position = bzVec2(x , y); float angle = randomRange(-PI, PI); bd = new bzBodyDef(position, angle); + bd.allowFreeze = false; + bd.allowSleep = false; rBody = world.createBody(bd); rBody.createShape(sd1); rBody.createShape(sd2); rBody.setMassFromShapes(); auto attractor = new bzAttractor(rBody, center, strength, minRadius, maxRadius); world.addForce(attractor); - rBody.linearVelocity = bzVec2(x*20, y*20); + rBody.linearVelocity = bzVec2(x*0.1, y*0.1); } } @@ -101,13 +103,15 @@ bzVec2 position = bzVec2(x , y); float angle = randomRange(-PI, PI); bd = new bzBodyDef(position, angle); + bd.allowFreeze = false; + bd.allowSleep = false; rBody = world.createBody(bd); rBody.createShape(sd1); rBody.createShape(sd2); rBody.setMassFromShapes(); auto attractor = new bzAttractor(rBody, center, strength, minRadius, maxRadius); world.addForce(attractor); - rBody.linearVelocity = bzVec2(x*20, y*20); + rBody.linearVelocity = bzVec2(x*0.1, y*0.1); } } @@ -141,13 +145,15 @@ bzVec2 position = bzVec2(x , y); float angle = 0.0f; bd = new bzBodyDef(position, angle); + bd.allowFreeze = false; + bd.allowSleep = false; rBody = world.createBody(bd); rBody.createShape(sd1); rBody.createShape(sd2); rBody.setMassFromShapes(); auto attractor = new bzAttractor(rBody, center, strength, minRadius, maxRadius); world.addForce(attractor); - rBody.linearVelocity = bzVec2(x, y); + rBody.linearVelocity = bzVec2(x*0.1, y*0.1); } } }
--- a/ships/orz.d Thu Mar 26 20:35:58 2009 -0400 +++ b/ships/orz.d Fri Mar 27 16:05:24 2009 -0400 @@ -57,6 +57,7 @@ bodyDef.position = bzVec2(20,15); bodyDef.angle = PI/2; bodyDef.allowFreeze = false; + bodyDef.allowSleep = false; rBody = world.createBody(bodyDef); float density = 5.0f; @@ -91,7 +92,7 @@ shapes.add(rBody.createShape(bWing)); rBody.setMassFromShapes(); - //setPlanetGravity(); + setPlanetGravity(); calcRadius(); } }
--- a/ships/planet.d Thu Mar 26 20:35:58 2009 -0400 +++ b/ships/planet.d Fri Mar 27 16:05:24 2009 -0400 @@ -36,20 +36,15 @@ import blaze.collision.shapes.bzCircle : bzCircleDef; import blaze.common.bzMath: bzVec2; -import openmelee.ships.ship: State; +import openmelee.ships.ship: Ship, State; -class Planet +class Planet : Ship { - bzWorld world; - bzBody rBody; - this(bzWorld world) { - this.world = world; + super(world); init(); - auto state = new State; - state.radius = rBody.shapeList.sweepRadius; - rBody.userData = state; + calcRadius(); } void init() {
--- a/ships/ship.d Thu Mar 26 20:35:58 2009 -0400 +++ b/ships/ship.d Fri Mar 27 16:05:24 2009 -0400 @@ -41,7 +41,7 @@ alias LinkedList!(bzShape) ShapeList; -class State +struct State { bzVec2 position; bzVec2 velocity; @@ -52,11 +52,12 @@ float speed = 0; float maxForce = 0; bool turn; - float radius = 0.0f; float enemyAngle = 0.0f; bzVec2 avoid; + Ship enemy; + bzVec2 predictFuturePosition(float dt) { return (position + velocity * dt); } @@ -82,7 +83,6 @@ this(bzWorld world) { this.world = world; shapes = new ShapeList; - state = new State; } void thrust() { @@ -127,12 +127,10 @@ } void calcRadius() { - rBody.userData = state; for (bzShape s = rBody.shapeList; s; s = s.next) { if(s.sweepRadius > state.radius) { state.radius = s.sweepRadius; } } } - }