First part of this series | Previous | Next | Index
In the last part I tried to solve a subproblem of a subproblem. BWEM is really not solving the exact problem I’m having (Not talking about midlife crisis, although it certainly no help with that either), so I’m writing a ton of stuff on top of it.
I should have titled this article “Terrain analyzers: What do they know? Do they know things? Let’s find out!”. Back to the problem at hand. When assigning areaId values to tiles, I had islands of -1 values, which signify passable tiles, that don’t have a proper id. If everything is working as intended (as they rarely do), these can be only islands at this point, where are no positive neighbors are present, just like in my hometown. But how to get out of this rabbit hole?
Before actually beginning to solve the problem, I need some debugging to verify my assumptions. The pictures in the previous part showed a tiny subsegment of the map. The BW map drawer can only draw around 40000 things at the same time, and I have way more tiles than that in most of the cases. Since I have strings with a length of 1 or 2 for the most part (Come think of it, probably always), I can just dump those into a file in glorious ASCII.
Yeah, back to the basics.
public class MapFileWriter {
public static void saveAreaDataArray() {
BufferedWriter writer = null;
try {
writer = new BufferedWriter(new FileWriter("mapdata/" + Main.bw.getBWMap().mapFileName() + ".dat"));
for (int x = 0; x< Main.areaDataArray.length; x++ ) {
for (int y = 0; y < Main.areaDataArray[x].length; y++) {
String tx = String.format("%" + 3 + "s", String.valueOf(Main.areaDataArray[x][y]+"|") );
writer.append(tx);
}
writer.append("\n");
}
writer.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
//And in the onStart() of the Main class...
//Sectio debugiensis
MapFileWriter.saveAreaDataArray();Let’s see if the hypothesis is correct.
Confirmed! This was surprisingly smooth. How to eliminate these islands? We already have areaIds assigned by bwem, why not just have more? For these islands, multi-area pathfinding won’t be an issue, since they are islands. Let’s collect the assigned ids, then just not assign those to new areas. I just refactored the Cartography.mostCommon() method to do this logic as well.
public static Set<Integer> areaIds;
//onStart() - whee, very functional, much srs
areaIds = bwem.getMap().getAreas().stream().map(Area::getId).collect(Collectors.toSet()).stream().map(AreaId::intValue).collect(Collectors.toSet());
//The refactored method in Cartography
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;
} else {
//Assign a new areaId
int newAreaId = -1;
int id = 1;
while (newAreaId == -1) {
if (Main.areaIds.contains(id)) {
id++;
} else {
newAreaId = id;
}
}
Main.areaDataArray[x][y] = newAreaId;
Main.areaIds.add(newAreaId);
}
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);
}
}
}
}
}
}And it seems to work. On Jade, bwem originally assigned 26 ids – this method extended that to 123. It’s not that surprising – there were pockets of one or two fields. These most likely won’t get any attention, as they are too small for most units to land on.
With that, I finally have complete area data. We managed to climb out from the deepest level of this problem. With that, my eyes are cast towards the not-really perfect in-area JPS.
Let’s take another look at our path of shame.
I debugged it some times, tried modifying the order of processing straight and diagonal jump points – then just decided, let’s take the one with the lowest importance first (Which is actually the highest. Not confusing!)
int sImp = Integer.MAX_VALUE;
int dImp = Integer.MAX_VALUE;
JPSInfo jumpPoint;
boolean straightNext = false;
if (!straight.isEmpty()) {
sImp = straight.peek().getImportance();
}
if (!diag.isEmpty()) {
dImp = diag.peek().getImportance();
}
if (sImp <= dImp) {
straightNext = true;
}The outer loop checks if the diag and straight priority queues are both null, so we don’t need to do that. After that, we just decide which queue to poll next. This has nothing to do with the wonky path though. I logged the order of processed jump points. The origin was (116,55), the destination was (136,60).
Processing diag jumpPoint:[131, 59] Imp:4 DIR:SE
Processing straight jumpPoint:[132, 60] Imp:4 DIR: S
Processing straight jumpPoint:[132, 60] Imp:4 DIR: E
Processing diag jumpPoint:[133, 60] Imp:2 DIR:SE
Processing straight jumpPoint:[134, 61] Imp:2 DIR:S
Processing straight jumpPoint:[134, 61] Imp:2 DIR:EOh, so we actually add the next straight jump point to the next diagonal position, not starting on the same tile as the original. Oh well, let me just try not doing that… Modifying that value in just one place just yielded an exception – I didn’t check if that field is passable actually. I also had to modify that method, because there I didn’t check if that field is on the map. House of cards, man. After doing all of this, I progressed to just having an infinite loop.
Processing straight jumpPoint:[134, 61] Imp:2 DIR:E
Processing diag jumpPoint:[135, 62] Imp:2 DIR:SE
Processing straight jumpPoint:[135, 62] Imp:2 DIR:E
Processing straight jumpPoint:[135, 62] Imp:2 DIR:S
Processing diag jumpPoint:[134, 61] Imp:2 DIR:SE
Processing straight jumpPoint:[134, 61] Imp:2 DIR:E
Processing diag jumpPoint:[135, 62] Imp:2 DIR:SE
Processing straight jumpPoint:[135, 62] Imp:2 DIR:E
Processing straight jumpPoint:[135, 62] Imp:2 DIR:S
Processing diag jumpPoint:[134, 61] Imp:2 DIR:SEWell, there are two factors at play here. First of all, my heuristics is not fine-grained enough – somehow I have to factor in the relative direction as well. Second, I don’t see the point in visiting any jump point twice (Meaning a jump point with the same WalkPosition, and importance we had before). So I added that too.
Step by step, I discovered, that I don’t add the jump points to their correct places. For straight jumps, I need to place it to the next applicable diagonal tile, and for diagonals, I need to place the straight jump points to the same tile where I started! I did it exactly the opposite way, and it kinda worked. This wasn’t something I missed, this stemmed from my wrong understanding of JPS. Also, a major bug was when the algorithm found a jump point while processing a straight path, it stopped. Turns out, I don’t need to. And all this even before I even considered the areaId in my calculation – so basically, this applies to my base JPS as well. I hope you followed along this far, and implemented everything dutifully, and very wrongly. You are a good boy, yes you are.
I would like to get a little philosophical here. This final(ish) rewrite proves the importance of sometimes taking a step back, and just working on something else. Tunnel vision is a common problem when developing software, especially when doing it alone. The whole Starcraft AI started as a fun hobby project, where I just bang out code, and see what happens. But time and again, the complexity quickly exceeded my expectations, and testing, re-evaluating, and asking for advice became necessary. This is by no means a negative thing – meaningful collaboration on a project can bring great fulfillment to every party involved. A lot of software engineers are just happy to help, too, especially with interesting problems. And creating a Brood War AI is full of just those.
Alright, done with the philosophy. I need to add the area checks to my code, and hopefully, this part is over, and I can climb up one level in the rabbit hole. But a work in progress image, because I’m such a proud dad.
The areaId restriction is actually fairly uninteresting. Here is the complete, hopefully final code.
public static Set<WalkPosition> findUnthreatenedPathInAreaJPS(WalkPosition start, WalkPosition end, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory, int areaId) {
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);
ArrayList<JPSInfo> processed = new ArrayList<>();
processed.addAll(straightJPSInfos);
processed.addAll(diagJPSInfos);
if (isUnderThreat(ground, start, useActiveThreatMap, useThreatMemory) || isUnderThreat(ground, end, useActiveThreatMap, useThreatMemory)
|| !Main.bw.getBWMap().isValidPosition(start)
|| !Main.bw.getBWMap().isValidPosition(end)) {
foundPath = true;
}
if (ground) {
if (!isPassableGround(start) || !isPassableGround(end)) {
foundPath = true;
}
}
while (!foundPath && (!straight.isEmpty() || !diag.isEmpty())) {
int sImp = Integer.MAX_VALUE;
int dImp = Integer.MAX_VALUE;
JPSInfo jumpPoint;
boolean straightNext = false;
if (!straight.isEmpty()) {
sImp = straight.peek().getImportance();
}
if (!diag.isEmpty()) {
dImp = diag.peek().getImportance();
}
if (sImp <= dImp) {
straightNext = true;
}
if (straightNext) {
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) || !Main.bw.getBWMap().isValidPosition(ahead) || (ground && !isPassableGround(ahead)) && !isWalkPositionInArea(ahead, areaId)) {
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 (Main.bw.getBWMap().isValidPosition(straightNeighbor)) {
if (isUnderThreat(ground, straightNeighbor, useActiveThreatMap, useThreatMemory) || (ground && !isPassableGround(straightNeighbor)) || !isWalkPositionInArea(straightNeighbor, areaId)) {
WalkPosition diagWP = getNeighborInDirection(current, getJPDirections(jumpPoint.getDirection(), checkDir).iterator().next());
if (Main.bw.getBWMap().isValidPosition(diagWP) && !isUnderThreat(ground, diagWP, useActiveThreatMap, useThreatMemory) && isPassableGround(diagWP) && isWalkPositionInArea(diagWP, areaId)) {
Direction jpsDir = getJPDirections(jumpPoint.getDirection(), checkDir).iterator().next();
JPSInfo jpsInfo = new JPSInfo(jpsDir, getNeighborInDirection(current, jpsDir), calcJPSImportance(diagWP, start, end, jumpPoint.getGeneration()), jumpPoint);
// straightPathProcessed = true;
if (!processed.contains(jpsInfo)) {
diag.add(jpsInfo);
processed.add(jpsInfo);
}
}
}
}
}
current = ahead;
ahead = getNeighborInDirection(ahead, jumpPoint.getDirection());
}
}
else {
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);
break;
}
//If the next tile in the diagonal direction isn't blocked, let's add that too
if (!isUnderThreat(ground, diagAhead, useActiveThreatMap, useThreatMemory) && Main.bw.getBWMap().isValidPosition(diagAhead) && isWalkPositionInArea(diagAhead, areaId)) {
JPSInfo jpsInfo = null;
if (Main.bw.getBWMap().isValidPosition(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) {
if (!processed.contains(jpsInfo)) {
diag.add(jpsInfo);
processed.add(jpsInfo);
}
}
}
//Check the 2 straight jump points in any case
for (Direction dir : diagForwardPos.get(jumpPoint.getDirection())) {
WalkPosition neighbor = getNeighborInDirection(jumpPoint.getWalkPosition(), dir);
Set<JPSInfo> jpsInfosInDirection;
if (!isUnderThreat(ground, neighbor, useActiveThreatMap, useThreatMemory) && isWalkPositionInArea(neighbor, areaId))
if (ground) {
if (isPassableGround(neighbor)) {
jpsInfosInDirection = getJPSInfosInDirection(jumpPoint, jumpPoint.getWalkPosition(), start, end, ground, useActiveThreatMap, useThreatMemory, dir);
for (JPSInfo j : jpsInfosInDirection) {
if (!processed.contains(j)) {
straight.addAll(jpsInfosInDirection);
processed.addAll(jpsInfosInDirection);
}
}
}
} else {
jpsInfosInDirection = getJPSInfosInDirection(jumpPoint, jumpPoint.getWalkPosition(), start, end, ground, useActiveThreatMap, useThreatMemory, dir);
for (JPSInfo j : jpsInfosInDirection) {
if (!processed.contains(j)) {
straight.addAll(jpsInfosInDirection);
processed.addAll(jpsInfosInDirection);
}
}
}
}
//Check the two remaining straight directions
for (Direction checkDir : diagCheckPos.get(jumpPoint.getDirection())) {
WalkPosition wp = getNeighborInDirection(diagAhead, checkDir);
if (Main.bw.getBWMap().isValidPosition(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 (isWalkPositionInArea(j.getWalkPosition(), areaId)) {
if (ground) {
if (isPassableGround(j.getWalkPosition())) {
if (!processed.contains(j)) {
diag.add(j);
processed.add(j);
}
}
} else {
if (!processed.contains(j)) {
diag.add(j);
processed.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;
}It’s grown so much! Unfortunately, this is just how BWAPI is – a lot of edge cases, and weird conditions to check. I’m sure this can be improved upon, but for now, I’m gonna move on to other problems. The next thing will be the multi-area pathfinding, and some more extensive testing of that. (Yes, I left the commented-out line in on purpose)
Thanks for reading! If you liked this article, consider subscribing to the mailing list in the sidebar for updates. Also, if you’d like to support me, check out my shop for Undermind-related (and other cool) items!