Aloha,
schön dich auch mal wieder hier zu sehen. Für dein Problem hab ich denke ich ne gute Erklärung. Hab auch noch streng geheimen source-code, den ich dir zukommen lassen könnte
Aber ich versuchs mal in C++. ZUm generellen Verfahren.
Man hat einen Startpunkt, einen Endpunkt und eine Menge von Punkten. Weiterhin gibt es Möglichkeiten von einen Punkt zu einem anderen zu kommen, wobei diese aber eine gewisse Distanz auseinander sind. Diese ist wichtig um abzuschätzen, welcher wohl der nächst beste Punkt ist, den man ansteuern könnte und wird mit einer Heuristik ermittelt. Weiterhin ist A* vollständig und korrekt. Ich versuch das mal alles am Beispeil zu erklären:
Erst definieren wir uns wie ein Punkt in unserer Welt aussieht:
Code:
struct Node
{
Node* parent;
position2d<int> pos;
int cost;
};
Wir halten uns ein paar Listen:
Code:
vector<Node*> queue, path, visited;
queue ist dabei unsere Liste von Punkten, die wir gerade bearbeiten, in path wird später uns weg sein, den wir abgehen werden und in visited speichern wir alle punkte, die wir bereits besucht haben, da sonst der Algorithmus unter umständen nicht terminieren würde.
Nun beginnen wir die suche:
Code:
void findPathWithAStar()
{
//Wir initialisieren unsere Listen
queue.clear();
path.clear();
visited.clear();
//Nun legen wir uns eine lokale variable an, mit der wir arbeiten können. Diese wird der aktuelle Punkt sein, auf dem wir
//uns befinden!
Node* currentNode;
//Node* getStartNode() gibt uns den Anfangspunkt zurück
//das heißt: currentNode->parent = NULL;
//currentNode->cost = 0;
currentNode = getStartNode();
//der anfangspunkt wird in die arbeitsliste hinzugefügt und als besucht markiert
queue.push_back(currentNode);
visited.push_back(currentNode);
//solange wir noch arbeitsknoten haben
while(!queue.empty())
{
//Node* getCheapestNode() gibt uns den Knoten mit den wenigsten Zugkosten zurück, also der jenige Knoten, bei
//dem cost minimal ist.
currentNode = getCheapestNode();
//Uuups. Fehler ;(
if(currentNode == NULL)
{
//fehlerausgabe ...
return;
}
if(currentNode == getEndNode())
{
//Wir haben einen Weg gefunden, nun rekonstruieren wir einen Weg zurück
restorePathFromNode(currentNode);
}
vector<Node*> allNeighborPointsFromHere = getAllNeighbors(currentNode);
//diese Funktion ermittelt alle Nachbarknoten von currentNode. In einem rechtwinkligen Grid wäre das als
//Beispiel wenn wir von dem Punkt (1,2) aus gehen die 4 Punkte { (0,2), (2,2), (1,1), (1,3) }
//Nun fügen wir all die neuen Knoten in unsere Arbeitskette hin zu und markieren sie als besucht
for(unsigned int i = 0; i < allNeighborPointsFromHere.size(); i ++)
{
queue.push_back(allNeighborPointsFromHere[i]);
visited.push_back(allNeighborPointsFromHere[i]);
}
}
}
Das ist im Prinzip der ganze Zauber. Wir lassen die Schleife solange durchlaufen, bis wir die Liste komplett geleert haben, oder wir den Endpunkt gefunden haben, währen fleißig immer neue Knoten expandiert werden.
Nun müssen wir uns noch die diversen Helferfunktionen anschauen. Das wäre im wesentlichen die Methode die uns den billigsten Knoten zurückliefert und die die uns alle Nachbarknoten besorgt.
Code:
Node* getCheapestNode(void)
{
//die liste ist leer
if(queue.empty())
return(NULL);
unsigned int index = 0;
int price = queue[0]->cost;
//Wir durchsuchen die gesamte Liste
for(unsigned int i = 0; i < queue.size(); i ++)
{
//Falls die Kosten des aktuellen Knoten kleiner sind als die des bisher besten, ist das nun unser bester!
if(queue[i]->cost < price)
{
index = i;
price = queue[i]->cost;
}
}
//Wir geben unsern so gefunden günstigsten Knoten zurück und löschen diesen aus der Arbeitskette!
//Falls man das vergisst, läuft man auch ne ganze Weile und findet auch nicht die optimale Lösung
Node* temp = queue[index];
queue.erase(queue.begin() + index);
return(temp);
}
vector<Node*> getAllNeighbors(Node* currentNode)
{
vector<Node*> temp;
Node* next = new Node;
next->parent = currentNode;
next->pos = currentNode->pos + position2d<int>(0,1)
// dann auch noch (0,-1), (1,0), (-1,0) das spare ich mir aber mal ;) dürfen aber nicht vergessen werden!
//Jetzt kommen wir zur Besonderheit von A*: Die Kosten ergeben sich aus der Entfernung von dem derzeitigen Knoten
//bis zum nächsten PLUS den bisherigen Wegkosten!
//getDistance(position2d<int> a, position2d<int> b) gibt die Entfernung von a und b via dem pythagoras zurück
next->cost = currentNode->cost + getDistance(currentNode->pos, next->pos);
//Wenn der Knoten bereits besucht wurde dürfen wir ihn nicht mehr hinzufügen!
if(nodeNotInVisited(next))
{
temp.push_back(next);
}
return(temp);
}
Nun haben wir in der while-schleife zwei Abbruchbedingungen. Einerseits wenn die Arbeitsschlange leer ist, dann haben wir keinen Weg (Knoten nicht erreichbar) oder wenn die Position des aktuellen Knotens gleich der des Endknotens ist, das heißt wir haben genau diesen Knoten gefunden und können abbrechen. So müssen wir aber noch den Wegrekonstruieren. Das geschiet folgendermaßen:
Code:
void restorePathFromNode(Node* currentNode)
{
vector<Node*> reversePath;
Node* temp = currentNode;
//Wir rufen einfach vom Endknoten her immer alle Parents auf. Der erste Parent, der NULL ergibt war unser Startpunkt,
//da deren Elternknoten als einziger mit NULL initialisiert wurde.
while(true)
{
if(temp == NULL)
break;
reversePath.push_back(temp);
temp = temp->parent;
}
//Nun haben wir die Reihenfolge, die wir gehen müssen rückwärts abgespeichert und müssen diese nur noch
//umdrehen
for(int i = (unsigned int) reversePath.size() - 1; i >= 0; i --)
{
path.push_back(reversePath[i]);
}
}
Also nochmal in kurz: A* hält sich alle Knoten in einer Liste. WIr beginnen zunächst mit einer Liste, die nur den Startknoten enthält. Wir überprüfen in jedem Schleifendurchlauf, ob der derzeitige Knoten, der jenige in unserer Arbeitsschlange queue mit den geringsten Wegkosten, unser gesuchte ist. Falls ja haben wir gewonnen. Falls nicht untersuchen wir alle Nachfolgerknoten. Falls diese nicht untersucht wurden. Berechnen wir die neuen Wegkosten in den Nachfolgerknoten und fügen sie sowohl unserer Arbeitskette queue hinzu als auch der schlange visited, damit wir wissen, dass wir diese nicht mehr untersuchen müssen. Und dann beginnen wir wieder von vorne. Die beiden Abbruchbedingungen können nur sein, dass die Liste leer ist, dann gibt es keinen Weg, oder dass der derzeitig billigste Knoten, der Endknoten ist. Et voila haben wir den Weg, den wir gesucht haben.
Ich hoffe man konnte helfen und falls es noch fragen gibt immer raus damit. Der source ist zum copy und paste übrigens nicht geeignet, da ich einige micro Funktionen nicht aufgeführt habe, da deren Funktionalität hoffentlich vom Namen her ableitbar waren
mfg heck
Anmelden
Registrieren
FAQ
Suche
...