✔ Implementierung des A*-Algorithmus in C++

[badday]

Moin zusammen,

ich habe mit mal am A* Algo versucht, bin aber bisher mehr oder weniger gescheitert, weiß allerdings momentan auch nicht mehr weiter, bin mir aber sicher, dass ihr mir helfen könnt.

Hier erstmal der Code:

class Node
{
public:
	Node(int _x, int _y, int _h, double _cost, double _way, double _heuristic, Node* _parent) : x(_x), y(_y), h(_h), cost(_cost), way(_way), heuristic(_heuristic), parent(_parent) {}
	int x, y;
	unsigned int h;
	Node *parent;
	double cost, way, heuristic;
};


bool checkNext(Node *next, std::list<Node*> &opened, const std::list<Node*> &closed)
{
	
	for(std::list<Node*>::const_iterator it = closed.begin(); it!=closed.end(); ++it)
	{
		if((*it)->x==next->x && (*it)->y==next->y)
			return false;
	}
	for(std::list<Node*>::iterator iter = opened.begin(); iter!=opened.end(); ++iter)
	{
		if((*iter)->x==next->x && (*iter)->y==next->y){
			if((*iter)->cost>next->cost) {
				opened.erase(iter);
				return true;
			}
			else
				return false;
		}
	}

	return true;
}

bool compare_cost(Node *first, Node *second)
{
	if(first->cost < second->cost)
		return true;

	return false;
}


