From e03683852cac9b31ca846fcf13ff53abf99232c7 Mon Sep 17 00:00:00 2001 From: Kelly Rauchenberger Date: Sat, 27 Feb 2021 17:40:26 -0500 Subject: Added A* pathfinding --- src/behaviour_system.cpp | 171 ++++++++++++++++++++++++++++++++++++++++++++++- src/behaviour_system.h | 12 ++++ src/character_system.cpp | 2 +- src/game.cpp | 2 +- src/input_system.cpp | 2 +- src/script_system.cpp | 15 ++++- src/sprite.h | 16 ++++- src/transform_system.cpp | 4 +- src/transform_system.h | 2 +- src/vector.h | 4 ++ 10 files changed, 221 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/behaviour_system.cpp b/src/behaviour_system.cpp index 2d46205..3637b3e 100644 --- a/src/behaviour_system.cpp +++ b/src/behaviour_system.cpp @@ -1,8 +1,16 @@ #include "behaviour_system.h" +#include +#include +#include #include #include "game.h" #include "character_system.h" #include "direction.h" +#include "transform_system.h" + +bool pathfindingOptionsContains(PathfindingOptions options, PathfindingOptions value) { + return (static_cast(options) & static_cast(value)) != 0; +} void BehaviourSystem::tick(double dt) { if (game_.isGameplayPaused()) return; @@ -11,7 +19,7 @@ void BehaviourSystem::tick(double dt) { while (timer_.step()) { for (int spriteId : game_.getSprites()) { Sprite& sprite = game_.getSprite(spriteId); - if (sprite.wander && !sprite.paused) { + if (!sprite.paused && sprite.behaviourType == BehaviourType::Wander) { // 75% chance of changing what's happening if (std::bernoulli_distribution(0.75)(game_.getRng())) { // 50% chance of choosing a direction or stopping @@ -31,4 +39,165 @@ void BehaviourSystem::tick(double dt) { } } } + + for (int spriteId : game_.getSprites()) { + Sprite& sprite = game_.getSprite(spriteId); + if (!sprite.paused && sprite.behaviourType == BehaviourType::Path) { + while (!sprite.path.empty() && sprite.path.front().endpoint == sprite.loc) { + sprite.path.pop_front(); + } + if (sprite.path.empty()) { + game_.getSystem().stopDirecting(spriteId); + } else { + if (sprite.characterState == CharacterState::Still || sprite.movementDir != sprite.path.front().dir) { + game_.getSystem().moveInDirection(spriteId, sprite.path.front().dir); + } + } + } + } +} + +void BehaviourSystem::directSpriteToLocation(int spriteId, vec2i pos, PathfindingOptions options) { + Sprite& sprite = game_.getSprite(spriteId); + sprite.behaviourType = BehaviourType::Path; + sprite.pathfindingDestination = pos; + sprite.cardinalDirectionsOnly = pathfindingOptionsContains(options, PathfindingOptions::CardinalDirectionsOnly); + + createPath(spriteId); +} + +bool BehaviourSystem::isFollowingPath(int spriteId) { + Sprite& sprite = game_.getSprite(spriteId); + return sprite.behaviourType == BehaviourType::Path && !sprite.path.empty(); +} + +struct PathNodeInfo { + int cheapestPathCost = INT_MAX; + int estimatedRemainingCost = INT_MAX; + vec2i previousPoint; + Direction dirFromPreviousPoint; +}; + +struct SearchNode { + vec2i point; + int estimatedCost = INT_MAX; + int tiebreaker; // this actually counts downward. wow + + SearchNode(vec2i point, int estimatedCost) : point(point), estimatedCost(estimatedCost) { + static int tiebreakerCounter = 0; + tiebreaker = tiebreakerCounter--; + } + + bool operator>(const SearchNode& rhs) const { + return std::tie(estimatedCost, tiebreaker) > std::tie(rhs.estimatedCost, rhs.tiebreaker); + } +}; + +int estimateRemainingCost(vec2i current, vec2i dest, int movementSpeed, bool cardinalDirectionsOnly) { + vec2i difference = dest - current; + if (cardinalDirectionsOnly) { + return (std::abs(difference.x()) + std::abs(difference.y())) / movementSpeed; + } else { + return std::max(std::abs(difference.x()), std::abs(difference.y())) / movementSpeed; + } +} + +void BehaviourSystem::createPath(int spriteId) { + Sprite& sprite = game_.getSprite(spriteId); + sprite.path.clear(); + + const Map& map = game_.getMap(); + vec2i mapBounds = map.getMapSize() * map.getTileSize(); + + // If it is not possible to reach the destination because of the parity (if + // the movement speed is above 1), then adjust the destination. + if (sprite.movementSpeed > 1) { + if ((sprite.loc.x() % sprite.movementSpeed) != (sprite.pathfindingDestination.x() % sprite.movementSpeed)) { + sprite.loc.x() = (sprite.loc.x() / sprite.movementSpeed) * sprite.movementSpeed + (sprite.pathfindingDestination.x() % sprite.movementSpeed); + } + if ((sprite.loc.y() % sprite.movementSpeed) != (sprite.pathfindingDestination.y() % sprite.movementSpeed)) { + sprite.loc.y() = (sprite.loc.y() / sprite.movementSpeed) * sprite.movementSpeed + (sprite.pathfindingDestination.y() % sprite.movementSpeed); + } + } + + int initialCostGuess = estimateRemainingCost(sprite.loc, sprite.pathfindingDestination, sprite.movementSpeed, sprite.cardinalDirectionsOnly); + + std::map pathNodes; + pathNodes[sprite.loc] = PathNodeInfo{.cheapestPathCost = 0, .estimatedRemainingCost = initialCostGuess}; + + std::priority_queue, std::greater> openSet; + openSet.emplace(sprite.loc, initialCostGuess); + + while (!openSet.empty()) { + SearchNode searchNode = openSet.top(); + openSet.pop(); + + if (searchNode.point == sprite.pathfindingDestination) { + // We're there! + break; + } + + PathNodeInfo& nodeInfo = pathNodes[searchNode.point]; + int newCost = nodeInfo.cheapestPathCost + 1; + + static const std::vector allDirections = { + Direction::down, + Direction::down_left, + Direction::left, + Direction::up_left, + Direction::up, + Direction::up_right, + Direction::right, + Direction::down_right }; + + static const std::vector cardinalDirections = { + Direction::down, + Direction::left, + Direction::up, + Direction::right }; + + const std::vector* directionList = sprite.cardinalDirectionsOnly ? &cardinalDirections : &allDirections; + for (Direction dir : *directionList) { + vec2i newPos = searchNode.point + unitVecInDirection(dir) * sprite.movementSpeed; + + if (newPos.x() < 0 || newPos.y() < 0 || newPos.x() >= mapBounds.w() || newPos.y() >= mapBounds.h()) { + // The path can't go outside the map. + continue; + } + + PathNodeInfo& neighborInfo = pathNodes[newPos]; + + if (neighborInfo.cheapestPathCost <= newCost) { + // There is already a faster path through this neighbor. + continue; + } + + CollisionResult collision = game_.getSystem().checkCollision(spriteId, searchNode.point, newPos, dir); + if (collision.horiz.blocked || collision.vert.blocked) { + // There isn't actually an edge to this neighbor. + continue; + } + + neighborInfo.cheapestPathCost = newCost; + neighborInfo.estimatedRemainingCost = estimateRemainingCost(newPos, sprite.pathfindingDestination, sprite.movementSpeed, sprite.cardinalDirectionsOnly); + neighborInfo.previousPoint = searchNode.point; + neighborInfo.dirFromPreviousPoint = dir; + + openSet.emplace(newPos, neighborInfo.cheapestPathCost + neighborInfo.estimatedRemainingCost); + } + } + + if (!pathNodes.count(sprite.pathfindingDestination)) { + // There was no path to the destination. + return; + } + + vec2i curPos = sprite.pathfindingDestination; + while (curPos != sprite.loc) { + PathNodeInfo& nodeInfo = pathNodes[curPos]; + if (sprite.path.empty() || sprite.path.front().dir != nodeInfo.dirFromPreviousPoint) { + sprite.path.push_front(PathfindingInstruction{.dir = nodeInfo.dirFromPreviousPoint, .endpoint = curPos}); + } + curPos = nodeInfo.previousPoint; + } } diff --git a/src/behaviour_system.h b/src/behaviour_system.h index 0eb4772..526a09b 100644 --- a/src/behaviour_system.h +++ b/src/behaviour_system.h @@ -3,6 +3,12 @@ #include "system.h" #include "timer.h" +#include "vector.h" + +enum class PathfindingOptions { + None = 0, + CardinalDirectionsOnly = 1 << 0 +}; class Game; @@ -15,8 +21,14 @@ public: void tick(double dt) override; + void directSpriteToLocation(int spriteId, vec2i pos, PathfindingOptions options = PathfindingOptions::None); + + bool isFollowingPath(int spriteId); + private: + void createPath(int spriteId); + Game& game_; Timer timer_ { 500 }; }; diff --git a/src/character_system.cpp b/src/character_system.cpp index 9b91716..53debb2 100644 --- a/src/character_system.cpp +++ b/src/character_system.cpp @@ -150,7 +150,7 @@ void CharacterSystem::tick(double dt) { pLoc += (unitVecInDirection(sprite.movementDir) * speed); // Check collision. - CollisionResult collision = game_.getSystem().checkCollision(spriteId, pLoc, sprite.movementDir); + CollisionResult collision = game_.getSystem().checkCollision(spriteId, sprite.loc, pLoc, sprite.movementDir); bool blocked = collision.horiz.blocked || collision.vert.blocked; if (collision.horiz.blocked && !sprite.clipping) { diff --git a/src/game.cpp b/src/game.cpp index 6564da6..8ba4c85 100644 --- a/src/game.cpp +++ b/src/game.cpp @@ -69,7 +69,7 @@ void Game::loadMap(std::string filename) { if (p.movementSpeed != -1) { getSystem().initSprite(spriteId, p.movementSpeed); if (p.wander) { - getSprite(spriteId).wander = true; + getSprite(spriteId).behaviourType = BehaviourType::Wander; } } if (!p.enclosureZone.empty()) { diff --git a/src/input_system.cpp b/src/input_system.cpp index 49b27ec..38423a2 100644 --- a/src/input_system.cpp +++ b/src/input_system.cpp @@ -85,7 +85,7 @@ void InputSystem::tick(double dt) { if (sprite.controllable) { // Interacting with objects always uses Lucas's movement speed. vec2i checkLoc = sprite.loc + (unitVecInDirection(sprite.dir) * LUCAS_MOVEMENT_SPEED); - CollisionResult collision = game_.getSystem().checkCollision(spriteId, checkLoc, sprite.dir); + CollisionResult collision = game_.getSystem().checkCollision(spriteId, sprite.loc, checkLoc, sprite.dir); if (collision.horiz.blocked || collision.vert.blocked) { inFrontOfSomething = true; diff --git a/src/script_system.cpp b/src/script_system.cpp index 7f9f908..931759d 100644 --- a/src/script_system.cpp +++ b/src/script_system.cpp @@ -7,6 +7,7 @@ #include "transform_system.h" #include "effect_system.h" #include "camera_system.h" +#include "behaviour_system.h" #include "vector.h" ScriptSystem::ScriptSystem(Game& game) : game_(game) { @@ -42,7 +43,8 @@ ScriptSystem::ScriptSystem(Game& game) : game_(game) { "clipping", &Sprite::clipping, "cantCrouch", &Sprite::cantCrouch, "bobsWhenNormal", &Sprite::bobsWhenNormal, - "animSlowdown", &Sprite::animSlowdown); + "animSlowdown", &Sprite::animSlowdown, + "enclosureZone", &Sprite::enclosureZone); engine_.new_usertype( "message", @@ -93,6 +95,11 @@ ScriptSystem::ScriptSystem(Game& game) : game_(game) { "unlockCamera", &CameraSystem::unlockCamera, "setFollowingSprite", &CameraSystem::setFollowingSprite); + engine_.new_usertype( + "behaviour", + "directSpriteToLocation", &BehaviourSystem::directSpriteToLocation, + "isFollowingPath", &BehaviourSystem::isFollowingPath); + engine_.new_usertype( "mixer", "playSound", &Mixer::playSound, @@ -145,6 +152,12 @@ ScriptSystem::ScriptSystem(Game& game) : game_(game) { return game_.getSystem(); }); + engine_.set_function( + "behaviour", + [&] () -> BehaviourSystem& { + return game_.getSystem(); + }); + engine_.set_function( "mixer", [&] () -> Mixer& { diff --git a/src/sprite.h b/src/sprite.h index 733c792..13d0383 100644 --- a/src/sprite.h +++ b/src/sprite.h @@ -40,12 +40,23 @@ enum class CharacterMedium { Water }; +enum class BehaviourType { + None, + Wander, + Path +}; + struct Movement { vec2i pos; Direction dir; CharacterMedium medium; }; +struct PathfindingInstruction { + Direction dir; + vec2i endpoint; +}; + class Sprite { public: @@ -106,7 +117,10 @@ public: bool player = false; // Behaviour - bool wander = false; + BehaviourType behaviourType = BehaviourType::None; + vec2i pathfindingDestination; + bool cardinalDirectionsOnly = false; + std::deque path; }; #endif /* end of include guard: SPRITE_H_70503825 */ diff --git a/src/transform_system.cpp b/src/transform_system.cpp index 4056f46..71b3a4f 100644 --- a/src/transform_system.cpp +++ b/src/transform_system.cpp @@ -47,7 +47,7 @@ void TransformSystem::moveSprite(int spriteId, vec2i newLoc) { } } -CollisionResult TransformSystem::checkCollision(int spriteId, vec2i newLoc, Direction dir) { +CollisionResult TransformSystem::checkCollision(int spriteId, vec2i curLoc, vec2i newLoc, Direction dir) { CollisionResult result; Sprite& sprite = game_.getSprite(spriteId); @@ -57,7 +57,7 @@ CollisionResult TransformSystem::checkCollision(int spriteId, vec2i newLoc, Dire vec2i mapBounds = map.getMapSize() * map.getTileSize(); - vec2i oldColUL = sprite.loc + sprite.collisionOffset; + vec2i oldColUL = curLoc + sprite.collisionOffset; vec2i oldColDR = oldColUL + sprite.collisionSize; vec2i newColUL = newLoc + sprite.collisionOffset; vec2i newColDR = newColUL + sprite.collisionSize; diff --git a/src/transform_system.h b/src/transform_system.h index a07447c..6707347 100644 --- a/src/transform_system.h +++ b/src/transform_system.h @@ -45,7 +45,7 @@ public: }); } - CollisionResult checkCollision(int spriteId, vec2i newLoc, Direction dir); + CollisionResult checkCollision(int spriteId, vec2i curLoc, vec2i newLoc, Direction dir); CharacterMedium getMediumAtPosition(int spriteId, vec2i newLoc); diff --git a/src/vector.h b/src/vector.h index 9f6d54f..c7b58dc 100644 --- a/src/vector.h +++ b/src/vector.h @@ -109,6 +109,10 @@ public: return (x() != other.x()) || (y() != other.y()); } + bool operator<(const vec2& other) const { + return std::tie(x(), y()) < std::tie(other.x(), other.y()); + } + }; using vec2i = vec2; -- cgit 1.4.1