First part of this series | Previous | Next | Index

So, in the last part, I yet again managed to implement a slow method. Now, unless you are an actual sloth, you probably don’t enjoy playing Starcraft under 1 FPS. I took a look at my handy-dandy VisualVM, what is the slow part of the pathfinding.

If you’re new to this series, you might want to read back a few parts – I’m really getting into subproblems of subproblems here. Maybe start with Jump Point Search for Jumpy Doggos.

The results are somewhat discouraging. Working with an ArrayList instead an array is of course, a performance disadvantage, but even so, would changing that speed up this in a meaningful way? JPS seemed reasonably fast in the past, why the sudden snail pace? Debugging time.

Entering level:0 start:[5, 5] end:[108, 63] areaID:5
Entering level:1 start:[108, 63] end:[136, 61] areaID:5
Entering level:0 start:[5, 5] end:[108, 62] areaID:5
Entering level:1 start:[108, 62] end:[136, 61] areaID:5
Entering level:0 start:[5, 5] end:[108, 61] areaID:5
Entering level:1 start:[108, 61] end:[136, 61] areaID:5
Entering level:0 start:[5, 5] end:[108, 60] areaID:5
Entering level:1 start:[108, 60] end:[136, 61] areaID:15
Entering level:2 start:[136, 61] end:[121, 155] areaID:15
Entering level:1 start:[108, 60] end:[136, 62] areaID:15
Entering level:2 start:[136, 62] end:[121, 155] areaID:12
Entering level:3 start:[121, 155] end:[284, 351] areaID:12

Oh noes. If different levels have the same areaIds, that’s bad. I normalized to the start tile’s areaId, and that’s only good at the first step. Okay, I changed the logic up.

                if (level == 0) {
                    startTile = start;
                    endTile = getFirstUnthreatened(bwemPath.get(level));
                    areaId = Main.areaDataArray[start.getX()][start.getY()];

                } else if (level == bwemPath.size()) {
                    startTile = getFirstUnthreatened(bwemPath.get(level-2));
                    endTile = end;
                    areaId = Main.areaDataArray[end.getX()][end.getY()];
                }
                else {
                    startTile = getFirstUnthreatened(bwemPath.get(level-1));
                    endTile = getFirstUnthreatened(bwemPath.get(level));
                    areaId = Main.areaDataArray[endTile.getX()][endTile.getY()];
                }

And I got… well, a NullPointerException, but disregard that for a moment, and also a good path, that I could easily find out while maintaining 50 FPS. Yeah, it turns out, JPS is fast. I wonder how did it find a path before? Well, I’m okay with not ever knowing that, to be honest. The NullPointer occurs when there is no unthreatened endpoint, and I still try to get the areaId.

But with all this, an unfamiliar thought just occured. This part is done. It is ready to use. There will be additions, of course, but the core functionality will be untouched.

The first addition is properly returning a partial path when requested. It’s somewhat easy, just give back the path to the last endpoint, which is of course a part of a ChokePoint. But that still leaves the last area to be considered. And considering the use case, what needs to be done here is not that trivial.

The basic use case was to do a zergling runby, and rush for the workers. For this, I need to avoid as many threats as possible. But the workers themselves have threatened areas, however small.

According to the picture, mmm waffles our brave biopupper will have to stop just a few positions short of our intended target. So okay, we know how to get to an unthreatened position. Let’s just get to the nearest one.

Except, nearest to who? The target or the attacker? The question is not so trivial. Consider the following:

The closest point is the red square, but we actually want the green one. So getting the best approach point is not just a matter of simple distance calculation. What could probably work is to go in an ever-increasing radius (radii? radish?), and compare path lengths to unthreatened positions. It’s my feeling that this won’t be perfect, because nothing ever can be in this damned life, I wonder whether it’s worth it at all edge cases, but let’s roll with it.

If you see another rabbit hole forming (getting digged? What’s the proper noun for creating a rabbit hole? Other than “software development”? ), you might be not wrong.

Let’s start by the simplest metric, path length. The amount of jump points is not meaningful in this case. When moving diagonally, we create one every step, while when moving straight, we only create one when stopping.

Other smart people already thought of this. Since we can move diagonally, and the cost of it is the same for moving straight, the simple sum distance between the path points can be used. Since this is after the pathfinding itself, there will be no obstacles between two consecutive jump points.

Oh, but we don’t actually return the jump positions in order, do we? I’m returning HashSets, where the order of elements is not guaranteed. I guess that’s an easy fix, in the JPS method, we only summarize it, working from the endpoint backwards. Just change the output to ArrayLists, which do preserve the order of elements (Could also do arrays, but it’s not a performance issue here). I tried it out, and actually, it worked perfectly well, without any noticeable performance drop.