void generatePathImpl(Node *act, Node *end, const video::IImage &hmap, std::list<Node*> &opened, std::list<Node*> &closed)
{
	
		if((act->x+10)<hmap.getDimension().Width) //the next one on the right side
		{
			
			double heur = sqrt(double((pow((act->x+10)-(end->x), 2.0)+pow((act->y)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y).getAverage()-(unsigned)(hmap.getPixel(act->x+10, act->y).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x+10, act->y, hmap.getPixel(act->x+10, act->y).getAverage(), cost+heur, 10, heur, act);

			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x+10)<hmap.getDimension().Width && (act->y+10)<hmap.getDimension().Height) //the next one 10 steps right and 10 steps up
		{
			
			double heur = sqrt(double((pow((act->x+10)-(end->x), 2.0)+pow((act->y+10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y+10).getAverage()-(unsigned)(hmap.getPixel(act->x+10, act->y+10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x+10, act->y+10, hmap.getPixel(act->x+10, act->y+10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->y+10)<hmap.getDimension().Height) //3
		{
			
			double heur = sqrt(double((pow((act->x)-(end->x), 2.0)+pow((act->y+10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y+10).getAverage()-(unsigned)(hmap.getPixel(act->x, act->y+10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x, act->y+10, hmap.getPixel(act->x, act->y+10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x-10)>0 && (act->y+10)<hmap.getDimension().Height) //4
		{
			
			double heur = sqrt(double((pow((act->x-10)-(end->x), 2.0)+pow((act->y-10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y-10).getAverage()-(unsigned)(hmap.getPixel(act->x-10, act->y-10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x-10, act->y-10, hmap.getPixel(act->x-10, act->y-10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x-10)>0) //5
		{
			
			double heur = sqrt(double((pow((act->x-10)-(end->x), 2.0)+pow((act->y)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y).getAverage()-(unsigned)(hmap.getPixel(act->x-10, act->y).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x-10, act->y, hmap.getPixel(act->x-10, act->y).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x-10)>0 && (act->y-10)>0) //6
		{
			
			double heur = sqrt(double((pow((act->x-10)-(end->x), 2.0)+pow((act->y-10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y-10).getAverage()-(unsigned)(hmap.getPixel(act->x-10, act->y-10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x-10, act->y-10, hmap.getPixel(act->x-10, act->y-10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->y-10)>0) //7
		{
			
			double heur = sqrt(double((pow((act->x)-(end->x), 2.0)+pow((act->y-10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y-10).getAverage()-(unsigned)(hmap.getPixel(act->x, act->y-10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x, act->y-10, hmap.getPixel(act->x, act->y-10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x+10)<hmap.getDimension().Width && (act->y-10)>0) //8
		{
			
			double heur = sqrt(double((pow((act->x+10)-(end->x), 2.0)+pow((act->y-10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y-10).getAverage()-(unsigned)(hmap.getPixel(act->x+10, act->y-10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x+10, act->y-10, hmap.getPixel(act->x+10, act->y-10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		closed.push_back(act);
		if(find(opened.begin(), opened.end(), act)!=opened.end())
			opened.erase(find(opened.begin(), opened.end(), act));

		opened.sort(compare_cost);

	
	
}			
		


			




std::stack<Node* > generatePath(Node *start, Node *end, const video::IImage &hmap)
{
	
	std::stack<Node*> paths;
	std::list<Node*> opened;
	std::list<Node*> closed;
	

	if(start->x == end->x && start->y == start->y)
	{
		return paths;
	}

	opened.push_back(start);

	generatePathImpl(start, end, hmap, opened, closed);
	
	while (opened.size() != 0)
	{
		start = (*opened.begin());
		opened.pop_front();
		generatePathImpl(start, end, hmap, opened, closed);
	}
	for(std::list<Node*>::iterator iter = closed.begin(); iter!=closed.end(); ++iter)
	{
		if((*iter)->x == end->x && (*iter)->y == end->y)
		{
			for(Node* act = (*iter); act != 0; act=act->parent)	{
				paths.push(act);				
			}

			return paths;
		}
	}


	return paths;
	
		
}

Ich denke für Leute, die den Algorithmus kennen, brauche ich nicht viel weiter sagen. Die Kosten werden anhand einer Gewichtung von Weg und Höhenunterschied errechnet, die Heuristik ist lediglich jeweils die Luftlinie ohne Höhenunterschied. hmap ist lediglich das Bild, ich hole mir jeweils die Farbwerte für den Höhenunterschied. Die Schritte sind jeweils sozusagen von einem Punkt, dort jeweils die angrenzenden Punkte (d. h. seitlich/oben/unten/Diagonalen), die Diagonalen sind teurer vom Weg her als "normale"(hier wird der Satz von Pythagoras verwendet).

Nun funktioniert es soweit. Also bei 50x50 (Größe des Heightmaps) ist es kein Problem, bei 640x640 dagegen schon, da es einfach zu lange dauert.

Sollte eigentlich nicht der Fall sein, wie ich meinte, da es ja nur 64*64 Knoten sein sollten.

Hier mal das Ergebnis (grüne Punkte sind jeweils die ausgewählten Knoten):

Das würde soweit passen, es ist aber schlicht zu langsam.

Für Hilfe wäre ich dankbar.



Gruß,


badday

 

[3Cyb3r]

Das wichtigste hast du nicht geschrieben. In was unterteilst du den Suchbereich (So wie es aussieht in Quadrate ... jeweils ein Pixel) ?
.. und ich glaube nicht umbedingt das sich einer die Mühe machen wird deine Code aufzuarbeiten, wenn du das Ganze als Strukturgramm darstellen würdest, wäre es wesentlich einfacher (dein Code schnell zu verstehen) verbesserungs Vorschläge zu machen und z.B. ich würde dir dann helfen !

MFG

 

[3Cyb3r]

Vorschläge von mir:

-Nimm größere Dreicke (oder Quadrate):

Bei einem längeren Pfad erst große Suchbereiche verwenden und dann in der nähe des Ziels wieder kleine (oder in der Nähe eines Hindernisses), also mehrere Pfadsuchsysteme die je nach Situation genommen werden. So wird es auch in Starcraft, Warcraft u.s.w. gemacht und rate mal woher es kommt das Figuren an Kanten hängen bleiben... (die ganzen Bugs halt )

- Benutze bei längeren Pfaden vorberechnete Pfade (welche für jede Map bei der Erstellung berechnet werden).

- Kompiliere deine Map vorher, d.h. du suchst vorher unereichbare Stellen herraus, welche bei normalem Vorgehen in Betracht gezogen werden. Und dazu gehört auch Sackgassen herauszufiltern und diese zu speichern.

- Optimiere dein Code (dabei ist ein Strukturgramm sehr nützlich!) (zur Not inline Assembler xD)

 

[badday]

Habe lediglich ein paar Optimierungen vorgenommen:
-Knoten werden nur erstellt, wenn sie wirklich neu sind (d. h., wenn es noch keine mit diesen x/y-Korrdinaten gibt)
-sonst werden sie modifiziert (cost und parent)
-closedSet und openedSet erlauben schnelle Überprüfung, ob die Punkte bereits in einer Liste sind

Nun ist keine Verzögerung mehr spürbar bei 64x64 Knoten.


Gruß,

badday