(This is an ongoing series. I’m referring to things I did in the previous installment. If you’re new to this, I recommend starting at the first episode.)
First part of this series | Previous | Next | Index
I decided to tackle the partial pathfinding problem first. More specifically, when I have no path between two chokepoints. In that case, when I can’t reach the other chokepoint (Chokepoints are lines, made up from multiple WalkPositions), I must have some kind of border of reachable objects. An over-simplified representation:
Where the fields marked with x are threatened (excluded), and the fields marked with O are the new border. If I have all the border points, then I need to pick one – since I’m stopping the pathfinding here, I’ll get the one that is closest to my desired endpoint.
Okay, but how to find out the border itself? I know where the threatened positions are, and what positions are within the area, but not much else. During the pathfinding, I’m checking all positions in the area – that might seem like a good place to put this at first glance. But since I know for a fact that the partial pathfinding will be called fewer times than the full, that would be an unnecessary slowdown. Instead, I’ll just check every position in a given area, and if it’s adjacent to a threatened position, I’ll add it to the border (No diagonal adjacency in this case).
I already have a method for this. You can observe the rarely seen XOR operator in it’s natural habitat.
//Only non-diagonal adjacency
public static boolean isAdjacentStrict(WalkPosition wp1, WalkPosition wp2) {
if (Math.abs(wp1.getX() - wp2.getX()) <= 1 ^ Math.abs(wp1.getY() - wp2.getY()) <= 1) {
return true;
}
return false;
}That’s nice and all, but I do have a 512*512 array to loop through. That’s like, a lot. If this proves to be too slow, I need to cache the coordinates by areaIds – after all, those won’t change during the game.
During this dumb implementation, I actually need to check things the opposite way. Get all the positions that are not threatened, and in the desired area, and then check it’s non-diagonal neighbors to see if they are threatened. But I’ll leave my glorious XOR code here nonetheless.
And the borderfinder algorithm, which is very glorious too, maybe less so.
public Set<WalkPosition> getThreatBorder(boolean useActiveThreatMap, boolean useThreatMemory, int areaId) {
HashSet<WalkPosition> border = new HashSet<>();
for (int x = 0; x < Main.areaDataArray.length; x++) {
for (int y = 0; y < Main.areaDataArray[0].length; y++) {
if (Main.areaDataArray[x][y] == areaId) {
if (useActiveThreatMap && Main.activeThreatMapArray[x][y] != null) {
if ((isWalkPositionOnTheMap(x + 1, y) && Main.activeThreatMapArray[x + 1][y] != null)
|| (isWalkPositionOnTheMap(x - 1, y) && Main.activeThreatMapArray[x - 1][y] != null)
|| (isWalkPositionOnTheMap(x, y + 1) && Main.activeThreatMapArray[x][y + 1] != null)
|| (isWalkPositionOnTheMap(x, y - 1) && Main.activeThreatMapArray[x][y - 1] != null)) {
border.add(new WalkPosition(x, y));
}
}
if (useThreatMemory && Main.threatMemoryMapArray[x][y] != null) {
if ((isWalkPositionOnTheMap(x + 1, y) && Main.threatMemoryMapArray[x + 1][y] != null)
|| (isWalkPositionOnTheMap(x - 1, y) && Main.threatMemoryMapArray[x - 1][y] != null)
|| (isWalkPositionOnTheMap(x, y + 1) && Main.threatMemoryMapArray[x][y + 1] != null)
|| (isWalkPositionOnTheMap(x, y - 1) && Main.threatMemoryMapArray[x][y - 1] != null)) {
border.add(new WalkPosition(x, y));
}
}
}
}
}
return border;
}Yeah, a lot of stuff needs to be checked. If I manage to get the border, it becomes another known problem, which is the closest pair of points. And that’s the best of these distances – I might get away with just picking one at random.
If the pathfinding stops at some level, that can mean two things. One case is if there is no unthreatened WalkPosition in the second chokepoint. Another when there is an unthreatened one, but no path to it. Getting the threat border is tricky, becuase I need an areaId for it. Fortunately, I kinda solved this problem before, with the findCommonAreaId() method. So in the end, the partial pathfinding parameters will look like this:
if (givePartialPath) {
for (ArrayList<WalkPosition> a : pathPieces) {
summaryPath.addAll(a);
if (level == bwemPath.size()) {
//Cannot find path to the endpoint in the last area
summaryPath.add(getApproachPoint(summaryPath.get(0), end, true, useActiveThreatMap, useThreatMemory, Main.areaDataArray[end.getX()][end.getY()]));
} else if (level>0){
int borderAreaId = findCommonAreaId(bwemPath.get(level - 1), bwemPath.get(level));
WalkPosition startTile = getFirstUnthreatenedPassable(bwemPath.get(level-1));
Set<WalkPosition> threatBorder = getThreatBorder(useActiveThreatMap, useThreatMemory, borderAreaId);
//TODO closest point or something
}
}
}I can’t just pick a random point in the threat border, because it’s entirely possible that there are “pockets” of unthreatened areas I can’t get to.
Weird as it is, I don’t actually have a heuristics for path existence that is faster than the pathfinding itself. So let’s just pick one path that works for now. In the meantime, I tried out the “approach point” method for getting the end tile. It works, but with noticeable slowdown. I’ll maybe revisit the efficiency later, but now I’ll just work with the hard limit of 10 calls per frame. It is quite enough, and actually, the paths can be even reused by mutliple units. “Conga line” is definitely not the best approach
One thing you might have noticed – the summaryPath is actually in reverse order, that’s why I’m taking the first element to compare for the approach point, not the last. So below is the partial pathfinding clause, in it’s nested glory. (Well, they do say AI stands for Accumulated If statements)
if (givePartialPath) {
for (ArrayList<WalkPosition> a : pathPieces) {
summaryPath.addAll(a);
Collections.reverse(summaryPath);
;
if (level == bwemPath.size()) {
//Cannot find path to the endpoint in the last area
summaryPath.add(getApproachPoint(summaryPath.get(summaryPath.size() - 1), end, true, useActiveThreatMap, useThreatMemory, Main.areaDataArray[end.getX()][end.getY()]));
} else if (level > 0) {
int borderAreaId = findCommonAreaId(bwemPath.get(level - 1), bwemPath.get(level));
WalkPosition startTile = getFirstUnthreatenedPassable(bwemPath.get(level - 1));
Set<WalkPosition> threatBorder = getThreatBorder(useActiveThreatMap, useThreatMemory, borderAreaId);
//boolean pathToBorderExists = false;
for (WalkPosition wp : threatBorder) {
ArrayList<WalkPosition> pathToBorder = findUnthreatenedPathInAreaJPS(startTile, wp, true, useActiveThreatMap, useThreatMemory, borderAreaId);
if (!pathToBorder.isEmpty()) {
Collections.reverse(pathToBorder);
summaryPath.addAll(pathToBorder);
break;
}
}
}
}
}
}Does it work? You might have guessed that of course, it does not! What were you even thinking? Okay, debugging time. The threat border seems to be ok.
Maybe I should normalize the chokepoint Ids, like I do in every other case? Could common sense be an answer? It never is! Regardless, I added the normalization, just to be sure, man.
Looking a little bit closer, my threat border is not at the place where it should be, but on the chokepoint coordinates themselves. Hmm, looking at the getThreatBorder() method, I have a line:
useActiveThreatMap && Main.activeThreatMapArray[x][y] != nullI’m actually looking at unthreatened areas, that are next to a threatened area. Oh well, maybe that way will work?
Yes it will. (I start to sound like Tribore)
To finish up, here is some code gore.
for (ArrayList<WalkPosition> a : pathPieces) {
summaryPath.addAll(a);
Collections.reverse(summaryPath);
;
if (level == bwemPath.size()) {
//Cannot find path to the endpoint in the last area
summaryPath.add(getApproachPoint(summaryPath.get(summaryPath.size() - 1), end, true, useActiveThreatMap, useThreatMemory, Main.areaDataArray[end.getX()][end.getY()]));
} else if (level > 0) {
int borderAreaId = findCommonAreaId(bwemPath.get(level - 1), bwemPath.get(level));
int[] startValues = new int[bwemPath.get(level-1).getGeometry().size()];
int[] endValues = new int[bwemPath.get(level).getGeometry().size()];
int i = 0;
for (WalkPosition startWp : bwemPath.get(level-1).getGeometry()) {
startValues[i++] = Main.areaDataArray[startWp.getX()][startWp.getY()];
Main.areaDataArray[startWp.getX()][startWp.getY()] = borderAreaId;
}
i = 0;
for (WalkPosition endWp : bwemPath.get(level).getGeometry()) {
endValues[i++] = Main.areaDataArray[endWp.getX()][endWp.getY()];
Main.areaDataArray[endWp.getX()][endWp.getY()] = borderAreaId;
}
WalkPosition startTile = getFirstUnthreatenedPassable(bwemPath.get(level - 1));
Set<WalkPosition> threatBorder = getThreatBorder(useActiveThreatMap, useThreatMemory, borderAreaId);
for (WalkPosition wp : threatBorder) {
ArrayList<WalkPosition> pathToBorder = findUnthreatenedPathInAreaJPS(startTile, wp, true, useActiveThreatMap, useThreatMemory, borderAreaId);
if (!pathToBorder.isEmpty()) {
Collections.reverse(pathToBorder);
summaryPath.addAll(pathToBorder);
break;
}
}
i = 0;
for (WalkPosition startWp : bwemPath.get(level-1).getGeometry()) {
Main.areaDataArray[startWp.getX()][startWp.getY()] = borderAreaId = startValues[i++];
}
i = 0;
for (WalkPosition endWp : bwemPath.get(level).getGeometry()) {
Main.areaDataArray[endWp.getX()][endWp.getY()] = borderAreaId = endValues[i++];
}
}
}Since I call the normalization so often, I’ll refactor that to a separate method, eventually. But for now, this actually works, and a large piece of functionality has been finally achieved.
Except I ran a few tests, and it is still very slow, especially when there is a large area. The culprit is the JPS method, where I compare tiles a lot. As portrayed in Exhibit FCK-THS below.
Time to go full retard very nerd on this. So, we learned previously, that when in doubt, we should use arrays. In my JPS, I have a HashSet that contains all the processed tiles. This should be converted into an array somehow. The problem is, if I have a two-dimensional array like before, it’s not enough – two jump points equal if their coordinates AND directions match. I can’t represent that with just one value.
But nerds, uh, find a way. I have 8 directions. If I were to represent those with bits, then I can represent the checked directions with one integer.
So we have our Directions array, which is such: {N, NW, W, SW, S, SE, E, NE}. When I fill the value for the coordinate, I want to fill the nth bit from the right (I can do it from the left as well, matter of choice), so for example, 0001 0001 (= 17) would be the representation of N and SW checked. So first of all, let’s create an array with values for every WalkPosition. We also have to reset this for every JPS . It’s not a problem, we only have one pathfinding active at a time, so we can work with a static variable here. For filling the values:
int jVal = (int)Math.pow(2, jpsInfo.getDirection().ordinal());
processedMap[jpsInfo.getWalkPosition().getX()][jpsInfo.getWalkPosition().getY()] = jVal;Oh, but Math.pow() gives us a double, and we have to cast it back to an int. Will someone please think of the CPU cycles? Just calculating powers of 2 is something our computing machine can do very well. If you said a faster method is to “just cache it”, you 1. get a cookie 2. are still wrong. The answer is a bitshift here.
int jVal = 1 << jpsInfo.getDirection().ordinal();Ordinal represents the place of the enum, so the jVal is 2^ordinal, but in binary. Yeah, it’s very readable. To check if a given direction is already processed, we need a reverse bitshift (what else?). More so, a a left shift, followed by a bitwise AND. – so basically just checking the nth bit. The checking algorithm:
public static boolean processedMapContains(JPSInfo jpsInfo) {
if (processedMap[jpsInfo.getWalkPosition().getX()][jpsInfo.getWalkPosition().getY()] != 0) {
int jVal = processedMap[jpsInfo.getWalkPosition().getX()][jpsInfo.getWalkPosition().getY()];
if ((jVal>>(jpsInfo.getDirection().ordinal()) & 1) == 1) {
return true;
}
}
return false;
}Now this actually needs some unit testing before going forward. Which I will do, and write about the results in the next installment of this series, because I just love ending on a cliffhanger.
Thanks for reading! If you liked this article, consider subscribing to the mailing list in the sidebar for updates, or to the RSS feed! Also, if you’d like to support me, my blog, or my podcast, check out my shop here! (And get 20% discount with the code “UNDERMIND”!)