Background - I am currently attempting to implement the A* algorithm into my game. I have done this previously in a standard grid style game and managed to get it working but for some reason, I can only get partial success here.I am trying to implement this into an isometric 2D game. I have already translated everything from cartesian to grid coordinates, so its working with a grid system.
Behavior - Initially, it works. You can move ~6-8 tiles away at a time with no problems. Small movements one after the other work. However, any more than that and everything freezes. I have identified it is definitely the path finding that is causing the crash. I presume the algorithm gets it wrong for whatever reason and veers off track determining the correct path to be too costly. This is strange as I'm using only 4 adjacents and the cost to calculate should be really small and shouldn't cause a freeze. It's also not a minor freeze, the freeze is >30 seconds (i'm yet to wait long enough to see if it actually DOES finish because I assume its going in the wrong direction and never will)
Things to consider - Due to the nature of this game being isometric and the translation from cartesian to grid and vice versa, everything is in floats rather than integers. However, when checking where the character is after movement, for example, it is always in an appropriate integer grid reference (so there is no "im at 1.9, check at 2.9" behavior. Its always int due to the rounding I do. Also, the nodes are not defined beforehand. The nodes are defined "on the fly" when children are created from the current node. This is because this system is unrelated to the game, I just care about a list of coordinates a character has to get to which is essentially returned in the desired path.
Here is the A* algorithm:
public class PathFinder {
private Node nodeStart;
private Node nodeGoal;
private float cost = 10f;
Set<Node> open = new HashSet<>();
Set<Node> closed = new HashSet<>();
public PathFinder(Node start, Node goal){
this.nodeStart = start;
this.nodeGoal = goal;
open.add(nodeStart);
}
public List<Node> findPath(){
while (!open.isEmpty()){
Node currentNode = open.stream().min(Comparator.comparing(Node::getF)).get();
open.remove(currentNode);
closed.add(currentNode);
if(currentNode.equals(nodeGoal)){
return reversePath(currentNode);
}
else{
for(Node child : getAdjacents(currentNode)){
if(!child.isBlock() && !closed.contains(child)) {
child.setNodeData(currentNode, cost);
open.add(child);
}
else{
boolean changed = child.checkBetterPath(currentNode, cost);
if (changed) {
// Remove and Add the changed node, so that the PriorityQueue can sort again its
// contents with the modified "finalCost" value of the modified node
open.remove(child);
open.add(child);
}
}
};
}
}
return new ArrayList<>();
}
private List<Node> getAdjacents(Node currentNode){
ArrayList<Node> children = new ArrayList<>();
children.add(new Node(currentNode.getX()+1, currentNode.getY(), currentNode, nodeGoal));
children.add(new Node(currentNode.getX()-1, currentNode.getY(), currentNode, nodeGoal));
children.add(new Node(currentNode.getX(), currentNode.getY() - 1, currentNode, nodeGoal));
children.add(new Node(currentNode.getX(), currentNode.getY() + 1, currentNode, nodeGoal));
return children;
}
public List<Node> reversePath(Node goal){
List<Node> finalPath = new ArrayList<>();
Node tmp;
Node current;
current = goal;
while(current.getParent() != null){
finalPath.add(0, current);
current = current.getParent();
}
return finalPath;
}}
And here is my node class:
public class Node {
private boolean isBlock;
private Node parent;
private float x;
private float y;
private float g;
private float f;
private float h;
Node finalNode;
public Node(float x, float y){
this.x = x;
this.y = y;
}
public Node(float x, float y, Node parent, Node finalNode){
this.x = x;
this.y = y;
this.parent = parent;
this.finalNode = finalNode;
calculateHeuristic(finalNode);
}
public void calculateHeuristic(Node finalNode) {
this.h = Math.abs(finalNode.getX() - getX()) + Math.abs(finalNode.getY() - getY());
}
public void setNodeData(Node currentNode, float cost) {
float gCost = currentNode.getG() + cost;
setParent(currentNode);
setG(gCost);
calculateFinalCost();
}
public boolean checkBetterPath(Node currentNode, float cost) {
float gCost = currentNode.getG() + cost;
if (gCost < getG()) {
setNodeData(currentNode, cost);
return true;
}
return false;
}
private void calculateFinalCost() {
float finalCost = getG() + getH();
setF(finalCost);
}
public float getX() {
return x;
}
public float getY() {
return y;
}
public Node getParent() {
return parent;
}
public boolean isBlock() {
return isBlock;
}
public void setBlock(boolean block) {
isBlock = block;
}
public void setParent(Node parent) {
this.parent = parent;
}
public void setX(float x) {
this.x = x;
}
public void setY(float y) {
this.y = y;
}
public float getG() {
return g;
}
public void setG(float g) {
this.g = g;
}
public float getF() {
return f;
}
public void setF(float f) {
this.f = f;
}
public float getH() {
return h;
}
public void setH(float h) {
this.h = h;
}
@Override
public boolean equals(Object arg0) {
Node other = (Node) arg0;
return this.getX() == other.getX() && this.getY() == other.getY();
}
@Override
public String toString() {
return "Node [row=" + x + ", col=" + y + "]";
}}
Here is some test data that causes the crash:
public class Main {
public static void main(String[] args) {
PathFinder pathFinder = new PathFinder(new Node(1,1), new Node(14,1));
List<Node> path = pathFinder.findPath();
System.out.println(path);
}}
Solution- So the solution by mchl_bld is correct although I opted for a custom remove function which solved part of the issue. I could click further than I could before but for larger numbers like 100+ for example it was still crashing. After some debugging here is the culprit:
private float cost = 10f;
I am moving 1 tile at a time, not 10. This was putting unnecessary importance on the cost of each tile away from the original and diluting the importance of the heuristic value. Changing it to:
private float cost = 1f;
Solved the long wait time issue.
There are two Flaws within your solution.
This isn't directly related to your problem but can lead to nasty side effects.
As stated here floats shouldn't be compared with == due to precision issues.
HashSets in Java use the HashCode method of objects to compare to values. As you didn't override it for Node it gives two different values even if your equals() method considers them equal:
public static void main(String[] args) {
final var a = new Node(1.0f, 1.0f);
final var b = new Node(1.0f, 1.0f);
System.out.println(a.equals(b));
// true
System.out.println(a.hashCode());
// 918221580
System.out.println(b.hashCode());
// 2055281021
}
So just implement hashCode() properly for Node to get rid of the problem:
@Override
public int hashCode() {
return Objects.hash(this.getX(), this.getY());
}