<分区>
我为我正在制作的游戏编写了一个星形算法(我第一次使用它),但它无法找到超过一个方格的任何目标。我使用调试器查看发生了什么,它看起来确实有点像在兜圈子。这是我的算法(sx,sy 是起始图 block 坐标,tx,ty 是目标坐标。此外,此函数是类的一部分,以防您对 undefined variable 感到疑惑):
void Pathfinder(int sx, int sy, unsigned int tx, unsigned int ty, int map[7][11],std::map<array2,Door*> doors,int dv){
if (!map[ty][tx] == 0){ return;}
Node map_nodes [7][11];
std::vector<Node*> open;
int current_index, x, y, tile;
path.clear();
map_nodes[sy][sx].load(sx,sy,tx,ty,0, true, false,0,0);
Node* current = &map_nodes[sy][sx];
open.push_back(current);
while (open.size() > 0) {
for (int b = 0; b < open.size(); ++b) {
if (b == 0 || open[b]->f < current->f) {
current = open[b];
current_index = b;
}
}
// checks if current is the target
if (current->x == tx && current->y == ty) {
int path_length = current->g + 1;
path.resize(path_length, {0, 0});
for (int p = 0; p < path_length; p++) {
path[p][0] = current->x;
path[p][1] = current->y;
current = &map_nodes[current->y][current->x];
}
return;
}
current->closed = true;
current->open = false;
open.erase(open.begin() + current_index);
for (int k = 0; k < 3; k++) {
for (int u = 0; u < 3; u++) {
if (k != 1 && u != 1) {
x = current->x + u - 1;
y = current->y + k - 1;
if (x >= 0 && y >= 0) {
//checks if it is traversable
if (map_nodes[y][x].closed || (map[y][x] == 0 || (map[y][x] >= dv && doors[{x, y}]->access_level <= acess_level))) {
if (!map_nodes[y][x].open) {
map_nodes[y][x].load(x, y, tx, ty, current->g + 1, true, false, current->x,current->y);
open.push_back(&map_nodes[y][x]);
} else if (current->g < map_nodes[y][x].g) {
map_nodes[y][x].update_f(current->g, current->x,current->y);
}
}
}
}
}
}
}
}
这是节点类:
class Node{
public:
int x = 0, y = 0, f = 0, g = 0, h = 0, px = 0, py = 0;
bool open = false, closed = false;
void load(int xa, int ya, int tx, int ty, unsigned int ga, bool opena, bool closeda, int pxa,int pya){
x = xa;
y = ya;
g = ga;
h = ((tx - x) * (tx - x)) + ((ty - y) * (ty - y));
f = g + h;
open = opena;
closed = closeda;
px = pxa;
py = pya;
}
void update_f(unsigned int ga, int pxa, int pya){
g = ga;
f = g + h;
px = pxa;
py = pya;
}
};
编辑: 没关系修复它,有一个 if 命令缺少一个!这把事情搞砸了。