I have implemented an A* algorithm into my game and I am having a few issues with it.
At first I was using calculate method that would take the start position and end position, which would jump into a while loop while searching, locking up my game for about 5-6 seconds. I then split it into 2 methods, one that sets the start and end positions, sets up the open and closed list. Then an update method that runs in the entity update method that only runs when a boolean is set, such as
boolean needsPath;
This works about 75% of the time, other times it completely deadlocks my game and crashes it, however when I press the key to initialize the pathfinder and move my entity, it takes about 5 seconds to actually move.
It is exactly 47 tiles to my destination, this means it checks 188 nodes as it checks in 4 compass directions, N, E, W, S.
Here is my pathfinder:
public Path calculatePath(int startX, int startY, int destX, int destY) {
map.setStart(startX, startY);
map.setDestination(destX, destY);
/* Check if the destination is passable, if not, just return null */
if (!(map.getNode(destX, destY)).isPassable) {
return null;
}
/* Set the distance from start at 0, we have not moved yet */
map.getStartNode().setDistanceFromStart(0);
/*
* We need to clear our arrays before calculating a new path, if we
* don't it will be all fucked up
*/
open.clear();
closed.clear();
/* Add our start node to the open list */
open.add(map.getStartNode());
/*
* Basically while our open array has objects, we obviously have not
* found our path to destination yet
*/
while (open.size != 0) {
/* Get the first node in our open list */
Node current = open.first();
/*
* If the current node position is the same as the dest position, we
* must be done calculating the path
*/
if ((current.getPosition().x == map.getDestPos().x)
&& (current.getPosition().y == map.getDestPos().y)) {
return recreate(current);
}
/*
* Remove the current node from the open list, it has already been
* searched
*/
open.removeValue(current, true);
/* Add it to the closed list */
closed.add(current);
for (Node neighbour : current.getNeighbours()) {
boolean neighbourShorter;
/*
* If this node is in the closed list we have already searched
* it, move on
*/
if (closed.contains(neighbour, true))
continue;
/*
* If the node is not passable, E.g a wall, just move on and
* keep looking
*/
if (!neighbour.isPassable) {
continue;
} else {
/* calculate the neighbours distance from the start point */
float neighbourDistanceFromStart = (current
.getDistanceFromStart() + map.compareNodeDistance(
current, neighbour));
/* Add our neighbour to the open list if not already there */
if (!open.contains(neighbour, true)) {
open.add(neighbour);
open.sort();
neighbourShorter = true;
/*
* if the neighbour is closer to the start, path is
* still shorter
*/
} else if (neighbourDistanceFromStart < current
.getDistanceFromStart()) {
neighbourShorter = true;
} else {
neighbourShorter = false;
}
/* If the neighour is the shortest path, use that node */
if (neighbourShorter) {
/*
* Set the neighbours previous node to the one we are
* currently on
*/
neighbour.setPreviousNode(current);
neighbour
.setDistanceFromStart(neighbour.distanceFromStart);
neighbour.setHeuristicalDistanceToDest(heuristic
.getEstimatedDistanceToDest(
(int) neighbour.getPosition().x,
(int) neighbour.getPosition().y,
(int) map.getDestPos().x,
(int) map.getDestPos().y));
}
}
}
}
return null;
}
It uses an exact heuristical method, as in tiles do not have move values as such. Instead it calculates the distance from the current node to the end node using a straight line, this is shitty atm and seems to result in my pathfinder “hugging” walls at points in the journey. Any idea how I can improve this? Should I just move over to the manhatten method and give nodes hardcoded values, this should simplify the math.
