First part of this series | Previous | Next | Index

A slight detour from the JPS problem first. I needed a way to write tests for stuff that can only be tested in-game, so I implemented a smoke test (I’m pretty sure professional testers will disagree with naming on this, but I’m a wild child). This just implements the BWEventListener, but instead of any logic, just tests methods. The first one I was suspicious about is the Cartography.isOnTheMap. In theory, this should give me back same as bw.getBWMap.isValidPosition(). Let’s check that!

    public void isOnTheMapTest() {
        int wph = bw.getBWMap().mapWidth()*4;
        int wpw = bw.getBWMap().mapHeight()*4;
        for (int i = 0; i<wph; i++) {
            for (int j = 0; j<wpw; j++) {
                WalkPosition wp = new WalkPosition(i, j);
                if (bw.getBWMap().isValidPosition(wp) != Cartography.isOnTheMap(wp, bw)) {
                    System.out.println("Cartography.isOnTheMap() is broken");
                }
            }
        }
    }

This is just an example, but at the heart of the test, it’s just a boolean comparison. It also turned to be okay, so today I found out that I actually don’t need the isOnTheMap() method. You might have noticed (I’m sure you didn’t), that I pass the bw object to the isOnTheMap(), contrary to previous usages. I hardcoded the Cartography methods to use stuff from my Main class, because I don’t want to pass the same parameters all the time. In this case, it’s a little bit of drawback, but I kinda want to keep the approach. If only there was a convenient way to get around that… I actually wrote a convenience method, before realizing that this is a redundant method. Time to purge! I won’t list all the methods here that I tested. Also, suffice to say, I’m somewhat far from 100% test coverage.

Back to the problem of stopping JPS in time. I mentioned that I want different pathfinding for ground, and air units. For ground units, I just need to check a select few regions, and I can use BWEM to aid my search. The bwem.getMap().getPath() returns a list of chokepoints between the two positions given as parameters. So I just need to find the path to the chokepoint within the same region, then repeat that for every area. An area is considerably smaller than the map, so if there is no path, it finishes faster.

The main problem that bugs me though is the “boxed in” heuristics. Let’s think for a moment. A square can be easily detected – this is what the Best Friend Search used. (searching for blocking squares in an increasing radius)

Consider this case:

This already fails. X marks our destination, so the problem is, that all the map gets visited if we don’t do something about this. We can’t just search in every direction naively, because:

I was thinking about how can I verify the existence of the path easily, when my eyes wandered to this icon:

Oh, MS Paint, you endless source of inspiration and creativity! Maybe a quick heuristics is flood-filling the grid, and if we can do that (meaning the destination will be “colored”), we just verified that a path exists.

Let’s try out in practice, if this is feasible – after all, there are a lot of positions on the map. First I just implemented a naivistic approach. Add every unthreatened neighbor, and in the next iteration, check the neighbors of those, until there is no more added.

    public static boolean pathExistsFloodFill(WalkPosition start, WalkPosition end, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory) {
        Set<WalkPosition> flood = new HashSet<>();
        Set<WalkPosition> unchecked = new HashSet<>();
        if ((isUnderThreat(ground, start, useActiveThreatMap, useThreatMemory) || !Main.bw.getBWMap().isValidPosition(start))) {
            return false;
        } else {
            flood.add(start);
            unchecked.add(start);
        }

        while (!unchecked.isEmpty()) {
            Set<WalkPosition> newWps = new HashSet<>();
            for (WalkPosition uc : unchecked) {
                for (WalkPosition n : getNeighborsInDirection(uc, Direction.values())) {
                    if ((!isUnderThreat(ground, n, useActiveThreatMap, useThreatMemory) && Main.bw.getBWMap().isValidPosition(n))) {
                        if (n.equals(end)) {
                            return true;
                        }

                        if (!flood.contains(n)) {
                            newWps.add(n);
                        }
                        flood.add(n);
                    }
                }
            }
            unchecked = newWps;
        }
        return false;
    }

I tested with three scenarios

• Origin boxed in
• Destination boxed in
• Origin and destination are in the opposite corners of the map.

In the first scenario, the algorithm gave the correct result (no path) quickly. The second and the third were very slow (the game ran at 1-2 FPS). So, this is not usable in it’s current form. As bad as it looks, it’s still good progress, as JPS just freezes in the second scenario.

To speed this up, I had multiple ideas. First, as mentioned above, to do it for both points at the same time – this would speed up scenario 2, but scenario 3 would be still very slow. Also, maybe just check fewer directions (non-diagonals)? I made a quick comparison for just that.

It actually sped up the method by a considerable amount – I guess there were too many redundancies. Now it reaches 3 FPS!

