A* pathfinding not working and is too slow

  a-star, c++, path-finding

I’ve looked over several different implementations of A*. The current one I am using is based off of the pseudocode from the Wikipedia page. It finds the path but then the monster doesn’t move so I’m guessing it doesn’t work. It’s also incredibly slow. This is inside the update function which is called after the player presses a key and moves in the selected direction. The map is only a 40 x 40. What am I doing wrong?

(Ref: https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode)

int tx;
int ty;
handler->getDungeon()->getPlayer()->getPos(&tx, &ty);

struct Node {
    int x;
    int y;
    float f;
    int g;
    int h;
    Node* parent;
};

std::vector<Node*> open;
std::vector<Node*> closed;

Node* start = new Node();
start->x = x;
start->y = y;
start->f = 0.0f;
start->g = 0.0f;
start->h = 0.0f;
start->parent = nullptr;

open.push_back(start);

bool found = false;
while (open.size()) {
    int least = 0;
    for (unsigned int i = 1; i < open.size(); i++) {
        if (open.at(i)->f < open.at(least)->f) {
            least = i;
        }
    }

    Node* node = open.at(least);
    open.erase(open.begin() + least);
    closed.push_back(node);

    if (node->x == tx && node->y == ty) {
        found = true;
        break;
    }

    for (int x = -1; x < 2; x++) {
        for (int y = -1; y < 2; y++) {
            Node* child = new Node();
            child->x = node->x + x;
            child->y = node->y + y;
            
            bool ignore = false;
            if (!handler->getDungeon()->getFloor()->getTile(child->x, child->y)) {
                ignore = true;
            }
            if (!ignore) {
                if (handler->getDungeon()->getFloor()->getTile(child->x, child->y)->isSolid()) {
                        ignore = true;
                }
            }
            if (!ignore) {
                for (unsigned int i = 0; i < closed.size(); i++) {
                    if (child->x == closed.at(i)->x && child->y == closed.at(i)->y) {
                        ignore = true;
                        break;
                    }
                }
            }
            if (ignore) {
                delete child;
                continue;
            }
            child->g = node->g + 1.0f;
            child->h = std::max(std::abs(child->x - static_cast<float>(tx)), std::abs(child->y - static_cast<float>(ty)));
            child->f = child->g + child->h;
            child->parent = node;
            
            for (unsigned int i = 0; i < open.size(); i++) {
                if (child->x == open.at(i)->x && child->y == open.at(i)->y) {
                    if (child->g > open.at(i)->g) {
                        delete child;
                        child = nullptr;
                        break;
                    } else {
                        delete open.at(i);
                        open.erase(open.begin() + i);
                        break;
                    }
                }
            }
            if (child) {
                open.push_back(child);
            }
        }
    }
}

if (found) {
    Node* node = closed.at(closed.size() - 1);
    while (node->parent && node->parent->parent) {
        node = node->parent;
    }

    int dx = node->x - x;
    int dy = node->y - y;
    move(dx, dy);
}

Source: Windows Questions C++

LEAVE A COMMENT