Mercurial > projects > openmelee
comparison steer.d @ 0:c10bc63824e7
Initial commit!
author | zzzzrrr <mason.green@gmail.com> |
---|---|
date | Fri, 20 Mar 2009 06:41:25 -0400 |
parents | |
children | a40d066ebbd1 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:c10bc63824e7 |
---|---|
1 // ---------------------------------------------------------------------------- | |
2 // | |
3 // | |
4 // OpenSteer -- Steering Behaviors for Autonomous Characters | |
5 // | |
6 // Copyright (c) 2002-2003, Sony Computer Entertainment America | |
7 // Original author: Craig Reynolds <craig_reynolds@playstation.sony.com> | |
8 // | |
9 // Permission is hereby granted, free of charge, to any person obtaining a | |
10 // copy of this software and associated documentation files (the "Software"), | |
11 // to deal in the Software without restriction, including without limitation | |
12 // the rights to use, copy, modify, merge, publish, distribute, sublicense, | |
13 // and/or sell copies of the Software, and to permit persons to whom the | |
14 // Software is furnished to do so, subject to the following conditions: | |
15 // | |
16 // The above copyright notice and this permission notice shall be included in | |
17 // all copies or substantial portions of the Software. | |
18 // | |
19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
20 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
21 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |
22 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
23 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING | |
24 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER | |
25 // DEALINGS IN THE SOFTWARE. | |
26 // | |
27 // | |
28 // ---------------------------------------------------------------------------- | |
29 // | |
30 // | |
31 // SteerLibraryMixin | |
32 // | |
33 // This mixin (class with templated superclass) adds the "steering library" | |
34 // functionality to a given base class. SteerLibraryMixin assumes its base | |
35 // class supports the Ship interface. | |
36 // | |
37 // 10-04-04 bk: put everything into the OpenSteer namespace | |
38 // 02-06-03 cwr: create mixin (from "SteerMass") | |
39 // 06-03-02 cwr: removed TS dependencies | |
40 // 11-21-01 cwr: created | |
41 // | |
42 // | |
43 // ---------------------------------------------------------------------------- | |
44 module melee.steer; | |
45 | |
46 class Steer | |
47 { | |
48 // Constructor: initializes state | |
49 this () | |
50 { | |
51 // set inital state | |
52 reset (); | |
53 } | |
54 | |
55 // reset state | |
56 void reset (void) | |
57 { | |
58 // initial state of wander behavior | |
59 wanderSide = 0; | |
60 wanderUp = 0; | |
61 | |
62 // default to non-gaudyPursuitAnnotation | |
63 gaudyPursuitAnnotation = false; | |
64 } | |
65 | |
66 // -------------------------------------------------- steering behaviors | |
67 | |
68 // Wander behavior | |
69 float wanderSide; | |
70 float wanderUp; | |
71 | |
72 bzVec2 steerForWander (float dt) { | |
73 // random walk wanderSide and wanderUp between -1 and +1 | |
74 float speed = 12 * dt; // maybe this (12) should be an argument? | |
75 wanderSide = scalarRandomWalk (wanderSide, speed, -1, +1); | |
76 wanderUp = scalarRandomWalk (wanderUp, speed, -1, +1); | |
77 | |
78 // return a pure lateral steering vector: (+/-Side) + (+/-Up) | |
79 return (side() * wanderSide) + (up() * wanderUp); | |
80 } | |
81 | |
82 // Seek behavior | |
83 bzVec2 steerForSeek (bzVec2 target) { | |
84 bzVec2 desiredVelocity = target - position; | |
85 return desiredVelocity - velocity; | |
86 } | |
87 | |
88 // Flee behavior | |
89 bzVec2 steerForFlee (bzVec2 target) { | |
90 bzVec2 desiredVelocity = position - target; | |
91 return desiredVelocity - velocity(); | |
92 } | |
93 | |
94 // xxx proposed, experimental new seek/flee [cwr 9-16-02] | |
95 bzVec2 xxxsteerForFlee (bzVec2 target) { | |
96 bzVec2 offset = position - target; | |
97 bzVec2 desiredVelocity = offset.truncateLength (maxSpeed ()); | |
98 return desiredVelocity - velocity(); | |
99 } | |
100 | |
101 bzVec2 xxxsteerForSeek (bzVec2 target) { | |
102 // bzVec2 offset = target - position; | |
103 bzVec2 offset = target - position; | |
104 bzVec2 desiredVelocity = offset.truncateLength (maxSpeed ()); //xxxnew | |
105 return desiredVelocity - velocity(); | |
106 } | |
107 | |
108 // ------------------------------------------------------------------------ | |
109 // Obstacle Avoidance behavior | |
110 // | |
111 // Returns a steering force to avoid a given obstacle. The purely | |
112 // lateral steering force will turn our vehicle towards a silhouette edge | |
113 // of the obstacle. Avoidance is required when (1) the obstacle | |
114 // intersects the vehicle's current path, (2) it is in front of the | |
115 // vehicle, and (3) is within minTimeToCollision seconds of travel at the | |
116 // vehicle's current velocity. Returns a zero vector value (bzVec2::zero) | |
117 // when no avoidance is required. | |
118 bzVec2 steerToAvoidObstacle (float minTimeToCollision, Obstacle obstacle) { | |
119 | |
120 bzVec2 avoidance = obstacle.steerToAvoid (this, minTimeToCollision); | |
121 // XXX more annotation modularity problems (assumes spherical obstacle) | |
122 if (avoidance != bzVec2::zero) | |
123 annotateAvoidObstacle (minTimeToCollision * speed()); | |
124 | |
125 return avoidance; | |
126 } | |
127 | |
128 // avoids all obstacles in an ObstacleGroup | |
129 | |
130 bzVec2 steerToAvoidObstacles (float minTimeToCollision, | |
131 ObstacleGroup obstacles) { | |
132 | |
133 bzVec2 avoidance; | |
134 PathIntersection nearest, next; | |
135 float minDistanceToCollision = minTimeToCollision * speed(); | |
136 | |
137 next.intersect = false; | |
138 nearest.intersect = false; | |
139 | |
140 // test all obstacles for intersection with my forward axis, | |
141 // select the one whose point of intersection is nearest | |
142 for (ObstacleIterator o = obstacles.begin(); o != obstacles.end(); o++) | |
143 { | |
144 // xxx this should be a generic call on Obstacle, rather than | |
145 // xxx this code which presumes the obstacle is spherical | |
146 findNextIntersectionWithSphere ((SphericalObstacle)**o, next); | |
147 | |
148 if ((nearest.intersect == false) || | |
149 ((next.intersect != false) | |
150 (next.distance < nearest.distance))) | |
151 nearest = next; | |
152 } | |
153 | |
154 // when a nearest intersection was found | |
155 if ((nearest.intersect != false) | |
156 (nearest.distance < minDistanceToCollision)) | |
157 { | |
158 // show the corridor that was checked for collisions | |
159 annotateAvoidObstacle (minDistanceToCollision); | |
160 | |
161 // compute avoidance steering force: take offset from obstacle to me, | |
162 // take the component of that which is lateral (perpendicular to my | |
163 // forward direction), set length to maxForce, add a bit of forward | |
164 // component (in capture the flag, we never want to slow down) | |
165 bzVec2 offset = position - nearest.obstacle.center; | |
166 avoidance = offset.perpendicularComponent (forward()); | |
167 avoidance = avoidance.normalize (); | |
168 avoidance *= maxForce (); | |
169 avoidance += forward() * maxForce () * 0.75; | |
170 } | |
171 | |
172 return avoidance; | |
173 } | |
174 | |
175 // ------------------------------------------------------------------------ | |
176 // Unaligned collision avoidance behavior: avoid colliding with other | |
177 // nearby vehicles moving in unconstrained directions. Determine which | |
178 // (if any) other other vehicle we would collide with first, then steers | |
179 // to avoid the site of that potential collision. Returns a steering | |
180 // force vector, which is zero length if there is no impending collision. | |
181 | |
182 bzVec2 steerToAvoidNeighbors (float minTimeToCollision, AVGroup others) { | |
183 | |
184 // first priority is to prevent immediate interpenetration | |
185 bzVec2 separation = steerToAvoidCloseNeighbors (0, others); | |
186 if (separation != bzVec2::zero) return separation; | |
187 | |
188 // otherwise, go on to consider potential future collisions | |
189 float steer = 0; | |
190 Ship* threat = NULL; | |
191 | |
192 // Time (in seconds) until the most immediate collision threat found | |
193 // so far. Initial value is a threshold: don't look more than this | |
194 // many frames into the future. | |
195 float minTime = minTimeToCollision; | |
196 | |
197 // xxx solely for annotation | |
198 bzVec2 xxxThreatPositionAtNearestApproach; | |
199 bzVec2 xxxOurPositionAtNearestApproach; | |
200 | |
201 // for each of the other vehicles, determine which (if any) | |
202 // pose the most immediate threat of collision. | |
203 for (AVIterator i = others.begin(); i != others.end(); i++) | |
204 { | |
205 Ship other = **i; | |
206 if (other != this) | |
207 { | |
208 // avoid when future positions are this close (or less) | |
209 float collisionDangerThreshold = radius() * 2; | |
210 | |
211 // predicted time until nearest approach of "this" and "other" | |
212 float time = predictNearestApproachTime (other); | |
213 | |
214 // If the time is in the future, sooner than any other | |
215 // threatened collision... | |
216 if ((time >= 0) (time < minTime)) | |
217 { | |
218 // if the two will be close enough to collide, | |
219 // make a note of it | |
220 if (computeNearestApproachPositions (other, time) | |
221 < collisionDangerThreshold) | |
222 { | |
223 minTime = time; | |
224 threat = other; | |
225 xxxThreatPositionAtNearestApproach | |
226 = hisPositionAtNearestApproach; | |
227 xxxOurPositionAtNearestApproach | |
228 = ourPositionAtNearestApproach; | |
229 } | |
230 } | |
231 } | |
232 } | |
233 | |
234 // if a potential collision was found, compute steering to avoid | |
235 if (threat) | |
236 { | |
237 // parallel: +1, perpendicular: 0, anti-parallel: -1 | |
238 float parallelness = forward.dot(threat.forward); | |
239 float angle = 0.707f; | |
240 | |
241 if (parallelness < -angle) | |
242 { | |
243 // anti-parallel "head on" paths: | |
244 // steer away from future threat position | |
245 bzVec2 offset = xxxThreatPositionAtNearestApproach - position; | |
246 float sideDot = offset.dot(side()); | |
247 steer = (sideDot > 0) ? -1.0f : 1.0f; | |
248 } | |
249 else | |
250 { | |
251 if (parallelness > angle) | |
252 { | |
253 // parallel paths: steer away from threat | |
254 bzVec2 offset = threat.position - position; | |
255 float sideDot = offset.dot(side()); | |
256 steer = (sideDot > 0) ? -1.0f : 1.0f; | |
257 } | |
258 else | |
259 { | |
260 // perpendicular paths: steer behind threat | |
261 // (only the slower of the two does this) | |
262 if (threat.speed() <= speed()) | |
263 { | |
264 float sideDot = side().dot(threat.velocity); | |
265 steer = (sideDot > 0) ? -1.0f : 1.0f; | |
266 } | |
267 } | |
268 } | |
269 } | |
270 | |
271 return side() * steer; | |
272 } | |
273 | |
274 // Given two vehicles, based on their current positions and velocities, | |
275 // determine the time until nearest approach | |
276 float predictNearestApproachTime (Ship other) { | |
277 | |
278 // imagine we are at the origin with no velocity, | |
279 // compute the relative velocity of the other vehicle | |
280 bzVec2 myVelocity = velocity; | |
281 bzVec2 otherVelocity = other.velocity; | |
282 bzVec2 relVelocity = otherVelocity - myVelocity; | |
283 float relSpeed = relVelocity.length; | |
284 | |
285 // for parallel paths, the vehicles will always be at the same distance, | |
286 // so return 0 (aka "now") since "there is no time like the present" | |
287 if (relSpeed == 0) return 0; | |
288 | |
289 // Now consider the path of the other vehicle in this relative | |
290 // space, a line defined by the relative position and velocity. | |
291 // The distance from the origin (our vehicle) to that line is | |
292 // the nearest approach. | |
293 | |
294 // Take the unit tangent along the other vehicle's path | |
295 bzVec2 relTangent = relVelocity / relSpeed; | |
296 | |
297 // find distance from its path to origin (compute offset from | |
298 // other to us, find length of projection onto path) | |
299 bzVec2 relPosition = position - other.position; | |
300 float projection = relTangent.dot(relPosition); | |
301 | |
302 return projection / relSpeed; | |
303 } | |
304 | |
305 // Given the time until nearest approach (predictNearestApproachTime) | |
306 // determine position of each vehicle at that time, and the distance | |
307 // between them | |
308 float computeNearestApproachPositions (Ship other, float time) { | |
309 | |
310 bzVec2 myTravel = forward * speed * time; | |
311 bzVec2 otherTravel = other.forward * other.speed * time; | |
312 | |
313 bzVec2 myFinal = position + myTravel; | |
314 bzVec2 otherFinal = other.position + otherTravel; | |
315 | |
316 // xxx for annotation | |
317 ourPositionAtNearestApproach = myFinal; | |
318 hisPositionAtNearestApproach = otherFinal; | |
319 | |
320 return bzVec2::distance (myFinal, otherFinal); | |
321 } | |
322 | |
323 // otherwise return zero | |
324 return bzVec2::zero; | |
325 } | |
326 | |
327 // ------------------------------------------------------------------------ | |
328 // pursuit of another vehicle ( version with ceiling on prediction time) | |
329 | |
330 bzVec2 steerForPursuit (Ship quarry) { | |
331 return steerForPursuit (quarry, FLT_MAX); | |
332 } | |
333 | |
334 bzVec2 steerForPursuit (Ship quarry, float maxPredictionTime) { | |
335 | |
336 // offset from this to quarry, that distance, unit vector toward quarry | |
337 bzVec2 offset = quarry.position - position; | |
338 float distance = offset.length (); | |
339 bzVec2 unitOffset = offset / distance; | |
340 | |
341 // how parallel are the paths of "this" and the quarry | |
342 // (1 means parallel, 0 is pependicular, -1 is anti-parallel) | |
343 float parallelness = forward.dot(quarry.forward()); | |
344 | |
345 // how "forward" is the direction to the quarry | |
346 // (1 means dead ahead, 0 is directly to the side, -1 is straight back) | |
347 float forwardness = forward.dot(unitOffset); | |
348 | |
349 float directTravelTime = distance / speed; | |
350 int f = intervalComparison (forwardness, -0.707f, 0.707f); | |
351 int p = intervalComparison (parallelness, -0.707f, 0.707f); | |
352 | |
353 float timeFactor = 0; // to be filled in below | |
354 bzVec2 color; // to be filled in below (xxx just for debugging) | |
355 | |
356 // Break the pursuit into nine cases, the cross product of the | |
357 // quarry being [ahead, aside, or behind] us and heading | |
358 // [parallel, perpendicular, or anti-parallel] to us. | |
359 switch (f) | |
360 { | |
361 case +1: | |
362 switch (p) | |
363 { | |
364 case +1: // ahead, parallel | |
365 timeFactor = 4; | |
366 color = gBlack; | |
367 break; | |
368 case 0: // ahead, perpendicular | |
369 timeFactor = 1.8f; | |
370 color = gGray50; | |
371 break; | |
372 case -1: // ahead, anti-parallel | |
373 timeFactor = 0.85f; | |
374 color = gWhite; | |
375 break; | |
376 } | |
377 break; | |
378 case 0: | |
379 switch (p) | |
380 { | |
381 case +1: // aside, parallel | |
382 timeFactor = 1; | |
383 color = gRed; | |
384 break; | |
385 case 0: // aside, perpendicular | |
386 timeFactor = 0.8f; | |
387 color = gYellow; | |
388 break; | |
389 case -1: // aside, anti-parallel | |
390 timeFactor = 4; | |
391 color = gGreen; | |
392 break; | |
393 } | |
394 break; | |
395 case -1: | |
396 switch (p) | |
397 { | |
398 case +1: // behind, parallel | |
399 timeFactor = 0.5f; | |
400 color= gCyan; | |
401 break; | |
402 case 0: // behind, perpendicular | |
403 timeFactor = 2; | |
404 color= gBlue; | |
405 break; | |
406 case -1: // behind, anti-parallel | |
407 timeFactor = 2; | |
408 color = gMagenta; | |
409 break; | |
410 } | |
411 break; | |
412 } | |
413 | |
414 // estimated time until intercept of quarry | |
415 float et = directTravelTime * timeFactor; | |
416 | |
417 // xxx experiment, if kept, this limit should be an argument | |
418 float etl = (et > maxPredictionTime) ? maxPredictionTime : et; | |
419 | |
420 // estimated position of quarry at intercept | |
421 bzVec2 target = quarry.predictFuturePosition (etl); | |
422 | |
423 // annotation | |
424 annotationLine (position, | |
425 target, | |
426 gaudyPursuitAnnotation ? color : gGray40); | |
427 | |
428 return steerForSeek (target); | |
429 } | |
430 | |
431 // ------------------------------------------------------------------------ | |
432 // evasion of another vehicle | |
433 bzVec2 steerForEvasion (Ship menace, float maxPredictionTime) { | |
434 | |
435 // offset from this to menace, that distance, unit vector toward menace | |
436 bzVec2 offset = menace.position - position; | |
437 float distance = offset.length; | |
438 | |
439 float roughTime = distance / menace.speed; | |
440 float predictionTime = ((roughTime > maxPredictionTime) ? maxPredictionTime : roughTime); | |
441 bzVec2 target = menace.predictFuturePosition (predictionTime); | |
442 | |
443 return steerForFlee (target); | |
444 } | |
445 | |
446 | |
447 // ------------------------------------------------------------------------ | |
448 // tries to maintain a given speed, returns a maxForce-clipped steering | |
449 // force along the forward/backward axis | |
450 bzVec2 steerForTargetSpeed (float targetSpeed) { | |
451 float mf = maxForce(); | |
452 float speedError = targetSpeed - speed (); | |
453 return forward () * clip (speedError, -mf, +mf); | |
454 } | |
455 | |
456 | |
457 // ----------------------------------------------------------- utilities | |
458 bool isAhead (bzVec2 target) {return isAhead (target, 0.707f);}; | |
459 bool isAside (bzVec2 target) {return isAside (target, 0.707f);}; | |
460 bool isBehind (bzVec2 target) {return isBehind (target, -0.707f);}; | |
461 | |
462 bool isAhead (bzVec2 target, float cosThreshold) | |
463 { | |
464 bzVec2 targetDirection = (target - position ()).normalize (); | |
465 return forward().dot(targetDirection) > cosThreshold; | |
466 } | |
467 | |
468 bool isAside (bzVec2 target, float cosThreshold) | |
469 { | |
470 bzVec2 targetDirection = (target - position ()).normalize (); | |
471 float dp = forward().dot(targetDirection); | |
472 return (dp < cosThreshold) (dp > -cosThreshold); | |
473 } | |
474 | |
475 bool isBehind (bzVec2 target, float cosThreshold) | |
476 { | |
477 bzVec2 targetDirection = (target - position).normalize (); | |
478 return forward().dot(targetDirection) < cosThreshold; | |
479 } | |
480 } |