Clearly, the Set-based approach is not fast enough. I turned to my old friend, arrays, and rewrote the method to use that. This is still not the 100% optimal solution.

   public static boolean pathExistsFloodFillArray(WalkPosition start, WalkPosition end, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory) {
        //Clearing out the threat array
        for (int x = 0; x < Main.threatArray.length; x++) {
            for (int y = 0; y < Main.threatArray[x].length; y++) {
                Main.threatArray[x][y] = 0;
            }
        }

        //Setting threatened positions to 1
        if (useActiveThreatMap) {
            for (WalkPosition wp : Main.activeThreatMap.keySet()) {
                Main.threatArray[wp.getX()][wp.getY()] = 1;
            }
        }

        if (useThreatMemory) {
            for (WalkPosition wp : Main.threatMemoryMap.keySet()) {
                Main.threatArray[wp.getX()][wp.getY()] = 1;
            }
        }

        ArrayList<WalkPosition> unchecked = new ArrayList<>();

        if ((isUnderThreat(ground, start, useActiveThreatMap, useThreatMemory) || !Main.bw.getBWMap().isValidPosition(start))) {
            return false;
        } else {
            Main.threatArray[start.getX()][start.getY()] = 1;
            unchecked.add(start);
        }

        while (!unchecked.isEmpty()) {
            ArrayList<WalkPosition> newWps = new ArrayList<>();
            for (WalkPosition uc : unchecked) {
                if (uc.equals(end)) {
                    return true;
                }
                int x = uc.getX();
                int y = uc.getY();

                x = uc.getX() + 1;
                y = uc.getY();
                if (isOnTheMap(x, y) && Main.threatArray[x][y] == 0) {
                    if (end.getX() == x && end.getY() == y) {
                        return true;
                    }
                    Main.threatArray[x][y] = 1;
                    newWps.add(new WalkPosition(x, y));
                }

                x = uc.getX() - 1;
                y = uc.getY();
                if (isOnTheMap(x, y) && Main.threatArray[x][y] == 0) {
                    if (end.getX() == x && end.getY() == y) {
                        return true;
                    }
                    Main.threatArray[x][y] = 1;
                    newWps.add(new WalkPosition(x, y));
                }

                x = uc.getX();
                y = uc.getY() - 1;
                if (isOnTheMap(x, y) && Main.threatArray[x][y] == 0) {
                    if (end.getX() == x && end.getY() == y) {
                        return true;
                    }
                    Main.threatArray[x][y] = 1;
                    newWps.add(new WalkPosition(x, y));
                }

                x = uc.getX();
                y = uc.getY() + 1;
                if (isOnTheMap(x, y) && Main.threatArray[x][y] == 0) {
                    if (end.getX() == x && end.getY() == y) {
                        return true;
                    }
                    Main.threatArray[x][y] = 1;
                    newWps.add(new WalkPosition(x, y));
                }
            }
            unchecked = newWps;
        }
        return false;
    }

This is clearly a halfway solution, as not everything is array-based. I’m using an ArrayList for the unchecked collection – otherwise I would need to resize arrays, which I’m just lazy to do at this point. First, I populate the threat array with the values from the maps – 1 if threatened in any way, 0 otherwise. The benefit of this method that I can just use the same value for visited, and threatened values – all I care about is finding the end point, and/or filling the whole map. I will shorten the method in the future a bit, now it demonstrates my train of thought a little bit closely. The methods I used

Quickly testing it out, calling the floodfill every frame – and working with the worst-case scenario – still produced 80 FPS, which is good enough at this point. JPS is kinda slow – 22-23 FPS for this, but in conjunction with the flood fill, I can live with it for now.

Also, you might have noticed that I’m not bothering with occupied ground checks. In general, ground pathfinding will be a separate affair, with area-to-area logic, so sidestepping this issue for now.

I got to say at this point, arrays are way more faster. I’m thinking of converting every kind of map I’m using to them – more error-prone, as collections are very nice things to work with, but unfortunately, performance constraints are a bitch.

Let’s shelve the flood fill for now. The next part is implementing the details of the ground-only pathfinding – if I find that it still needs optimization, then I’ll probably return to the flood fill, but I got a feeling that this will be unnecessary. So let’s return to our Lord and Saviour preferred library, BWEM. An important note to make here is that there is a bwem-community version, which is maintained by, well, a community. I suggest using that (Even though I’m not doing so). Of course, there is no Java port for that at the moment.

The method mentioned above returns a list of ChokePoints (in order). These are the boundaries between areas (Arbitrary units of the map, although looking at a map, you can have a pretty good guess where they are), and are composed of nodes, which are WalkPositions. Between those, we can find paths (And between two sequential chokepoints, there is always only one area we have to consider). I would like to avoid having n*m comparisons (Nodes of both chokepoints), but maybe I just have to live with that. I’m also seriously considering writing a lower-resolution pathfinding too. After all, as I previously mentioned, hierarchical pathfinding is a definite improvement of A* – how useful is it for JPS, I will have to find out.

This is it for this article. I will continue with implementing the ground-based pathfinding in the next one. Thanks for reading, and please consider subsciribing to the mailing list!