fork(1) download
copy 
  1. #include <vector>
  2. #include <iostream>
  3. #include <functional>
  4. #include <stack>
  5. #include <array>
  6. #include <limits>
  7. #include <cmath>
  8.  
  9. #include <chrono>
  10.  
  11.  
  12. struct SDL_Point {
  13.     int x, y;
  14. };
  15. namespace pathfinders {
  16.     enum class Heuristic : unsigned char {
  17.         kManhattan,   // Best for 4-directional
  18.         kDiagonal,   // Best for 8-directional
  19.         kChebyshev,   // Diagonal with `D = D2 = 1`
  20.         kOctile,   // Diagonal with `D = 1, D2 = std::sqrt(2)`
  21.         kEuclidean,   // Works for any directions
  22.         kConstantZero,   // `g << h`, reverts into Dijkstra
  23.         kContantInf,   // `g >> h`, reverts into Greedy Best-First-Search
  24.     };
  25.  
  26.     enum class MovementType : bool {
  27.         k4Directional,
  28.         k8Directional,
  29.     };
  30.  
  31.     enum class Status : unsigned char {
  32.         kInvalidSrc,
  33.         kInvalidDest,
  34.         kBlockedSrc,
  35.         kBlockedDest,
  36.         kCoincidents,
  37.  
  38.         kSuccess,
  39.         kFailure,
  40.     };
  41.  
  42.     struct Cell {
  43.         int x, y;
  44.  
  45.         inline bool operator==(Cell const& other) const { return x == other.x && y == other.y; }
  46.         inline Cell operator+(Cell const& other) const { return { x + other.x, y + other.y }; }
  47.         inline Cell operator-(Cell const& other) const { return { x - other.x, y - other.y }; }
  48.         friend inline std::ostream& operator<<(std::ostream& os, Cell const& self) { return os << '(' << self.x << ", " << self.y << ')'; }
  49.  
  50.         static inline SDL_Point cltopt(Cell const& self) { return { self.x, self.y }; }
  51.         static inline Cell pttocl(SDL_Point const& pt) { return { pt.x, pt.y }; }
  52.  
  53.         static double getG(Cell const& distance);
  54.  
  55.         template <Heuristic H>
  56.         typename std::enable_if_t<H == Heuristic::kManhattan, double>
  57.         static getH(Cell const& lhs, Cell const& rhs);
  58.  
  59.         template <Heuristic H>
  60.         typename std::enable_if_t<H == Heuristic::kChebyshev, double>
  61.         static getH(Cell const& lhs, Cell const& rhs);
  62.  
  63.         template <Heuristic H>
  64.         typename std::enable_if_t<H == Heuristic::kOctile, double>
  65.         static getH(Cell const& lhs, Cell const& rhs);
  66.  
  67.         template <Heuristic H>
  68.         typename std::enable_if_t<H == Heuristic::kEuclidean, double>
  69.         static getH(Cell const& lhs, Cell const& rhs);
  70.  
  71.         template <Heuristic H>
  72.         typename std::enable_if_t<H == Heuristic::kConstantZero, double>
  73.         static constexpr inline getH(Cell const& lhs, Cell const& rhs) { return 0; }
  74.  
  75.         template <Heuristic H>
  76.         typename std::enable_if_t<H == Heuristic::kContantInf, double>
  77.         static constexpr inline getH(Cell const& lhs, Cell const& rhs) { return std::pow(10, 307); }   // Might cause overflow
  78.  
  79.         struct Data;   // Forward declaration to prevent "incomplete type" compilation error
  80.  
  81.         private:
  82.             template <Heuristic H, unsigned short int Dsq, unsigned short int D2sq>   // Floating-point template parameter is nonstandardC/C++(605)
  83.             typename std::enable_if_t<H == Heuristic::kDiagonal, double>
  84.             static getH(Cell const& lhs, Cell const& rhs);
  85.     };
  86.  
  87.     struct Cell::Data {
  88.         Cell parent;
  89.         double g, h, f = std::numeric_limits<double>::max();
  90.     };
  91.  
  92.     struct Result {
  93.         const Status status;
  94.         std::stack<Cell> path;
  95.  
  96.         Result(Status status, std::stack<Cell> path = {}) : status(status), path(path) {}
  97.         inline Result(Status status, Cell const& cell) : status(status) { path.push(cell); }
  98.     };
  99.  
  100.     /**
  101.      * @brief Implementation of A* pathfinding algorithm.
  102.      * @see https://w...content-available-to-author-only...s.org/a-search-algorithm/
  103.     */
  104.     template <Heuristic H = Heuristic::kManhattan, MovementType M = MovementType::k4Directional>
  105.     class ASPF {
  106.         public:
  107.             ASPF(std::vector<std::vector<int>> const& grid);
  108.             ~ASPF() = default;
  109.  
  110.             void setBegin(Cell const& begin);
  111.             void setEnd(Cell const& end);
  112.  
  113.             Result search(Cell const& src, Cell const& dest) const;
  114.             Result quicksearch(Cell const& src, Cell const& dest) const;
  115.  
  116.         private:
  117.             bool isValid(Cell const& cell) const;
  118.             bool isUnblocked(Cell const& cell) const;
  119.             bool isUnblocked(Cell const& parent, Cell const& successor) const;
  120.  
  121.             std::stack<Cell> getPath(std::vector<std::vector<Cell::Data>> const& cellData, Cell const& dest) const;
  122.  
  123.             static inline constexpr auto getDirections() {
  124.                 if constexpr(M == MovementType::k4Directional) {
  125.                     return std::array<Cell, 4>{{
  126.                         { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 },
  127.                     }};
  128.                 } else {
  129.                     return std::array<Cell, 8>{{
  130.                         { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 },
  131.                         { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 },
  132.                     }};
  133.                 }
  134.             }
  135.  
  136.             std::vector<std::vector<int>> const& mGrid;
  137.             Cell mBegin, mEnd;
  138.  
  139.             static inline constexpr auto mDirections = getDirections();
  140.     };
  141.  
  142.     /**
  143.      * @brief Implementation of Dijkstra pathfinding algorithm (reverted from A* search algorithm by setting heuristic `h` to constant `0`).
  144.      * @see https://c...content-available-to-author-only...e.com/questions/83618/best-heuristic-for-a
  145.      * @see https://t...content-available-to-author-only...d.edu/~amitp/GameProgramming/Heuristics.html
  146.     */
  147.     template <MovementType M = MovementType::k4Directional>
  148.     using DJPF = ASPF<Heuristic::kConstantZero, M>;
  149.  
  150.     /**
  151.      * @brief Implementation of Greedy Best-First-Search pathfinding algorithm (reverted from A* search algorithm by setting heuristic `h` to be much higher than `g` so that `g` do not contribute to `f`).
  152.      * @see https://t...content-available-to-author-only...d.edu/~amitp/GameProgramming/Heuristics.html
  153.     */
  154.     template <MovementType M = MovementType::k4Directional>
  155.     using GBFSPF = ASPF<Heuristic::kContantInf, M>;
  156. };
  157.  
  158.  
  159.  
  160. double pathfinders::Cell::getG(Cell const& cell) {
  161.     return std::sqrt(std::pow(cell.x, 2) + std::pow(cell.y, 2));
  162. }
  163.  
  164. template <pathfinders::Heuristic H>
  165. typename std::enable_if_t<H == pathfinders::Heuristic::kManhattan, double>
  166. pathfinders::Cell::getH(Cell const& cell, Cell const& dest) {
  167.     return std::abs(cell.x - dest.x) + std::abs(cell.y - dest.y);
  168. }
  169.  
  170. template <pathfinders::Heuristic H, unsigned short int Dsq, unsigned short int D2sq>
  171. typename std::enable_if_t<H == pathfinders::Heuristic::kDiagonal, double>
  172. pathfinders::Cell::getH(Cell const& cell, Cell const& dest) {
  173.     auto dx = std::abs(cell.x - dest.x);
  174.     auto dy = std::abs(cell.y - dest.y);
  175.     return std::sqrt(Dsq) * std::max(dx, dy) + (std::sqrt(D2sq) - std::sqrt(Dsq)) * std::min(dx, dy);
  176. }
  177.  
  178. template <pathfinders::Heuristic H>
  179. typename std::enable_if_t<H == pathfinders::Heuristic::kChebyshev, double>
  180. pathfinders::Cell::getH(Cell const& cell, Cell const& dest) {
  181.     return getH<Heuristic::kDiagonal, 1, 1>(cell, dest);
  182. }
  183.  
  184. template <pathfinders::Heuristic H>
  185. typename std::enable_if_t<H == pathfinders::Heuristic::kOctile, double>
  186. pathfinders::Cell::getH(Cell const& cell, Cell const& dest) {
  187.     return getH<Heuristic::kDiagonal, 1, 2>(cell, dest);
  188. }
  189.  
  190. template <pathfinders::Heuristic H>
  191. typename std::enable_if_t<H == pathfinders::Heuristic::kEuclidean, double>
  192. pathfinders::Cell::getH(Cell const& cell, Cell const& dest) {
  193.     return std::sqrt(std::pow(cell.x - dest.x, 2) + std::pow(cell.y - dest.y, 2));
  194. }
  195.  
  196. template <pathfinders::Heuristic H, pathfinders::MovementType M>
  197. pathfinders::ASPF<H, M>::ASPF(std::vector<std::vector<int>> const& grid) : mGrid(grid) {
  198.     setBegin({ 0, 0 });
  199.     setEnd({ 0, 0 });
  200. }
  201.  
  202. template <pathfinders::Heuristic H, pathfinders::MovementType M>
  203. bool pathfinders::ASPF<H, M>::isValid(Cell const& cell) const {
  204.     return static_cast<int>(mBegin.x) <= cell.x && cell.x <= static_cast<int>(mEnd.x) && static_cast<int>(mBegin.y) <= cell.y && cell.y <= static_cast<int>(mEnd.y);
  205. }
  206.  
  207. template <pathfinders::Heuristic H, pathfinders::MovementType M>
  208. bool pathfinders::ASPF<H, M>::isUnblocked(Cell const& cell) const {
  209.     return mGrid[cell.y][cell.x] != 0;
  210. }
  211.  
  212. template <pathfinders::Heuristic H, pathfinders::MovementType M>
  213. bool pathfinders::ASPF<H, M>::isUnblocked(Cell const& cell, Cell const& successor) const {
  214.     return mGrid[successor.y][successor.x] != 0;
  215. }
  216.  
  217. template <pathfinders::Heuristic H, pathfinders::MovementType M>
  218. std::stack<pathfinders::Cell> pathfinders::ASPF<H, M>::getPath(std::vector<std::vector<Cell::Data>> const& cellData, Cell const& dest) const {
  219.     std::stack<Cell> path;
  220.     auto curr = dest;
  221.  
  222.     while (!(cellData[curr.y - mBegin.y][curr.x - mBegin.x].parent == curr)) {
  223.         path.push(curr);
  224.         curr = cellData[curr.y - mBegin.y][curr.x - mBegin.x].parent;
  225.     }
  226.  
  227.     path.push(curr);
  228.     return path;
  229. }
  230.  
  231. template <pathfinders::Heuristic H, pathfinders::MovementType M>
  232. void pathfinders::ASPF<H, M>::setBegin(Cell const& begin) {
  233.     mBegin = {
  234.         std::max(0, begin.x),
  235.         std::max(0, begin.y),
  236.     };
  237. }
  238.  
  239. template <pathfinders::Heuristic H, pathfinders::MovementType M>
  240. void pathfinders::ASPF<H, M>::setEnd(Cell const& end) {
  241.     mEnd = {
  242.         std::min(static_cast<int>(mGrid.front().size()) - 1, end.x),
  243.         std::min(static_cast<int>(mGrid.size()) - 1, end.y),
  244.     };
  245. }
  246.  
  247. template <pathfinders::Heuristic H, pathfinders::MovementType M>
  248. pathfinders::Result pathfinders::ASPF<H, M>::search(Cell const& src, Cell const& dest) const {
  249.     if (mGrid.empty()) return Result(Status::kFailure);
  250.  
  251.     if (!isValid(src)) return Result(Status::kInvalidSrc);
  252.     if (!isValid(dest)) return Result(Status::kInvalidDest);
  253.     if (!isUnblocked(src)) return Result(Status::kBlockedSrc);
  254.     if (!isUnblocked(dest)) return Result(Status::kBlockedDest);
  255.     if (src == dest) return Result(Status::kCoincidents);
  256.  
  257.     // Note that index-based operations on two following lists require substracting `mBegin` to match `mGrid`
  258.     // Initialize closed list
  259.     std::vector<std::vector<bool>> closedList(mEnd.y - mBegin.y + 1, std::vector<bool>(mEnd.x - mBegin.x + 1, false));   // `false` means not visited (and vice versa)
  260.  
  261.     // Initialize cell data list
  262.     std::vector<std::vector<Cell::Data>> cellDataList(mEnd.y - mBegin.y + 1, std::vector<Cell::Data>(mEnd.x - mBegin.x + 1, Cell::Data{}));
  263.  
  264.     // Initialize starting node parameters
  265.     auto& srcData = cellDataList[src.y - mBegin.y][src.x - mBegin.x];
  266.     srcData.f = 0;
  267.     srcData.parent = src;
  268.  
  269.     // Initialize open list
  270.     std::stack<Cell> openList;   // For operations at O(1) time complexity
  271.     openList.push(src);   // Place the starting cell on the open list
  272.  
  273.     double g, h, f;
  274.  
  275.     while (!openList.empty()) {
  276.         g = h = f = 0;
  277.  
  278.         auto parent = openList.top();
  279.         openList.pop();   // Remove cell from open list
  280.         closedList[parent.y - mBegin.y][parent.x - mBegin.x] = true;   // Add cell to closed list
  281.  
  282.         // Generate all successors
  283.         for (const auto& direction : mDirections) {
  284.             auto successor = parent + direction;
  285.             if (!isValid(successor)) continue;
  286.  
  287.             // If successor is destination, search is considered successful
  288.             if (successor == dest) {
  289.                 cellDataList[successor.y - mBegin.y][successor.x - mBegin.x].parent = parent;
  290.                 return Result(Status::kSuccess, getPath(cellDataList, dest));
  291.             }
  292.  
  293.             // Ignore if successor is already on the closed list or is blocked
  294.             if (!closedList[successor.y - mBegin.y][successor.x - mBegin.x] && isUnblocked(successor)) {
  295.                 g = cellDataList[parent.y - mBegin.y][parent.x - mBegin.x].g + Cell::getG(direction);
  296.                 h = Cell::getH<H>(successor, dest);
  297.                 f = g + h;
  298.  
  299.                 auto& successorData = cellDataList[successor.y - mBegin.y][successor.x - mBegin.x];
  300.  
  301.                 // Add successor to the open list if successor is not on the open list or provides a better path
  302.                 if (successorData.f == std::numeric_limits<double>::max() || successorData.f > f) {
  303.                     openList.push(successor);
  304.  
  305.                     // Update successor data
  306.                     successorData.f = f;
  307.                     successorData.g = g;
  308.                     successorData.h = h;
  309.                     successorData.parent = parent;
  310.                 }
  311.             }
  312.         }
  313.     }
  314.  
  315.     // Search is considered unsuccessful if the open list is emptied before destination cell is found
  316.     return Result(Status::kFailure);
  317. }
  318.  
  319. /**
  320.  * @note Only returns direction.
  321. */
  322. template <pathfinders::Heuristic H, pathfinders::MovementType M>
  323. pathfinders::Result pathfinders::ASPF<H, M>::quicksearch(Cell const& src, Cell const& dest) const {
  324.     // Pre-checks as usual
  325.     if (mGrid.empty()) return Result(Status::kFailure);
  326.  
  327.     if (!isValid(src)) return Result(Status::kInvalidSrc);
  328.     if (!isValid(dest)) return Result(Status::kInvalidDest);
  329.     if (!isUnblocked(src)) return Result(Status::kBlockedSrc);
  330.     if (!isUnblocked(dest)) return Result(Status::kBlockedDest);
  331.     if (src == dest) return Result(Status::kCoincidents);
  332.  
  333.     double fc = std::numeric_limits<double>::min();
  334.     Cell directionc;
  335.  
  336.     for (const auto& direction : mDirections) {
  337.         auto successor = src + direction;
  338.         if (!isValid(successor) || !isUnblocked(successor)) continue;
  339.  
  340.         if (successor == dest) return Result(Status::kSuccess, direction);   // If successor is destination, search is considered successful
  341.  
  342.         // Calculate `f` value of successor
  343.         double f = std::sqrt(std::pow(direction.x, 2) + std::pow(direction.y, 2)) + Cell::getH<H>(successor, dest);
  344.  
  345.         // Cache the successor if it provides a better path
  346.         if (f > fc) {
  347.             fc = f;
  348.             directionc = direction;
  349.         } 
  350.     }
  351.  
  352.     // Search is considered unsuccessful if the open list is emptied before destination cell is found
  353.     return fc == std::numeric_limits<double>::min() ? Result(Status::kFailure) : Result(Status::kSuccess, directionc);
  354. }
  355.  
  356.  
  357. template class pathfinders::ASPF<pathfinders::Heuristic::kManhattan, pathfinders::MovementType::k4Directional>;
  358.  
  359.  
  360. /* * * * * * */
  361. int main(void) {
  362.     std::vector<std::vector<int>> vec = {
  363. {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
  364. {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
  365. {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
  366. {{ 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, }},
  367. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889,
  368.  5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  369. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 0, 0, 0, 0, 0, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  370. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  371. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 0, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  372. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  373. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  374. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  375. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  376. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  377. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  378. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  379. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  380. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  381. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  382. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  383. {{ 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, 5889, 0, 0, 5889, }},
  384. {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
  385. {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
  386. {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
  387. {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
  388. {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
  389.     };
  390.  
  391.     // input is not inverted
  392.     pathfinders::Cell src = { 1120 / 32, 384 / 32 };
  393.     pathfinders::Cell dest = { 32 / 32, 384 / 32 };
  394.  
  395.     pathfinders::Cell range = { std::numeric_limits<short>::max(), std::numeric_limits<short>::max() };
  396.  
  397.     auto obj = pathfinders::ASPF<pathfinders::Heuristic::kEuclidean>(vec);
  398.     obj.setBegin(src - range);
  399.     obj.setEnd(src + range);
  400.  
  401.     auto start = std::chrono::high_resolution_clock::now();
  402.  
  403.     auto res = obj.search(src, dest);
  404.     auto dir = obj.quicksearch(src, dest);
  405.  
  406.     auto end = std::chrono::high_resolution_clock::now();
  407.     auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
  408.  
  409.     std::cout << "Execution time: " << duration.count() << " ms" << std::endl;
  410.     std::cout << "Status: " << static_cast<int>(res.status) << std::endl;
  411.  
  412.     auto path = res.path;
  413.     while (path.size() > 1) {
  414.         std::cout << "(" << path.top().x << ", " << path.top().y << ") -> ";
  415.         path.pop();
  416.     }
  417.     std::cout << path.top() << std::endl;
  418.  
  419.     std::cout << "Status-dir: " << static_cast<int>(dir.status) << std::endl;
  420.     std::cout << dir.path.top().x << ", " << dir.path.top().y << std::endl;
  421.  
  422.     return 0;
  423. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Execution time: 72 ms
Status: 5
(35, 12) -> (35, 11) -> (35, 10) -> (35, 9) -> (35, 8) -> (35, 7) -> (35, 6) -> (35, 5) -> (35, 4) -> (34, 4) -> (33, 4) -> (33, 5) -> (33, 6) -> (33, 7) -> (33, 8) -> (33, 9) -> (33, 10) -> (33, 11) -> (33, 12) -> (33, 13) -> (33, 14) -> (33, 15) -> (33, 16) -> (33, 17) -> (33, 18) -> (32, 18) -> (31, 18) -> (31, 17) -> (31, 16) -> (31, 15) -> (31, 14) -> (31, 13) -> (31, 12) -> (31, 11) -> (31, 10) -> (31, 9) -> (31, 8) -> (31, 7) -> (31, 6) -> (31, 5) -> (31, 4) -> (30, 4) -> (29, 4) -> (29, 5) -> (29, 6) -> (29, 7) -> (29, 8) -> (29, 9) -> (29, 10) -> (29, 11) -> (29, 12) -> (29, 13) -> (29, 14) -> (29, 15) -> (29, 16) -> (29, 17) -> (29, 18) -> (28, 18) -> (27, 18) -> (27, 17) -> (27, 16) -> (27, 15) -> (27, 14) -> (27, 13) -> (27, 12) -> (27, 11) -> (27, 10) -> (27, 9) -> (27, 8) -> (27, 7) -> (27, 6) -> (27, 5) -> (27, 4) -> (26, 4) -> (25, 4) -> (25, 5) -> (25, 6) -> (25, 7) -> (25, 8) -> (25, 9) -> (25, 10) -> (25, 11) -> (25, 12) -> (25, 13) -> (25, 14) -> (25, 15) -> (25, 16) -> (25, 17) -> (25, 18) -> (24, 18) -> (23, 18) -> (23, 17) -> (23, 16) -> (23, 15) -> (23, 14) -> (23, 13) -> (23, 12) -> (23, 11) -> (23, 10) -> (23, 9) -> (23, 8) -> (23, 7) -> (23, 6) -> (23, 5) -> (23, 4) -> (22, 4) -> (21, 4) -> (21, 5) -> (21, 6) -> (21, 7) -> (21, 8) -> (21, 9) -> (21, 10) -> (21, 11) -> (21, 12) -> (21, 13) -> (21, 14) -> (21, 15) -> (21, 16) -> (21, 17) -> (21, 18) -> (20, 18) -> (19, 18) -> (19, 17) -> (19, 16) -> (19, 15) -> (19, 14) -> (19, 13) -> (19, 12) -> (19, 11) -> (19, 10) -> (19, 9) -> (19, 8) -> (19, 7) -> (19, 6) -> (19, 5) -> (19, 4) -> (18, 4) -> (17, 4) -> (17, 5) -> (17, 6) -> (17, 7) -> (17, 8) -> (17, 9) -> (17, 10) -> (17, 11) -> (17, 12) -> (17, 13) -> (17, 14) -> (17, 15) -> (17, 16) -> (17, 17) -> (17, 18) -> (16, 18) -> (15, 18) -> (15, 17) -> (15, 16) -> (15, 15) -> (15, 14) -> (15, 13) -> (15, 12) -> (15, 11) -> (15, 10) -> (15, 9) -> (15, 8) -> (15, 7) -> (15, 6) -> (15, 5) -> (15, 4) -> (14, 4) -> (13, 4) -> (13, 5) -> (13, 6) -> (13, 7) -> (13, 8) -> (13, 9) -> (13, 10) -> (13, 11) -> (13, 12) -> (13, 13) -> (13, 14) -> (13, 15) -> (13, 16) -> (13, 17) -> (13, 18) -> (12, 18) -> (11, 18) -> (11, 17) -> (11, 16) -> (11, 15) -> (11, 14) -> (11, 13) -> (11, 12) -> (11, 11) -> (11, 10) -> (11, 9) -> (11, 8) -> (11, 7) -> (11, 6) -> (10, 6) -> (9, 6) -> (8, 6) -> (8, 7) -> (8, 8) -> (8, 9) -> (8, 10) -> (8, 11) -> (8, 12) -> (8, 13) -> (8, 14) -> (8, 15) -> (8, 16) -> (8, 17) -> (8, 18) -> (7, 18) -> (6, 18) -> (6, 17) -> (6, 16) -> (6, 15) -> (6, 14) -> (6, 13) -> (6, 12) -> (6, 11) -> (6, 10) -> (6, 9) -> (6, 8) -> (6, 7) -> (6, 6) -> (6, 5) -> (6, 4) -> (5, 4) -> (4, 4) -> (4, 5) -> (4, 6) -> (4, 7) -> (4, 8) -> (4, 9) -> (4, 10) -> (4, 11) -> (4, 12) -> (4, 13) -> (4, 14) -> (4, 15) -> (4, 16) -> (4, 17) -> (4, 18) -> (3, 18) -> (2, 18) -> (2, 17) -> (2, 16) -> (2, 15) -> (2, 14) -> (2, 13) -> (2, 12) -> (1, 12)
Status-dir: 5
1, 0
https://ideone.com/i9e0yg
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!