Okay, back to the “get nearest unthreatened to target” functionality. I already have a getWalkPositionsInGridRadius() method, so I can make great use of it here. Also, I wrote the path length summary method earlier. It wouldn’t be too interesting, but I left some shitposting in my own code, and I must share that. (That usually happens when you code late into the night)

    public static int getPathLength(ArrayList<WalkPosition> path) {
        int sumLength = 0;
           /*
        U WANT
            _ _
           < ö )

        SUM LENGTH?
            _____
            (O  O )
              V

            */
        for (int i=1; i<path.size(); i++) {
            sumLength = sumLength + FastIntSqrt.fastSqrt(positionToPositionDistanceSq(path.get(i).getX(), path.get(i).getY(), path.get(i-1).getX(), path.get(i-1).getY()));
        }
        return sumLength;
    }

Back to getting the approach point for the partial pathfinding. I plan this to be a generic method, not just for ground-based pathfinding – so it will be parameterized accordingly. If there is an areaId given, it will consider it – or more precisely, if a positive value is given. The maximum radius will be the distance between the start and end point. There is probably no path if we exceed that.

    //Find the WalkPosition, where the shortest unthreatened route leads from the start position
    public static WalkPosition getApproachPoint(WalkPosition start, WalkPosition end, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory, int areaId) {
        //getWalkPositionsInGridRadius
        boolean inArea = false;
        if (areaId > 0) {
            inArea = true;
        }
        int maxDist = getDistanceFastSqrt(start, end);
        WalkPosition approachPoint = null;
        int currentDist = 1;
        while (approachPoint == null && currentDist < maxDist ) {
            Set<WalkPosition> positions = getWalkPositionsInGridRadius(start, currentDist);
            int minPathLength = Integer.MAX_VALUE;
            for (WalkPosition wp : positions) {
                if (isWalkPositionOnTheMap(wp.getX(), wp.getY())
                        && !isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)
                        && (!inArea || Main.areaDataArray[wp.getX()][wp.getY()] == areaId)) {
                    int pathLength;
                    if (inArea) {
                        pathLength = getPathLength(findUnthreatenedPathInAreaJPS(start, wp, ground, useActiveThreatMap, useThreatMemory, areaId));
                    } else {
                        pathLength = getPathLength(findUnthreatenedPathJPS(start, wp, ground, useActiveThreatMap, useThreatMemory));
                    }
                    if (pathLength < minPathLength) {
                        minPathLength = pathLength;
                        approachPoint = wp;
                    }
                }
            }
            currentDist++;
        }
        return approachPoint;
    }

I’m starting to rely more and more on my own methods here. Ah well, it’s not like my code has bugs or anything. Back to the partial path problem, the case when we want to give a path as close to the target as possible. This will likely be a frequent use case.

Also, a quick side note about using FastSqrt. I’m only working with integers so far, so having an integer square root library makes sense. However, I have a pretty good guess of the range of integers I’ll be working with for the most part. Considering this, and the fact that I might have to calculate square roots frequently, just simply storing square roots somewhere for the first n integers can make sense, and could lead to performance gains.

In giving the partial path, there are three notable cases.

• No path between the start point, and the first chokepoint. We can simply GTFO gracefully terminate here.
• No path between the last chokepoint, and the final endpoint. This is what we basically solved with the method above. Also, this will occur frequently – Imagine that we want to reach some unit, but it’s inside the enemy’s base, well insulated by other units, and their big scary guns.
• No path between any two chokepoints. Now this is much trickier, since it’s not clear to what point we want a path to. Areas and chokepoints are not uniformly shaped, they resemble something like a smashed liquid potato instead.

I’m noting down another concern for a future date (There will be more and more of that sort). All that is done so far is applicable for threats at a point in time. Which is to say, a frame, of which a considerable amount happen per second. During these, besides the jumpy doggo, another unit might decide to change their place, and consequently, their threatened area. (They can’t really just leave the guns home, I’m afraid). So, I need to re-plan the path sometime, but I don’t want to do this every frame. Just for the lulz, I tried out how many times I can get away with it without FPS drops. The answer is a whopping four.

I can easily have hundreds of units. I’m sure I can optimize my pathfinding further, but probably not to a degree that every unit can call it every frame. So down in the line, some resource (CPU) allocation logic might be in order.

And that concludes this episode of my journey. Thanks for reading! If you liked this article, consider subscribing to the mailing list in the sidebar for updates, or to the RSS feed!