First part of this series | Previous | Next | Index

After getting JPS to work reasonably well in the last part, for once I decided to tidy up, and improve things on the to-do list instead of diving headfirst into some new thing.

Last time, it has been shown that the heuristics for my JPS is a piece of shit needs some slight improvement. For the first iteration, I’ll borrow the approach from A*, and besides the distance from the destination, I’ll weigh in the number of parent jump points. Now, so far I used the squared distance for my calculations, and that clearly increases at a non-linear rate, so I have to get the square root of that.

Also, my JPSInfo objects will have a generation field – just the number of ancestors they have.

    public static int calcJPSImportance(WalkPosition actual, WalkPosition start, WalkPosition end, int gen) {
        int endImp = positionToPositionDistanceSq(end.getX(), end.getY(), actual.getX(), actual.getY());
        return FastIntSqrt.fastSqrt(endImp) + gen;
    }
//Also, changed the JPSInfo class
    private int generation = 0;

    public JPSInfo(Cartography.Direction direction, WalkPosition walkPosition, int importance, JPSInfo precursor) {
        this.direction = direction;
        this.walkPosition = walkPosition;
        this.importance = importance;
        this.precursor = precursor;
        if (precursor != null) {
            this.generation = precursor.getGeneration()+1;
        }
    }

Upon running, it consistently gives us the best path (the second one in the previous article):

That, of course is not evidence that it will behave correctly every time. Another pressing issue was the passability of tiles – the algorithm clearly gave wrong paths in that regard, passing through mineral fields, and buildings.

In the past, I used the BW.isWalkable() method, which it turns out, only checks static map features, not buildings/units. Yes, geysers and minerals are units.

I’m starting to think that there are no easy problems in bot development. After speaking with fellow bot authors (and actually discussing this problem in the podcast), the easiest solution seems to be to keep track of tiles occupied by units. For my units, and units I can see, that’s not really a problem, I can just loop through them and get their occupied WalkPositions, and cache that. (Doing that efficiently is another matter)

For enemy units, it’s not that easy. I have a memory of enemy units, but that might or might not be correct. An enemy unit can just walk into my planned path while moving. The bastard. So this just generates a new problem: When to re-plan my route? This is not strictly a pathfinding issue though, so i’m shelving it for a bit.

So the first sub-problem is just keeping in mind the occupied tiles. There are two viable approaches I thought about: the first is just keeping some kind of set of the positions, and updating those every now and then. (Preferably on every frame, but we’ll see)

The other is two-dimensional, I would keep track of tiles, and the last frame they were occupied. This could come in handy when assessing risks later.

With both approaches, I have to keep in mind, that cache is plenty, but processing time is limited. Maybe the two can be used together somehow? Anyway, onto the first one, with the naivistic approach.

	public HashSet<WalkPosition> occupiedGroundPositions = new HashSet<>();
	public void updateOccupiedGroundPositions() {
		occupiedGroundPositions.clear();
		for (Unit unit : bw.getAllUnits()) {
			if (!unit.isFlying()) {
				occupiedGroundPositions.addAll(Cartography.getOccupiedWalkPositionsOfUnit(unit));
			}
		}
	}

I tried it first with assigning the variable a new Set every time, and measured that:

Then compared that with the HashSet.clear() approach:

Interesting, and I actually don’t want to delve more into why is that. The important thing is that I tried it out with a LOT of units, and it didn’t seem to affect the performance.

Onto the second approach. Yet again I talked with some smart people, and turns out, it might be even faster, by using arrays, which are surprisingly fast in Java. While at it, I compared the everything. UpdateOccupiedGroundPositions1 is assigning a new Set, version 2 is using. the clear() method on it. GroundMap is using a HashMap, the other three is using one, or two dimensional arrays, respectively. The results are a bit surprising, I expected the bitwise calculation to win, but the 2D array seems to be the clear first here. I would use that for convenience as well. I guess, yet again I failed to be smarter than decades of compiler development.

Now that the marginally useful optimization is done, I’ll keep the 2D array approach. It’s actually very simple.

//In the onStart method:
		dim1GroundArray = new int[bw.getBWMap().mapWidth() * bw.getBWMap().mapHeight() *16];
//
public void updateOccupied2DimArray() {
		for (Unit unit : bw.getAllUnits()) {
			if (!unit.isFlying()) {
				for (WalkPosition wp : Cartography.getOccupiedWalkPositionsOfUnit(unit)) {
					dim2GroundArray[wp.getX()][wp.getY()] = frameCount;
				}
			}
		}
	}

Now, in the Cartography class, I’ll just have a method that checks if the tile is walkable, and it hasn’t been occupied lately. How lately? Well, the best answer I have for that is “i dunno lol”. Let’s give it 100 frames, because why not. But we have to have a default value as well, that is not obtainable by default. If it’s the default value, or the difference between the value and the current frame is greater than the set period, then we return true for passability.

