Hi I am implementing a "Star Craft" game and I have troubles on my A* algorithm. I followed the steps in here and created my own implementation using object oriented c++. Now when I have say 32 x 32 grid, and I need to move 1 unit, it takes for about 1.2 seconds to finish. If I use a smaller grid, say 16 x 16, it is much faster. What optimizations do you recommend so that my path finding will become faster?
This is my code:
stack<Node*> AStar::generatePath(Node *start, Node *end, MyMap *map) {
Node*** grid = map->getNodes();
int width = map->getWidth();
int height = map->getHeight();
//reset node values
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
grid[j][i]->reset();
}
}
stack<Node*> paths;
list<Node*> opened;
list<Node*> closed;
Node *current;
//make sure start and end is not equal
if ((start->getX() == end->getX()) && (start->getY() == end->getY())) {
cout << "start and end positions are equal" << endl;
return paths;
}
//step 1
opened.push_back(start);
//step 2
while ((!listContains(closed, end)) || (opened.size() != 0)) {
//a
current = getLowestF(opened);
if (current == NULL) {
cout << "current == null" << endl;
break;
}
//b
opened.remove(current);
closed.push_back(current);
//c
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
//traverse all nodes 1 unit from the current
if (((i != 0) || (j != 0)) &&
(j + current->getY() >= 0) && (j + current->getY() < height) &&
(i + current->getX() >= 0) && (i + current->getX() < width)) {
//check if next node is in diagonal
if ((fabs(i) == 1) && (fabs(j) == 1)) {
//make sure ver and hor nodes are walkable when moving diagonally
if (!grid[i + current->getX()][current->getY()]->isWalkable()) {
continue;
}
if (!grid[current->getX()][j + current->getY()]->isWalkable()) {
continue;
}
}
Node *child = grid[i + current->getX()][j + current->getY()];
//c 1
if ((child->isWalkable() && !listContains(closed, child)) ||
((child->getX() == end->getX()) && (child->getY() == end->getY()) && !listContains(closed, child))) {
//c 2
if (!listContains(opened, child)) {
//c 2 i
opened.push_back(child);
//c 2 ii
child->setParent(current);
//c 2 iii
computeValues(child, current, end);
} else {
//c 3
if (child->getGValue() > newGValue(child, current)) {
//change child's parent
child->setParent(current);
child->setGValue(newGValue(child, current));
}
}
}
}
}
}
}
//step 3
if (end->getParent() == NULL) {
cout << "no path found!" << endl;
} else {
addToPath(paths, end);
//pop the source node
paths.pop();
cout << "found path!" << endl;
}
return paths;
}