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;
}

Edited 7 Years Ago by racumin: n/a

Problem solved! Step 2 should be

while ((!listContains(closed, end)) && (opened.size() != 0)) {

Thanks anyways,..

This question has already been answered. Start a new discussion instead.