//In the onStart() method, initialize the array to the default value:
		for (int x=0; x<occupiedGroundArray.length; x++ ) {
			for (int y=0; y<occupiedGroundArray[x].length; y++ ) {
				occupiedGroundArray[x][y] = -1;
			}
		
//FUCK YEAH CONSTANTS
    public static final int GROUND_FORGET_PERIOD = 100;

    public static boolean isPassableGround(WalkPosition wp) {
        if (Main.bw.isWalkable(wp) &&
                (Main.occupiedGroundArray[wp.getX()][wp.getY()] == -1 ||
                (Main.frameCount - Main.occupiedGroundArray[wp.getX()][wp.getY()]) > GROUND_FORGET_PERIOD)) {
            return true;
        }
        return false;
    }

And of course, every walkability check I substituted with the isPassableGround() method.

Does this work? The answer is “sorta”. Let’s take a look at this image:

Things that are not apparent: The SCV was moving from the left to the right, and I ran the pathfinding on every frame. It ground to a halt. After setting the forget period to just 10 frames, it sped up a little, but still, running every frame is not a viable option.

One thing that is apparent though, that the mineral field is considered passable for some reason.

Still, progress!

Upon some debugging, I found out that actually my JPS logic was not complete in this particular case. I added the passable checks to the algorithm. Let’s test that out. I drew the occupied tiles of neutral units in orange.

It seems alright, finally! The threat grid I didn’t draw, but it doesn’t matter – I’m reasonably certain that it functions at this point. The slowness, however, didn’t disappear. The problem is, like a drug addict, JPS just doesn’t know when to stop.

First, I just added a restriction for checking the start and end positions, and this eliminated some of the problems. But every time I blocked the paths, the algorithm ground to a halt. First I checked if maybe I’m re-adding points continuously. Turns out that was not the crux of the issue – the algorithm just checked the whole map, and it didn’t actually froze, was just very slow. I did find one edge case when I got an error – turns out, I don’t check if WalkPositions in the map in every case, and the isWalkable() method returns an ArrayIndexOutOfBounds Exception. I’m not sure that is right, so I was a good boi, and contacted the BWAPI4J team. But for my code, I just added the isOnTheMap() checks everywhere. Here is the current complete code, because I know you like wall of codez.

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;
        Set<JPSInfo> straightJPSInfos = getJPSInfosInDirection(startJPSInfo, start, start, end, ground, useActiveThreatMap, useThreatMemory, Direction.E, Direction.W, Direction.S, Direction.N);
        straight.addAll(straightJPSInfos);
        Set<JPSInfo> diagJPSInfos = getJPSInfosInDirection(startJPSInfo, start, start, end, ground, useActiveThreatMap, useThreatMemory, Direction.NE, Direction.NW, Direction.SE, Direction.SW);
        diag.addAll(diagJPSInfos);

        if (isUnderThreat(ground, start, useActiveThreatMap, useThreatMemory) || isUnderThreat(ground, end, useActiveThreatMap, useThreatMemory)
                || !isOnTheMap(start)
                || !isOnTheMap(end)) {
            foundPath = true;
        }

        if (ground) {
            if (!isPassableGround(start) || !isPassableGround(end)) {
                foundPath = true;
            }
        }
        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) || (ground && !isPassableGround(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 (isOnTheMap(straightNeighbor)) {
                            if (isUnderThreat(ground, straightNeighbor, useActiveThreatMap, useThreatMemory) || (ground && !isPassableGround(straightNeighbor))) {
                                WalkPosition diagWP = getNeighborInDirection(current, getJPDirections(jumpPoint.getDirection(), checkDir).iterator().next());
                                if (isOnTheMap(diagWP) && !isUnderThreat(ground, diagWP, useActiveThreatMap, useThreatMemory) && isPassableGround(diagWP)) { //Todo passableground rework
                                    JPSInfo jpsInfo = new JPSInfo(getJPDirections(jumpPoint.getDirection(), checkDir).iterator().next(), current, calcJPSImportance(diagWP, start, end, jumpPoint.getGeneration()), jumpPoint);
                                    straightPathProcessed = true;
                                    diag.add(jpsInfo);
                                }
                            }
                        } else { //We reached the edge of the map
                            straightPathProcessed = true;
                        }
                    }
                    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 = null;
                        if (isOnTheMap(diagAhead)) {
                            if (ground) {
                                if (isPassableGround(diagAhead)) {
                                    jpsInfo = new JPSInfo(jumpPoint.getDirection(), diagAhead, calcJPSImportance(diagAhead, start, end, jumpPoint.getGeneration()), jumpPoint);
                                }
                            } else {
                                jpsInfo = new JPSInfo(jumpPoint.getDirection(), diagAhead, calcJPSImportance(diagAhead, start, end, jumpPoint.getGeneration()), jumpPoint);
                            }
                        }
                        if (jpsInfo != null) {
                            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);
                        for (JPSInfo j : jpsInfosInDirection) {
                            straight.add(j);
                        }
                        //straight.addAll(jpsInfosInDirection);
                    }
                    //Check the two remaining straight directions
                    for (Direction checkDir : diagCheckPos.get(jumpPoint.getDirection())) {
                        WalkPosition wp = getNeighborInDirection(diagAhead, checkDir);
                        if (isOnTheMap(wp) && isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
                            Set<JPSInfo> jpsInfosInDirection = getJPSInfosInDirection(jumpPoint, wp, start, end, ground, useActiveThreatMap, useThreatMemory, getJPDirections(jumpPoint.getDirection(), checkDir));
                            for (JPSInfo j : jpsInfosInDirection) {
                                if (ground) {
                                    if (isPassableGround(j.getWalkPosition())) {
                                        diag.add(j);
                                    }
                                } else {
                                    diag.add(j);
                                }
                            }
                        }
                    }
                }
            }
        }
        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;
    }

This is actually good news. It means that it’s performance problem, not a functional one. Back to our drug addict problem!

Through meticulous testing (clicking crabbos around like an idiot) I found out that the problem occured when the end point is “boxed in”. The algorithm just checks the whole map. In the Best Friend Search, I implemented a very naive check (boxes with increasing radiuses). But that’s obviously not foolproof. For example, it fails for even a rectangle, not a perfect square.

But that’s a topic for the next article. Thanks for reading, and if you liked this article, please consider subscribing!