Jump point search with penalties

General
1

Hi! I’m trying to optimize my pathfinding in a grid graph that’s modified quite often (destructible walls). Presuming the pivot heuristic optimization isn’t suitable for an often modified graph, I think Jump Point Search would be a good optimization since my level consists of large empty rooms and tunnels.

I use penalties to mark nodes that are seen by the player, so the AI can avoid direct LOS to them. I saw a forum post mention A* Pathfinding Project’s JPS doesn’t support penalties, so that would rule it out, but I think JPS could be made to support penalties: whenever pruning a neighbor node, make it a forced neighbor if it has a different penalty than the current node. Of course this isn’t good for a map where every node has a unique weight, but I have large areas of uniform weight, so JPS should still be a good fit.

I’m wondering if I could write my own JPS implementation if the A* Project doesn’t support this out of the box - is this possible?

2

Hi

I haven’t studied JPS in enough detail to say if your algorithm is correct, but if you want to try it out then sure. You will have to modify the source code for this though. The JPS code exists in the gridnode.cs file.

3

Great to know it can be overridden! I’m basing my assumption it’ll work with weighted nodes on this comment here: https://harablog.wordpress.com/2011/09/07/jump-point-search/

"By the way, I can confirm that your last suggestion regarding weighted grids works.

After grabbing all the neighbors of an expanded node, I do a quick check to see if any of them have a weight that is different than the node being expanded. If they do, they’re marked as forced……. and the paths that are returned will follow the route of least resistance, as expected.

So…JPS isn’t limited to uniform-cost grids, which is great!"

1 Like