У меня есть некоторый код C ++, который я написал, чтобы найти путь A *, но он ведет себя странно. Здесь довольно много кода, поэтому я разделю его на куски и попытаюсь объяснить, что я делаю. Я не буду объяснять, как работает A * pathing. Я полагаю, если вы пытаетесь помочь, вы уже знаете алгоритм.
Прежде всего, вот моя функция для вычисления значения h узла:
int
calculateH(int cX, int cY, int eX, int eY, int horiCost = 10, int diagCost = 14) {
int h;
int xDist = abs(eX - cX);
int yDist = abs(eY - cY);
if (xDist > yDist)
h = (diagCost * yDist) + (horiCost * (xDist - yDist));
else
h = (diagCost * xDist) + (horiCost * (yDist - xDist));
return h;
}
Я почти уверен, что здесь нет проблем; довольно простые вещи.
Следующий мой класс Node. И я знаю, я знаю, сделайте эти переменные частными и используйте получатели; Я просто сделал это для тестирования.
class Node {
public:
Node(int x_, int y_, int g_, int h_, int pX_, int pY_, bool list_) {
x = x_;
y = y_;
g = g_;
h = h_;
pX = pX_;
pY = pY_;
list = list_;
};
int x, y, g, h, pX, pY;
bool list;
};
Каждый узел имеет переменные X и Y. Я храню только G и H, а не F, и вычисляю F, когда мне это нужно (что только один раз в моем коде). Тогда есть родительские значения X и Y. Список является логическим: fale = открытый список, true = закрытый список.
У меня также есть класс Object. Здесь важны только переменные X, Y и Passable, доступ к которым осуществляется через геттеры.
Теперь вот начало моего реального кода поиска пути. Возвращает строку чисел, соответствующую направлениям, как показано ниже:
432
501
678
Итак, 1 означает движение вправо, 8 означает движение вниз и вправо, 0 означает, что никуда не денется.
string
findPath(int startX, int startY, int finishX, int finishY) {
// Check if we're already there.
if (startX == finishX && startY == finishY)
return "0";
// Check if the space is occupied.
for (int k = 0; k < objects.size(); k ++)
if ((objects[k] -> getX() == finishX) &&
(objects[k] -> getY() == finishY) &&
(!objects[k] -> canPass()))
return "0";
// The string that contains our path.
string path = "";
// The identifier of the current node.
int currentNode = 0;
// The list of nodes.
vector<Node> nodes;
// Add the starting node to the closed list.
nodes.push_back(Node(startX, startY, 0,
calculateH(startX, startY, finishX, finishY),
startX, startY, true));
Теперь мы перебираем, пока не найдем пункт назначения. Обратите внимание, что sizeLimit просто для того, чтобы быть уверенным, что мы не зациклимся (это НЕ БУДЕТ, если я смогу исправить этот код. На данный момент это очень необходимо). Все с этого момента, пока я не отмечу иначе, находится внутри петель i j.
int sizeLimit = 0;
while ((nodes[currentNode].x != finishX) | (nodes[currentNode].y != finishY)) {
// Check the surrounding spaces.
for (int i = -1; i <= 1; i ++) {
for (int j = -1; j <= 1; j ++) {
bool isEmpty = true;
// Check if there's a wall there.
for (int k = 0; k < objects.size(); k ++) {
if ((objects[k] -> getX() == (nodes[currentNode].x + i)) &&
(objects[k] -> getY() == (nodes[currentNode].y + j)) &&
(!objects[k] -> canPass())) {
isEmpty = false;
}
}
Следующая часть:
// Check if it's on the closed list.
for (int k = 0; k < nodes.size(); k ++) {
if ((nodes[k].x == (nodes[currentNode].x + i)) &&
(nodes[k].y == (nodes[currentNode].y + j)) &&
(nodes[k].list)) {
isEmpty = false;
}
}
Продолжение:
// Check if it's on the open list.
for (int k = 0; k < nodes.size(); k ++) {
if ((nodes[k].x == (nodes[currentNode].x + i)) &&
(nodes[k].y == (nodes[currentNode].y + j)) &&
(!nodes[k].list)) {
// Check if the G score is lower from here.
if (nodes[currentNode].g + 10 + (abs(i * j) * 4) <= nodes[k].g) {
nodes[k].g = nodes[currentNode].g + 10 + (abs(i * j) * 4);
nodes[k].pX = nodes[currentNode].x;
nodes[k].pY = nodes[currentNode].y;
}
isEmpty = false;
}
}
Это последняя часть цикла i j:
if (isEmpty) {
nodes.push_back(Node(nodes[currentNode].x + i,
nodes[currentNode].y + j,
nodes[currentNode].g + 10 + (abs(i * j) * 4),
calculateH(nodes[currentNode].x + i, nodes[currentNode].y + j, finishX, finishY),
nodes[currentNode].x,
nodes[currentNode].y,
false));
}
}
}
Теперь мы находим узел с наименьшей F-оценкой, меняем его на текущий узел и добавляем в закрытый список. Защита от бесконечной блокировки также завершена здесь:
// Set the current node to the one with the lowest F score.
int lowestF = (nodes[currentNode].g + nodes[currentNode].h);
int lowestFIndex = currentNode;
for (int k = 0; k < nodes.size(); k ++) {
if (((nodes[k].g + nodes[k].h) <= lowestF) &&
(!nodes[k].list)) {
lowestF = (nodes[k].g + nodes[k].h);
lowestFIndex = k;
}
}
currentNode = lowestFIndex;
// Change it to the closed list.
nodes[currentNode].list = true;
sizeLimit ++;
if (sizeLimit > 1000)
return "";
}
Проблема, с которой я столкнулся, заключается в том, что он не находит определенных путей. Кажется, никогда не сработает, если путь идет вверх или влево в любой точке. Вниз, влево и вправо все работает нормально. Во всяком случае, большую часть времени. Я понятия не имею, что вызывает эту проблему; В какой-то момент я даже попытался вручную , следуя моему коду, чтобы увидеть, в чем проблема. Не удивительно, что это не сработало.
И еще одна вещь: если вы считаете мои фигурные скобки (во-первых, вау, у вас больше преданности, чем я думал), вы заметите, что в конце мне не хватает закрывающей скобки. Не говоря уже о моем ответном заявлении. В конце есть немного кода, чтобы фактически проложить путь, который я пропустил. Я знаю, что эта часть не проблема, однако; В настоящее время я закомментировал это, и это все еще не работает таким же образом. Я добавил код, чтобы сообщить мне, где он не работает, и он находится в части поиска пути, а не в интерпретации.
Извините, мой код такой грязный и неэффективный. Я новичок в c ++, поэтому любые критические советы по моей технике также приветствуются.