First part of this series | Previous | Next | Index

This time, I’ll continue working on the ground-only pathfinding. Last time I mentioned that BWEM returns a bunch of chokepoints, which are composed of WalkPositions. It looks like this:

There are even wider chokes. I mentioned that I’m not sure that I want to use the flood fill here. I changed my mind, I am sure now. I’m a different man. The reason is that although I implemented a version that checks two positions, it can be easily adapted to check multiple target tiles. If we have path between any two WalkPositions, we have a path. A somewhat serious problem is, that it might be too narrow (for example, just one WalkPosition wide, and larger units will simply not fit through). Also, I would generally like to go around on the side where the threats aren’t (But that’s an another, different set of problems). First I just compared a collection with the filled fields.

//Method signature
   public static boolean pathExistsFloodFillArray(WalkPosition start, Collection<WalkPosition> endPoints, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory) {
//(..) Relevant part
   for (WalkPosition end : endPoints) {
                        if (end.getX() == x && end.getY() == y) {
                            return true;
                        }

This is not bad, but worst case scenario, I still compare a lot. Arrays are powerful, but the syntax, and maintainability can be hell if you overuse them. I decided that this is good enough, and instead I’ll restrict the problem space into a target area.

Chokepoints are always between two Area objects. BWEM returns a Pair of Areas that the ChokePoint is bordering. Logically, ther Area between two ChokePoints is the intersection of these two. (This Pair is a custom, BWAPI4J class, more or less working as you would expect)

Decomposing the problem, the steps we need to take:

• Writing the method for flood filling just one area
• Writing a modified JPS for pathfinding within an area
• Writing a method that does these area by area.

There is a method called bwem.getMap().getArea() – this can verify which are the WalkPosition belongs to. The problem is, this works with objects, which I would like to avoid creating. Since I’m already working with arrays, let’s go deeper into this rabbit hole this time. Sigh.

I’ll use a 2D array, as before.

Bytekeeper actually warned me, that the getArea() is not the girl I fell in love with working entirely as I would expect. If the target tile is not walkable, it might search for the nearest walkable one. With ground pathfinding, I’d have excluded those tiles anyway, but still, good to know. Oh, and also, it can just return nulls. With all that in mind, the initializer in the onStart() method:

		areaDataArray  = new int[bw.getBWMap().mapWidth()*4][bw.getBWMap().mapHeight()*4];
		for (int x=0; x<areaDataArray.length; x++ ) {
			for (int y = 0; y < areaDataArray[x].length; y++) {
				areaDataArray[x][y] = -1;
			}
		}
		areaDataArray  = new int[bw.getBWMap().mapWidth()*4][bw.getBWMap().mapHeight()*4];
		for (int x=0; x<areaDataArray.length; x++ ) {
			for (int y = 0; y < areaDataArray[x].length; y++) {
				WalkPosition wp = new WalkPosition(x, y);
				if (bwem.getMap().getArea(wp) != null) {
					areaDataArray[x][y] = bwem.getMap().getArea(wp).getId().intValue();
				}
			}
		}

For the next step, I started to fill the areaDataArray, and I thought – maybe if I don’t fill every field, just the ones with values different from (-1) – makes sense, right? But in order to compare these, I need to compare it to a coordinate of a WalkPosition. This is a great example of why premature optimization can be a stupid thing. I tried out three approaches for this. Code dump incoming.

//The original
       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;
            }
        }
//Version 2, the "optimized"
        for (int x = 0; x < Main.threatArray.length; x++) {
            for (int y = 0; y < Main.threatArray[x].length; y++) {
                if(Main.areaDataArray[x][y] != -1) {
                    Main.threatArray[x][y] = 0;
                }
            }
        }

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

        if (useThreatMemory) {
            for (WalkPosition wp : Main.threatMemoryMap.keySet()) {
                if(Main.areaDataArray[wp.getX()][wp.getY()] != -1) {
                    Main.threatArray[wp.getX()][wp.getY()] = 1;
                }
            }
        }
//Version 3, where I only use arrays to compare stuff
    for (int x = 0; x < Main.threatArray.length; x++) {
            for (int y = 0; y < Main.threatArray[x].length; y++) {
                if(Main.areaDataArray[x][y] != -1) {
                    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;
            }
        }

Can you guess what happened?

Yeah, the optimized version was 2.5x as slow as the original. Like I said before, arrays are fast. The sensible optimization was only faster by a real marginal amount. Other than this, the method is similar to the generic flood fill. I’m just copying here the relevant parts – basically one more check if we are still within the same area.

//
  int areaId = area.getId().intValue();
//Checks are extended
  if (isOnTheMap(x, y) && Main.threatArray[x][y] == 0 && Main.areaDataArray[x][y] == areaId) {

Now, the question pops up: What areas are chokepoints in? After all, they are the border between two. The answer is “I DUNNO LOL”, and also, it doesn’t really matter, as I’m only testing if I can reach it, and not extending the fill from them. They belong to some area by some logic, but I don’t really need to know that. Also, let’s not forget to check if the ground is actually passable. I have the isPassableGround() method, but that works with WalkPositions. Let’s write one that uses coordinates, and add that check to the fill as well. A lot of work for a very simple method. Such is life.

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;
}
//Later that class
 if (isOnTheMap(x, y) && Main.threatArray[x][y] == 0 && Main.areaDataArray[x][y] == areaId && isPassableGround(x, y)) 

This needs testings. And I just realized that for the pathfinding, I don’t actually give the two points where is a path present. Another concern is that if I just give the first pair, then I might not find the shortest / most optimal route. Consider the following:

There is a path between point 1 and point 2, sure. Still, maybe I would like to go from point 3 to point 4 instead. I can just consider every pair of start and end points, then pick the best route, but that’s gonna be costly, and a little contrary to what I actually want to achieve here.

Let’s think about this from another angle. When is this kind of path acceptable, and when it isn’t? This kind of pathfinding is used for completely avoiding threats. In practice, my units will still get hit, because I won’t be calling this all the time, and also, I don’t see every enemy unit. The major use case for this is scouting, and harassing. For scouting, I don’t really need the fastest route – seeing a few tiles less and/or later is probably not a big deal. For harassing, it’s maybe more of an issue. I want to get there as fast as possible (Think of early worker harasses, for example), and receiving as less damage as possible.

And also, what if I find the best two points first? How do I know that? Well, the closest distance between two points is in a straight line – point-to-point distance. Maybe if my path is exactly that long, or close enough to it, then I shouldn’t bother searching for a better one.

Taking all of the above into account, I decided to branch this out two “find any path”, and “find best path” usages.

First subproblem: find the common area of chokepoints. I was tempted to use a fancy data structure, namely a disjoint set for this, because I’m very smart.

So it will be just a simple, inefficient plebeians solution for now.

    public int findCommonAreaId(ChokePoint cp1, ChokePoint cp2) {
        for (WalkPosition wp1 : cp1.getGeometry()) {
            for (WalkPosition wp2 : cp2.getGeometry()) {
                if (Main.areaDataArray[wp1.getX()][wp1.getY()] == Main.areaDataArray[wp2.getX()][wp2.getY()]) {
                    return Main.areaDataArray[wp1.getX()][wp1.getY()];
                }
            }
        }
        return -1;
    }

I will flesh out the details for the ground algorithm in the next part. (I know I promised that before, but I’m a wild child, and cannot be tamed). Thanks for reading, and consider subscribing to the mailing list!