First part of this series | Previous | Next | Index

In the last part, I managed to work out some bugs in my in-area jump point pathfinding. Again, let’s climb up a level of my rabbit hole. The end goal here is to have a reasonably fast, threat-aware pathfinding algorithm between any two (walkable) tiles of the map. I started to break down the map already, using BWEM.

First, bwem.getMap().getPath() will return an empty collection if we search for a path between two points in the same area. In this case, we can just call the existing findUnthreatenedPathInAreaJPS() method. (Of course, verifying the existence of the path with a flood fill first).

If BWEM gives back exactly one chokepoint, that’s a little bit tricky – the chokepoint belongs to one of the neighboring areas. Currently, I can give just one as a parameter.

I don’t really want to modify any of my existing methods to this, so I’ll just temporarily set the values in my dataarray to the same areaId as my starting point – I know for a fact that they share an area, and after that, I will restore the original ids. Come to think of it, that might be the proper way otherwise as well. But at this point, we are at the “find any path” stage, not the “find the absolute best” one. I take advantage of the fact that bwem’s getPath() returns a list, therefore an ordered collection. I just store them in order, in an array.

        int startAreaId = Main.areaDataArray[start.getX()][start.getY()];
        int cpData[] = new int[cp.getGeometry().size()];

        int i =0;
        for (WalkPosition wp : cp.getGeometry()) {
            cpData[i++] = Main.areaDataArray[wp.getX()][wp.getY()];  
            Main.areaDataArray[wp.getX()][wp.getY()] = startAreaId;
        }

        WalkPosition end = pathExistsInArea(start, cp.getGeometry(), true, useActiveThreatMap, useThreatMemory, startAreaId);
        if (end != null) {
            path = findUnthreatenedPathInAreaJPS(start, end, true, useActiveThreatMap, useThreatMemory, startAreaId);
        }
        i =0;
        for (Integer id : cpData) {
            Main.areaDataArray[cp.getGeometry().get(i).getX()][cp.getGeometry().get(i).getY()] = id;
            i++;
        }

I overloaded the same method, it made sense in this context. I tried this out, and it worked like a charm – a rare occurence! Now back to the multi-area pathfinding in question. We got the path from the start to a chokepoint tile, now we need to do the same from the same tile to the end point. This is the same method call.

    public static Set<WalkPosition> findAnyPathMultiArea(WalkPosition start, WalkPosition end, boolean useActiveThreatMap, boolean useThreatMemory) {
        Set<WalkPosition> summaryPath = new HashSet<>();
        CPPath bwemPath = Main.bwem.getMap().getPath(start.toPosition(), end.toPosition());
        if (bwemPath.size() == 0) {
            if (pathExistsFloodFillArray(start, end, true, useActiveThreatMap, useThreatMemory)) {
                return findUnthreatenedPathInAreaJPS(start, end, true, useActiveThreatMap, useThreatMemory, Main.areaDataArray[start.getX()][start.getY()]);
            }
        } else  if (bwemPath.size() == 1) {
            summaryPath.addAll(findAnyPathInArea(bwemPath.get(0), start, useActiveThreatMap, useThreatMemory));
            summaryPath.addAll(findAnyPathInArea(bwemPath.get(0), end, useActiveThreatMap, useThreatMemory));
        }

        return  summaryPath;

    }

And the result (The second location is actually to the right of the first)

This seems okay to me. The method can actually be just extended to any number of areas – I just like posting work in progress code to confuse, disappoint, and sow discontent. With that uplifting thought, the complete code so far:

    public static Set<WalkPosition> findAnyPathMultiArea(WalkPosition start, WalkPosition end, boolean useActiveThreatMap, boolean useThreatMemory) {
        Set<WalkPosition> summaryPath = new HashSet<>();
        CPPath bwemPath = Main.bwem.getMap().getPath(start.toPosition(), end.toPosition());
        if (bwemPath.size() == 0) {
            if (pathExistsFloodFillArray(start, end, true, useActiveThreatMap, useThreatMemory)) {
                return findUnthreatenedPathInAreaJPS(start, end, true, useActiveThreatMap, useThreatMemory, Main.areaDataArray[start.getX()][start.getY()]);
            }
        } else if (bwemPath.size() >= 1) {
            summaryPath.addAll(findAnyPathInArea(bwemPath.get(0), start, useActiveThreatMap, useThreatMemory));
            for (int cc = 1; cc< bwemPath.size(); cc++ ) {
                Set<WalkPosition> pathInArea = findAnyPathInArea(bwemPath.get(cc), bwemPath.get(cc - 1), useActiveThreatMap, useThreatMemory);
                if (pathInArea.size() >0 ) {
                    summaryPath.addAll(findAnyPathInArea(bwemPath.get(cc), bwemPath.get(cc - 1), useActiveThreatMap, useThreatMemory));
                } else {
                    //no path!
                    break;
                }
            }
            summaryPath.addAll(findAnyPathInArea(bwemPath.get(bwemPath.size()-1), end, useActiveThreatMap, useThreatMemory));
        }
        return  summaryPath;
    }

