First part of this series | Previous| Next | Index

As you might have guessed, the JPS code in the previous post wasn’t entirely correct. What a shocking revelation! I mean, it found some paths some times, much slower than expected. Remember, this is supposed to be a vast improvement over A*.

With the current implementation, it isn’t.

I stared at the code for some hours, then I realized that wasn’t the best method to track down problems.

Initially, I just used the debugger, but since the algorithm tended to visit half of the map before finding something (Some 100k objects), that was not time efficient. Onwards to a different approach then. First of all, let’s test our assumptions. For this purpose, a great tool was invented, it’s called unit testing. Banging out code and trying if it works properly is fine for a while, but I have clearly passed that point. Let’s borrow the approach from my professional life (I’m a developer by day, and developerer by night). I added JUnit to libs (I used the 4.13 version from here – you need the hamcrest-all-X.X.jar as dependency, get it here)

My first intuition was that the heuristic might be wrong.

    @Test
    public void calcJPSTest() {
        WalkPosition origin = new WalkPosition(10, 10);
        WalkPosition destination = new WalkPosition(20, 20);

        WalkPosition wp1 = new WalkPosition(10,11);
        WalkPosition wp2 = new WalkPosition(21,21);
        int wp1Imp = Cartography.calcJPSImportance(origin, destination, wp1);
        int wp2Imp = Cartography.calcJPSImportance(origin, destination, wp2);
        Assert.assertTrue(wp2Imp < wp1Imp);

    }

It was.

Yeah, I added equal weight to the distance from the origin, and the destination points. This was not great, but unfortunately, not the root cause of everything. I modified it to only consider the distance from the destination – this is not perfect either, but closer to what I really want.

    public static int calcJPSImportance(WalkPosition start, WalkPosition end, WalkPosition wp) {
        int endImp = positionToPositionDistanceSq(end.getX(), end.getY(), wp.getX(), wp.getY());

        return  FastIntSqrt.fastSqrt(endImp);
    }

After that, I re-read the JPS algorithm documentation multiple times. When a search stops in a direction, and makes new jump points, those are starting from the same square where the search ended – I was starting them from the neighbor in the target direction. I also modified the JPSInfo class to have a precursor (parent) object – this will be needed for path reconstruction.

//Code is still convoluted, as it should be
    public static Set<JPSInfo> getJPSInfosInDirection(JPSInfo jpsInfo, WalkPosition wp, WalkPosition start, WalkPosition end,  boolean ground, boolean useActiveThreatMap, boolean useThreatMemory, Direction... dirs) {
        HashSet<JPSInfo> jpsInfos = new HashSet<>();
        for (Direction d : dirs) {
            if (!isUnderThreat(ground, jpsInfo.getWalkPosition(), useActiveThreatMap, useThreatMemory)) {
                jpsInfos.add(new JPSInfo(d,
                        wp,
                        calcJPSImportance(start, end, jpsInfo.getWalkPosition()), jpsInfo));
            }
        }
        return jpsInfos;
    }

And yes, I’m still passing the end parameter to the calcJPSImportance(), even though I’m not using it. I consider that method work in progress, so let’s leave it for the moment.

With that, let’s dissect the case when evaluating straight paths. I rewrote it a few times, and well, there is nothing more to be said than name your variables consistently, and test sub-functions. Welp. Verbosity isn’t actually hurting anyone – we can afford the extra bytes for slightly longer variable names. It’s okay to have a thousand methods, then consolidate those later – or maybe not even then. For group projects, I like to follow Clean Code principles, and code as the maintenance programmer after me is a psychopath with a rusty hatchet who knows where I live. In my private projects, the only person I’m hurting with being sloppy is myself. And maybe I like that, you don’t know my life.

Another rather embarassing mistake I made was to have method parameters of the same type in different order for different methods. I won’t list those all, but in the end, I decided to standardize those.

