# HG changeset patch # User zzzzrrr # Date 1238006687 14400 # Node ID 08ddf9e71b88f329fe324811462aa3e2a0b6f9d6 # Parent 7f74e064dad5da1011d45ffdb7ffd5944f8b3a12 steer to avoid diff -r 7f74e064dad5 -r 08ddf9e71b88 ai/ai.d --- a/ai/ai.d Wed Mar 25 11:28:25 2009 -0400 +++ b/ai/ai.d Wed Mar 25 14:44:47 2009 -0400 @@ -34,6 +34,7 @@ import tango.math.Math : atan2, abs, PI; import blaze.common.bzMath: bzVec2, bzClamp; +import blaze.bzWorld : bzWorld; import openmelee.ai.steer : Steer; import openmelee.ships.ship : Ship; @@ -44,8 +45,11 @@ Steer steer; Ship ship; float maxPredictionTime = 0.1f; - - this(Ship ship) { + bzWorld m_world; + bzVec2 st; + + this(Ship ship, bzWorld world) { + m_world = world; this.ship = ship; steer = new Steer(ship); } @@ -53,11 +57,20 @@ void move(Ship enemy) { // Elementary steering AI + steer.update(); + st = steer.steerToAvoidObstacles(5, m_world.bodyList); - steer.update(); - bzVec2 st; - st = steer.steerForPursuit(enemy.state, maxPredictionTime); - ship.state.target = st; + if(st == bzVec2.zeroVect) { + st = steer.steerForPursuit(enemy.state, maxPredictionTime); + chase(enemy); + } else { + avoid(); + } + } + + void chase(Ship enemy) { + + ship.state.target = st; st = ship.rBody.localPoint(st); float x = st.x; float y = st.y; @@ -84,5 +97,26 @@ ship.thrust(); } } + + void avoid() { + + st = ship.rBody.localPoint(st); + float x = st.x; + float y = st.y; + st = -bzVec2(y,-x); + float angle = atan2(st.x, st.y); + + if(st.x >= 0) { + ship.turnRight(); + } else { + ship.turnLeft(); + } + + ship.state.turn = true; + + if(abs(angle) > PI/4) { + ship.thrust(); + } + } } diff -r 7f74e064dad5 -r 08ddf9e71b88 ai/steer.d --- a/ai/steer.d Wed Mar 25 11:28:25 2009 -0400 +++ b/ai/steer.d Wed Mar 25 14:44:47 2009 -0400 @@ -32,7 +32,11 @@ */ module openmelee.ai.steer; +import tango.io.Stdout : Stdout; + import blaze.common.bzMath: bzDot, bzClamp, bzVec2; +import blaze.collision.shapes.bzShape : bzShape; +import tango.math.Math : sqrt; import blaze.dynamics.bzBody: bzBody; import openmelee.ships.ship : Ship, State; @@ -43,7 +47,16 @@ // Constructor: initializes state this (Ship ship) { - m_ship = ship; + m_ship = ship; + m_body = ship.rBody; + m_radius = 0.0f; + + // Find radius of body + for (bzShape s = m_body.shapeList; s; s = s.next) { + if(s.sweepRadius > m_radius) { + m_radius = s.sweepRadius; + } + } } struct PathIntersection @@ -135,37 +148,95 @@ bzVec2 avoidance; PathIntersection nearest, next; float minDistanceToCollision = 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; o; o = o.next) { + 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); + 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)) { + Stdout("Distance: ")(nearest.distance).newline; // 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 = Vector3Helpers.PerpendicularComponent(offset, this.Forward); + avoidance = perpendicularComponent(offset, m_forward); avoidance.normalize; - avoidance *= m_maxForce; - avoidance += m_forward * m_maxForce * 0.75f; + //avoidance *= m_maxForce; + //avoidance += m_forward * m_maxForce * 0.75f; } return avoidance; } + 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://www.swin.edu.au/astronomy/pbourke/geometry/sphereline/ + + 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 boid's 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 @@ -463,6 +534,8 @@ bzVec2 m_up; bzVec2 m_side; bzVec2 m_forward; + float m_radius; + bzBody m_body; float m_speed = 0; float m_maxForce = 0; diff -r 7f74e064dad5 -r 08ddf9e71b88 ai/utilities.d --- a/ai/utilities.d Wed Mar 25 11:28:25 2009 -0400 +++ b/ai/utilities.d Wed Mar 25 14:44:47 2009 -0400 @@ -31,6 +31,7 @@ module openmelee.ai.utilities; import tango.math.random.Kiss : Kiss; +import blaze.common.bzMath : bzVec2, bzDot; float scalarRandomWalk(float initial, float walkspeed, float min, float max) { @@ -40,6 +41,19 @@ return next; } +// return component of vector perpendicular to a unit basis vector +// IMPORTANT NOTE: assumes "basis" has unit magnitude(length==1) +bzVec2 perpendicularComponent(bzVec2 vector, bzVec2 unitBasis) { + return (vector - parallelComponent(vector, unitBasis)); +} + +// return component of vector parallel to a unit basis vector +// IMPORTANT NOTE: assumes "basis" has unit magnitude (length == 1) +bzVec2 parallelComponent(bzVec2 vector, bzVec2 unitBasis) { + float projection = bzDot(vector, unitBasis); + return unitBasis * projection; +} + // ---------------------------------------------------------------------------- // classify a value relative to the interval between two bounds: // returns -1 when below the lower bound @@ -52,6 +66,10 @@ return 0; } +float square(float x) { + return x * x; +} + T randomRange(T = int) (T min, T max) { return min + Kiss.instance.natural() % (max + 1 - min); diff -r 7f74e064dad5 -r 08ddf9e71b88 melee/melee.d --- a/melee/melee.d Wed Mar 25 11:28:25 2009 -0400 +++ b/melee/melee.d Wed Mar 25 14:44:47 2009 -0400 @@ -119,7 +119,7 @@ draw = new Render(world, ship1, ship2, settings); human = new Human(ship1); - ai = new AI(ship2); + ai = new AI(ship2, world); gui.begin(cfg).retained; gui.push(`main`);