First part of this series | Previous | Next | Index
What a coincidence in naming. I plan to finish my “derping around with already solved problems while not improving my bot in any meaningful way” adventure with this post.
There are some important things to know about JPS. It is basically a variant of A*, but optimized for uniform-cost grids. This fits our use case very well, as units don’t have different movement costs for different terrain in Brood War. Here is an awesome explanation. And here.
So, let’s implement the magic. In large part, JPS is about eliminating “uninteresting” nodes from the path search. There is a thing called Rectangular Symmetry Reduction dividing the map to some rectangles (or some large units), and if the start and end points are in different ones, then the past must contain the “pass” between them. Brood War has a concept called regions, which is basically what we need here. Modern maps usually have regions divided by ramps, and if the goal is in a different region, a ground unit has to pass through that. Logically, if the ramp is threatened, there is no path to the destination. I mentioned previously, that I feel that the optimal path, and the existence of any path at all seem to be different problems to me.
An easier visualization is if you are searching for a path in a building between two rooms, you must go through the door.
RSR is not JPS, though, so this is just a thought – let’s worry about this later (Note to self: Use bwem). JPS is still a variant of A*, we still need the heuristic, and the open/closed lists, or however you want to call them.
A key point of JPS is to examine straight directions first, then diagonal. I need to store the field-direction pairs, whether they are diagonal or straight, and some other heuristic, to order them. One idea is to have two collections, and only consider diagonal ones if the collection of straight ones is empty. The another is to somehow factor in the diagonality into the importance of the fields, and order them accordingly. Let’s do the simpler one, and have two collections. I might revisit this, if i feel this needs more speedz.
public class JPSInfo {
private Cartography.Direction direction;
private WalkPosition walkPosition;
private int importance;
//+getters, setters, all the jazz, also:
public class JPSInfoComparator implements Comparator<JPSInfo> {
@Override
public int compare(JPSInfo o1, JPSInfo o2) {
if (o1.getImportance() > o2.getImportance()) {
return 1;
} else if (o1.getImportance() < o2.getImportance()) {
return -1;
}
return 0;
}I decided to write a helper method (and a convenience method to the helper method, because I’m all about comfort) to get the neighbors in a set direction- the getWalkPositionsInGridRadius() is useful, but usually I want to just get the subset of those.
//With varargs, and stuff!
public static Set<WalkPosition> getNeighborsInDirection(WalkPosition origin, Collection<Direction> dirs) {
return getNeighborsInDirection(origin, dirs.toArray(new Direction[dirs.size()]));
}
public static Set<WalkPosition> getNeighborsInDirection(WalkPosition origin, Direction ... dirs) {
HashSet<WalkPosition> neighbors = new HashSet<>();
for (Direction dir : dirs) {
if (dir.equals(Direction.N)) {
neighbors.add(new WalkPosition(origin.getX(), origin.getY()-1));
}
if (dir.equals(Direction.S)) {
neighbors.add(new WalkPosition(origin.getX(), origin.getY()+1));
}
if (dir.equals(Direction.W)) {
neighbors.add(new WalkPosition(origin.getX()-1, origin.getY()));
}
if (dir.equals(Direction.E)) {
neighbors.add(new WalkPosition(origin.getX()+1, origin.getY()));
}
if (dir.equals(Direction.NW)) {
neighbors.add(new WalkPosition(origin.getX()-1, origin.getY()-1));
}
if (dir.equals(Direction.NE)) {
neighbors.add(new WalkPosition(origin.getX()+1, origin.getY()-1));
}
if (dir.equals(Direction.SW)) {
neighbors.add(new WalkPosition(origin.getX()-1, origin.getY()+1));
}
if (dir.equals(Direction.SE)) {
neighbors.add(new WalkPosition(origin.getX()+1, origin.getY()+1));
}
}
return neighbors;
}
So, I started first with something like this:
PriorityQueue<JPSInfo> straight = new PriorityQueue<>(new JPSInfoComparator());
PriorityQueue<JPSInfo> diag = new PriorityQueue<>(new JPSInfoComparator());
WalkPosition wp = getNeighborInDirection(start, Direction.N);
if (!isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
straight.add(new JPSInfo(Direction.N, wp, calcJPSImportance(start, end, wp)));
}
wp = getNeighborInDirection(start, Direction.S);
if (!isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
straight.add(new JPSInfo(Direction.S, wp, calcJPSImportance(start, end, wp)));
}
wp = getNeighborInDirection(start, Direction.W);
if (!isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
straight.add(new JPSInfo(Direction.W, wp, calcJPSImportance(start, end, wp)));
}
wp = getNeighborInDirection(start, Direction.E);
if (!isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
straight.add(new JPSInfo(Direction.E, wp, calcJPSImportance(start, end, wp)));
}Clearly, this will be too much code in the long run. I just need to create JPSInfo objects, so let’s have a method for that. I also decided to have the importance calculation (the heuristic, basically) in a separate method.
public static Set<JPSInfo> getJPSInfosInDirection(WalkPosition wp, WalkPosition start, WalkPosition end, Direction... dirs) {
HashSet<JPSInfo> jpsInfos = new HashSet<>();
for (Direction d : dirs) {
jpsInfos.add(new JPSInfo(d,
getNeighborInDirection(wp, d),
calcJPSImportance(start, end, wp)));
}
return jpsInfos;
}
//Heuristic for calculation importance of jump points
public static int calcJPSImportance(WalkPosition start, WalkPosition end, WalkPosition wp) {
int startImp = positionToPositionDistanceSq(start.getX(), start.getY(), wp.getX(), wp.getY());
int endImp = positionToPositionDistanceSq(end.getX(), end.getY(), wp.getX(), wp.getY());
return FastIntSqrt.fastSqrt(startImp) + FastIntSqrt.fastSqrt(endImp);
}For the starting points, I kind of need this filtering though – I don’t want to put the threatened/impassable logic in the JPS generator method. Okay, let’s have yet another method. The reason for adding so many is twofold. First, it helps me think, and subsequently, explain why I did things. Second is of course, that it will be convenient later on. Never underestimate the joy of convenience methods!
//Pure fun!
public static Set<JPSInfo> getJPSInfosInDirection(WalkPosition wp, WalkPosition start, WalkPosition end, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory, Direction... dirs) {
HashSet<JPSInfo> jpsInfos = new HashSet<>();
for (Direction d : dirs) {
WalkPosition newWp = getNeighborInDirection(wp, d);
if (!isUnderThreat(ground, newWp, useActiveThreatMap, useThreatMemory)) {
jpsInfos.add(new JPSInfo(d,
newWp,
calcJPSImportance(start, end, wp)));
}
}
return jpsInfos;
}So the large block above becomes this:
straight.addAll(getJPSInfosInDirection(start, start, end, ground, useActiveThreatMap, useThreatMemory, Direction.E, Direction.W, Direction.S, Direction.N));
//Consequently
diag.addAll(getJPSInfosInDirection(start, start, end, ground, useActiveThreatMap, useThreatMemory, Direction.NE, Direction.NW, Direction.SE, Direction.SW));
//write ALL the convenience methods!
public static Set<JPSInfo> getJPSInfosInDirection(WalkPosition wp, WalkPosition start, WalkPosition end, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory, Collection<Direction> dirs) {
return getJPSInfosInDirection(wp, start, end, ground, useActiveThreatMap, useActiveThreatMap, dirs.toArray(new Direction[dirs.size()]));
}
public static Set<JPSInfo> getJPSInfosInDirection(WalkPosition wp, WalkPosition start, WalkPosition end, Collection<Direction> dirs) {
return getJPSInfosInDirection(wp, start, end, dirs.toArray(new Direction[dirs.size()]));
}It’s a little convoluted, but these methods are basically the same. I just love writing the same thing but slightly different!
I added a map for straight path checking, based on the direction, it returns the left and right neighbors. I can just add this to the JPS method loop, but it’s not terribly interesting. I also use a static initializer here – the Cartography class is staticly used anyway. Most of my stuff is just static, as this use case – one BW game – seems like a good fit for that. There are very marginal performance benefits to this, but mostly, it’s just how I like it.
public static HashMap<Direction, HashSet<Direction>> straightCheckPos;
static {
straightCheckPos = new HashMap<>();
HashSet<Direction> dirs = new HashSet<>();
dirs.add(Direction.W);
dirs.add(Direction.E);
straightCheckPos.put(Direction.N, dirs);
dirs = new HashSet<>();
dirs.add(Direction.W);
dirs.add(Direction.E);
straightCheckPos.put(Direction.S, dirs);
dirs = new HashSet<>();
dirs.add(Direction.S);
dirs.add(Direction.N);
straightCheckPos.put(Direction.W, dirs);
dirs = new HashSet<>();
dirs.add(Direction.S);
dirs.add(Direction.N);
straightCheckPos.put(Direction.E, dirs);
}Onward to the actual searching part. As per the article above, depending on the direction, I only need to evaluate certain neighbors. For straight paths, the logic is the following: If there is an obstacle right ahead, stop the search. If there is an obstacle to the left or right, stop the search, and add a jump point with the diagonal direction pointing that way. The relevant parts for the straight path processing looks like this:
public static Set<WalkPosition> findUnthreatenedPathJPS(WalkPosition start, WalkPosition end, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory) {
boolean foundPath = false;
PriorityQueue<JPSInfo> straight = new PriorityQueue<>(new JPSInfoComparator());
PriorityQueue<JPSInfo> diag = new PriorityQueue<>(new JPSInfoComparator());
straight.addAll(getJPSInfosInDirection(start, start, end, ground, useActiveThreatMap, useThreatMemory, Direction.E, Direction.W, Direction.S, Direction.N));
diag.addAll(getJPSInfosInDirection(start, start, end, ground, useActiveThreatMap, useThreatMemory, Direction.NE, Direction.NW, Direction.SE, Direction.SW));
while (!straight.isEmpty() && !foundPath) {
JPSInfo jumpPoint = straight.poll();
Direction dir = jumpPoint.getDirection();
//Straight path processing
boolean straightPathProcessed = false;
while (!straightPathProcessed) {
WalkPosition ahead = getNeighborInDirection(jumpPoint.getWalkPosition(), jumpPoint.getDirection());
//Terminate search if the next tile in the direction is under threat/impassable
if (isUnderThreat(ground, ahead, useActiveThreatMap, useThreatMemory)) {
straightPathProcessed = true;
}
if (ahead.equals(end)) {
straightPathProcessed = true;
foundPath = true;
}
//Check neighbors to the left and right
HashSet<Direction> checkDirs = straightCheckPos.get(jumpPoint.getDirection());
for (Direction checkDir : checkDirs) {
WalkPosition wp = getNeighborInDirection(jumpPoint.getWalkPosition(), checkDir);
if (isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory )) {
straightPathProcessed = true;
straight.addAll(getJPSInfosInDirection(wp, start,end, ground, useActiveThreatMap, useThreatMemory, getJPDirections(jumpPoint.getDirection(), checkDir)));
}
}
}You might have noticed that this article is a little more code-heavy this time.
For the diagonal path, I just need to add the proper directions to the getJPDirections() method. I’ll spare you the details. Code for the diagonal cases:
if (!diag.isEmpty()) {
jumpPoint = diag.poll();
if (jumpPoint.getWalkPosition() == end) {
foundPath = true;
} else {
WalkPosition diagAhead = getNeighborInDirection(jumpPoint.getWalkPosition(), jumpPoint.getDirection());
//If the next tile in the diagonal direction isn't blocked, let's add that too
if (!isUnderThreat(ground, diagAhead, useActiveThreatMap, useThreatMemory)) {
diag.addAll(getJPSInfosInDirection(diagAhead, start, end, jumpPoint.getDirection()));
}
//Add the 2 straight jump points in any case
for (Direction dir : diagForwardPos.get(jumpPoint.getDirection())) {
straight.add(new JPSInfo(dir, jumpPoint.getWalkPosition(), calcJPSImportance(start, end, jumpPoint.getWalkPosition())));
}
//Check the two remaining straight directions
for (Direction checkDir : diagCheckPos.get(jumpPoint.getDirection())) {
WalkPosition wp = getNeighborInDirection(jumpPoint.getWalkPosition(), checkDir);
if (isUnderThreat(ground, wp, useActiveThreatMap, useThreatMemory)) {
straight.addAll(getJPSInfosInDirection(wp, start, end, getJPDirections(jumpPoint.getDirection(), checkDir)));
}
}
}
}That’s the core of the algorithm, but it does not actually give us the path, just terminates if it finds it. Also, it checks positions outside of the map. Path reconstruction is similar to A*. We add all the jump points to a collection, but each of them has a parent. If we find a path, then we start from the end, and go through all of the parents until we find the start position.
Will this work? I have no clue. Find out next on CSI: Code Scene Investigation! (Spoilers: Of course it doesn’t)
(Also consider subscribing to the mailing list, on the right, or the RSS feeds).