First part of this series | Previous | Next | Index
Today’s lesson is: Always test your assumptions. A while ago, I posted a method for getting WalkPositions in a radius. I added a check for bounds outside the map, because I am very smart. Turns out this caused some bugs. A map’s size is measured in TilePositions, which are 32×32 pixels, while WalkPositions are 8×8. I added a check that if the map’s width/8 is greater than the coordinate, then I just set it to that. Except I should actually multiply it by 4, since the TilePositions are bigger. So, allow me a humble correction.
public static Set<WalkPosition> getWalkPositionsInGridRadius(WalkPosition origin, int radius) {
HashSet<WalkPosition> walkPositions = new HashSet<>();
int left = origin.getX()-radius;
int top = origin.getY()-radius;
int right = origin.getX()+radius;
int bottom = origin.getY()+radius;
System.out.println("mw:" + Main.bw.getBWMap().mapWidth() + " mw/4:" + (Main.bw.getBWMap().mapWidth()/4));
System.out.println("bottom:" + bottom);
if (left < 0) {left = 0;}
if (top < 0) {top = 0;}
if (bottom > Main.bw.getBWMap().mapHeight() *4) {bottom = Main.bw.getBWMap().mapHeight() *4;}
if (right > Main.bw.getBWMap().mapWidth() *4) {right = Main.bw.getBWMap().mapWidth() *4;}
int steps = radius*2+1;
//Top row
for (int i=0; i<steps;i++) {
walkPositions.add(new WalkPosition(left+i, top));
}
//Bottom row
System.out.println("bottom row:" + bottom);
for (int i=0; i<steps;i++) {
walkPositions.add(new WalkPosition(left+i, bottom));
System.out.println("b:" + (left+i) + ": " + bottom);
}
//Left column
for (int i=1; i<steps-1;i++) {
walkPositions.add(new WalkPosition(left, top+i));
}
//Right column
for (int i=1; i<steps-1;i++) {
walkPositions.add(new WalkPosition(right, top+i));
}
return walkPositions;
}With that, we can return to the pathfinding, finally.
I read up on the various pathfinding algorithms, and I realized that I did not manage to invent a better one than decades of work by AI researchers did. I’m a fucking disgrace. Bearing this in mind, I get to work, and searched for the one that achieves what I want.
The search I implemented is basically a variation of a breadth-first search. It can find a path, but not necessarily the best. Also, the results can be filtered and optimized to contain fewer points – generally, points on straight lines without forbidden positions between them. The latter point is somewhat separate from pathfinding.
This time, I came up with an actual plan of what I will do – unusual, I know. First, I will implement some known algorithms, and benchmark them. While implementing, I’ll add some domain-specific conditions, I obviously want to use this. Then I’ll figure out some way to filter the results, and optimize the path – I’m not sure at this point, that will be necessary in the long term.
A* is the go-to algorithm here. I want to implement it, even as an exercise. The link contains more than enough information about it, and it’s well-written, so I won’t repeat it. For the heuristics, I’ll just use the Diagonal distance. I’ll skip Dijkstra’s algorithm, and Greedy Best-first implementation, as A* is clearly superior to those here. (My previous algorithm is kind of a version of BFS. Let’s just name it Best Friend Search for future reference, and greater confusion)
So, I need a PriorityQueue with WalkPositions, and their importance. For that, I need a custom Comparator, which returns the lowest importance first. Or actually, since I don’t want to wrap the WalkPositions into another object, is there a Map-like structure, with keys ordered?
Turns out there is, the TreeMap. The only problem is, I can’t have duplicate keys there by default. I can just map a collection to a key, though. Which one to choose? I’ll implement the traditional PriorityQueue first, then consider if there is anything to be gained with changing it.
public class WPInfo{
private long costFromStart;
private WalkPosition walkPosition;
private WPInfo precursor;
(...)
//The comparator
public class WPInfoComparator implements Comparator<WPInfo> {
@Override
public int compare(WPInfo o1, WPInfo o2) {
if (o1.getCostFromStart() > o2.getCostFromStart()) {
return 1;
} else if (o1.getCostFromStart() < o2.getCostFromStart()) {
return -1;
}
return 0;
}One thing to consider is when to stop? Unlike my original method, this one does not contain any accesibility logic (yet). Unfortunately, there is no great answer – you just need to add another heuristic on top of the existing ones. Let’s just skip that for the moment. First time, I used a squared value for a heuristic, despite the guide linked above explicitly advising against it. I’m a badass an actual idiot.
I did achieve moderate success, though.
Since I don’t plan my crabbos to go on sightsheeing rides (or any other unit, but for useless hovercrabs it’s expressly forbidden, go back to work), I examined my code a little better. Turns out, that the PriorityQueue already orders according to the least element, so my Comparator was wrong the first time (I copied the correct version above). I also added other logics, like reconstructing the path, as you can see in the (mostly) correct code:
public static Set<WalkPosition> findUnthreatenedPathAStar(WalkPosition start, WalkPosition end, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory ) {
Set<WPInfo> path = new HashSet<>();
Set<WalkPosition> visited = new HashSet<>();
WPInfo endNode = null;
PriorityQueue<WPInfo> frontier = new PriorityQueue<>(new WPInfoComparator());
WPInfo startinfo = new WPInfo(0, start, null);
path.add(startinfo);
frontier.add(startinfo);
HashMap<WalkPosition, Long> distances = new HashMap<>();
distances.put(start, 0L);
while (!frontier.isEmpty()) {
WPInfo current = frontier.poll();
if (!visited.contains(current.getWalkPosition())) {
visited.add(current.getWalkPosition());
if (current.getWalkPosition().equals(end)) {
endNode = current;
break;
}
}
boolean noThreat = false;
int step = 1;
Set<WalkPosition> neighbors = new HashSet<>();
while (!noThreat) {
neighbors = getWalkPositionsInGridRadius(current.getWalkPosition(), step);
neighbors = neighbors.stream().filter(n -> !isUnderThreat(ground, n, useActiveThreatMap, useThreatMemory))
.collect(Collectors.toSet());
if (neighbors.size() == 0) {
step++;
} else {
noThreat = true;
}
}
for (WalkPosition wp : neighbors) {
if (!visited.contains(wp)) {
int predictedDist = positionToPositionDistanceSq(end.getX(), end.getY(), wp.getX(), wp.getY()); //predicted distance
predictedDist = FastIntSqrt.fastSqrt(predictedDist);
long nDist = current.getCostFromStart() + step;
nDist = FastIntSqrt.fastSqrt(predictedDist);
long totalDist = nDist+predictedDist;
if (totalDist < distances.getOrDefault(wp, Long.MAX_VALUE)) {
distances.put(wp, totalDist);
WPInfo neighborInfo = new WPInfo(totalDist, wp, current);
frontier.add(neighborInfo);
}
}
}
}
HashSet<WalkPosition> finalPath = new HashSet<>();
boolean precc = true;
path.add(endNode);
WPInfo p = endNode;
while (precc) {
if (p.getPrecursor() != null) {
path.add(p);
finalPath.add(p.getWalkPosition());
p = p.getPrecursor();
} else {
precc = false;
}
}
return finalPath;
}This produced a somewhat better path, but still not the one I wanted. (Also, the logic with the steps is not entirely correct – but let’s leave that for now)
The problem this time was that I priced diagonal movements the same cost as sideways ones. This is more easily corrected. I’ll just add a test logic here: diagonal moves cost 2 units.
//(..) instead of adding the step
int nCost = 1;
if (!isAdjacentStrict(current.getWalkPosition(), wp)) {
nCost++;
}
long nDist = current.getCostFromStart() + nCost;
//The helper method
public static boolean isAdjacentStrict(WalkPosition wp1, WalkPosition wp2) {
if (wp1.getX() == wp2.getX() || wp1.getY() == wp2.getY()) {
return true;
}
return false;
}And for the grand finale.
So with a lot of derp and fail, I finally implemented something that resembles A*. Even though the base idea behind the algorithm is not that complex, it took some time. It’s definitely not “production-ready”.
Another hax you might have noticed is the use of fastSqrt. Since I work with integer values (in the mathematical sense, not Java integers), I don’t need exact square roots, which are costly to calculate. I found a great library here, that implements very fast square roots for integers. Google’s Guava IntMath library contains something like this, too – I just used the one from the link. In the vast majority of cases, a good enough result is what I want, not the perfect one, especially if the performance tradeoff is huge.
Also, how fast is this? A quick peek at VisualVM gives us an answer.
In the onFrame() method, I also ran the Best Friend Search, which didn’t even show up in the statistics – and it gave a sorta good path. So yeah, A star is costly, or at least my implementation certainly is.
Earlier, I mentioned that a TreeMap might be another approach – at this stage, I concluded that the gains from that are marginal, so I will continue with some actually usable improvements. I did some research, my use case is not really benefiting from this, so I’ll shelve it. My point was to implement an A* algorithm, which took longer than I expected – but it has been achieved.
In this problem space, I’m limited by CPU resources, and much less constrained by memory – I can store a lot of stuff there, and access it quite quickly. A method that leverages this is (near-optimal) hierarchical pathfinding, or HPA*. Maybe I will take a look some day, but instead exploring algorithms, I’ll prioritize some actual functionality.
Hence, there is some magic called Jump Point Search, or JPS for short. This will be implemented next.
Independently of any pathfinding algorithm, I want to implement the aforementioned result optimization. Again, this is nothing new, other people have worked on this – it’s called path smoothing. For “good enough” algorithms, and ones that don’t order the fields returned (Like the Best Friend Search), it might be even a necessity.
Thanks for reading! If you liked this article, consider subscribing to updates via the box in the right, or RSS.