Although not directly Java (C#), I have some Pathfinding code that is using a Breadth First Search algorithm which just uses brute force to scan the entire map for the base to attack. My game consists of lanes, as it is a Tower Defence game so this is not too much of an issue with dozens of enemies.
But as soon as I start to open the lanes up to 2-3 tiles wide, I double/triple the amount of tiles required to check.
I am using this algorithm:
public Path CalculatePath(Node start, Node destination){
Logger.Print(Logger.LogLevel.DEBUG,
"Starting path calculation from " + start.Position + " to " + destination.Position, "AI");
// Add the start node to the open list
open.Add(start);
// Loop constantly untilt he open list is empty, so every node is searched
while (open.Count != 0){
// Grab the first node in the list and set it as current
Node current = open.First();
// Check if the current node is equal to the destination, if so we have found a path
if (current.Equals(destination)){
Logger.Print(Logger.LogLevel.DEBUG,
"Path found from " + start.Position + " to " + destination.Position, "AI");
return new Path(start, destination);
}
// Check every neighbour and add them to the open list if they are not null,
// are not on the closed list and are not blocked
foreach (Node neighbour in current.Neighbours){
if (neighbour == null || closed.Contains(neighbour) || neighbour.Blocked) continue;
open.Add(neighbour);
neighbour.Previous = current;
}
// Remove the current node fom the open list, it has been checked
open.Remove(current);
// Add it to the closed list so we don't search it again
closed.Add(current);
}
Logger.Print(Logger.LogLevel.DEBUG, "NO PATH FOUND FROM " + start.Position + " to " + destination.Position,
"AI");
return null;
}
Which works fine, I can run it several times in a row on a decent sized map without too much issue, but the thing is I only run this ONCE when the map first loads. All Paths are then stored in the spawners that the enemies generate from, they simply grab a copy of it. The problem is, although I have avoided a while loop I now need to fire every enemy that spawns into a for loop to clone the already generated path.
This here is the 1 time path generation code, runs once after a path has been found:
public Path(Node start, Node destination){
this.start = start;
this.destination = destination;
Node n = destination;
nodes.Add(destination);
// Start bulding the path backwards until the previous node is equal to the start node
while (!n.Equals(start)){
n = n.Previous;
nodes.Add(n);
}
nodes.Add(start);
nodes.Reverse();
currentNode = nodes [currentNodeIndex];
}
And when my enemies spawn, they grab a Path from the spawner by doing
path = spawner.Path.Clone();
Which looks like this:
private Path(IEnumerable<Node> nodes){
foreach (var n in nodes){
this.nodes.Add(n);
}
currentNode = this.nodes[currentNodeIndex];
}
As you can expect, with enough enemies, frankly considerably less than I would like to spawn in harder levels, it lags to hell. Causing hangtime.
Does anyone know a good way to duplicate an already created path without this look issue?