Overview:
The AStar class integrates the AStar pathfinding algorithm into my pathfinding algorithm visualizer.
Design choices:
The AStar algorithm is mostly unmodified except where it needs to be slowed to be properly visualized and where it must update the map.
Takeaways:
Slowing the algorithm proved harder in this project than I first though and I eventually had to use threading to solve the problem.
package Pathfinding;
import java.awt.*;
import java.util.ArrayList;
import java.util.Stack;
/**
* @author Ian Sodersjerna
* @date 6/30/2020
*/
public class AStar extends Algorithm {
private Node current;
private final Color openColor = Color.green;
private final Color closedColor = Color.red;
/**
* Constructor for algorithm
*
* @param panel panel to be used by algorithm
*/
public AStar(mapPanel panel) {
super(panel); // Pass panel to super constructor
}
/**
* Generate and print path to panel
*/
public void generatePath() throws IllegalArgumentException {
Node[][] nodeMap = new Node[this.size.x][this.size.y];
ArrayList<Node> open = new ArrayList<>(); // The set of nodes to be evaluated
ArrayList<Node> closed = new ArrayList<>(); // The set of nodes already evaluated
this.current = null; // The node that will be evaluated
ArrayList<Node> neighbors = new ArrayList<>(); // The set of neighboring nodes to the current node
// Create a 2-d Node array and set walls
for (int i = 0; i < size.x; i++) {
for (int j = 0; j < size.y; j++) {
if (map[i][j] == 1) {
nodeMap[i][j] = new Node(new Point(i, j), end, true);
} else {
nodeMap[i][j] = new Node(new Point(i, j), end, false);
}
}
}
nodeMap[start.x][start.y].gCost = 0;
open.add(nodeMap[start.x][start.y]);
while (!open.isEmpty()) {
// Find the node in the open set with the lowest f cost.
this.current = open.get(0);
for (Node n : open) {
if (n.getFCost() < this.current.getFCost() || n.getFCost() == this.current.getFCost()) {
if (n.hCost < this.current.hCost) {
this.current = n;
}
}
}
// Remove selected node from open set and add it to the closed set checking if it is the end node and clearing neighbors
open.remove(this.current);
closed.add(this.current);
this.panel.setPosition(current.position, closedColor);
if (this.current.end) {
break;
}
neighbors.clear();
// Populate neighbor set with neighbors
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
// Insure the current node is not added
if (i != 0 || j != 0) {
// If the neighbor is on the board
if ((this.current.position.x + i) >= 0 && (this.current.position.y + j) >= 0 && (this.current.position.x + i) < this.size.x && (this.current.position.y + j) < this.size.y) {
// If the neighbor is inaccessible due to neighboring walls
if ((i != 0 && j != 0) && (nodeMap[this.current.position.x + i][this.current.position.y].wall && nodeMap[this.current.position.x][this.current.position.y + j].wall)) {
continue;
}
neighbors.add(nodeMap[this.current.position.x + i][this.current.position.y + j]);
}
}
}
}
//for each neighbor calculate F, G, and H costs and assign parent
for (Node n : neighbors) {
if (n.wall || closed.contains(n)) {
continue;
}
int newCostToNeighbour = this.current.gCost + distanceBetween(n.position, this.current.position);
if (!open.contains(n) || newCostToNeighbour < n.gCost) {
n.gCost = newCostToNeighbour;
n.setHCost(this.end);
n.parent = this.current;
if (!open.contains(n)) {
open.add(n);
this.panel.setPosition(n.position, openColor);
}
}
}
try {
if (mapPanel.completed) {
Thread.sleep(0);
}else{
Thread.sleep(1);
}
} catch (InterruptedException e) {
GUI.panelTread.interrupt();
return;
}
}
if (current == null || !current.end) {
GUI.panelTread.interrupt();
this.panel.setPosition(this.start, mapPanel.START_COLOR);
this.panel.setPosition(this.end, mapPanel.END_COLOR);
this.panel.paintComponent(this.panel.getGraphics());
throw new IllegalArgumentException("course cannot be solved.");
}
this.paintPath();
}
/**
* Method to paint the panel the path generated using the colors defined in MapPanel.
*
* @apiNote evaluate if stack is really optimal here, because it forces mapPanel to have two setPosition methods.
*/
public void paintPath() {
GUI.panelTread.interrupt();
Stack<Point> path = new Stack<>();
while (this.current.parent != null) {
path.push(current.position);
this.current = this.current.parent;
}
while (!path.empty()) {
this.panel.setPosition(path.pop(), Color.blue);
}
this.panel.setPosition(this.start, mapPanel.START_COLOR);
this.panel.setPosition(this.end, mapPanel.END_COLOR);
this.panel.paintComponent(this.panel.getGraphics());
}
static class Node {
private final Point position; //location of the Node on a 2d plane.
private final boolean wall; //boolean value to determine if a wall.
private boolean end = false; //boolean value to determine if the ending node
private int gCost; //distance from starting node
private int hCost; //distance from end node
private Node parent = null; // parent of the node.
/**
* Constructor for a node with distance to ending node.
*
* @param position Location the node is located on a 2-d plane.
* @param target Location of the target to determine hcost(distance from the end node)
*/
public Node(Point position, Point target, boolean wall) {
this.position = position;
hCost = AStar.distanceBetween(position, target);
if (hCost == 0) {
end = true;
}
this.wall = wall;
}
/**
* Calculates the f-cost from the h and g cost.
*
* @return The F-cost which is the h-cost + the g-cost.
*/
public int getFCost() {
return hCost + gCost;
}
/**
* Sets the h-cost by getting distance between it and the target.
*
* @param target Point representing the target.
*/
public void setHCost(Point target) {
this.hCost = distanceBetween(position, target);
}
}
}