# HG changeset patch # User Mason Green # Date 1237728924 14400 # Node ID d998bf1b065479478f6923cfe1349c0f31c85698 # Parent bdca08c79cf3512d8beb6a1a53642126c61dfa40 Added utilities and AI; fixed steer diff -r bdca08c79cf3 -r d998bf1b0654 ai.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ai.d Sun Mar 22 09:35:24 2009 -0400 @@ -0,0 +1,55 @@ +/* + * Copyright (c) 2009, Mason Green (zzzzrrr) + * http://www.dsource.org/projects/openmelee + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of the polygonal nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +module openmelee.ai; + +import openmelee.steer : Steer; +import openmelee.ship : Ship; + +class AI { + + + Steer steer; + Ship ship; + float maxPredictionTime = 0; + + this(Ship ship) { + this.ship = ship; + steer = new Steer(ship); + } + + void move(Ship enemy) { + + steer.update(); + steer.steerForPursuit(enemy.state, maxPredictionTime); + + } + +} diff -r bdca08c79cf3 -r d998bf1b0654 main.d --- a/main.d Sun Mar 22 08:03:43 2009 -0400 +++ b/main.d Sun Mar 22 09:35:24 2009 -0400 @@ -45,6 +45,7 @@ import openmelee.melee; import openmelee.render; +import openmelee.ai; const ITERS_PER_SECOND = 60; @@ -56,7 +57,8 @@ scope cfg = loadHybridConfig("./gui.cfg"); scope renderer = new Renderer; auto whut = new Render(&settings); - + auto ai = new AI(whut.ship2); + gui.begin(cfg).retained; gui.push(`main`); GLViewport(`glview`).renderingHandler(&whut.draw) diff -r bdca08c79cf3 -r d998bf1b0654 melee.d --- a/melee.d Sun Mar 22 08:03:43 2009 -0400 +++ b/melee.d Sun Mar 22 09:35:24 2009 -0400 @@ -34,7 +34,6 @@ import Integer = tango.text.convert.Integer; import tango.math.Math; -import tango.math.random.Kiss; import xf.hybrid.Event; import xf.input.KeySym; @@ -144,11 +143,6 @@ } } -T randomRange(T = int) (T min, T max) -{ - return min + Kiss.instance.natural() % (max + 1 - min); -} - class Melee { diff -r bdca08c79cf3 -r d998bf1b0654 ship.d --- a/ship.d Sun Mar 22 08:03:43 2009 -0400 +++ b/ship.d Sun Mar 22 09:35:24 2009 -0400 @@ -41,6 +41,21 @@ alias LinkedList!(bzShape) ShapeList; +struct State +{ + bzVec2 position; + bzVec2 velocity; + bzVec2 up; + bzVec2 side; + bzVec2 forward; + float speed = 0; + float maxForce = 0; + + bzVec2 predictFuturePosition(float dt) { + return (position + velocity * dt); + } +} + abstract class Ship { bzWorld world; @@ -50,7 +65,8 @@ bzVec2 turnForce; bzVec2 leftTurnPoint; bzVec2 rightTurnPoint; - + State state; + float maxLinVel = 100; float maxAngVel = 2; @@ -78,7 +94,6 @@ } void setGravity() { - float minRadius = 0.1; float maxRadius = 10; float strength = 3.5; @@ -88,7 +103,6 @@ } void limitVelocity() { - float vx = rBody.linearVelocity.x; float vy = rBody.linearVelocity.y; float av = rBody.angularVelocity; @@ -96,4 +110,14 @@ rBody.linearVelocity.y = bzClamp(vy, -maxLinVel, maxLinVel); rBody.angularVelocity = bzClamp(av, -maxAngVel, maxAngVel); } + + void updateState() { + state.velocity = rBody.linearVelocity; + state.speed = state.velocity.length; + state.position = rBody.position; + bzVec2 heading = engineForce.rotate(rBody.angle); + heading.normalize(); + state.forward = heading; + } + } diff -r bdca08c79cf3 -r d998bf1b0654 steer.d --- a/steer.d Sun Mar 22 08:03:43 2009 -0400 +++ b/steer.d Sun Mar 22 09:35:24 2009 -0400 @@ -1,84 +1,73 @@ -// ---------------------------------------------------------------------------- -// -// -// OpenSteer -- Steering Behaviors for Autonomous Characters -// -// Copyright (c) 2002-2003, Sony Computer Entertainment America -// Original author: Craig Reynolds -// -// Permission is hereby granted, free of charge, to any person obtaining a -// copy of this software and associated documentation files (the "Software"), -// to deal in the Software without restriction, including without limitation -// the rights to use, copy, modify, merge, publish, distribute, sublicense, -// and/or sell copies of the Software, and to permit persons to whom the -// Software is furnished to do so, subject to the following conditions: -// -// The above copyright notice and this permission notice shall be included in -// all copies or substantial portions of the Software. -// -// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL -// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING -// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER -// DEALINGS IN THE SOFTWARE. -// -// -// ---------------------------------------------------------------------------- -// -// -// SteerLibraryMixin -// -// This mixin (class with templated superclass) adds the "steering library" -// functionality to a given base class. SteerLibraryMixin assumes its base -// class supports the Ship interface. -// -// 10-04-04 bk: put everything into the OpenSteer namespace -// 02-06-03 cwr: create mixin (from "SteerMass") -// 06-03-02 cwr: removed TS dependencies -// 11-21-01 cwr: created -// -// -// ---------------------------------------------------------------------------- +/* + * Copyright (c) 2009, Mason Green (zzzzrrr) + * http://www.dsource.org/projects/openmelee + * Based on OpenSteer, Copyright (c) 2002-2003, Sony Computer Entertainment America + * Original author: Craig Reynolds + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of the polygonal nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ module openmelee.steer; + +import blaze.common.bzMath: bzDot, bzClamp, bzVec2; +import openmelee.ship : Ship, State; +import openmelee.utilities; class Steer { // Constructor: initializes state - this () + this (Ship ship) { - // set inital state - reset (); + m_ship = ship; } // reset state void reset () { // initial state of wander behavior - wanderSide = 0; - wanderUp = 0; + m_wanderSide = 0; + m_wanderUp = 0; } - void update(bzBody rBody) { - - m_position = rBody.position; - m_velocity = rBody.linearVelocity; + void update() { + m_position = m_ship.state.position; + m_velocity = m_ship.state.velocity; + m_speed = m_ship.state.speed; + m_maxForce = m_ship.state.maxForce; } // -------------------------------------------------- steering behaviors - // Wander behavior - float wanderSide; - float wanderUp; - bzVec2 steerForWander (float dt) { - // random walk wanderSide and wanderUp between -1 and +1 + // random walk m_wanderSide and m_wanderUp between -1 and +1 float speed = 12 * dt; // maybe this (12) should be an argument? - wanderSide = scalarRandomWalk (wanderSide, speed, -1, +1); - wanderUp = scalarRandomWalk (wanderUp, speed, -1, +1); + m_wanderSide = scalarRandomWalk (m_wanderSide, speed, -1, +1); + m_wanderUp = scalarRandomWalk (m_wanderUp, speed, -1, +1); // return a pure lateral steering vector: (+/-Side) + (+/-Up) - return (side() * wanderSide) + (up() * wanderUp); + return (m_side * m_wanderSide) + (m_up * m_wanderUp); } // Seek behavior @@ -92,11 +81,12 @@ bzVec2 desiredVelocity = m_position - target; return desiredVelocity - m_velocity; } - + + /* // xxx proposed, experimental new seek/flee [cwr 9-16-02] bzVec2 xxxsteerForFlee (bzVec2 target) { bzVec2 offset = m_position - target; - bzVec2 desiredVelocity = offset.truncateLength (maxSpeed ()); + bzVec2 desiredVelocity = bzClamp(offset.truncateLength (maxSpeed ()); return desiredVelocity - m_velocity; } @@ -105,8 +95,10 @@ bzVec2 offset = target - m_position; bzVec2 desiredVelocity = offset.truncateLength (maxSpeed ()); //xxxnew return desiredVelocity - m_velocity; - } - + } + */ + + /* // ------------------------------------------------------------------------ // Obstacle Avoidance behavior // @@ -130,7 +122,7 @@ bzVec2 avoidance; PathIntersection nearest, next; - float minDistanceToCollision = minTimeToCollision * speed(); + float minDistanceToCollision = minTimeToCollision * speed; next.intersect = false; nearest.intersect = false; @@ -161,10 +153,10 @@ // 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.center; - avoidance = offset.perpendicularComponent (forward()); - avoidance = avoidance.normalize (); - avoidance *= maxForce (); - avoidance += forward() * maxForce () * 0.75; + avoidance = offset.perpendicularComponent (m_forward()); + avoidance = avoidance.normalize; + avoidance *= maxForce; + avoidance += m_forward * maxForce * 0.75; } return avoidance; @@ -204,7 +196,7 @@ if (other != this) { // avoid when future positions are this close (or less) - float collisionDangerThreshold = radius() * 2; + float collisionDangerThreshold = radius * 2; // predicted time until nearest approach of "this" and "other" float time = predictNearestApproachTime (other); @@ -233,7 +225,7 @@ if (threat) { // parallel: +1, perpendicular: 0, anti-parallel: -1 - float parallelness = forward.dot(threat.forward); + float parallelness = m_forward.dot(threat.forward); float angle = 0.707f; if (parallelness < -angle) @@ -241,7 +233,7 @@ // anti-parallel "head on" paths: // steer away from future threat position bzVec2 offset = xxxThreatPositionAtNearestApproach - m_position; - float sideDot = offset.dot(side()); + float sideDot = offset.dot(m_side()); steer = (sideDot > 0) ? -1.0f : 1.0f; } else @@ -250,28 +242,29 @@ { // parallel paths: steer away from threat bzVec2 offset = threat.position - m_position; - float sideDot = offset.dot(side()); + float sideDot = bzDot(offset, m_side); steer = (sideDot > 0) ? -1.0f : 1.0f; } else { // perpendicular paths: steer behind threat // (only the slower of the two does this) - if (threat.speed() <= speed()) + if (threat.speed() <= speed) { - float sideDot = side().dot(threat.velocity); + float sideDot = bzDot(m_side, threat.velocity); steer = (sideDot > 0) ? -1.0f : 1.0f; } } } } - return side() * steer; + return m_side() * steer; } - + */ + // Given two vehicles, based on their current positions and velocities, // determine the time until nearest approach - float predictNearestApproachTime (Ship other) { + float predictNearestApproachTime (State other) { // imagine we are at the origin with no velocity, // compute the relative velocity of the other vehicle @@ -295,7 +288,7 @@ // find distance from its path to origin (compute offset from // other to us, find length of projection onto path) bzVec2 relPosition = m_position - other.position; - float projection = relTangent.dot(relPosition); + float projection = bzDot(relTangent, relPosition); return projection / relSpeed; } @@ -303,48 +296,40 @@ // Given the time until nearest approach (predictNearestApproachTime) // determine position of each vehicle at that time, and the distance // between them - float computeNearestApproachPositions (Ship other, float time) { + float computeNearestApproachPositions (State other, float time) { - bzVec2 myTravel = forward * speed * time; + bzVec2 myTravel = m_forward * m_speed * time; bzVec2 otherTravel = other.forward * other.speed * time; bzVec2 myFinal = m_position + myTravel; bzVec2 otherFinal = other.position + otherTravel; - // xxx for annotation - ourPositionAtNearestApproach = myFinal; - hisPositionAtNearestApproach = otherFinal; - - return bzVec2::distance (myFinal, otherFinal); - } - - // otherwise return zero - return bzVec2.zeroVect; + return (myFinal - otherFinal).length; } // ------------------------------------------------------------------------ // pursuit of another vehicle ( version with ceiling on prediction time) - bzVec2 steerForPursuit (Ship quarry) { - return steerForPursuit (quarry, FLT_MAX); + bzVec2 steerForPursuit (State quarry) { + return steerForPursuit (quarry, float.max); } - bzVec2 steerForPursuit (Ship quarry, float maxPredictionTime) { + bzVec2 steerForPursuit (State quarry, float maxPredictionTime) { // offset from this to quarry, that distance, unit vector toward quarry bzVec2 offset = quarry.position - m_position; - float distance = offset.length (); + float distance = offset.length; bzVec2 unitOffset = offset / distance; // how parallel are the paths of "this" and the quarry // (1 means parallel, 0 is pependicular, -1 is anti-parallel) - float parallelness = forward.dot(quarry.forward()); + float parallelness = bzDot(m_forward , quarry.forward); // how "forward" is the direction to the quarry // (1 means dead ahead, 0 is directly to the side, -1 is straight back) - float forwardness = forward.dot(unitOffset); + float forwardness = bzDot(m_forward , unitOffset); - float directTravelTime = distance / speed; + float directTravelTime = distance / m_speed; int f = intervalComparison (forwardness, -0.707f, 0.707f); int p = intervalComparison (parallelness, -0.707f, 0.707f); @@ -360,7 +345,6 @@ { case +1: // ahead, parallel timeFactor = 4; - color = gBlack; break; case 0: // ahead, perpendicular timeFactor = 1.8f; @@ -407,14 +391,14 @@ float etl = (et > maxPredictionTime) ? maxPredictionTime : et; // estimated position of quarry at intercept - bzVec2 target = quarry.predictFuturePosition (etl); + bzVec2 target = quarry.predictFuturePosition(etl); return steerForSeek (target); } // ------------------------------------------------------------------------ // evasion of another vehicle - bzVec2 steerForEvasion (Ship menace, float maxPredictionTime) { + bzVec2 steerForEvasion (State menace, float maxPredictionTime) { // offset from this to menace, that distance, unit vector toward menace bzVec2 offset = menace.position - m_position; @@ -432,9 +416,9 @@ // tries to maintain a given speed, returns a maxForce-clipped steering // force along the forward/backward axis bzVec2 steerForTargetSpeed (float targetSpeed) { - float mf = maxForce(); - float speedError = targetSpeed - speed (); - return forward () * clip (speedError, -mf, +mf); + float mf = m_maxForce; + float speedError = targetSpeed - m_speed; + return m_forward * bzClamp(speedError, -mf, +mf); } @@ -445,26 +429,40 @@ bool isAhead (bzVec2 target, float cosThreshold) { - bzVec2 targetDirection = (target - m_position ()).normalize (); - return forward().dot(targetDirection) > cosThreshold; + bzVec2 targetDirection = target - m_position; + targetDirection.normalize(); + return bzDot(m_forward, targetDirection) > cosThreshold; } bool isAside (bzVec2 target, float cosThreshold) { - bzVec2 targetDirection = (target - m_position ()).normalize (); - float dp = forward().dot(targetDirection); - return (dp < cosThreshold) (dp > -cosThreshold); + bzVec2 targetDirection = target - m_position; + targetDirection.normalize(); + float dp = bzDot(m_forward, targetDirection); + return (dp < cosThreshold) && (dp > -cosThreshold); } bool isBehind (bzVec2 target, float cosThreshold) { - bzVec2 targetDirection = (target - m_position).normalize (); - return forward().dot(targetDirection) < cosThreshold; + bzVec2 targetDirection = target - m_position; + targetDirection.normalize(); + return bzDot(m_forward, targetDirection) < cosThreshold; } private: + Ship m_ship; + bzVec2 m_position; bzVec2 m_velocity; - + bzVec2 m_up; + bzVec2 m_side; + bzVec2 m_forward; + + float m_speed = 0; + float m_maxForce = 0; + + // Wander behavior + float m_wanderSide; + float m_wanderUp; } diff -r bdca08c79cf3 -r d998bf1b0654 utilities.d --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/utilities.d Sun Mar 22 09:35:24 2009 -0400 @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2009, Mason Green (zzzzrrr) + * http://www.dsource.org/projects/openmelee + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of the polygonal nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +module openmelee.utilities; + +import tango.math.random.Kiss : Kiss; + +float scalarRandomWalk(float initial, float walkspeed, float min, float max) { + + float next = initial + (((randomRange(0, 1) * 2) - 1) * walkspeed); + if (next < min) return min; + if (next > max) return max; + return next; +} + +// ---------------------------------------------------------------------------- +// classify a value relative to the interval between two bounds: +// returns -1 when below the lower bound +// returns 0 when between the bounds (inside the interval) +// returns +1 when above the upper bound +int intervalComparison(float x, float lowerBound, float upperBound) +{ + if (x < lowerBound) return -1; + if (x > upperBound) return +1; + return 0; +} + +T randomRange(T = int) (T min, T max) +{ + return min + Kiss.instance.natural() % (max + 1 - min); +}