CODEWITHSUNDEEP
algorithmpointpath-findinga-star
Roland Y.
Roland Y.

Reputation: 423

Pathfinding : Jump Point Search - Straight Moves vs Diagonal Moves

Planning working on a 2D RTS, I tried to learn how Astar works. Indeed, I found articles explaining how Astar could be optimized coupling it with binary heaps, and algorithms taking advantages of Path symmetry, like Jump Poin Search algorithm. I tried to implement Jump Point Search, and it runs fine. I even made some benchmarks tests with maps from MovingAI.

Yet there is a problem. Everything runs fine when diagonal moves are allowed.When disabled, no path is returned...

It may be linked to the way I implementd it, then I'm all asking...In general, how would you oblige the algorithm (JPS) to search for path involving only straight moves (not diagonals moves) to reach a goal?

Upvotes: 3

Views: 4614

Answers (3)

user2712865
user2712865

Reputation: 15

It should be possible to create a version of JPS that uses only cardinal directions if you have it send sub-searches(as you would with the diagonal movement) along the directions perpendicular to the original direction. Doing that, it will be able to find when a node at a given location will find a node further ahead.

Upvotes: 1

Bruno Ayllon
Bruno Ayllon

Reputation: 75

Well, technically speaking, if no diagonal moves are allowed, then your optimal heuristic is Manhattan Distance. That means that A* will find na answer with a minimum of moves. Representing your map in a grid with each node having a onOpen and onClosed booleans, as opposed to using a closed list, is a HUGE optimization. In addition, if you use std make heap, push_heap and pop heap, you can get the cheapest node with cost log n (1 to pop + log n to sort = O(logn)), which scales much better than using a vector.

Upvotes: 0

Lovro Gregorčič
Lovro Gregorčič

Reputation: 228

Jump point search NEEDS diagonals enabled to work. In state algorithm is in, this is one of its limitations. Also, you wont be able to make your terrain distinguishable (mud = penalty to movement, etc.) since this would destroy symmetries. I suggest you stick to A* and try to gain performance by terrain presentation (mesh, waypoints). Or maybe check HPA*.

Upvotes: 7

Related Questions