First part of this series | Previous | Next | Index

First, a sub-problem from the last part. Given a start point, and a collection of endpoints, I’ll return the first endpoint that the flood fill reaches. This is not the optimal path, but it’s a fast calculation. With that, let’s begin implementing the findAnyPathInArea() function. This will first verify if there is a path, then use JPS within the area to find it. The input parameters are two chokepoints, courtesy of BWEM. Two preliminary checks are added: If there is no common area for the chokepoints, then they are not bordering the same area, so this point is no good here. The second is, if there is no path found with flood fill, then no need to do JPS.

A convention I started is to return empty collections for this kind of things, and avoid returning nulls, where possible. I still do that sometimes, but the NullPointerException is always lurking around the corner.

In my method, I assume that I’m trying to find a path on the ground, so everywhere there is a “ground” boolean parameter (Signifying ground-based search), I just give a true value. Currently, I see no use case when I would need to restrict my pathfinding to an area for air units. (Talking about the BWEM Area objects of course).

I will only modify my JPS to add an extra check for termination, if it reaches another areId. First, just filter the initial jump points:

      straightJPSInfos.stream().filter(j -> Main.areaDataArray[j.getWalkPosition().getX()][j.getWalkPosition().getY()] == areaId).collect(Collectors.toSet());
(...)
 diag.addAll(diagJPSInfos.stream().filter(j -> Main.bwem.getMap().getArea(j.getWalkPosition()).getId().intValue() != areaId).collect(Collectors.toSet()));

Looks complicated, but actually just a simple filtering. To not bloat the code more, I added a simple checking method for WalkPositions.

    public static boolean isWalkPositionInArea(WalkPosition wp, int areaId) {
        if (wp.getX() <= 0 || wp.getY() <= 0) {
            return false;
        }
        if (Main.areaDataArray[wp.getX()][wp.getY()] == areaId) {
            return true;
        }
        return false;
    }

Other than that, I added the check for every termination condition basically. The main method is the following:

    public static Set<WalkPosition> findAnyPathInArea(ChokePoint cp1, ChokePoint cp2, boolean useActiveThreatMap, boolean useThreatMemory) {
        int areaId = findCommonAreaId(cp1, cp2);
        HashSet<WalkPosition> path = new HashSet<>();
        if (areaId == -1 ) {
            return path;
        }

        WalkPosition start = null;
        WalkPosition end = null;

        for (WalkPosition wp : cp1.getGeometry()) {
            start = wp;
            end = pathExistsInArea(wp, cp2.getGeometry(), true, useActiveThreatMap, useThreatMemory, areaId);
            if (end != null) {
                break;
            }
        }

        if (end == null) {
            return path;
        }

        return findUnthreatenedPathInAreaJPS(start, end, true, useActiveThreatMap, useThreatMemory, areaId);
    }

Let’s have a first try.

Well, it’s… less than optimal, however successful. The problem is evaluating my paths – this will be ironed out later. First let’s make it work, then make it pretty (This methodology is considerable less effective in other industries).

When debugging this, I also noticed a slight problem with the area-based search. It doesn’t fucking work. When I populate the areaDataArray, I use bwem’s getMap().getArea().getId() method, which sometimes can return null. Okay, there is the getNearestArea() method, which returns some approximation. I tried initializing with that, when getArea() is giving me null.

I expected nothing, and I was still let down. It was slow as hell (It uses Breadth-first search), and for some reason, still gave nulls for some areas.

Okay, so I can’t really use bwem alone for this. This is only problematic for ground-based pathfinding (well, for now), and for passable ground tiles. I investigated the root cause a little, and it’s working as intended, just doesn’t fit my use case.

The main function of area-based pathfinding would be to decompose, and speed up global pathfinding, and not search the whole map. So as long every field has some id, this could more or less work. Again, keep in mind, that only passable ground tiles. Bwem is kinda-sorta fills my array. Exhibit 1:

Okay, this might make your eyes bleed be not very intuitive – I’m working with WalkPositions (8*8 pixels), while bwem is sort of not. Judging by this (albeit small) sample, what if I just take the fields in question, and set their values based on their neighbours? Obviously discarding “-1” values, and deciding randomly in a case of a tie. It will be mostly correct, and it’s arbitrary anyway. Since I only care about passable tiles, I can just prefilter them when filling the array in the first place.

//Pre-fill
		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();
				} else {
					if (!bw.getBWMap().isWalkable(x, y)) {
						areaDataArray[x][y] = -2;
					} else {
						areaDataArray[x][y] = -1;
					}
				}
			}
		}

-2 is the value for not passable, -1 is passable, but bwem was a jerk and didn’t gave us an areaId.

With the power of smarts, let’s see what we have here. Exhibit B: (This sounds so clever)

This is… what I wanted, actually. The water is proper impassable ground, and the coast has some tiles that are walkable. (The two images are not 100% of the same area, because I was lazy to do that). With that in mind, let’s have the neighbor vote algorithm.