With those life lessons in mind, here is the version which seems to work best so far.

    public static Set<WalkPosition> findUnthreatenedPathJPS(WalkPosition start, WalkPosition end, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory) {
        boolean foundPath = false;
        PriorityQueue<JPSInfo> straight = new PriorityQueue<>(new JPSInfoComparator());
        PriorityQueue<JPSInfo> diag = new PriorityQueue<>(new JPSInfoComparator());
        JPSInfo startJPSInfo = new JPSInfo(null, start, 0, null);

        JPSInfo endJPSInfo = null;
        straight.addAll(getJPSInfosInDirection(startJPSInfo, start, start, end, ground, useActiveThreatMap, useThreatMemory, Direction.E, Direction.W, Direction.S, Direction.N));
        diag.addAll(getJPSInfosInDirection(startJPSInfo, start, start, end, ground, useActiveThreatMap, useThreatMemory, Direction.NE, Direction.NW, Direction.SE, Direction.SW));

        while (!foundPath && (!straight.isEmpty() || !diag.isEmpty())) {
            JPSInfo jumpPoint;
            while (!straight.isEmpty()) {
                jumpPoint = straight.poll();
                Direction dir = jumpPoint.getDirection();
                //Straight path processing
                boolean straightPathProcessed = false;
                WalkPosition current = jumpPoint.getWalkPosition();
                WalkPosition ahead = getNeighborInDirection(current, jumpPoint.getDirection());

                while (!straightPathProcessed) {
                    //Terminate search if the next tile in the direction is under threat/impassable
                    if (isUnderThreat(ground, ahead, useActiveThreatMap, useThreatMemory) || !isOnTheMap(ahead)) {
                        straightPathProcessed = true;

                    }
                    if (ahead.equals(end)) {
                        straightPathProcessed = true;
                        foundPath = true;
                        endJPSInfo = new JPSInfo(null, ahead, 0, jumpPoint);
                        break;
                    }

                    //Check neighbors to the left and right
                    HashSet<Direction> checkDirs = straightCheckPos.get(jumpPoint.getDirection());
                    for (Direction checkDir : checkDirs) {
                        WalkPosition straightNeighbor = getNeighborInDirection(current, checkDir);
                        if (isUnderThreat(ground, straightNeighbor, useActiveThreatMap, useThreatMemory)) {
                            WalkPosition diagWP = getNeighborInDirection(current, getJPDirections(jumpPoint.getDirection(), checkDir).iterator().next());
                            if (!isUnderThreat(ground, diagWP, useActiveThreatMap, useThreatMemory)) {
                                JPSInfo jpsInfo = new JPSInfo(getJPDirections(jumpPoint.getDirection(), checkDir).iterator().next(), current, calcJPSImportance(diagWP, start, end), jumpPoint);
                                straightPathProcessed = true;
                                diag.add(jpsInfo);
                            }
                        }
                    }
                    current = ahead;
                    ahead = getNeighborInDirection(ahead, jumpPoint.getDirection());
                }
            }

            if (!diag.isEmpty()) {
                jumpPoint = diag.poll();
                if (jumpPoint.getWalkPosition().equals(end)) {
                    foundPath = true;
                    endJPSInfo = new JPSInfo(null, jumpPoint.getWalkPosition(), 0, jumpPoint);
                    break;
                } else {

                    WalkPosition diagAhead = getNeighborInDirection(jumpPoint.getWalkPosition(), jumpPoint.getDirection());

                    if (jumpPoint.getWalkPosition().equals(end)) {
                        foundPath = true;
                        endJPSInfo = new JPSInfo(null, diagAhead, 0, jumpPoint);
                        System.out.println("IZ END");
                        break;
                    }

                    //If the next tile in the diagonal direction isn't blocked, let's add that too
                    if (!isUnderThreat(ground, diagAhead, useActiveThreatMap, useThreatMemory) && isOnTheMap(diagAhead)) {
                        JPSInfo jpsInfo = new JPSInfo(jumpPoint.getDirection(), diagAhead, calcJPSImportance(diagAhead, start, end), jumpPoint);
                        diag.add(jpsInfo);
                    }

                    //Add the 2 straight jump points in any case
                    for (Direction dir : diagForwardPos.get(jumpPoint.getDirection())) {
                        Set<JPSInfo> jpsInfosInDirection = getJPSInfosInDirection(jumpPoint, diagAhead, start, end, ground, useActiveThreatMap, useThreatMemory, dir);
                        straight.addAll(jpsInfosInDirection);
                    }
                    //Check the two remaining straight directions
                    for (Direction checkDir : diagCheckPos.get(jumpPoint.getDirection())) {
                        WalkPosition wp = getNeighborInDirection(diagAhead, checkDir);
                        if (isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
                            Set<JPSInfo> jpsInfosInDirection = getJPSInfosInDirection(jumpPoint, wp, start, end, ground, useActiveThreatMap, useThreatMemory, getJPDirections(jumpPoint.getDirection(), checkDir));
                            diag.addAll(jpsInfosInDirection);
                        }
                    }
                }
            }
        }

//Path reconstruction
        Set<WalkPosition> patherino = new HashSet<>();
        JPSInfo precc;

        if (endJPSInfo != null) {
            patherino.add(end);
            precc = endJPSInfo.getPrecursor();
            while (precc != null) {
                patherino.add(precc.getWalkPosition());
                precc = precc.getPrecursor();
            }
        }

        return patherino;
    }

The question pops up: If there were this many mistakes, why didn’t I approach it more meticulously in the first place? I have multiple answers for that.

• I code in my spare time on this, so I’m more lax regarding testing
• As a result, I’m usually more tired when doing so, and make mistakes easier
• Shut up, you’re not my real dad

So basically, do as I say, not as I do.

With that in mind, let’s see how it performs. With my test data, it found two paths – here you can see the jump points (in green):

The algorithm was giving me these two alternatively – so clearly, the importance heuristic is not perfect, but that’s not a bug, but an unfinished task. And how fast is this? After all, that was the main driving point here.

So, with a just stable version, in this particular use case, I was able to get a 7x speed increase. I would say this is pretty convincing.

Old and wizened now, I took a step back, and just began planning the next steps, instead of diving headfirst into the code. My plans are the following:

• Obviously, making the heuristic better
• Separating the pathfinding for air and ground. Brood War maps have the concept of regions, and chokepoints between them. BWEM could be a serious help here. If the origin, and destination are in the same region, I can make the search even faster. If they are in different regions, then I can safely assume that the unit will travel throught the chokepoints, and so, plan according to that.
• Even if JPS is very fast, I can always benefit from making it faster – usually there are multiple units that want to find a path.
• And well, maybe putting pathfinding on the back burner for now – if this version is good enough, maybe I can use it for devious zergling runbys.

There is also a great video on improving JPS, by no one else than the inventor of the algorithm itself. Watch it to gain +1 smarts points instantly.

Thanks for reading! If you liked this article, consider subscribing to the RSS feed, or the mailing list on the right.