Test case: pathfinding

TEST_CASE_METHOD(ServerAndClientWithData, "Pathfinding") {
  GIVEN("a colliding square wall object type, and a wolf NPC") {
    auto data = ""s;
    data = R"(
      <npcType id="wolf" maxHealth="10000" attack="1" speed="100"
        pursuesEndlessly="1" >
        <collisionRect x="-5" y="-5" w="10" h="10" />
      </npcType>
      <objectType id="wall">
        <collisionRect x="-5" y="-5" w="10" h="10" />
      </objectType>
    )";

    SECTION("Single static obstacle") {
      GIVEN("a wall between a wolf and a player") {
        useData(data.c_str());
        server->addObject("wall", {60, 10});
        auto &wolf = server->addNPC("wolf", {90, 10});

        WHEN("the wolf starts chasing the user") {
          wolf.makeAwareOf(*user);

          THEN("it can reach him") {
            WAIT_UNTIL_TIMEOUT(distance(wolf, *user) <= wolf.attackRange(),
                               10000);
          }
        }
      }
    }

    SECTION("Random obstacles") {
      GIVEN("three walls randomly between a wolf and the user") {
        data += R"(
            <spawnPoint y="55" x="55" type="wall" quantity="3" radius="50" />
          )";
        useData(data.c_str());

        auto &wolf = server->addNPC("wolf", {100, 100});

        WHEN("the wolf starts chasing the user") {
          wolf.makeAwareOf(*user);

          THEN("it can reach him") {
            WAIT_UNTIL_TIMEOUT(distance(wolf, *user) <= wolf.attackRange(),
                               10000);
          }
        }
      }
    }

    SECTION("Reacting to a path becoming blocked") {
      GIVEN("a clear path between wolf and user") {
        useData(data.c_str());
        auto &wolf = server->addNPC("wolf", {280, 10});

        WHEN("the wolf starts following a path to the user") {
          const auto wolfStartLocation = wolf.location();
          wolf.makeAwareOf(*user);
          WAIT_UNTIL(wolf.location() != wolfStartLocation);

          AND_WHEN("a wall appears that blocks the wolf") {
            server->addObject("wall", {200, 10});

            THEN("the wolf can reach the user without getting stuck") {
              WAIT_UNTIL_TIMEOUT(distance(wolf, *user) <= wolf.attackRange(),
                                 3000);
            }
          }
        }
      }
    }

    SECTION("Reacting to the target moving") {
      GIVEN("a clear path between wolf and user") {
        useData(data.c_str());
        auto &wolf = server->addNPC("wolf", {280, 10});

        WHEN("the wolf starts following a path to the user") {
          const auto wolfStartLocation = wolf.location();
          wolf.makeAwareOf(*user);
          WAIT_UNTIL(wolf.location() != wolfStartLocation);

          AND_WHEN("the user teleports away") {
            user->teleportTo({200, 200});

            THEN("the wolf can reach the user") {
              WAIT_UNTIL_TIMEOUT(distance(wolf, *user) <= wolf.attackRange(),
                                 10000);
            }
          }
        }
      }
    }

    SECTION("Performance on a large, empty map") {
      GIVEN("a very large map") {
        data += LARGE_MAP;
        useData(data.c_str());

        AND_GIVEN("a wolf that's very far from the player") {
          auto &wolf = server->addNPC("wolf", {2000, 2000});

          WHEN("the wolf starts chasing the user") {
            wolf.makeAwareOf(*user);

            THEN("it begins moving in a reasonable amount of time") {
              const auto originalLocation = wolf.location();
              REPEAT_FOR_MS(500);
              CHECK(wolf.isAwareOf(*user));
              CHECK(wolf.location() != originalLocation);
            }
          }
        }
      }
    }

    SECTION("Obstacles are properly identified across collision chunks") {
      GIVEN("a map spanning a number of collision chunks") {
        data += R"(
          <newPlayerSpawn x="10" y="10" range="0" />
          <terrain index="." id="grass" />
          <list id="default" default="1" >
            <allow id="grass" />
          </list>
          <size x="30" y="2" />
          <row y= "0" terrain = ".............................." />
          <row y= "1" terrain = ".............................." />
        )";
        useData(data.c_str());

        AND_GIVEN("the user is blocked by walls in the leftmost chunk") {
          /* ...W....|.......|.......|...
             .U.W....|.......|.......|.N.
             ...W....|.......|.......|... */
          server->addObject("wall", {150, 5});
          server->addObject("wall", {150, 15});
          server->addObject("wall", {150, 25});
          server->addObject("wall", {150, 35});
          server->addObject("wall", {150, 45});
          server->addObject("wall", {150, 55});
          server->addObject("wall", {150, 65});

          AND_GIVEN("a wolf on the opposite side of the map") {
            auto &wolf = server->addNPC("wolf", {900, 30});

            WHEN("the wolf tries to chase the user") {
              const auto wolfStartingPosition = wolf.location();
              wolf.makeAwareOf(*user);

              THEN("the wolf never moves (i.e., it knows there's no path") {
                REPEAT_FOR_MS(1000);
                CHECK(wolf.location() == wolfStartingPosition);
              }
            }
          }
        }
      }
    }

    SECTION("More efficient than breadth-first") {
      GIVEN("a very large map") {
        data += LARGE_MAP;
        useData(data.c_str());

        AND_GIVEN("the user is walled off to block the direct-path shortcut") {
          /* ...W.
             .U.W.
             ...W.
             ...W.
             .....
             WWWW.
             ..... */
          server->addObject("wall", {90, 0});
          server->addObject("wall", {90, 10});
          server->addObject("wall", {90, 20});
          server->addObject("wall", {90, 30});
          server->addObject("wall", {0, 90});
          server->addObject("wall", {10, 90});
          server->addObject("wall", {20, 90});
          server->addObject("wall", {30, 90});
          server->addObject("wall", {40, 90});
          server->addObject("wall", {50, 90});
          server->addObject("wall", {60, 90});
          server->addObject("wall", {70, 90});
          server->addObject("wall", {80, 90});
          server->addObject("wall", {90, 90});

          AND_GIVEN("a wolf on the opposite side of the map from the user") {
            auto &wolf = server->addNPC("wolf", {2000, 2000});

            WHEN("the wolf starts chasing the user") {
              const auto originalLocation = wolf.location();
              wolf.makeAwareOf(*user);

              THEN("it begins moving in a reasonable amount of time") {
                WAIT_UNTIL_TIMEOUT(wolf.location() != originalLocation, 5000);
              }
            }
          }
        }
      }
    }

    SECTION("a large target entity doesn't block pathfinding to it") {
      GIVEN("dinosaurs have a wide collision rect") {
        data += R"(
          <npcType id="dinosaur">
            <collisionRect x="-100" y="-100" w="200" h="200" />
          </npcType>
        )";
        useData(data.c_str());

        AND_GIVEN("a dinosaur and a wolf hostile to it") {
          auto &dinosaur = server->addNPC("dinosaur", {100, 150});
          dinosaur.permissions.setPlayerOwner(user->name());
          dinosaur.ai.giveOrder(AI::PetOrder::ORDER_TO_STAY);

          auto &wolf = server->addNPC("wolf", {275, 150});

          WHEN("the wolf starts chasing the dinosaur") {
            const auto originalLocation = wolf.location();
            wolf.makeAwareOf(dinosaur);

            THEN("it begins moving (i.e., a path is successfully found)") {
              WAIT_UNTIL_TIMEOUT(wolf.location() != originalLocation, 5000);
            }
          }
        }
      }
    }
  }

  GIVEN("walls, and ranged longbowmen") {
    auto data = R"(
      <npcType id="longbowman" maxHealth="10000" attack="1" isRanged="1"
        pursuesEndlessly="1" >
        <collisionRect x="-5" y="-5" w="10" h="10" />
      </npcType>
      <objectType id="wall">
        <collisionRect x="-5" y="-5" w="10" h="10" />
      </objectType>
    )";
    useData(data);

    AND_GIVEN("the user is blocked off from a longbowman") {
      auto &longbowman = server->addNPC("longbowman", {280, 280});
      server->addObject("wall", {90, 0});
      server->addObject("wall", {90, 10});
      server->addObject("wall", {90, 20});
      server->addObject("wall", {90, 30});
      server->addObject("wall", {90, 40});
      server->addObject("wall", {90, 50});
      server->addObject("wall", {90, 60});
      server->addObject("wall", {90, 70});
      server->addObject("wall", {90, 80});
      server->addObject("wall", {0, 90});
      server->addObject("wall", {10, 90});
      server->addObject("wall", {20, 90});
      server->addObject("wall", {30, 90});
      server->addObject("wall", {40, 90});
      server->addObject("wall", {50, 90});
      server->addObject("wall", {60, 90});
      server->addObject("wall", {70, 90});
      server->addObject("wall", {80, 90});
      server->addObject("wall", {90, 90});

      SECTION("longer-ranged NPCs don't need to path as close") {
        WHEN("the longbowman starts chasing the player") {
          longbowman.makeAwareOf(*user);

          THEN("the user takes damage)") {
            WAIT_UNTIL_TIMEOUT(user->health() < user->stats().maxHealth, 10000);
          }
        }
      }

      SECTION("ranged pets follow close") {
        WHEN("the longbowman becomes the user's pet [and tries to follow]") {
          longbowman.permissions.setPlayerOwner(user->name());

          THEN("it doesn't move (i.e., correctly concludes there's no path)") {
            const auto oldLocation = longbowman.location();
            REPEAT_FOR_MS(1000);
            CHECK(longbowman.location() == oldLocation);
          }
        }
      }
    }
  }

  SECTION("Path lengths are limited") {
    GIVEN("kobold NPCs (without pursuesEndlessly)") {
      auto data = ""s;
      data = R"(
        <npcType id="kobold" attack="1" />
      )";

      AND_GIVEN("a very large map") {
        data += LARGE_MAP;
        useData(data.c_str());

        AND_GIVEN("a kobold on the other side of the map from the user") {
          auto &kobold = server->addNPC("kobold", {2000, 2000});

          WHEN("the kobold starts chasing the user") {
            const auto originalLocation = kobold.location();
            kobold.makeAwareOf(*user);

            THEN("it never moves") {
              REPEAT_FOR_MS(5000);
              CHECK(kobold.location() == originalLocation);
            }
          }
        }
      }
    }
  }
}