ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

walk.cpp

Go to the documentation of this file.
00001 /* ResidualVM - A 3D game interpreter
00002  *
00003  * ResidualVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the AUTHORS
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #include "engines/stark/movement/walk.h"
00024 
00025 #include "engines/stark/movement/shortestpath.h"
00026 #include "engines/stark/movement/stringpullingpath.h"
00027 
00028 #include "engines/stark/services/global.h"
00029 #include "engines/stark/services/services.h"
00030 #include "engines/stark/services/stateprovider.h"
00031 
00032 #include "engines/stark/resources/anim.h"
00033 #include "engines/stark/resources/floor.h"
00034 #include "engines/stark/resources/floorface.h"
00035 #include "engines/stark/resources/item.h"
00036 #include "engines/stark/resources/location.h"
00037 
00038 #include "math/vector2d.h"
00039 
00040 namespace Stark {
00041 
00042 Walk::Walk(Resources::FloorPositionedItem *item) :
00043         Movement(item),
00044         _item3D(item),
00045         _running(false),
00046         _reachedDestination(false),
00047         _turnDirection(kTurnNone),
00048         _collisionWaitTimeout(-1),
00049         _collisionWaitCount(0) {
00050     _path = new StringPullingPath();
00051 }
00052 
00053 Walk::~Walk() {
00054     delete _path;
00055 }
00056 
00057 void Walk::start() {
00058     Movement::start();
00059 
00060     updatePath();
00061     changeItemAnim();
00062 
00063     Resources::Location *location = StarkGlobal->getCurrent()->getLocation();
00064     location->startFollowingCharacter();
00065 }
00066 
00067 void Walk::stop(bool force) {
00068     if (force) {
00069         _destinations.clear();
00070     }
00071 
00072     if (_destinations.empty()) {
00073         Movement::stop(force);
00074         changeItemAnim();
00075         _avoidedItems.clear();
00076     } else {
00077         Math::Vector3d destination = _destinations.front();
00078         _destinations.remove_at(0);
00079         setDestination(destination);
00080         updatePath();
00081     }
00082 }
00083 
00084 void Walk::updatePath() const {
00085     _path->reset();
00086 
00087     Resources::Floor *floor = StarkGlobal->getCurrent()->getFloor();
00088 
00089     Math::Vector3d startPosition = _item3D->getPosition3D();
00090     int32 startFloorFaceIndex = floor->findFaceContainingPoint(startPosition);
00091     if (startFloorFaceIndex == -1) {
00092         startFloorFaceIndex = 0;
00093     }
00094 
00095     Resources::FloorFace *startFloorFace = floor->getFace(startFloorFaceIndex);
00096     Resources::FloorEdge *startFloorEdge = startFloorFace->findNearestEdge(startPosition);
00097     if (!startFloorEdge) {
00098         // Unable to find enabled start edge
00099         return;
00100     }
00101 
00102     int32 destinationFloorFaceIndex = floor->findFaceContainingPoint(_destination);
00103     if (destinationFloorFaceIndex < 0) {
00104         // Unable to find the destination's face
00105         return;
00106     }
00107 
00108     Resources::FloorFace *destinationFloorFace = floor->getFace(destinationFloorFaceIndex);
00109     Resources::FloorEdge *destinationFloorEdge = destinationFloorFace->findNearestEdge(_destination);
00110     if (!destinationFloorEdge) {
00111         // Unable to find enabled destination edge
00112         return;
00113     }
00114 
00115     ShortestPath pathSearch;
00116     ShortestPath::NodeList edgePath = pathSearch.search(startFloorEdge, destinationFloorEdge);
00117 
00118     for (ShortestPath::NodeList::const_iterator it = edgePath.begin(); it != edgePath.end(); it++) {
00119         _path->addStep((*it)->getPosition());
00120     }
00121 
00122     _path->addStep(_destination);
00123 }
00124 
00125 void Walk::queueDestinationToAvoidItem(Resources::FloorPositionedItem *item, const Math::Vector3d &destination) {
00126     _destinations.push_back(destination);
00127     _avoidedItems.push_back(item);
00128 }
00129 
00130 bool Walk::isItemAlreadyAvoided(Resources::FloorPositionedItem *item) const {
00131     return Common::find(_avoidedItems.begin(), _avoidedItems.end(), item) != _avoidedItems.end();
00132 }
00133 
00134 void Walk::onGameLoop() {
00135     Resources::ItemVisual *interactiveItem = StarkGlobal->getCurrent()->getInteractive();
00136 
00137     if (_item != interactiveItem) {
00138         // NPCs have a simple collision handling strategy.
00139         // They stop when they collide with other items,
00140         // and wait for their path to be clear.
00141         doWalkCollisionSimple();
00142     } else {
00143         // April has a more advanced collision handling approach.
00144         // She goes either left or right of the items on her path.
00145         // When impossible to pick a direction, she walks until the
00146         // obstacle is reached.
00147         doWalkCollisionAvoid();
00148     }
00149 }
00150 
00151 void Walk::doWalk() {
00152     if (!_path->hasSteps()) {
00153         // There is no path to the destination
00154         stop();
00155         return;
00156     }
00157 
00158     Resources::Floor *floor = StarkGlobal->getCurrent()->getFloor();
00159 
00160     // Get the target to walk to
00161     Math::Vector3d currentPosition = _item3D->getPosition3D();
00162     Math::Vector3d target = _path->computeWalkTarget(currentPosition);
00163 
00164     // Compute the direction to walk into
00165     Math::Vector3d direction = target - currentPosition;
00166     direction.z() = 0;
00167     direction.normalize();
00168 
00169     // Compute the angle with the current character direction
00170     Math::Vector3d currentDirection = _item3D->getDirectionVector();
00171     float directionDeltaAngle = computeAngleBetweenVectorsXYPlane(currentDirection, direction);
00172 
00173     // If the angle between the current direction and the new one is too high,
00174     // make the character turn on itself until the angle is low enough
00175     if (ABS(directionDeltaAngle) > getAngularSpeed() + 0.1f) {
00176         _turnDirection = directionDeltaAngle < 0 ? kTurnLeft : kTurnRight;
00177     } else {
00178         _turnDirection = kTurnNone;
00179     }
00180 
00181     float distancePerGameloop = computeDistancePerGameLoop();
00182 
00183     Math::Vector3d newPosition;
00184     if (_turnDirection == kTurnNone) {
00185         // Compute the new position using the distance per gameloop
00186         if (currentPosition.getDistanceTo(target) > distancePerGameloop) {
00187             newPosition = currentPosition + direction * distancePerGameloop;
00188         } else {
00189             newPosition = target;
00190         }
00191     } else {
00192         // The character does not change position when it is turning
00193         newPosition = currentPosition;
00194         direction = currentDirection;
00195 
00196         Math::Matrix3 rot;
00197         rot.buildAroundZ(_turnDirection == kTurnLeft ? -getAngularSpeed() : getAngularSpeed());
00198         rot.transformVector(&direction);
00199     }
00200 
00201     _previousPosition = currentPosition;
00202     _currentTarget = target;
00203 
00204     // Some scripts expect the character position to be the exact destination
00205     if (newPosition == _destination) {
00206         _reachedDestination = true;
00207         stop();
00208     }
00209 
00210     // Update the new position's height according to the floor
00211     int32 newFloorFaceIndex = floor->findFaceContainingPoint(newPosition);
00212     if (newFloorFaceIndex >= 0) {
00213         floor->computePointHeightInFace(newPosition, newFloorFaceIndex);
00214     } else {
00215         warning("Item %s is walking off the floor", _item->getName().c_str());
00216     }
00217 
00218     // Update the item's properties
00219     _item3D->setPosition3D(newPosition);
00220     if (direction.getMagnitude() != 0.f) {
00221         _item3D->setDirection(computeAngleBetweenVectorsXYPlane(direction, Math::Vector3d(1.0, 0.0, 0.0)));
00222     }
00223     if (newFloorFaceIndex >= 0) {
00224         // When unable to find the face containing the new position, keep the previous one
00225         // to prevent draw order glitches.
00226         _item3D->setFloorFaceIndex(newFloorFaceIndex);
00227     }
00228 
00229     changeItemAnim();
00230 }
00231 
00232 bool Walk::isPointNearPath(const Math::Vector3d &point3d, const Math::Vector3d &pathStart3d, const Math::Vector3d &pathEnd3d) {
00233     Math::Vector2d point     = Math::Vector2d(point3d.x(), point3d.y());
00234     Math::Vector2d pathStart = Math::Vector2d(pathStart3d.x(), pathStart3d.y());
00235     Math::Vector2d pathEnd   = Math::Vector2d(pathEnd3d.x(), pathEnd3d.y());
00236 
00237     // Project the point onto the path
00238     Math::Vector2d pointToStart = point - pathStart;
00239     Math::Vector2d path = pathEnd - pathStart;
00240     float dot = pointToStart.dotProduct(path);
00241     float len = path.getSquareMagnitude();
00242 
00243     float t = dot / len;
00244 
00245     Math::Vector2d projection;
00246     if (0.f <= t && t < 1.f) {
00247         projection = path * t + pathStart;
00248     } else {
00249         projection = pathEnd;
00250     }
00251 
00252     // Check if the projection is near the actual point
00253     return point.getDistanceTo(projection) <= (15.f + 15.f);
00254 }
00255 
00256 void Walk::doWalkCollisionSimple() {
00257     if (_collisionWaitTimeout > 0) {
00258         _collisionWaitTimeout -= StarkGlobal->getMillisecondsPerGameloop();
00259         return;
00260     } else {
00261         _collisionWaitTimeout = -1;
00262     }
00263 
00264     Resources::Location *location = StarkGlobal->getCurrent()->getLocation();
00265     Common::Array<Resources::ItemVisual *> characters = location->listCharacters();
00266 
00267     // Check if any of the other characters is in our way
00268     for (uint i = 0; i < characters.size(); i++) {
00269         Resources::FloorPositionedItem *otherItem = dynamic_cast<Resources::FloorPositionedItem *>(characters[i]);
00270         if (!otherItem || !otherItem->isEnabled() || otherItem == _item) continue;
00271 
00272         Math::Vector3d otherPosition = otherItem->getPosition3D();
00273 
00274         if (isPointNearPath(otherPosition, _previousPosition, _currentTarget)) {
00275             if (_previousPosition.getDistanceTo(otherPosition) <= 15.f * 3.f) {
00276                 if (_collisionWaitCount >= 10) {
00277                     doWalk();
00278                     return;
00279                 }
00280 
00281                 // A collision is detected. Remove the walk animation, and wait a bit.
00282                 if (_item->getAnimActivity() != Resources::Anim::kActorActivityIdle) {
00283                     _item->setAnimActivity(Resources::Anim::kActorActivityIdle);
00284                 }
00285 
00286                 _collisionWaitCount++;
00287                 _collisionWaitTimeout = 500; // ms
00288                 return;
00289             }
00290         }
00291     }
00292 
00293     // The path is clear, walk normally
00294     _collisionWaitCount = 0;
00295     doWalk();
00296 }
00297 
00298 void Walk::doWalkCollisionAvoid() {
00299     float collisionRadius = 15.f * 2.0999999f;
00300 
00301     Math::Vector3d previousPosition = _item3D->getPosition3D();
00302     doWalk();
00303     Math::Vector3d newPosition = _item3D->getPosition3D();
00304 
00305     Resources::Location *location = StarkGlobal->getCurrent()->getLocation();
00306     Common::Array<Resources::ItemVisual *> characters = location->listCharacters();
00307 
00308     // Check if we're colliding with another character, but going away from it.
00309     // In that case, the collision is being solved. There is nothing to do.
00310     for (uint i = 0; i < characters.size(); i++) {
00311         Resources::FloorPositionedItem *otherItem = dynamic_cast<Resources::FloorPositionedItem *>(characters[i]);
00312         if (!otherItem || !otherItem->isEnabled() || otherItem == _item) continue;
00313 
00314         Math::Vector3d otherPosition = otherItem->getPosition3D();
00315 
00316         Math::Vector2d newPosition2d(newPosition.x(), newPosition.y());
00317         Math::Vector2d otherPosition2d(otherPosition.x(), otherPosition.y());
00318 
00319         float newDistance = newPosition2d.getDistanceTo(otherPosition2d);
00320         if (newDistance < 15.f + 15.f) {
00321             Math::Vector2d previousPosition2d(previousPosition.x(), previousPosition.y());
00322 
00323             float previousDistance = previousPosition2d.getDistanceTo(otherPosition2d);
00324             if (previousDistance < newDistance) {
00325                 return;
00326             }
00327         }
00328     }
00329 
00330     Resources::Floor *floor = StarkGlobal->getCurrent()->getFloor();
00331 
00332     for (uint i = 0; i < characters.size(); i++) {
00333         Resources::FloorPositionedItem *otherItem = dynamic_cast<Resources::FloorPositionedItem *>(characters[i]);
00334         if (!otherItem || !otherItem->isEnabled() || otherItem == _item || isItemAlreadyAvoided(otherItem)) continue;
00335 
00336         Math::Vector3d otherPosition = otherItem->getPosition3D();
00337         if (!isPointNearPath(otherPosition, _previousPosition, _currentTarget)) continue;
00338 
00339         Math::Vector3d newPosition2d(newPosition.x(), newPosition.y(), 0.f);
00340         Math::Vector3d otherPosition2d(otherPosition.x(), otherPosition.y(), 0.f);
00341 
00342         Math::Vector3d directionToOther = otherPosition2d - newPosition2d;
00343         float distanceToOther = directionToOther.getMagnitude();
00344         directionToOther.normalize();
00345 
00346         Math::Vector3d up(0.f, 0.f, 1.f);
00347         Math::Vector3d rightDirection = Math::Vector3d::crossProduct(directionToOther, up);
00348         rightDirection.normalize();
00349 
00350         Math::Vector3d otherPositionNear = newPosition2d + directionToOther * (distanceToOther - collisionRadius);
00351         Math::Vector3d otherPostionFar   = newPosition2d + directionToOther * (distanceToOther + collisionRadius);
00352 
00353         Math::Vector3d rightOfOtherNear = otherPositionNear + rightDirection * collisionRadius;
00354         Math::Vector3d leftOfOtherNear  = otherPositionNear - rightDirection * collisionRadius;
00355         Math::Vector3d rightOfOtherFar  = otherPostionFar   + rightDirection * collisionRadius;
00356         Math::Vector3d leftOfOtherFar   = otherPostionFar   - rightDirection * collisionRadius;
00357 
00358         bool canGoRight = false;
00359         if (floor->isSegmentInside(Math::Line3d(otherPositionNear, rightOfOtherNear))) {
00360             if (floor->isSegmentInside(Math::Line3d(rightOfOtherNear, rightOfOtherFar))) {
00361                 canGoRight = true;
00362             }
00363         }
00364 
00365         bool canGoLeft = false;
00366         if (floor->isSegmentInside(Math::Line3d(otherPositionNear, leftOfOtherNear))) {
00367             if (floor->isSegmentInside(Math::Line3d(leftOfOtherNear, leftOfOtherFar))) {
00368                 canGoLeft = true;
00369             }
00370         }
00371 
00372         for (uint j = 0; j < characters.size(); j++) {
00373             if (j == i) continue;
00374             Resources::FloorPositionedItem *anotherItem = dynamic_cast<Resources::FloorPositionedItem *>(characters[j]);
00375             if (!anotherItem || !anotherItem->isEnabled() || anotherItem == _item) continue;
00376 
00377             Math::Vector3d anotherPosition = anotherItem->getPosition3D();
00378 
00379             if (isPointNearPath(anotherPosition, otherPositionNear, rightOfOtherNear)) {
00380                 canGoRight = false;
00381             }
00382 
00383             if (isPointNearPath(anotherPosition, rightOfOtherNear, rightOfOtherFar)) {
00384                 canGoRight = false;
00385             }
00386 
00387             if (isPointNearPath(anotherPosition, otherPositionNear, leftOfOtherNear)) {
00388                 canGoLeft = false;
00389             }
00390 
00391             if (isPointNearPath(anotherPosition, leftOfOtherNear, leftOfOtherFar)) {
00392                 canGoLeft = false;
00393             }
00394         }
00395 
00396         if (distanceToOther < collisionRadius) {
00397             int32 floorFace = floor->findFaceContainingPoint(previousPosition);
00398             if (floorFace >= 0) {
00399                 floor->computePointHeightInFace(previousPosition, floorFace);
00400 
00401                 _item3D->setFloorFaceIndex(floorFace);
00402                 _item3D->setPosition3D(previousPosition);
00403             }
00404             _reachedDestination = false;
00405             // _skipped = false;
00406             stop();
00407             break;
00408         }
00409 
00410         // If our target destination is in the collision radius of the tested item
00411         // Then adjust our destination to be just outside of the item's collision radius.
00412         float distanceToDestination = _destination.getDistanceTo(otherPosition);
00413         if (distanceToDestination < collisionRadius) {
00414             setDestinationWithoutHeight(otherPosition - directionToOther * collisionRadius);
00415             // _field_51 = true;
00416             updatePath();
00417             continue;
00418         }
00419 
00420         if (canGoLeft) {
00421             Math::Vector3d lookDirection = _item3D->getDirectionVector();
00422             Math::Vector3d previousToLeft = leftOfOtherNear - _previousPosition;
00423 
00424             Math::Angle angle = Math::Vector3d::angle(lookDirection, previousToLeft);
00425             if (angle > 270) {
00426                 canGoLeft = false;
00427             }
00428         }
00429 
00430         if (canGoRight) {
00431             Math::Vector3d lookDirection = _item3D->getDirectionVector();
00432             Math::Vector3d previousToRight = rightOfOtherNear - _previousPosition;
00433 
00434             Math::Angle angle = Math::Vector3d::angle(lookDirection, previousToRight);
00435             if (angle > 270) {
00436                 canGoRight = false;
00437             }
00438         }
00439 
00440         if (canGoRight && !canGoLeft) {
00441             queueDestinationToAvoidItem(otherItem, _destination);
00442             setDestinationWithoutHeight(rightOfOtherNear);
00443             updatePath();
00444         } else if (!canGoRight && canGoLeft) {
00445             queueDestinationToAvoidItem(otherItem, _destination);
00446             setDestinationWithoutHeight(leftOfOtherNear);
00447             updatePath();
00448         } else if (canGoRight && canGoLeft) {
00449             Math::Vector3d forwardDirection = _currentTarget - _previousPosition;
00450             Math::Vector3d cross = Math::Vector3d::crossProduct(forwardDirection, directionToOther);
00451 
00452             if (cross.z() < 0.f) {
00453                 queueDestinationToAvoidItem(otherItem, _destination);
00454                 setDestinationWithoutHeight(leftOfOtherNear);
00455                 updatePath();
00456             } else {
00457                 queueDestinationToAvoidItem(otherItem, _destination);
00458                 setDestinationWithoutHeight(rightOfOtherNear);
00459                 updatePath();
00460             }
00461         }
00462     }
00463 }
00464 
00465 float Walk::getAngularSpeed() const {
00466     return _defaultTurnAngleSpeed * StarkGlobal->getMillisecondsPerGameloop();
00467 }
00468 
00469 float Walk::computeDistancePerGameLoop() const {
00470     Resources::Anim *anim = _item->getAnim();
00471     float distancePerGameloop = anim->getMovementSpeed() * StarkGlobal->getMillisecondsPerGameloop() / 1000.f;
00472 
00473     return distancePerGameloop;
00474 }
00475 
00476 void Walk::setDestination(const Math::Vector3d &destination) {
00477     _destination = destination;
00478 }
00479 
00480 void Walk::setDestinationWithoutHeight(Math::Vector3d destination) {
00481     Resources::Floor *floor = StarkGlobal->getCurrent()->getFloor();
00482     int32 faceIndex = floor->findFaceContainingPoint(destination);
00483     if (faceIndex >= 0) {
00484         floor->computePointHeightInFace(destination, faceIndex);
00485     }
00486 
00487     setDestination(destination);
00488 }
00489 
00490 void Walk::setRunning() {
00491     _running = true;
00492     changeItemAnim();
00493 }
00494 
00495 void Walk::changeItemAnim() {
00496     if (_ended) {
00497         _item->setAnimActivity(Resources::Anim::kActorActivityIdle);
00498     } else if (_turnDirection != kTurnNone) {
00499         _item->setAnimActivity(Resources::Anim::kActorActivityIdle);
00500     } else if (_running) {
00501         _item->setAnimActivity(Resources::Anim::kActorActivityRun);
00502     } else {
00503         _item->setAnimActivity(Resources::Anim::kActorActivityWalk);
00504     }
00505 }
00506 
00507 void Walk::changeDestination(const Math::Vector3d &destination) {
00508     _collisionWaitTimeout = -1;
00509     setDestination(destination);
00510     updatePath();
00511 }
00512 
00513 bool Walk::hasReachedDestination() const {
00514     return _reachedDestination;
00515 }
00516 
00517 uint32 Walk::getType() const {
00518     return kTypeWalk;
00519 }
00520 
00521 void Walk::saveLoad(ResourceSerializer *serializer) {
00522     serializer->syncAsVector3d(_destination);
00523     serializer->syncAsUint32LE(_running);
00524 }
00525 
00526 } // End of namespace Stark


Generated on Sat May 18 2019 05:01:29 for ResidualVM by doxygen 1.7.1
curved edge   curved edge