Problem mit A* Wegsuchsalgorithmus

*Q* 1

Hallo zusammen,

ich arbeite gerade an einer C++-Implementierung des A* Wegsuchalgorithmus (http://de.wikipedia.org/wiki/A*).
Leider funktioniert es nicht richtig, es wird zwar ein Pfad gefunden, aber der geht quasi durchs ganze feld durch, ist also auf keinen fall ein optimaler weg, der eigentlich gefunden werden sollte.
Ich vermute, dass es (zumindest unter anderem) daran liegt, dass ich eine std::priority_queue verwende, die zeiger auf Node-Objekte speichert und ich zwischendrin im algorithmus werte der Node-Objekte ändern muss und deshalb die priority_queue natürlich nicht mehr richtig funktioniert.
Allerdings ist die priority_queue schon recht wichtig, damit der algorithmus effizient abläuft. Leider hat die queue aber nichts zum entfernen (sonst könnte ichs entfernen und neu einfügen, wenn ichs ändere). Habt ihr ne idee, durch was ich die priority_queue ersetzen kann, oder sonst nen Vorschlag?
Ich poste hier mal den wichtigsten teil des codes, den rest verlinke ich bei pastebin: http://pastebin.com/3ZFJEhF4 , weils etwas viel ist.

Die kritische Stelle mit der priorityqueue ist unten markiert.

//pathfinder.h
class PathFinder
{
public:
	PathFinder(const Map& map);
	bool FindPath(/*out*/ std::vector<Point>& result, const Point& start, const Point& end);
private:
	struct Node
	{
		enum ListStatus
		{
			NotSeen, Open, Closed
		};

		Node(){pred = nullptr;}
		int GetRating() const {return stepsToHere + heuristicRating;}

		Node * pred;		
		bool passable;
		Point pos;
		int stepsToHere;
		int heuristicRating;
		unsigned int lastUsedIndex;			
		ListStatus listStatus;
	};

	struct NodeComparator
	{
		bool operator()(const Node* lhs, const Node* rhs) const
		{
			return lhs->GetRating() < rhs->GetRating();
		}
	};

	typedef std::priority_queue<Node*, std::vector<Node*>, NodeComparator> OpenList;
	void InitGrid(const Map& map);
	void ExpandNode(Node & currentNode, OpenList& openNodes);	
	void ExamineNodeAt(Node& pred, int stepsToHere, const Point& pos, OpenList& openNodes);
	static void CreateTrace(std::vector<Point>& result, Node & currentNode);

	TwoDimensionalArray<Node> grid_;
	unsigned int currentUseIndex;
	ManhattanDistanceCalculator manhattan_;
	Point endPos_;
};

//pathfinder.cpp
PathFinder::PathFinder(const Map& map):
grid_(map.GetWidth(), map.GetHeight())
{
	currentUseIndex = 0;
	InitGrid(map);
}

void PathFinder::InitGrid(const Map& map)
{
	for(int i = 0; i < grid_.GetWidth(); ++i)
	{
		for(int j = 0; j < grid_.GetHeight(); ++j)
		{
			Node & node = grid_.GetRefAt(i, j);
			node.lastUsedIndex = 0;
			node.passable = map.IsPassable(i, j);
			node.pos = Point(i, j);
		}
	}
}

bool PathFinder::FindPath(std::vector<Point>& result, const Point& start, const Point& end)
{
	endPos_ = end;
	result.clear();
	++currentUseIndex;

	Node & startNode = grid_.GetRefAt(start.x, start.y);
	startNode.lastUsedIndex = currentUseIndex;
	startNode.listStatus = Node::Open;
	startNode.passable = true;
	startNode.pos = start;
	startNode.heuristicRating = manhattan_(start, end);
	startNode.pred = nullptr;
	OpenList openNodes;
	openNodes.push(&startNode);
	while(!openNodes.empty())
	{
		Node & currentNode = *openNodes.top();
		openNodes.pop();
		if(currentNode.pos == end)
		{
			CreateTrace(result, currentNode);
			return true;
		}
		currentNode.lastUsedIndex = currentUseIndex;
		ExpandNode(currentNode, openNodes);
		currentNode.listStatus = Node::Closed;
	}
	return false;
}

void PathFinder::ExpandNode(Node & currentNode, OpenList& openNodes)
{
	int x = currentNode.pos.x;
	int y = currentNode.pos.y;
	Point pos = currentNode.pos;
	int steps = currentNode.stepsToHere;

	pos.y--;
	ExamineNodeAt(currentNode, steps, pos, openNodes);

	pos.x++;
	ExamineNodeAt(currentNode, steps, pos, openNodes);

	pos.y++;
	ExamineNodeAt(currentNode, steps, pos, openNodes);

	pos.y++;
	ExamineNodeAt(currentNode, steps, pos, openNodes);

	pos.x--;
	ExamineNodeAt(currentNode, steps, pos, openNodes);

	pos.x--;
	ExamineNodeAt(currentNode, steps, pos, openNodes);

	pos.y--;
	ExamineNodeAt(currentNode, steps, pos, openNodes);

	pos.y--;
	ExamineNodeAt(currentNode, steps, pos, openNodes);
}

void PathFinder::ExamineNodeAt(Node & pred, int stepsToHere, const Point& pos, OpenList& openNodes)
{
	if(pos.x < 0 || pos. x >= grid_.GetWidth() || pos.y < 0 || pos.y >= grid_.GetHeight())
	{
		return;
	}
	++stepsToHere;
	Node& node = grid_.GetRefAt(pos.x, pos.y);
	if(!node.passable)
	{
		return;
	}
	//node first seen
	if(node.lastUsedIndex != currentUseIndex)
	{
		node.pred = &pred;
		node.stepsToHere = stepsToHere;
		node.lastUsedIndex = currentUseIndex;
		node.listStatus = Node::Open;
		node.heuristicRating = manhattan_(pos, endPos_);
		openNodes.push(&node);
	}
	//a better way to node was found
	else
	{
		Node::ListStatus status = node.listStatus;
		if(status == Node::Closed)
		{
			return;
		}
		if(stepsToHere < node.stepsToHere)
		{
//----------->//messes up priorityqueue...<--------------
			node.stepsToHere = stepsToHere;
			node.pred = &pred;
		}
	}
}

void PathFinder::CreateTrace(std::vector<Point>& result, Node & currentNode)
{
	if(currentNode.pred != nullptr)
	{
		CreateTrace(result, *currentNode.pred);
	}
	result.emplace_back(currentNode.pos);
}

Noch ein paar Hinweis:
Damit ich das grid nicht jedes mal neu erstellen / auf null setzen muss, hab ich diesen lastUsedIndex und currentUseIndex gemacht. Falls der lastUsedIndex einer Node != currentIndex ist, ist die Node noch nicht besucht worden in diesem Suchvorgang.

Vielen Dank schonmal für eure Hilfe!

*Q* 1

Hat denn keiner eine Idee?

Ich fasse das Problem nochmal kurz zusammen, dann müsst ihr euch nicht durch den länglichen text oben quälen

Ich brauche eine priority_queue, um immer dan Knoten mit der niedrigsten Bewertung zu entfernen. Außerdem muss ich ab und zu ein Element mittendrin ändern, das kann z.B. auch durch entfernen und neueinfügen passieren.
Das ganze soll trotzdem möglichst effizient sein.
Was für eine Datenstruktur bietet sich da an?

Ich werde es evtl. mal mit einem Multiset versuchen (multi, weil die elemente nach Bewertung verglichen werden und mehrere Knoten trotz verschiedener Positionen die selbe Bewertung haben können).
Vermutlich ist das entfernen in der mitte (um den wert zu ändern) aber relativ ineffizient...
Edit: Vll doch nicht, in der referenz steht amortisiert konstante laufzeit, hört sich ja ganz gut an.
Edit2: Ich glaube ich nehme besser ein normales set, dass primär nach bewertung geht und sekundär nach position, damit ich überhaupt ein element nach position entfernen kann.

Nexus

std::priority_queue ist ja nur ein Adapter für einen anderen Container wie std::vector . Du kannst mit dem letzteren die gleiche Funktionalität erreichen, dabei können dir std::push_heap() , std::pop_heap() und std::make_heap() aus <algorithm> helfen.

Übrigens hat Boost.Graph eine Implementierung für A*, falls du das Rad nicht neu erfinden willst. Die ist wahrscheinlich auch optimiert.

Wenn es effizient sein soll, musst du dir wohl eine eigene Heap Klasse implementieren. Du kannst die std::push_heap() , std::pop_heap() Funktionen verwenden und musst noch eine Funktion schreiben, mit der du den Wert eines Eintrags im Heap ändern kannst. Das lässt sich noch ein wenig effizienter schreiben, als einer Entfernen gefolgt von ein Einfügen-Operation.

Falls du es ganz effizient haben willst, kannst du auch einen Fibbonacci-Heap implementieren.

*Q* 1

Heap selbst implementieren ist mir (zumindest erstmal) zuviel aufwand, ich versuchs erstmal mit nem set, bring es zum laufen und guck obs schnell genug läuft und wenn nicht such ich erstmal nach dem bottleneck und nur falls es dann wirklich die OpenList ist guck ich nochmal in Richtung Heaps

Edit: Hab mir gerade doch nochmal die heap-algorithmen angeguckt, ist dann wohl doch nicht soviel aufwand, vll benutz ich doch den heap.

Wie kriegt man denn dabei die decreaseKey-Operation gut hin?

Welche DecreaseKey-Operation? Ruf einfach makeHeap auf, wenn du
Elemente in der PQ geändert hast.

knivil

make_heap: At most, (3*(last-first)) comparisons.

Ich sage mal O(n). Eine set mit Einfuegen/Loeschen ist aber O(log n).

*Q* 1

Dann bleib ich wohl doch beim set, außer wenn wer nen guten Vorschlag hat.

DecreaseKey soll heißen, dass ein element so verändert wird, dass er in der priority_queue früher drankommt als vorher.

Jedes element bei mir hat eine rating.
Je niedriger, desto früher wirds abgearbeitet.
Hin und wieder muss ich die Rating eines Elements verringern.

knivil schrieb:

make_heap: At most, (3*(last-first)) comparisons.
Ich sage mal O(n). Eine set mit Einfuegen/Loeschen ist aber O(log n).

Ein Heap lässt sich auch so implementieren, dass beliebige Elemente in O(log n) entfernt werden können. Ein Heap ist nur im Allgemeinen schneller als ein set (um einen konstanten Faktor). Das geht natürlich nur, wenn man weis, wo sich das entsprechende Element im Moment im Heap befindet.

Q schrieb:

Wie kriegt man denn dabei die decreaseKey-Operation gut hin?

Wenn du die irgendwo gefunden hast, dann wird die schon in Ordnung sein. Es ging mir nur darum, zu erwähnen, dass es besser geht, als entfernen und einfügen. Eben mit einer decreaseKey -Funktion. Man kann auch relativ einfach eine changeKey -Funktion bauen.

Heaps sind btw. hier recht gut erklärt:
Introduction to Algorithms | ISBN: 9780262033848

*Q* 1

ProgChild schrieb:

Q schrieb:

Wie kriegt man denn dabei die decreaseKey-Operation gut hin?

Wenn du die irgendwo gefunden hast, dann wird die schon in Ordnung sein. Es ging mir nur darum, zu erwähnen, dass es besser geht, als entfernen und einfügen. Eben mit einer decreaseKey -Funktion. Man kann auch relativ einfach eine changeKey -Funktion bauen.

Ich habe ja keine gefunden, sondern will eine basteln

*Q* 1

Jetzt hab ich folgendes Problem:

struct NodeComparator
	{
		bool operator()(const Node* lhs, const Node* rhs) const
		{
			if(lhs->GetRating() < rhs->GetRating())
				return true;
			if(lhs->pos.x < rhs->pos.x)
				return true;
			return lhs->pos.y < rhs->pos.y;
		}
	};

	typedef std::set<Node*, NodeComparator> OpenList;

Debug Assertion Failed!
Expression: invalid operator<

Was ist denn falsch an meinem Comparator?

Th69

Hallo Q,

du willst ja nur die Positionen vergleichen, wenn dein Rating gleich ist (und daselbe dann für dein pos.x und pos.y):

struct NodeComparator
    {
        bool operator()(const Node* lhs, const Node* rhs) const
        {
            if(lhs->GetRating() < rhs->GetRating())
                return true;
            else if(lhs->GetRating() > rhs->GetRating())
                return false;

            if(lhs->pos.x < rhs->pos.x)
                return true;
            else if(lhs->pos.x > rhs->pos.x)
                return false;

            return lhs->pos.y < rhs->pos.y;
        }
    };

*Q* 1

Danke! Jetzt funktionierts!
Hab std::set statt priority_queue verwendet.

Edit: Irgendwo ist nocjh nen fehler, gerade wurde ein ungültiger Pfad mit sprüngen drin gefunden.
Edit2: Ups ich glaube, die Sprünge hab ich nur gesehen, weil die Konsole Zeilenumbrüche reingemacht hat Bin mir aber nicht ganz sicher.

Q schrieb:

Ich habe ja keine gefunden, sondern will eine basteln

Ach so. Dann habe ich dich falsch verstanden.

Angenommen bei deinem Heap ist immer das Minimum die Wurzel. Wenn du jetzt den Schlüssel von einem Element verminderst, dann muss dieses Element im Binärbaum so weit nach oben geschoben werden, bis der Schlüssel seiner Söhne größer sind, als es selbst. Dazu immer mit dem Vater-Knoten vergleichen und falls die Eigenschaft noch nicht erfüllt ist, die Knoten vertauschen. Das gleiche dann mit der neuen Position wiederholen, usw.

Mehr Details müsstest du in entsprechender Literatur nachlesen.