1 #ifndef JUMP_POINT_SEARCH_H
2 #define JUMP_POINT_SEARCH_H
3
4 // Public domain Jump Point Search implementation by False.Genesis
5 // Very fast pathfinding for uniform cost grids.
6 // Supports incremental pathfinding.
7
8 // Please keep the following source information intact when you use this file in your own projects:
9 // This file originates from: https://github.com/fgenesis/jps
10 // Based on the paper http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf
11 // by Daniel Harabor & Alban Grastien.
12 // Jumper (https://github.com/Yonaba/Jumper) and PathFinding.js (https://github.com/qiao/PathFinding.js)
13 // served as reference for this implementation.
14 // If you use this, attribution would be nice, but is not necessary.
15
16 // ====== COMPILE CONFIG ======
17
18 // If this is defined, compare all jumps against recursive reference implementation (only if _DEBUG is defined)
19 //#define JPS_VERIFY
20
21 // ============================
22
23 // Usage:
24 /*
25 // Define a class that overloads `operator()(x, y) const`, returning a value that can be treated as boolean.
26 // You are responsible for bounds checking!
27 // You want your operator() to be as fast as possible, as it will be called a LOT.
28
29 struct MyGrid
30 {
31 inline bool operator()(unsigned x, unsigned y) const
32 {
33 if(x < width && y < height) // Unsigned will wrap if < 0
34 ... return true if terrain at (x, y) is walkable.
35 }
36 unsigned width, height;
37 };
38
39 // Then you can retrieve a path:
40
41 MyGrid grid;
42 // ... set grid width, height, and whatever
43 unsigned step = 0; // set this to 1 if you want a detailed single-step path
44 // (e.g. if you plan to further mangle the path yourself),
45 // or any other higher value to output every Nth position.
46 JPS::PathVector path; // The resulting path will go here.
47
48
49 // Single-call interface:
50 bool found = JPS::findPath(path, grid, startx, starty, endx, endy, step);
51
52
53 // Alternatively, if you want more control:
54
55 JPS::Searcher<MyGrid> search(grid);
56 while(true)
57 {
58 // ..stuff happening ...
59
60 // build path incrementally from waypoints
61 JPS::Position a, b, c, d; // some waypoints
62 search.findPath(path, a, b);
63 search.findPath(path, b, c);
64 search.findPath(path, c, d);
65
66 if(!search.findPath(path2, JPS::Pos(startx, starty), JPS::Pos(endx, endy), step))
67 {
68 // ...handle failure...
69 }
70 // ... more stuff happening ...
71
72 // At convenient times, you can clean up accumulated nodes to reclaim memory.
73 // This is never necessary, but performance will drop if too many cached nodes exist.
74 if(mapWasReloaded)
75 search.freeMemory();
76 }
77
78 // Further remarks about the super lazy single-call function can be found at the bottom of this file.
79
80 // -------------------------------
81 // --- Incremental pathfinding ---
82 // -------------------------------
83
84 First, call findPathInit(Position start, Position end). Don't forget to check the return value,
85 as it may return NO_PATH if one or both of the points are obstructed,
86 or FOUND_PATH if the points are equal and not obstructed.
87 If it returns NEED_MORE_STEPS then the next part can start.
88
89 Repeatedly call findPathStep(int limit) until it returns NO_PATH or FOUND_PATH.
90 For consistency, you will want to ensure that the grid does not change between subsequent calls;
91 if the grid changes, parts of the path may go through a now obstructed area.
92 If limit is 0, it will perform the pathfinding in one go. Values > 0 abort the search
93 as soon as possible after the number of steps was exceeded, returning NEED_MORE_STEPS.
94 Use getStepsDone() after some test runs to find a good value for the limit.
95
96 Lastly, generate the actual path points from a successful run via findPathFinish(PathVector& path, unsigned step = 0).
97 Like described above, path points are appended, and granularity can be adjusted with the step parameter.
98 Returns false if the pathfinding did not finish or generating the path failed.
99
100 */
101
102
103 #include <stdlib.h>
104 #include <algorithm>
105 #include <vector>
106 #include <map>
107 #include <cmath>
108
109 #ifdef _DEBUG
110 #include <cassert>
111 #define JPS_ASSERT(cond) assert(cond)
112 #else
113 #define JPS_ASSERT(cond)
114 #endif
115
116
117 namespace JPS {
118
119 enum Result
120 {
121 NO_PATH = 0,
122 FOUND_PATH = 1,
123 NEED_MORE_STEPS = 2
124 };
125
126 struct Position
127 {
128 unsigned x, y;
129
130 inline bool operator==(const Position& p) const
131 {
132 return x == p.x && y == p.y;
133 }
134 inline bool operator!=(const Position& p) const
135 {
136 return x != p.x || y != p.y;
137 }
138
139 // for sorting
140 inline bool operator<(const Position& p) const
141 {
142 return y < p.y || (y == p.y && x < p.x);
143 }
144
isValidPosition145 inline bool isValid() const { return x != unsigned(-1); }
146 };
147
148 typedef std::vector<Position> PathVector;
149
150 // ctor function to keep Position a real POD struct.
Pos(unsigned x,unsigned y)151 inline static Position Pos(unsigned x, unsigned y)
152 {
153 Position p;
154 p.x = x;
155 p.y = y;
156 return p;
157 }
158
159 namespace Internal {
160
161 static const Position npos = Pos(-1, -1);
162
163 class Node
164 {
165 public:
Node(const Position & p)166 Node(const Position& p) : f(0), g(0), pos(p), parent(0), flags(0) {}
167 unsigned f, g;
168 const Position pos;
169 const Node *parent;
170
setOpen()171 inline void setOpen() { flags |= 1; }
setClosed()172 inline void setClosed() { flags |= 2; }
isOpen()173 inline unsigned char isOpen() const { return flags & 1; }
isClosed()174 inline unsigned char isClosed() const { return flags & 2; }
clearState()175 inline void clearState() { f = 0; g = 0, parent = 0; flags = 0; }
176
177 private:
178 unsigned char flags;
179
180 bool operator==(const Node& o); // not implemented, nodes should not be compared
181 };
182 } // end namespace Internal
183
184 namespace Heuristic
185 {
Manhattan(const Internal::Node * a,const Internal::Node * b)186 inline unsigned Manhattan(const Internal::Node *a, const Internal::Node *b)
187 {
188 return abs(int(a->pos.x - b->pos.x)) + abs(int(a->pos.y - b->pos.y));
189 }
190
Euclidean(const Internal::Node * a,const Internal::Node * b)191 inline unsigned Euclidean(const Internal::Node *a, const Internal::Node *b)
192 {
193 float fx = float(int(a->pos.x - b->pos.x));
194 float fy = float(int(a->pos.y - b->pos.y));
195 return unsigned(int(sqrtf(fx*fx + fy*fy)));
196 }
197 } // end namespace heuristic
198
199 namespace Internal {
200
201 typedef std::vector<Node*> NodeVector;
202
203 class OpenList
204 {
205 public:
push(Node * node)206 inline void push(Node *node)
207 {
208 JPS_ASSERT(node);
209 nodes.push_back(node);
210 std::push_heap(nodes.begin(), nodes.end(), _compare);
211 }
pop()212 inline Node *pop()
213 {
214 std::pop_heap(nodes.begin(), nodes.end(), _compare);
215 Node *node = nodes.back();
216 nodes.pop_back();
217 return node;
218 }
empty()219 inline bool empty() const
220 {
221 return nodes.empty();
222 }
clear()223 inline void clear()
224 {
225 nodes.clear();
226 }
fixup(const Node * item)227 inline void fixup(const Node *item)
228 {
229 std::make_heap(nodes.begin(), nodes.end(), _compare);
230 }
231
232 protected:
_compare(const Node * a,const Node * b)233 static inline bool _compare(const Node *a, const Node *b)
234 {
235 return a->f > b->f;
236 }
237 NodeVector nodes;
238 };
239
240 template <typename GRID> class Searcher
241 {
242 public:
Searcher(const GRID & g)243 Searcher(const GRID& g)
244 : grid(g), endNode(NULL), skip(1), stepsRemain(0), stepsDone(0)
245 {}
246
247 // single-call
248 bool findPath(PathVector& path, Position start, Position end, unsigned step = 0);
249
250 // incremental pathfinding
251 Result findPathInit(Position start, Position end);
252 Result findPathStep(int limit);
253 bool findPathFinish(PathVector& path, unsigned step = 0);
254
255 // misc
256 void freeMemory();
setSkip(int s)257 inline void setSkip(int s) { skip = std::max(1, s); }
getStepsDone()258 inline size_t getStepsDone() const { return stepsDone; }
getNodesExpanded()259 inline size_t getNodesExpanded() const { return nodegrid.size(); }
260
261 private:
262
263 typedef std::map<Position, Node> NodeGrid;
264
265 const GRID& grid;
266 Node *endNode;
267 int skip;
268 int stepsRemain;
269 size_t stepsDone;
270 OpenList open;
271
272 NodeGrid nodegrid;
273
274 Node *getNode(const Position& pos);
275 void identifySuccessors(const Node *n);
276 unsigned findNeighbors(const Node *n, Position *wptr) const;
277 Position jumpP(const Position& p, const Position& src);
278 Position jumpD(Position p, int dx, int dy);
279 Position jumpX(Position p, int dx);
280 Position jumpY(Position p, int dy);
281 bool generatePath(PathVector& path, unsigned step) const;
282 #ifdef JPS_VERIFY
283 Position jumpPRec(const Position& p, const Position& src) const;
284 #endif
285 };
286
getNode(const Position & pos)287 template <typename GRID> inline Node *Searcher<GRID>::getNode(const Position& pos)
288 {
289 JPS_ASSERT(grid(pos.x, pos.y));
290 return &nodegrid.insert(std::make_pair(pos, Node(pos))).first->second;
291 }
292
jumpP(const Position & p,const Position & src)293 template <typename GRID> Position Searcher<GRID>::jumpP(const Position &p, const Position& src)
294 {
295 JPS_ASSERT(grid(p.x, p.y));
296
297 int dx = int(p.x - src.x);
298 int dy = int(p.y - src.y);
299 JPS_ASSERT(dx || dy);
300
301 if(dx && dy)
302 return jumpD(p, dx, dy);
303 else if(dx)
304 return jumpX(p, dx);
305 else if(dy)
306 return jumpY(p, dy);
307
308 // not reached
309 JPS_ASSERT(false);
310 return npos;
311 }
312
jumpD(Position p,int dx,int dy)313 template <typename GRID> Position Searcher<GRID>::jumpD(Position p, int dx, int dy)
314 {
315 JPS_ASSERT(grid(p.x, p.y));
316 JPS_ASSERT(dx && dy);
317
318 const Position& endpos = endNode->pos;
319 int steps = 0;
320
321 while(true)
322 {
323 if(p == endpos)
324 break;
325
326 ++steps;
327 const unsigned x = p.x;
328 const unsigned y = p.y;
329
330 if( (grid(x-dx, y+dy) && !grid(x-dx, y)) || (grid(x+dx, y-dy) && !grid(x, y-dy)) )
331 break;
332
333 const bool gdx = grid(x+dx, y);
334 const bool gdy = grid(x, y+dy);
335
336 if(gdx && jumpX(Pos(x+dx, y), dx).isValid())
337 break;
338
339 if(gdy && jumpY(Pos(x, y+dy), dy).isValid())
340 break;
341
342 if((gdx || gdy) && grid(x+dx, y+dy))
343 {
344 p.x += dx;
345 p.y += dy;
346 }
347 else
348 {
349 p = npos;
350 break;
351 }
352 }
353 stepsDone += (unsigned)steps;
354 stepsRemain -= steps;
355 return p;
356 }
357
jumpX(Position p,int dx)358 template <typename GRID> inline Position Searcher<GRID>::jumpX(Position p, int dx)
359 {
360 JPS_ASSERT(dx);
361 JPS_ASSERT(grid(p.x, p.y));
362
363 const unsigned y = p.y;
364 const Position& endpos = endNode->pos;
365 const int skip = this->skip;
366 int steps = 0;
367
368 unsigned a = ~((!!grid(p.x, y+skip)) | ((!!grid(p.x, y-skip)) << 1));
369
370 while(true)
371 {
372 const unsigned xx = p.x + dx;
373 const unsigned b = (!!grid(xx, y+skip)) | ((!!grid(xx, y-skip)) << 1);
374
375 if((b & a) || p == endpos)
376 break;
377 if(!grid(xx, y))
378 {
379 p = npos;
380 break;
381 }
382
383 p.x += dx;
384 a = ~b;
385 ++steps;
386 }
387
388 stepsDone += (unsigned)steps;
389 stepsRemain -= steps;
390 return p;
391 }
392
jumpY(Position p,int dy)393 template <typename GRID> inline Position Searcher<GRID>::jumpY(Position p, int dy)
394 {
395 JPS_ASSERT(dy);
396 JPS_ASSERT(grid(p.x, p.y));
397
398 const unsigned x = p.x;
399 const Position& endpos = endNode->pos;
400 const int skip = this->skip;
401 int steps = 0;
402
403 unsigned a = ~((!!grid(x+skip, p.y)) | ((!!grid(x-skip, p.y)) << 1));
404
405 while(true)
406 {
407 const unsigned yy = p.y + dy;
408 const unsigned b = (!!grid(x+skip, yy)) | ((!!grid(x-skip, yy)) << 1);
409
410 if((a & b) || p == endpos)
411 break;
412 if(!grid(x, yy))
413 {
414 p = npos;
415 break;
416 }
417
418 p.y += dy;
419 a = ~b;
420 }
421
422 stepsDone += (unsigned)steps;
423 stepsRemain -= steps;
424 return p;
425 }
426
427 #ifdef JPS_VERIFY
428 // Recursive reference implementation -- for comparison only
jumpPRec(const Position & p,const Position & src)429 template <typename GRID> Position Searcher<GRID>::jumpPRec(const Position& p, const Position& src) const
430 {
431 unsigned x = p.x;
432 unsigned y = p.y;
433 if(!grid(x, y))
434 return npos;
435 if(p == endNode->pos)
436 return p;
437
438 int dx = int(x - src.x);
439 int dy = int(y - src.y);
440 JPS_ASSERT(dx || dy);
441
442 if(dx && dy)
443 {
444 if( (grid(x-dx, y+dy) && !grid(x-dx, y)) || (grid(x+dx, y-dy) && !grid(x, y-dy)) )
445 return p;
446 }
447 else if(dx)
448 {
449 if( (grid(x+dx, y+skip) && !grid(x, y+skip)) || (grid(x+dx, y-skip) && !grid(x, y-skip)) )
450 return p;
451 }
452 else if(dy)
453 {
454 if( (grid(x+skip, y+dy) && !grid(x+skip, y)) || (grid(x-skip, y+dy) && !grid(x-skip, y)) )
455 return p;
456 }
457
458 if(dx && dy)
459 {
460 if(jumpPRec(Pos(x+dx, y), p).isValid())
461 return p;
462 if(jumpPRec(Pos(x, y+dy), p).isValid())
463 return p;
464 }
465
466 if(grid(x+dx, y) || grid(x, y+dy))
467 return jumpPRec(Pos(x+dx, y+dy), p);
468
469 return npos;
470 }
471 #endif
472
findNeighbors(const Node * n,Position * wptr)473 template <typename GRID> unsigned Searcher<GRID>::findNeighbors(const Node *n, Position *wptr) const
474 {
475 Position *w = wptr;
476 const unsigned x = n->pos.x;
477 const unsigned y = n->pos.y;
478
479 #define JPS_CHECKGRID(dx, dy) (grid(x+(dx), y+(dy)))
480 #define JPS_ADDPOS(dx, dy) do { *w++ = Pos(x+(dx), y+(dy)); } while(0)
481 #define JPS_ADDPOS_CHECK(dx, dy) do { if(JPS_CHECKGRID(dx, dy)) JPS_ADDPOS(dx, dy); } while(0)
482 #define JPS_ADDPOS_NO_TUNNEL(dx, dy) do { if(grid(x+(dx),y) || grid(x,y+(dy))) JPS_ADDPOS_CHECK(dx, dy); } while(0)
483
484 if(!n->parent)
485 {
486 // straight moves
487 JPS_ADDPOS_CHECK(-skip, 0);
488 JPS_ADDPOS_CHECK(0, -skip);
489 JPS_ADDPOS_CHECK(0, skip);
490 JPS_ADDPOS_CHECK(skip, 0);
491
492 // diagonal moves + prevent tunneling
493 JPS_ADDPOS_NO_TUNNEL(-skip, -skip);
494 JPS_ADDPOS_NO_TUNNEL(-skip, skip);
495 JPS_ADDPOS_NO_TUNNEL(skip, -skip);
496 JPS_ADDPOS_NO_TUNNEL(skip, skip);
497
498 return unsigned(w - wptr);
499 }
500
501 // jump directions (both -1, 0, or 1)
502 int dx = int(x - n->parent->pos.x);
503 dx /= std::max(abs(dx), 1);
504 dx *= skip;
505 int dy = int(y - n->parent->pos.y);
506 dy /= std::max(abs(dy), 1);
507 dy *= skip;
508
509 if(dx && dy)
510 {
511 // diagonal
512 // natural neighbors
513 bool walkX = false;
514 bool walkY = false;
515 if((walkX = grid(x+dx, y)))
516 *w++ = Pos(x+dx, y);
517 if((walkY = grid(x, y+dy)))
518 *w++ = Pos(x, y+dy);
519
520 if(walkX || walkY)
521 JPS_ADDPOS_CHECK(dx, dy);
522
523 // forced neighbors
524 if(walkY && !JPS_CHECKGRID(-dx,0))
525 JPS_ADDPOS_CHECK(-dx, dy);
526
527 if(walkX && !JPS_CHECKGRID(0,-dy))
528 JPS_ADDPOS_CHECK(dx, -dy);
529 }
530 else if(dx)
531 {
532 // along X axis
533 if(JPS_CHECKGRID(dx, 0))
534 {
535 JPS_ADDPOS(dx, 0);
536
537 // Forced neighbors (+ prevent tunneling)
538 if(!JPS_CHECKGRID(0, skip))
539 JPS_ADDPOS_CHECK(dx, skip);
540 if(!JPS_CHECKGRID(0,-skip))
541 JPS_ADDPOS_CHECK(dx,-skip);
542 }
543
544
545 }
546 else if(dy)
547 {
548 // along Y axis
549 if(JPS_CHECKGRID(0, dy))
550 {
551 JPS_ADDPOS(0, dy);
552
553 // Forced neighbors (+ prevent tunneling)
554 if(!JPS_CHECKGRID(skip, 0))
555 JPS_ADDPOS_CHECK(skip, dy);
556 if(!JPS_CHECKGRID(-skip, 0))
557 JPS_ADDPOS_CHECK(-skip,dy);
558 }
559 }
560 #undef JPS_ADDPOS
561 #undef JPS_ADDPOS_CHECK
562 #undef JPS_ADDPOS_NO_TUNNEL
563 #undef JPS_CHECKGRID
564
565 return unsigned(w - wptr);
566 }
567
identifySuccessors(const Node * n)568 template <typename GRID> void Searcher<GRID>::identifySuccessors(const Node *n)
569 {
570 Position buf[8];
571 const int num = findNeighbors(n, &buf[0]);
572 for(int i = num-1; i >= 0; --i)
573 {
574 // Invariant: A node is only a valid neighbor if the corresponding grid position is walkable (asserted in jumpP)
575 Position jp = jumpP(buf[i], n->pos);
576 #ifdef JPS_VERIFY
577 JPS_ASSERT(jp == jumpPRec(buf[i], n->pos));
578 #endif
579 if(!jp.isValid())
580 continue;
581
582 // Now that the grid position is definitely a valid jump point, we have to create the actual node.
583 Node *jn = getNode(jp);
584 JPS_ASSERT(jn && jn != n);
585 if(!jn->isClosed())
586 {
587 unsigned extraG = Heuristic::Euclidean(jn, n);
588 unsigned newG = n->g + extraG;
589 if(!jn->isOpen() || newG < jn->g)
590 {
591 jn->g = newG;
592 jn->f = jn->g + Heuristic::Manhattan(jn, endNode);
593 jn->parent = n;
594 if(!jn->isOpen())
595 {
596 open.push(jn);
597 jn->setOpen();
598 }
599 else
600 open.fixup(jn);
601 }
602 }
603 }
604 }
605
generatePath(PathVector & path,unsigned step)606 template <typename GRID> bool Searcher<GRID>::generatePath(PathVector& path, unsigned step) const
607 {
608 if(!endNode)
609 return false;
610 size_t offset = path.size();
611 if(step)
612 {
613 const Node *next = endNode;
614 const Node *prev = endNode->parent;
615 if(!prev)
616 return false;
617 do
618 {
619 const unsigned x = next->pos.x, y = next->pos.y;
620 int dx = int(prev->pos.x - x);
621 int dy = int(prev->pos.y - y);
622 JPS_ASSERT(!dx || !dy || abs(dx) == abs(dy)); // known to be straight, if diagonal
623 const int steps = std::max(abs(dx), abs(dy));
624 dx /= std::max(abs(dx), 1);
625 dy /= std::max(abs(dy), 1);
626 dx *= int(step);
627 dy *= int(step);
628 int dxa = 0, dya = 0;
629 for(int i = 0; i < steps; i += step)
630 {
631 path.push_back(Pos(x+dxa, y+dya));
632 dxa += dx;
633 dya += dy;
634 }
635 next = prev;
636 prev = prev->parent;
637 }
638 while (prev);
639 }
640 else
641 {
642 const Node *next = endNode;
643 if(!next->parent)
644 return false;
645 do
646 {
647 path.push_back(next->pos);
648 next = next->parent;
649 }
650 while (next->parent);
651 }
652 std::reverse(path.begin() + offset, path.end());
653 return true;
654 }
655
findPath(PathVector & path,Position start,Position end,unsigned step)656 template <typename GRID> bool Searcher<GRID>::findPath(PathVector& path, Position start, Position end, unsigned step /* = 0 */)
657 {
658 Result res = findPathInit(start, end);
659
660 // If this is true, the resulting path is empty (findPathFinish() would fail, so this needs to be checked before)
661 if(res == FOUND_PATH)
662 return true;
663
664 while(true)
665 {
666 switch(res)
667 {
668 case NEED_MORE_STEPS:
669 res = findPathStep(0);
670 break; // the switch
671
672 case FOUND_PATH:
673 return findPathFinish(path, step);
674
675 case NO_PATH:
676 default:
677 return false;
678 }
679 }
680 }
681
findPathInit(Position start,Position end)682 template <typename GRID> Result Searcher<GRID>::findPathInit(Position start, Position end)
683 {
684 for(NodeGrid::iterator it = nodegrid.begin(); it != nodegrid.end(); ++it)
685 it->second.clearState();
686 open.clear();
687 endNode = NULL;
688 stepsDone = 0;
689
690 // If skip is > 1, make sure the points are aligned so that the search will always hit them
691 start.x = (start.x / skip) * skip;
692 start.y = (start.y / skip) * skip;
693 end.x = (end.x / skip) * skip;
694 end.y = (end.y / skip) * skip;
695
696 if(start == end)
697 {
698 // There is only a path if this single position is walkable.
699 // But since the starting position is omitted, there is nothing to do here.
700 return grid(end.x, end.y) ? FOUND_PATH : NO_PATH;
701 }
702
703 // If start or end point are obstructed, don't even start
704 if(!grid(start.x, start.y) || !grid(end.x, end.y))
705 return NO_PATH;
706
707 open.push(getNode(start));
708 endNode = getNode(end);
709 JPS_ASSERT(endNode);
710
711 return NEED_MORE_STEPS;
712 }
713
findPathStep(int limit)714 template <typename GRID> Result Searcher<GRID>::findPathStep(int limit)
715 {
716 stepsRemain = limit;
717 do
718 {
719 if(open.empty())
720 return NO_PATH;
721 Node *n = open.pop();
722 n->setClosed();
723 if(n == endNode)
724 return FOUND_PATH;
725 identifySuccessors(n);
726 }
727 while(stepsRemain >= 0);
728 return NEED_MORE_STEPS;
729 }
730
findPathFinish(PathVector & path,unsigned step)731 template<typename GRID> bool Searcher<GRID>::findPathFinish(PathVector& path, unsigned step /* = 0 */)
732 {
733 return generatePath(path, step);
734 }
735
freeMemory()736 template<typename GRID> void Searcher<GRID>::freeMemory()
737 {
738 NodeGrid v;
739 nodegrid.swap(v);
740 endNode = NULL;
741 open.clear();
742 // other containers known to be empty.
743 }
744
745 } // end namespace Internal
746
747 using Internal::Searcher;
748
749 // Single-call convenience function
750 //
751 // path: If the function returns true, the path is stored in this vector.
752 // The path does NOT contain the starting position, i.e. if start and end are the same,
753 // the resulting path has no elements.
754 // The vector does not have to be empty. The function does not clear it;
755 // instead, the new path positions are appended at the end.
756 // This allows building a path incrementally.
757 //
758 // grid: expected to overload operator()(x, y), return true if position is walkable, false if not.
759 //
760 // step: If 0, only return waypoints.
761 // If 1, create exhaustive step-by-step path.
762 // If N, put in one position for N blocks travelled, or when a waypoint is hit.
763 // All returned points are guaranteed to be on a straight line (vertically, horizontally, or diagonally),
764 // and there is no obstruction between any two consecutive points.
765 // Note that this parameter does NOT influence the pathfinding in any way;
766 // it only controls the coarseness of the output path.
767 //
768 // skip: If you know your map data well enough, this can be set to > 1 to speed up pathfinding even more.
769 // Warning: Start and end positions will be rounded down to the nearest <skip>-aligned position,
770 // so make sure to give appropriate positions so they do not end up in a wall.
771 // This will also skip through walls if they are less than <skip> blocks thick at any reachable position.
772 template <typename GRID> bool findPath(PathVector& path, const GRID& grid, unsigned startx, unsigned starty, unsigned endx, unsigned endy,
773 unsigned step = 0, int skip = 0, // optional params
774 size_t *stepsDone = NULL, size_t *nodesExpanded = NULL // for information
775 )
776 {
777 Searcher<GRID> search(grid);
778 search.setSkip(skip);
779 bool found = search.findPath(path, Pos(startx, starty), Pos(endx, endy), step);
780 if(stepsDone)
781 *stepsDone = search.getStepsDone();
782 if(nodesExpanded)
783 *nodesExpanded = search.getNodesExpanded();
784 return found;
785 }
786
787
788
789 } // end namespace JPS
790
791
792 #endif
793