fork 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. #define RUN(h, m, t) \
  361. do {\
  362. 	double sum = 0;\
  363. 	\
  364. 	auto obj = pathfinders::ASPF<h, m>(vec);\
  365. 	obj.setBegin(src - range);\
  366. 	obj.setEnd(src + range);\
  367. 	\
  368. 	for (int i = 0; i < times; ++i) {\
  369. 		auto start = std::chrono::high_resolution_clock::now();\
  370. 	\
  371. 		auto res = obj.search(src, dest);\
  372. 		auto dir = obj.quicksearch(src, dest);\
  373. 	\
  374. 		auto end = std::chrono::high_resolution_clock::now();\
  375. 		auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);\
  376. 		sum += duration.count();\
  377. 	}\
  378. 	\
  379. 	std::cout << static_cast<int>(h) << "-" << static_cast<int>(m) << " : " << sum / times << " ms" << std::endl;\
  380. } while (0);
  381.  
  382. #define RUNM(h, t) \
  383. 	RUN(h, pathfinders::MovementType::k4Directional, t);\
  384. 	RUN(h, pathfinders::MovementType::k8Directional, t);
  385.  
  386. #define RUNHM(t) \
  387. do {\
  388. 	RUNM(pathfinders::Heuristic::kManhattan, t)\
  389. 	RUNM(pathfinders::Heuristic::kChebyshev, t)\
  390. 	RUNM(pathfinders::Heuristic::kOctile, t)\
  391. 	RUNM(pathfinders::Heuristic::kEuclidean, t)\
  392. 	RUNM(pathfinders::Heuristic::kConstantZero, t)\
  393. 	RUNM(pathfinders::Heuristic::kContantInf, t)\
  394. } while (0);
  395.  
  396.  
  397. /* * * * * * */
  398. int main(void) {
  399.     std::vector<std::vector<int>> vec = {
  400. {{ 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, }},
  401. {{ 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, }},
  402. {{ 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, }},
  403. {{ 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, }},
  404. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889,
  405.  5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  406. {{ 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, }},
  407. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  408. {{ 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, }},
  409. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  410. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  411. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  412. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  413. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  414. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  415. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  416. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  417. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  418. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  419. {{ 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, 5889, }},
  420. {{ 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, }},
  421. {{ 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, }},
  422. {{ 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, }},
  423. {{ 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, }},
  424. {{ 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, }},
  425. {{ 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, }},
  426.     };
  427.  
  428.     // input is not inverted
  429.     const pathfinders::Cell src = { 1120 / 32, 384 / 32 };
  430.     const pathfinders::Cell dest = { 32 / 32, 384 / 32 };
  431.     const pathfinders::Cell range = { std::numeric_limits<short>::max(), std::numeric_limits<short>::max() };
  432.  
  433. 	constexpr std::size_t times = 1e2;
  434. 	std::cout << "Running tests for t = " << times << std::endl;
  435. 	RUNHM(t);
  436.  
  437. 	// for (int i = 0; i < times; ++i) {
  438. 	// 	auto obj = pathfinders::ASPF<h, m>(vec);
  439. 	// 	obj.setBegin(src - range);
  440. 	// 	obj.setEnd(src + range);
  441.  
  442. 	// 	auto start = std::chrono::high_resolution_clock::now();
  443.  
  444. 	// 	auto res = obj.search(src, dest);
  445. 	// 	auto dir = obj.quicksearch(src, dest);
  446.  
  447. 	// 	auto end = std::chrono::high_resolution_clock::now();
  448. 	// 	auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
  449. 	// 	sum += duration.count();
  450. 	// }
  451.  
  452. 	// std::cout << static_cast<int>(h) << "-" << static_cast<int>(m) << " : " << sum / times << " ms" << std::endl;
  453.  
  454.  
  455.  
  456.     // std::cout << "Execution time: " << duration.count() << " ms" << std::endl;
  457.     // std::cout << "Status: " << static_cast<int>(res.status) << std::endl;
  458.  
  459.     // auto path = res.path;
  460.     // while (path.size() > 1) {
  461.     //     std::cout << "(" << path.top().x << ", " << path.top().y << ") -> ";
  462.     //     path.pop();
  463.     // }
  464.     // std::cout << path.top() << std::endl;
  465.  
  466.     // std::cout << "Status-dir: " << static_cast<int>(dir.status) << std::endl;
  467.     // std::cout << dir.path.top().x << ", " << dir.path.top().y << std::endl;
  468.  
  469.     return 0;
  470. }
Success #stdin #stdout 0.03s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Running tests for t = 100
0-0 : 26.49 ms
0-1 : 12.11 ms
2-0 : 25.31 ms
2-1 : 12.17 ms
3-0 : 25.32 ms
3-1 : 12.68 ms
4-0 : 43.1 ms
4-1 : 20.23 ms
5-0 : 37.66 ms
5-1 : 19.21 ms
6-0 : 38.45 ms
6-1 : 12.18 ms
https://ideone.com/KKyW5L
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!