This is a 4 part series on how the path finding works in Battlefleet. Please ask in the comments if something doesn’t make sense. Here are parts 1, 2, 3, 4.
So my code has two static functions, one called findPath, and one called reconstructPath.
public class PathFinder {
public PathFinder() {
}
public static ArrayList<MoveOrder> findPath(ArrayList<ShipBase> ships, int shipId, float[] dest) {
}
public static ArrayList<MoveOrder> reconstructPath(ArrayList<Node> list) {
}
}
You might be wondering what the classes MoveOrder, ShipBase and Node are. ShipBase is actually a very big class, with loads of stuff going on, however for this all you need to know is that it has an X, a Y, a Height, a Width and a rotation. MoveOrder, amongst other things, is basically just a X, Y coordinate. And Node we covered in part 2.
Lets look at findPath first, as it’s the interesting one. The first thing you need to add is the list of nodes. That is, the start, the end and one for each of the four corners of each ship.
ArrayList<Node> fullList = new ArrayList<Node>();
Node start = new Node(ships.get(shipId).getCoord());
start.setParentId(-1); // -1 to means "has no parent"
start.setG(0);
start.setF(Geometry.getDistAtoB(start.getCoord(), dest));
start.setOpen();
fullList.add(start);
fullList.add(new Node(dest));
for(int i = 0; i < ships.size(); ++i) {
if(i != shipId) {
float [] boundBox = Geometry.getRectFromDimensions(
ships.get(i).getCoord(),
ships.get(i).getHeight() + 2 * ships.get(shipId).getHeight(),
ships.get(i).getWidth() + 2 * ships.get(shipId).getWidth(),
ships.get(i).getRotation()
);
fullList.add(new Node(new float [] {boundBox[0], boundBox[1]}));
fullList.add(new Node(new float [] {boundBox[2], boundBox[3]}));
fullList.add(new Node(new float [] {boundBox[4], boundBox[5]}));
fullList.add(new Node(new float [] {boundBox[6], boundBox[7]}));
}
}
The function Geometry.getRectFromDimensions pretty much does what it says, it works out the four corners of a rectangle from a centre point, a height, a width and a rotation. Next you want to go through and do the actual A star algorithm.
while(1) {
int lowestFIndex = -1;
int x = 0;
while(lowestFIndex == -1) {
if(x >= fullList.size()) {
return null;
} else if(fullList.get(x).isOpen()) {
lowestFIndex = x;
}
x++;
}
for(int i = 0; i < fullList.size(); ++i) {
if(fullList.get(i).isOpen() &&
fullList.get(i).getF() < fullList.get(lowestFIndex).getF()) {
lowestFIndex = i;
}
}
if(fullList.get(lowestFIndex).isPoint(dest)) {
return reconstructPath(fullList);
}
fullList.get(lowestFIndex).setClosed();
for(int i = 0; i < fullList.size(); ++i) {
boolean hasPathToNode = true;
if(i != lowestFIndex) {
for(int j = 0; j < ships.size(); ++j) {
if(j != shipId &&
hasPathToNode &&
Geometry.lineIntersectsRect(
fullList.get(i).getCoord(),
fullList.get(lowestFIndex).getCoord(),
ships.get(j).getCoord(),
ships.get(j).getHeight() + ships.get(shipId).getHeight(),
ships.get(j).getWidth() + ships.get(shipId).getWidth(),
ships.get(j).getRotation())) {
hasPathToNode = false;
}
}
if(hasPathToNode) {
float tempG = fullList.get(lowestFIndex).getG() + Geometry.getDistAtoB(fullList.get(i).getCoord(), fullList.get(lowestFIndex).getCoord());
float tempF = tempG + Geometry.getDistAtoB(fullList.get(i).getCoord(), dest);
if(fullList.get(i).isClosed() && tempF >= fullList.get(i).getF()) {
continue;
}
if(!fullList.get(i).isOpen() || tempF < fullList.get(i).getF()) {
fullList.get(i).setParentId(lowestFIndex);
fullList.get(i).setG(tempG);
fullList.get(i).setF(tempF);
if(!fullList.get(i).isOpen()) {
fullList.get(i).setOpen();
}
}
}
}
}
return null;
}
Geometry.lineIntersectsRect, again, does what you might think: tests to see if a line intersects a rectangle. To do this, it just treats the rectangle as four separate lines, and tests each to see if the line passes through them. I can post the code if anyone wants, just let me know in the comments. You might have noticed that H isn’t mentioned anywhere in my code. That’s because, as I said in part 3, I am just using the as-the-crow-files distance, which is given by the function Geometry.getDistAtoB. Comparatively, reconstructPath is a pretty simple function.
ArrayList<MoveOrder> path = new ArrayList<MoveOrder>();
int index = 1; // End node is always index 1
while(list.get(index).getParentId() != -1) {
path.add(0, list.get(index).convertToMoveOrder());
index = list.get(index).getParentId();
}
return path;
It just runs through from the end, until it gets to the start.
So there you have it, hopefully you can make sense of all this. If you notice any errors, please let me know, so that other people don’t have to struggle with the same problems. Have fun not crashing into stuff.
