In the latter part of the last episode, I outlined two problems I want to solve next. The first is to weigh in the direction of my target when finding a path. It’s not a particularly hard problem, but how to do it most efficiently is kind of interesting.
First, I’ll reorder my Directions, then I’ll convert the Directions enum into an array. There is even a built-in method for that. It’s amazing how far has science come. Then, I can just work with indexes. Here is the pointy star for a reminder.
I take the absolute difference between the indexes, then if it’s greater than 4, i’ll get the difference from 8.
public enum Direction {N, NW, W, SW, S, SE, E, NE}
public static Direction[] dirArray = Direction.values();
//
public static int directionWeight(Direction source, Direction target) {
int sourceIndex = 0, targetIndex = 0;
for (int i=0; i<dirArray.length;i++) {
if (dirArray[i] == source) {
sourceIndex = i;
}
if (dirArray[i] == target) {
targetIndex = i;
}
}
int weight = Math.abs(sourceIndex-targetIndex);
if (weight > 4) {
weight = 8-weight;
}
return weight;
}This is simple, and quite fast. Technically O(n), but we only have 8 directions in any case. I guess I could have a map with values and indexes, then it would be O(1), but just for 8 elements, this is very marginal. Anyway, I tried this out, without changing anything else, and I already saw some smoother paths, and no “flicker” between two paths.
And now, while I’m sure there will be bugs, there is an usable, and fast algorithm for a path that avoids threats.
Let’s take it one step further, and find the best one, performance be damned. The thing is, we probably can’t really brute-force this. Let’s say we have 10 areas, and 10-10 chokepoints. Thats 10^3 paths to compare. We have to be aware that we are looking for the shortest overall path, If I find the shortest path in an area, the next one might be longer, as I might be starting in a worse position.
This is by no means a new problem. There is the well known hill-climbing algorithm that sort of deals with this. Except I’m trying to find a minimum here, so it’s more like a pit-digging algorithm, maybe? Would fit better my rabbit hole theme.
For testing the brute force algorithm, a very simple concept needs to be added – starting from the endpoint of the previous path. Now the problem is, that of course, not every endpoint will be a good starting point. The endpoint could very well be in a “pocket”. Oh well, this might be more complicated than I first thought.
An option is a kind of step-by-step search. First of all, I know how many areas I need to consider. Then I need to go to the first endpoint, start the search again from there, and if I can’t find a path, go one area back, and find another path. Essentially, I’m just traversing a tree here, where the nodes are the WalkPositions of the bwem’s ChokePoints. Yay, Computer Science!
/https://public-media.si-cdn.com/filer/bb/26/bb2665df-3384-4a0f-a5a4-ef9fa7b0d8e0/dsc06022.jpg?resize=400%2C300&ssl=1)
First, a consideration: Where should I put the excluded endpoints? I think an obvious choice is the areaDataArray. It is designed for this purpose, after all.
Second, I realized I don’t need to store an actual tree here. It is enough if I store the path pieces in some kind of structure, and replace them as needed. Since bwem gives us the chokepoints between areas, the size of this collection should be one more than the amount of chokepoints. Something like this:
ArrayList<Set<WalkPosition>> pathPieces = new ArrayList<>();
int level = 0; //Counter for the level we are in
if (bwemPath.size() == 0) {
return findUnthreatenedPathInAreaJPS(start, end, true, useActiveThreatMap, useThreatMemory, Main.areaDataArray[start.getX()][start.getY()]);
} else if (bwemPath.size() >= 1) {
//...todo implement actual smart thingsThen I need to consider the start and end tile. If i’m at level 0 of our imaginary tree, the start position is the start of the method, and if i’m at the last level, I finally get to use the rocket launcher the end position is similarly the end position given to the method.
Since I’m using WalkPosition to WalkPosition search, there is no need to use an intermediary method, as I did before (the findAnyPathInArea()). Can you follow all the method names? I sometimes can’t. Oh well, note to self: be smarter.
No need of intermediary methods, however, there is a need for areaId normalization, which is a term I just invented, but it means that the chokepoints should have the same areaIds, and I did that before. Taking care to not overwrite any -1 values, of course, which will also be added during the method, signifying dead ends in the search tree.
For the algorithm itself, the core of it is quite simple: If I find a path to some position in the next chokepoint, I increase the level variable, otherwise decrease, and mark the starting position (which was the end position one level up) as a dead end. I do this until I reach the last level with the plutonium dragon endpoint given to the method.
This sounds like a well thought-out plan, let’s see it crash and burn properly implemented!
On the question of area normalization: First, let’s save all the chokepoint values. Yet again, we can make use of the fact that they are ordered. Let’s have an ArrayList of arrays (array of arrays would be more efficient, but we need this only once, and working with collections is more convenient)
} else if (bwemPath.size() >= 1) {
//Saving the areadata values
for (ChokePoint cp : bwemPath) {
int[] cpData = new int[cp.getGeometry().size()];
int x = 0;
for (WalkPosition wp : cp.getGeometry()) {
cpData[x++] = Main.areaDataArray[wp.getX()][wp.getY()];
}
originalAreaValues.add(cpData);
}Also, we must take care to not return anything before restoring the original values. This is getting complicated. The “local” areaId normalization is more elaborate. We have three cases. Let’s call the number of total levels n. It’s the height of the search tree, basically.
- Level 0: We are searching from the method start. The areaId is normalized for the level 1 chokepoints, to the areaId value of the start tile.
- Level between 0 and n. Both for the start, and the end tile we need to get the first tile with non -1 value from the chokepoint. We need to normalize these two tiles, doesn’t really matter to which value.
- Level n. From the last chokepoint to the end tile. We need to normalize to the area data value of the end tile.
Even from a glance, the “get first unthreatened tile from a chokepoint” will be a very common functionality, so I extracted it to a method.
public static WalkPosition getFirstUnthreatened(ChokePoint cp) {
WalkPosition tile = null;
for (WalkPosition wp : cp.getGeometry()) {
if (Main.areaDataArray[wp.getX()][wp.getY()] != -1) {
tile = wp;
break;
}
}
return tile;
}With all that planning here is the full method in it’s long-winded glory.
public static Set<WalkPosition> findAnyPathMultiAreaContinuous(WalkPosition start, WalkPosition end, boolean useActiveThreatMap, boolean useThreatMemory, boolean givePartialPath) {
Set<WalkPosition> summaryPath = new HashSet<>();
CPPath bwemPath = Main.bwem.getMap().getPath(start.toPosition(), end.toPosition());
boolean fullPathExists = true;
ArrayList<Set<WalkPosition>> pathPieces = new ArrayList<>();
ArrayList<int[]> originalAreaValues = new ArrayList<>();
int level = 0; //Counter for the level we are in
if (bwemPath.size() == 0) {
return findUnthreatenedPathInAreaJPS(start, end, true, useActiveThreatMap, useThreatMemory, Main.areaDataArray[start.getX()][start.getY()]);
} else if (bwemPath.size() >= 1) {
//Saving the areadata values
for (ChokePoint cp : bwemPath) {
int[] cpData = new int[cp.getGeometry().size()];
int x = 0;
for (WalkPosition wp : cp.getGeometry()) {
cpData[x++] = Main.areaDataArray[wp.getX()][wp.getY()];
}
originalAreaValues.add(cpData);
}
while (level <= bwemPath.size()+1 && fullPathExists) {
WalkPosition startTile = null;
WalkPosition endTile = null;
int areaId;
if (level == 0) {
startTile = start;
endTile = getFirstUnthreatened(bwemPath.get(level));
areaId = Main.areaDataArray[start.getX()][start.getY()];
} else if (level == bwemPath.size()) {
startTile = getFirstUnthreatened(bwemPath.get(level-2));
endTile = end;
areaId = Main.areaDataArray[end.getX()][end.getY()];
}
else {
startTile = getFirstUnthreatened(bwemPath.get(level-1));
endTile = getFirstUnthreatened(bwemPath.get(level));
areaId = Main.areaDataArray[startTile.getX()][startTile.getY()];
}
if (startTile == null || endTile == null) {
fullPathExists = false;
break;
}
//local normalization
int startValue = Main.areaDataArray[startTile.getX()][startTile.getY()];
int endValue = Main.areaDataArray[endTile.getX()][endTile.getY()];
Main.areaDataArray[startTile.getX()][startTile.getY()] = areaId;
Main.areaDataArray[endTile.getX()][endTile.getY()] = areaId;
boolean excludeStart = false, excludeEnd = false;
Set<WalkPosition> partialPath = findUnthreatenedPathInAreaJPS(startTile,endTile, true, useActiveThreatMap, useThreatMemory, areaId);
if (partialPath.size() > 0) {
if (pathPieces.size() <= level) {
pathPieces.add(partialPath);
} else {
pathPieces.set(level, partialPath);
}
level++;
} else {
if (level == 0) {
excludeEnd = true;
} else {
excludeStart = true;
level--;
}
}
if (excludeStart) {
Main.areaDataArray[startTile.getX()][startTile.getY()] = -1;
} else {
Main.areaDataArray[startTile.getX()][startTile.getY()] = startValue;
}
if (excludeEnd) {
Main.areaDataArray[endTile.getX()][endTile.getY()] = -1;
} else {
Main.areaDataArray[endTile.getX()][endTile.getY()] = endValue;
}
}
//Loading the original values back, after all is done
int i = 0;
for (ChokePoint cp : bwemPath) {
//int[] cpData = new int[bwemPath.size()];
int j = 0;
for (WalkPosition wp : cp.getGeometry()) {
Main.areaDataArray[wp.getX()][wp.getY()] = originalAreaValues.get(i)[j++];
}
i++;
}
}
for (Set<WalkPosition> a : pathPieces) {
summaryPath.addAll(a);
}
return summaryPath;
}One thing it doesn’t do is give a partial path – I might add that later, now it’s just not terribly important. So I finally tried that out…
And of course it ground to a halt. As far as I could tell, it worked, but since I could only move the screen about every 5 seconds, I’m really not confident in my analysis. But definitely, the concept is somewhat sound. Next time I’ll track down what went wrong. Maybe another Code Scene Investigation?
Thanks for reading!
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! (Use the code UNDERMIND for 20% discount)
