First part of this series | Previous | Next | Index

In the last episode, I left some problems unsolved. So, I’m still wrestling with pathfinding. I’m just the same way as when I first used vim – “I wish I knew how to quit you”.

Now, my dream goal is to be able to run hundreds of multi-area pathfinds per frame, but that probably won’t be achieved. A frame is, however, a very small timeframe (ehh), so finding the path just a few frames later is likely not a big issue. First, I measured, how many times the algorithm gets called until it finds the path. For my particular example, which used about 10 areas, JPS got called 78 times. This will just get worse with more things occupying the map, and I’m not sure my goal should be to reduce this number.

Somewhat orthogonal to this (you know, the thing with the birds) is that in general, I should not call every method I can in every frame (Shocking!). Some kind of resource allocation is in order, and it should be based on performance. I also need to be pessimistic with that – my machine is not the actual benchmark here.

At this point, i didn’t see any obvious improvement points, so I delved into the nitty-gritty. Since the getJPSInfosInDirection() consumed the most resources, I began to convert that to an array-based method. Some of the relevant parts now look like this:

 if (ground) {
        if (isPassableGround(neighbor)) {
            JPSInfo[] jpsInfosArrayInDirection = getJPSInfosArrayInDirection(jumpPoint, jumpPoint.getWalkPosition(), start, end, ground, useActiveThreatMap, useThreatMemory, dir);
            for (int j = 0; j < jpsInfosArrayInDirection.length; j++) {
                straight.add(jpsInfosArrayInDirection[j]);
            }
        }
//

    public static JPSInfo[] getJPSInfosArrayInDirection(JPSInfo jpsInfo, WalkPosition actual, WalkPosition start, WalkPosition end,  boolean ground, boolean useActiveThreatMap, boolean useThreatMemory, Direction... dirs) {
        JPSInfo[] jpsInfos = new JPSInfo[dirs.length];

        for (int i=0; i<dirs.length; i++) {
            if (!isUnderThreat(ground, actual, useActiveThreatMap, useThreatMemory)) {
                jpsInfos[i] = new JPSInfo(dirs[i],
                        actual,
                        calcJPSImportance(actual, start, end, jpsInfo.getGeneration(), dirs[i]), jpsInfo);
            }
        }
        return jpsInfos;
    }

So not improving the comprehensibility more. But maybe we do improve the performance? Well… not by a meaningful amount, although the pain points moved elsewhere.

So, I tried to run the pathfinding 10 times every frame, and aim for the magic 50 FPS mark. With the previous pathfinding, I achieved 13 FPS. With the new, harder, faster, improved Jump Point Search 2000 Turbo, I managed to pump up that number to… 14 FPS.

Before crying in the corner, it is important to note that generally, these improvements are not additive, but rather often multiplicative. So not to worry – Improve as much as I can, than just do damage control (Premium life advice right here). It is clear that switching to arrays instead of collections wherever I can pays off. It is, however, not improving code readability. Oh, well.

The isUnderThreat() method uses our threat maps, which are large collections, and very clearly not arrays. First I changed the active threat map calculation to use arrays. Not only it didn’t speed up the pathfinding, but it caused – well, uncovered – some bugs as well. First, the isUnderThreat() method now worked with arrays, which allowed it to throw the wonderful ArrayIndexOutOfBoundsException. Which it did. While with maps, if I try to get an element that’s not in the map, I just don’t get it. Okay, I just added a check for the map boundaries (The error was caused by negative coordinates).

But that was not the only problem. My multi-area pathfinding just didn’t find the last segment – from the last chokepoint to the actual end tile. Other than the threat check, nothing changed. At this point, I had no idea if this have any correlation, or just pure coincidence, but my intuition said it’s the latter.

So far, the normalization for the chokepoints was done only for the two points that I actually wanted to connect with a path. However, there is no reason why I cannot go through the other points while searching for a path.

I tried it out, and it absolutely did not solve the problem, and even slowed me down. Upon much debugging such software engineering wow, it turned out that I had an one-off error when calculating the levels of the multi-area pathfinding. This is a little awkward, but at least I wasted considerable time on unrelated and fruitless pursuits. In any case, I managed to run 10 calls per frame at 50 FPS – this was kind of the goal here. This improvement was caused by the bugfix, and also, the switch of the activeThreatMap to an array-based solution. Next target is 20 calls per frame, maybe? With ten, I can already work with, I just need a rationing system for the poor, CPU-hungry zerglings.

There is no reason not to continue down this road. After the active threat map, the passive is the natural next step. I didn’t expect much from that step, but it did increase my average FPS from 26-28 to 30-31 (at 20 runs/frame) – the improvement is not even marginal!

At this point I decided it’s time for some actual playtesting, since this was done with a relatively static environment. Everything went well, until I blocked the path.

After much debugging, it turned out to be a combination of two factors. First, I didn’t check if the chokepoint is occupied (Well, my JPS method did, and then subsequently didn’t find a path, so that could have been avoided). I modified the getFirstUnthreatened() method – renamed it to getFirstUnthreatenedPassable(), to better reflect it’s new purpose.

    public static WalkPosition getFirstUnthreatenedPassable(ChokePoint cp) {
        WalkPosition tile = null;
        for (WalkPosition wp : cp.getGeometry()) {
            if (isWalkPositionOnTheMap(wp.getX(), wp.getY()) &&
                    (Main.occupiedGroundArray[wp.getX()][wp.getY()] < 0 ||
                            (Main.frameCount - Main.occupiedGroundArray[wp.getX()][wp.getY()]) > GROUND_FORGET_PERIOD)
                    && Main.areaDataArray[wp.getX()][wp.getY()] > 0) {
                tile = wp;
                break;
            }
        }
        return tile;
    }

Yes, it has almost the same checks as isPassableGround(), with the exception of calling bw.IsWalkable(). The walkability of the tile is already decided for us in the areaDataArray.

The second factor was that I stepped back too much with my method, and recalculated the path every time. Obviously I didn’t need to do that, so I just added the following:

 if (pathPieces.size() > level) {
    level++;
 }

Very simple thing, but it took some thinking to realize I need it. With that, the method was dropping back to bearable speeds, 15 FPS, while doing 10 iterations per frame. Still kinda meh, but I think this is where I will stop wrestling with this. Pathfinding will always be a resource-hungry method, it would’ve been nice to call it every frame, but I can live with this result. Also, I kinda want to do other things now – actually using the threat-aware pathfinding, for one. I do realize I’m not done with this – I fully expect a few more articles on just this.

Just for the optimization part – There are still some places where I create a WalkPosition object only to pass it to method that verifies it’s coordinates in some array. It would seem that is unnecessary, and it indeed is – however, I have a lot of methods that are somewhat tested and working with this, so at this point, I’m choosing to not focus on this.

It is also time to overhaul the project a little. I just committed everything to my github repo, which is therefore an absolute mess. I will clean up the codebase, remove methods that were left only as demonstrations, and generally, will try and fail to act as a professional software dev about this.

My Cartography class is becoming a God object, and I don’t really like it, so some structural reforms are in order. Jumpy Doggo Bot will rise!

With all that in mind, the current tasks ahead:

• Some good heuristic for giving a partial path between two chokepoints
• The “big boi” problem, checking if a path is wide enough for a unit to actually pass through it without all the hurt.
• Add more arrays and primitives, whenever possible. The performance gains are very serious.

I think I will do all this, but at least analyze them, before wrapping this up. A natural next step would be to extend this to something that finds a path with the minimal amount of damage suffered. After that, maybe group pathfinding? That’s an even deeper rabbit hole, and I literally spent months on perfecting an algorithm – and enjoyed every second of it.

Thanks for reading! If you liked this article, consider subscribing to the mailing list in the sidebar for updates, or to the RSS feed! Also, if you’d like to support me, my blog, or my podcast,
check out my shop here! (And get 20% discount with the code “UNDERMIND”!)