search

fgenesis / jps

Jump Point Search, public domain, single .h -- OBSOLETE! See tinypile repo for a better version.
The Unlicense
72 stars 21 forks source link

Huge amount of steps needed? #1

Open codecat opened 8 years ago

codecat commented 8 years ago

If you have a big map, it looks like you need a huge amount of steps in order to find a path, even though point A and point B are close to each other. Is it intentional that it steps through every single point on the map even if there's only a few points in between?

fgenesis commented 8 years ago

I'm not sure what you mean, but if it is what i'm thinking, then yes. Try https://qiao.github.io/PathFinding.js/visual/ and place the goal to the right and above the start (just not exactly on the diagonal) and you will see how the recursion works. That's part of the algorithm and (unfortunately) how it works. Assuming you have a super fast isWalkable(x, y) function this is usually no big deal and part of what makes the JPS algorithm so fast, since it doesn't have to expand each node as a possible candidate. However if you have a very large space it probes huge distances, especially when going diagonally -- since every diagonal step is followed by horizontal and vertical probing until it hits a wall.

If your map testing function is slow, A* is a better option, as A* does not know about spatial locality (x/y position), since it's essentially an algorithm operating on graphs. It's just a matter of changing some code, i'll give this a shot... maybe it helps you to compare the performance.

fgenesis commented 8 years ago

Update your master branch and define JPS_ASTAR_ONLY (see top of JPS.h), then try again. The number of grid checks should be less now, but the number of expanded nodes should increase a lot.

I implemented this in a way that it first checks if a tile is walkable, and only then grabs a node & checks if it can be expanded. This could be inverted but the std::map lookup in getNode() is generally slower than a grid check.

Some notes from personal testing: I implemented JPS into Aquaria (relevant file) and this increased pathfinding speed by at least a factor of 5, possibly a lot more. Has been a while, but what used to stall the game for ~200ms is now calculated in real time. So JPS has been a huge win for me there.

Should you run into performance problems, try incremental pathfinding and split it over multiple frames. I didn't actually need that yet.

One last note. An interesting experiment would be to try and use a greedy method to try and only ever run towards the goal, but as soon as it hits a wall, switch to JPS. I'll see if i have the time to implement something like this...

fgenesis commented 8 years ago

7db3ad2a Adds the greedy search i mentioned. I can't measure any direct performance benefits, but it may be useful if you implement some kind of follower AI that tries to stay close at all times (i.e. repeated pathfinding calls every second or so), and thus only has to perform actual pathfinding when the greedy check fails.

codecat commented 8 years ago

Thanks for the update! I'll be doing some testing myself over the next week.