Я пишу алгоритм поиска пути A * для класса. Это отлично работает, я могу щелкнуть моего персонажа и переместить его в нужное место. Однако, после запуска в течение примерно 30 секунд врагов, также вызывающих алгоритм A *, он выдает java.lang.StackOverflowError.
Вызов непосредственно перед вызовом функции библиотеки ArrayList увеличивается. Я не могу себе представить, что я делаю неправильно, поскольку я создаю экземпляр объекта и просто вызываю ArrayList.add(Node);
Я думаю, что происходит то, что есть много символов ai, которые полагаются на эту функцию, и после того, как многие из них вызвали его, программе не хватает памяти и она превышает максимальный размер стека, выделенный для программы. Тем не менее, Eclipse не говорит, что Java не хватило памяти или что-то в этом роде, что, я думаю, произойдет, если программе действительно не хватит памяти.
Есть ли что-то, что я делаю не так? Или мне не хватает памяти? Если да, есть ли способ увеличить объем выделенной памяти (я вижу, что у меня осталось много оперативной памяти)? Или есть лучший способ хранения данных для уменьшения нагрузки на память?
Спасибо! Вот код, который я сейчас написал, пожалуйста, дайте мне знать, если вам нужна дополнительная информация.
public class AStar {
class Node
{
public double x, y, g, h;
public Node parent;
public Node(double _x, double _y, double _g, double _h, Node _parent)
{
x = _x;
y = _y;
g = _g;
h = _h;
parent = _parent;
}
}
double start_x, start_y, goal_x, goal_y;
private double heuristic(double s_x, double s_y)
{
double x = Math.abs(s_x - goal_x);
double y = Math.abs(s_y - goal_y);
return x + y;
}
private Node GenerateRelativeNode(Node origin, double dX, double dY, List<Node> closed, List<Node> open)
{
double newX = origin.x + dX;
double newY = origin.y + dY;
Node temp = new Node(newX, newY, origin.g+1, heuristic(newX, newY), origin);
for(int i = 0; i < closed.size(); ++i)
{
if(closed.get(i).x == temp.x && closed.get(i).y == temp.y)
return null;
}
for(int i = 0; i < open.size(); ++i)
{
if(open.get(i).x == temp.x && open.get(i).y == temp.y)
{
return null;
}
}
return temp;
}
private int GetLowestFIndex(List<Node> set)
{
double min = 1000000;
int index = -1;
for(int i = 0; i < set.size(); ++i)
{
double f = set.get(i).h + set.get(i).g;
if(f < min)
{
min = f;
index = i;
}
}
return index;
}
private List<Pair<Double, Double>> PathFromNode(Node _n)
{
List<Pair<Double, Double>> path = new ArrayList<Pair<Double, Double>>();
List<Node> nodes = new ArrayList<Node>();
Node curr = _n;
while(curr.parent != null)
{
nodes.add(curr);
curr = curr.parent;
}
//now need to reverse the list.
for(int i = nodes.size()-1; i >= 0; --i)
{
Pair<Double, Double> pair = pairFromNode(nodes.get(i));
path.add(pair);
}
return path;
}
private Pair<Double, Double> pairFromNode(Node _n)
{
return new Pair<Double, Double>(new Double(_n.x), new Double(_n.y));
}
public static int pathDistance(double start_x, double start_y, double goal_x, double goal_y,
S3PhysicalEntity i_entity, S3 the_game) {
AStar a = new AStar(start_x,start_y,goal_x,goal_y,i_entity,the_game);
List<Pair<Double, Double>> path = a.computePath();
if (path!=null) return path.size();
return -1;
}
public AStar(double sX, double sY, double gX, double gY,
S3PhysicalEntity i_entity, S3 the_game) {
start_x = sX;
start_y = sY;
goal_x = gX;
goal_y = gY;
}
public List<Pair<Double, Double>> computePath() {
double start_h = heuristic(start_x, start_y);
Node start = new Node(start_x, start_y, 0, start_h, null);
List<Node> OpenSet = new ArrayList<>();
List<Node> ClosedSet = new ArrayList<>();
OpenSet.add(start);
while(!OpenSet.isEmpty())
{
int index = GetLowestFIndex(OpenSet);
Node N = OpenSet.get(index);
OpenSet.remove(index);
if(N.x == goal_x && N.y == goal_y)
{
return PathFromNode(N);
}
ClosedSet.add(N);
Node Up = GenerateRelativeNode(N, 0, 1, ClosedSet, OpenSet);
Node Left = GenerateRelativeNode(N, -1, 0, ClosedSet, OpenSet);
Node Right = GenerateRelativeNode(N, 1, 0, ClosedSet, OpenSet);
Node Down = GenerateRelativeNode(N, 0, -1, ClosedSet, OpenSet);
if(Up != null)
OpenSet.add(Up);
if(Left != null)
OpenSet.add(Left);
if(Right != null)
OpenSet.add(Right);
if(Down != null)
OpenSet.add(Down);
}
return null;
}
}
Вот стек во время StackOverflow 
На этом этапе WPeasant(WTroop).moveTowardsTarget(S3, int, int) line: 202 вызывается тысячи раз подряд. Код для этой функции не в каком-либо виде, в то время как l oop или для l oop или в любом другом.
Однако это может вызываться несколько раз из-за столкновения игрового объекта с чем-то, как Я не принимал во внимание препятствия при поиске пути.
Трудно сказать наверняка, что это проблема, так как я не написал ни одного из этого движка, мне нужно только реализовать A *. Я могу попытаться включить обход препятствий и посмотреть, исправит ли это все.