First part of this series | Previous | Next | Index
Time to implement the very smart things I outlined in the last part. I decomposed it to many parts. First of all, a helper method to check if a WalkPosition is present in one of the threat maps, and if the threat is ground or air.
public static boolean isUnderThreat(boolean ground, WalkPosition wp, boolean useActiveThreatMap, boolean useThreatMemory) {
boolean underThreat = false;
if ((useActiveThreatMap && Main.activeThreatMap.containsKey(wp)) ) {
if (!Main.activeThreatMap.get(wp).getGroundThreats().isEmpty()) {
underThreat = true;
}
}
if ((useThreatMemory && Main.threatMemoryMap.containsKey(wp))) {
if (!Main.threatMemoryMap.get(wp).getGroundThreats().isEmpty()) {
underThreat = true;
}
}
return underThreat;
}This is in turn used by another method which determines the if the path between two points is threatened.
public static boolean hasUnthreatenedPath(boolean ground, WalkPosition start, WalkPosition end, boolean useActiveThreatMap, boolean useThreatMemory) {
Set<WalkPosition> wpPath = getWalkPositionsOnLine(start.toPosition(), end.toPosition());
boolean hasPath = true;
for (WalkPosition wp : wpPath) {
if (isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
hasPath = false;
break;
}
}
return hasPath;
}And for the grand finale, the actual pathfinding, with recursion and stuff!
public static List<WalkPosition> findUnthreatenedPath(boolean ground, WalkPosition start, WalkPosition end, boolean useActiveThreatMap, boolean useThreatMemory) {
ArrayList<WalkPosition> path = new ArrayList<>();
if (!useActiveThreatMap && ! useThreatMemory) {
//Why use this method then?
}
if (hasUnthreatenedPath(ground, start, end, useActiveThreatMap, useThreatMemory)) {
System.out.println("no prob");
path.add(start);
path.add(end);
return path;
} else {
// System.out.println("prob");
path.add(start);
WalkPosition halfway = new WalkPosition((start.getX()+end.getX()/2), (start.getY()+end.getY())/2);
int radius = 1;
WalkPosition target = null;
while (target == null) {
Collection<WalkPosition> searchPoints = getWalkPositionsInGridRadius(halfway, radius);
for (WalkPosition wp : searchPoints) {
if (!isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
target = wp;
break;
}
}
radius++;
}
if (hasUnthreatenedPath(ground, start, target, useActiveThreatMap, useThreatMemory)) {
path.add(target);
} else {
path.addAll(findUnthreatenedPath(ground, start, target, useActiveThreatMap, useThreatMemory));
}
if (hasUnthreatenedPath(ground, target, end, useActiveThreatMap, useThreatMemory)) {
path.add(target);
} else {
path.addAll(findUnthreatenedPath(ground, target, end, useActiveThreatMap, useThreatMemory));
}
}
path.add(end);
return path;
}Upon first running it, I got a StackOverFlowError. Can you spot why? Well, neither could I, because it was caused by another method, surprisingly the getWalkPositionsInGridRadius(). It returned a Set, which is unordered, so I verified stuff in random directions, and never quite found what I wanted. Upon modifying it to return an ArrayList, this problem disappeared. This later turned out to be not the problem at all.
I mocked up some threats, and tried to find a path around them. The first version is promising, but as you can see, not perfect. The red squares are threatened positions, the top left and bottom right green ones of that is the origin, and destination of the pathfinding. All the other green squares are added by the pathfinding.
So, what did we learn?
- Obviously, there is a better path.
- I didn’t check terrain passability.
- Since the order of the generated positions is fixed, the pathfinding will always favor one direction (in this case, the top) .
- I didn’t really add any stopping conditions either.
After some time passed, I dissected the code and the plans and you might have guessed it – one of the problems were caused by a parentheses in a wrong place. But wait, there’s more!
If I placed the start and end points diagonally adjacent, and on the top right corner, I yet again encountered an infinite loop. So there is, err, a lot of room to improve!
Let’s examine the problem: When to give up?
- If either of the positions are surrounded by only threatened positions. The problem is, this could be of any radius, so we have to consider that too. Maybe knowing if there is a path, and actually knowing the path are different problems, with different solutions.
- After some precision, we have to stop. If the positions on the path are all horizontally/vertically adjacent, that’s one for certain.
So I got to work, and noticed that for some edge cases, I still get an infinite loop. I debugged my method, and a pattern popped up:
Start:[14, 8] End:[16, 10]Halfway:15:9 target:[15, 8]
Start:[15, 8] End:[16, 10]Halfway:15:9 target:[14, 8]
The recursion kept bouncing between two points, always founding the other as a halfway point. So I need to have keep in mind the previous path, when calling the method, and verify if the target point is already on it. Makes sense, in retrospect.
This finally didn’t produce infinite loops. I also changed the return type to a Set, as to avoid duplicates.
In our particular case, it returns the following path (Blue squares are the start and end points)
I thought about testing end conditions – I’ve added a boxed in check for the calculations, always testing with the same radius as I do with the halfway points. This might be not optimal, but works well enough, and I can find paths around obstacles with it. Test case below.
I considered just adding a check if the start or end position is threatened, but decided against it, for exactly the edge case in the picture. By choice, the method will return an empty collection if there is no path.
public static Set<WalkPosition> findUnthreatenedPath(boolean ground, WalkPosition start, WalkPosition end,
boolean useActiveThreatMap, boolean useThreatMemory, HashSet<WalkPosition> existingPath) {
if (existingPath == null) {
existingPath = new HashSet<>();
}
if (!useActiveThreatMap && !useThreatMemory) {
//Why use this method then?
}
if (hasUnthreatenedPath(ground, start, end, useActiveThreatMap, useThreatMemory)) {
existingPath.add(start);
existingPath.add(end);
return existingPath;
} else {
existingPath.add(start);
WalkPosition halfway = new WalkPosition((start.getX() + end.getX()) / 2, (start.getY() + end.getY()) / 2);
int radius = 1;
WalkPosition target = null;
boolean startBoxedIn = false;
boolean endBoxedIn = false;
while (target == null && !startBoxedIn && !endBoxedIn) {
startBoxedIn = true;
endBoxedIn = true;
Collection<WalkPosition> startSearchPoints = getWalkPositionsInGridRadius(start, radius);
Collection<WalkPosition> endSearchPoints = getWalkPositionsInGridRadius(start, radius);
for (WalkPosition wp : startSearchPoints) {
if (!isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
startBoxedIn = false;
break;
}
}
for (WalkPosition wp : endSearchPoints) {
if (!isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
endBoxedIn = false;
break;
}
}
Collection<WalkPosition> searchPoints = getWalkPositionsInGridRadius(halfway, radius);
for (WalkPosition wp : searchPoints) {
if (!wp.equals(start) && !wp.equals(end) && !existingPath.contains(wp) && !isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
target = wp;
break;
}
}
radius++;
}
//No path
if (target == null) {
return new HashSet<>();
}
if (hasUnthreatenedPath(ground, start, target, useActiveThreatMap, useThreatMemory)) {
existingPath.add(target);
} else {
if (!existingPath.contains(target)) {
existingPath.add(target);
existingPath.addAll(findUnthreatenedPath(ground, start, target, useActiveThreatMap, useThreatMemory, existingPath));
}
}
if (hasUnthreatenedPath(ground, target, end, useActiveThreatMap, useThreatMemory)) {
existingPath.add(target);
} else {
existingPath.add(end);
existingPath.addAll(findUnthreatenedPath(ground, target, end, useActiveThreatMap, useThreatMemory, existingPath));
}
}
existingPath.add(end);
return existingPath;
}It seems to work well enough, and fast too – after all, we mostly work with primitives. Also, this method won’t be called that often, definitely not in every frame.
There are a lot of points to improve.
- Filtering the results to eliminate redundancies, either during, or after the method. For example, I could add some heuristics to search in a particular direction.
- Handling unwalkable positions, and subsequently, finding a terminating conditions for a walled-in section.
- Unit bounding boxes are usually bigger than a WalkPosition, so I need to take that into consideration, when moving. The WalkPosition’s coordinates are of it’s top left corner. I need to take care to ignore “tunnel” type paths for larger units. I’m not sure if this will be implemented here, or with the unit movement.
At this point I decided to actually research some of the pathfinding algorithms. Here is a great collection, and also Jay Scott’s blog is a great place for getting some insights (Jay writes about a lot of stuff though). Also, navigation using potential fields.
While I’m doing that, let’s just implement the easy stuff (best programming practice!). Check the walkability when evaluating the positions:
for (WalkPosition wp : searchPoints) {
if (!wp.equals(start) && !wp.equals(end) && !existingPath.contains(wp) && !isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
if (ground) {
if (Main.bw.getBWMap().isWalkable(wp)) {
target = wp;
break;
}
} else {
target = wp;
break;
}
}
}Actually, the boxed in check can be easily extended to check this too. Last large code block, I promise. (I’m also prone to lying)
public static Set<WalkPosition> findUnthreatenedPath(boolean ground, WalkPosition start, WalkPosition end,
boolean useActiveThreatMap, boolean useThreatMemory, HashSet<WalkPosition> existingPath) {
if (existingPath == null) {
existingPath = new HashSet<>();
}
if (!useActiveThreatMap && !useThreatMemory) {
//Why use this method then?
}
if (hasUnthreatenedPath(ground, start, end, useActiveThreatMap, useThreatMemory)) {
existingPath.add(start);
existingPath.add(end);
return existingPath;
} else {
existingPath.add(start);
WalkPosition halfway = new WalkPosition((start.getX() + end.getX()) / 2, (start.getY() + end.getY()) / 2);
int radius = 1;
WalkPosition target = null;
boolean startBoxedIn = false;
boolean endBoxedIn = false;
boolean unWalkableBox = false;
while (target == null && !startBoxedIn && !endBoxedIn && !unWalkableBox) {
startBoxedIn = true;
endBoxedIn = true;
if (ground) {
unWalkableBox = true;
}
Collection<WalkPosition> startSearchPoints = getWalkPositionsInGridRadius(start, radius);
Collection<WalkPosition> endSearchPoints = getWalkPositionsInGridRadius(start, radius);
for (WalkPosition wp : startSearchPoints) {
if (ground && Main.bw.getBWMap().isWalkable(wp)) {
unWalkableBox = false;
}
if (!isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
startBoxedIn = false;
break;
}
}
for (WalkPosition wp : endSearchPoints) {
if (ground && Main.bw.getBWMap().isWalkable(wp)) {
unWalkableBox = false;
}
if (!isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
endBoxedIn = false;
break;
}
}
Collection<WalkPosition> searchPoints = getWalkPositionsInGridRadius(halfway, radius);
for (WalkPosition wp : searchPoints) {
if (!wp.equals(start) && !wp.equals(end) && !existingPath.contains(wp) && !isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
if (ground) {
if (Main.bw.getBWMap().isWalkable(wp)) {
unWalkableBox = false;
target = wp;
break;
}
} else {
target = wp;
break;
}
}
}
radius++;
}
//No path
if (target == null) {
System.out.println("no path" + "unwalkablebox:" + unWalkableBox);
return new HashSet<>();
}
if (hasUnthreatenedPath(ground, start, target, useActiveThreatMap, useThreatMemory)) {
existingPath.add(target);
} else {
if (!existingPath.contains(target)) {
existingPath.add(target);
existingPath.addAll(findUnthreatenedPath(ground, start, target, useActiveThreatMap, useThreatMemory, existingPath));
}
}
if (hasUnthreatenedPath(ground, target, end, useActiveThreatMap, useThreatMemory)) {
existingPath.add(target);
} else {
existingPath.add(end);
existingPath.addAll(findUnthreatenedPath(ground, target, end, useActiveThreatMap, useThreatMemory, existingPath));
}
}
existingPath.add(end);
return existingPath;
}I began testing this, and found something very curious.
So, according to BWAPI, minerals are walkable. Oops.
I know the suspense is killing you – how will I get out of this? Will I find the answer? Find out in the next episode! Pro tip: A great way of finding out the end of this adventure is by subsciribing to the mailing list!