Unfortunately, 2-way, and 4-way ties are both possible. I began to search for a quick solution. Solving this with a HashMap-based approach would be trivial, but potentially slow. I consulted my fellow SSCAIT authors, and there were a bunch of great suggestions. First, there were a “double array” method, when I just count the occurences, and then pick the maximum. Another, somewhat insane method is to store the coordinates as floats, and store the occurences in the fractional parts (Thanks krasi0!) – but that’s a bit much for my tastes. In the end, I picked a solution from here, which is very similar to the “double array”. Basically get the numbers, sort the array, then loop through once with a running maximum count.

Now, since this is Brood War, it’s not that simple. First, I get the neighbors based on the coordinates. Of course, these should be on the map. And within the areaDataArray‘s bounds. Then run the method on the neighbors, discarding -1 and -2 results.

   public static int mostCommonNeighbor(int x, int y) {
        int[] neighbors = new int[8];
        //Get the neighbors
        int ind = 0;
        for (int i = -1; i<=1; i++) {
            for (int j=-1; j<=1;j++) {
                if (!(j == 0 && i == 0)) {
                    if (x+i>=0 && y+j >=0 && x+i< Main.bw.getBWMap().mapWidth()*4 && y+j < Main.bw.getBWMap().mapHeight()*4) {
                            int current = Main.areaDataArray[x + i][y + j];
                    neighbors[ind] = current;
                    } else {
                        neighbors[ind] = -1;
                    }
                    ind++;
                }
            }
        }

        Arrays.sort(neighbors);
        int maxCount = 0;
        int currCount = 0;
        int result = -1;
        for (int n=1; n<neighbors.length; n++) {
            if (neighbors[n] != -1 && neighbors[n] != -2) {

                if (neighbors[n] == neighbors[n - 1]) {
                    currCount++;
                } else {
                    if (currCount > maxCount) {
                        maxCount = currCount;
                        result = neighbors[n - 1];
                    }
                    currCount = 1;
                }

                if (currCount > maxCount) {
                    result = neighbors[n];
                }
            }
        }
        return result;
    }
//Add this to onStart()
		for (int x=0; x<areaDataArray.length; x++ ) {
			for (int y = 0; y < areaDataArray[x].length; y++) {
				if (areaDataArray[x][y] == -1) {
					areaDataArray[x][y] = Cartography.mostCommonNeighbor(x,y);
				}
			}
		}

Yeah, not pretty, but it (maybe) works. Let’s check…

It is considerably better, the border of “-1″s have disappeared. Still, there are tiles with -1 values – the ones that had only negative neighbors to begin with. If I make another pass with this method, those might disappear. But then, I might still have -1s. The solution is kind of simple, I just call the method recursively, until there are no more -1s present. Or it would be simple, if there were no islands of -1 fields. I will deal with those later.

This is kind of like playing inverse minesweeper, come think of it.

Okay, let’s call the method recursively, when we find another -1 among the neighbors, but terminate early (and not run into an infinite loop when there are no positive neighbors). There is code duplication, kind of, but we have to live with that. You might notice that I changed the method to void – made sense for this usage.

    public static void mostCommonNeighbor(int x, int y) {
        int[] neighbors = new int[8];
        //Get the neighbors
        boolean hasPositive = false;
        int ind = 0;
        for (int i = -1; i<=1; i++) {
            for (int j=-1; j<=1;j++) {
                if (!(j == 0 && i == 0)) {
                    if (x+i>=0 && y+j >=0 && x+i< Main.bw.getBWMap().mapWidth()*4 && y+j < Main.bw.getBWMap().mapHeight()*4) {
                    neighbors[ind] = Main.areaDataArray[x + i][y + j];
                    if (neighbors[ind] > 0) {
                        hasPositive = true;
                    }
                    } else {
                        neighbors[ind] = -1;
                    }
                    ind++;
                }
            }
        }

        if (hasPositive) {
            Arrays.sort(neighbors);
            int maxCount = 0;
            int currCount = 0;
            int result = -1;
            for (int n = 1; n < neighbors.length; n++) {
                if (neighbors[n] != -1 && neighbors[n] != -2) {
                    if (neighbors[n] == neighbors[n - 1]) {
                        currCount++;
                    } else {
                        if (currCount > maxCount) {
                            maxCount = currCount;
                            result = neighbors[n - 1];
                        }
                        currCount = 1;
                    }

                    if (currCount > maxCount) {
                        result = neighbors[n];
                    }
                }
            }
            Main.areaDataArray[x][y] = result;

            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (!(j == 0 && i == 0)) {
                        if (x + i >= 0 && y + j >= 0 && x + i < Main.bw.getBWMap().mapWidth() * 4 && y + j < Main.bw.getBWMap().mapHeight() * 4) {
                            if (Main.areaDataArray[x + i][y + j] == -1) {
                                mostCommonNeighbor(x + i, y + j);
                            }
                        }
                    }
                }
            }
        }
    }

Another look, and as I suspected…

The islands of -1s remain. Since I decided to go down into this rabbit hole, I’m gonna solve this one way or another. Maybe assigning a random, previously unused variable to the islands? Maybe going to Nepal and live as a goat herder? Who knows – I’ll continue this in the next episode. Thanks for reading!