If you are very smart, you saw the comment about no path existing. In these cases, we shouldn’t add the last bit either, and just return an empty collection – or do we? We might want to get closer to our target, even if we can’t reach it. On the other hand, I do see scenarios where I don’t want to bother. So, I will just do both solutions by adding a boolean to the method signature. I tried this out with the worst case scenario, things on opposite ends of the map. Predictably, it slowed down things considerably, I got about 12 FPS, which is less than acceptable. Upon profiling, I discovered a horrible, horrible thing.

My checking of a path’s existence was actually slower than calculating the path! That is the exact opposite of what I want to do with it. Out of curiosity, I just calculated the paths, and what do you know, I was back to 50 FPS.

Well, it works, I guess. The paths I got were a bit weird, but in-area, they were good choices.

The main problem is that I didn’t use the same starting point for the next in-area JPS where the previous one ended. I will correct this soon. But first, I will describe two other problems – I find that outlining everything that bugs me first is more productive. First, well, I don’t forget them (I use this series as a diary of sorts also), second, it allows the readers to ponder on the problems, and suggest smart stuff. Or for me to do the same thing.

Bearing all that in mind, the first thing I’d like to add is a direction-based heuristic. This is most important when we are very close to the target tile, and want to choose the best direction. Also, as a tiebreaker. This should be a small, non-scaling amount. The other heuristics are scaling exponentially, and will outpace this one at a larger pace, as they should. The idea is very simple, and I’d like to describe it with an image.

Since we are using a lowest-first heuristic, 0 will represent the target direction, and the other directions will get the weights accordingly. Now, since I don’t know of any library in Java that has a “Spiky star with numbers” data structure, we have to think here a little bit, how to implement this efficiently.

If you’re not quite a Computer Science Wizard, maybe just a Computer Science Apprentice, and you only have mana to cast basic data structures, you might say doubly-linked circular linked list! You just search in two directions at the same time.

But the first thing is I need a method to determine the relative directions of two positions. This is easily done, given the coordinates.

    public static Direction relativeDirection(WalkPosition start, WalkPosition end) {
        if (start.getX() < end.getX()) {
            if (start.getY() == end.getY()) {
                return Direction.E;
            } else if (start.getY() > end.getY()) {
                return Direction.NE;
            } else if (start.getY() < end.getY()) {
                return Direction.SE;
            }
        } else if (start.getX() > end.getX()) {
            if (start.getY() == end.getY()) {
                return Direction.W;
            } else if (start.getY() > end.getY()) {
                return Direction.NW;
            } else if (start.getY() < end.getY()) {
                return Direction.SW;
            }
        } else if (start.getX() == end.getX()) {
            if (start.getY() > end.getY()) {
                return Direction.N;
            } else if (start.getY() < end.getY()) {
                return Direction.S;
            }
        }
        return null;
    }

I will continue with this a little later. This is the kind of method that could use a unit test. Ah, I’m sure it will be fine, I don’t ever make mistakes when coding.

Another problem is, and the more units I have, the more apparent this will become , is that I’m working at a WalkPosition-level resolution, and some (well, most) units are bigger than that. My feeling is that threats are mostly “blobs”, and narrow pathways between threatened areas are rare, but not nonexistent.

Let’s take a look at what we have. We have some path positions, and we know our unit’s size.

We also know that the next position is reachable by going in a straight line (Or diagonal, but for our purposes, this does not matter). Let’s assume a unit can go in a straight line (A bold assumption, especially for our shitlord hovercrabs), so its sides will move along an axis. Let’s assume they behave analogously when moving diagonally. Therefore, we can project the Big Boi’s path, like so:

All we know is that we should touch that position in some way. We need to ask to show me on the doll, where the Ultralisk touched you to which corner of the moving unit to align to have a pleasant journey.

In one of the previous parts, I already dealt with the surprisingly hard problem of determining if a line touches a given tile. We can make use of that here.

But as I promised, I will mostly just outline stuff in this part.

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!

PS.: Yegers started a great tutorial for BW API beginners here. Be sure to check it out!