A Start Algorithmus zur Wegfindung
-
Ich habe hier ein problem mit diesem A Star Algorithmus den versucht hab nachzumachen, aber leider funktioniert dieser nicht ganz hat jemand eine Ahnung wo der Fehler liegt? oder hat jemand sonst noch einen A Star code der einfach geschrieben ist und auch funktioniert;) würde mich über jede hilfe freuen
struct PFPoint { int x,y; }; /////////////////////////Pathfinding Klasse /////////// class Pathfinding { private: /////////////////Knotenpunkt Klasse //////////// class Knotenpunkte { private: PFPoint koordinate; int schaetzweg; Knotenpunkte *Ursprungspunkt; public: Knotenpunkte(PFPoint koordinate,int schaetzweg,Knotenpunkte *Ursprungspunkt) { this->koordinate=koordinate; this->schaetzweg=schaetzweg; this->Ursprungspunkt=Ursprungspunkt; } Knotenpunkte(PFPoint Start,int schaetzweg) { koordinate=Start; this->schaetzweg=schaetzweg; } PFPoint returnkoordinaten(void) { return koordinate; } Knotenpunkte * returnUrsprungspunkt(void) { return(Ursprungspunkt); } void setUrsprungspunkt(Knotenpunkte *Ursprungspunkt) { this->Ursprungspunkt=Ursprungspunkt; } int returnschaetzweg(void) { return(schaetzweg); } }; //////////////////////////////////////////////// ///////////Private////////////////////////////// PFPoint Start,End; Knotenpunkte *Aktuknotenpunkt; /////////////////////////////////////////////diese Variable speichert die aktuell benutze variable int unbearbeiteteKnotenanzahl; int bearbeiteteKnotenanzahl; vector<Knotenpunkte *> unbearbeiteteKnoten; vector<Knotenpunkte *> bearbeiteteKnoten; int schaetzweg; int mapbreite; int maphoehe; bool *Knotenpunkt; bool *map; int *weg; public: Pathfinding(PFPoint,PFPoint,int,int,bool *); int * findthewaynow(void); /// }; Pathfinding::Pathfinding(PFPoint Start,PFPoint End,int mapbreite,int maphoehe,bool *map) { this->Start=Start; this->End=End; this->mapbreite=mapbreite; this->maphoehe=maphoehe; this->map=map; unbearbeiteteKnotenanzahl=0; bearbeiteteKnotenanzahl=0; unbearbeiteteKnotenanzahl++; unbearbeiteteKnoten.resize(unbearbeiteteKnotenanzahl); schaetzweg=abs(Start.x-End.x)+abs(Start.y-End.y); Knotenpunkte *temp=new Knotenpunkte(Start,schaetzweg); unbearbeiteteKnoten[unbearbeiteteKnotenanzahl-1]=temp; unbearbeiteteKnoten[unbearbeiteteKnotenanzahl-1]->setUrsprungspunkt(temp); } int * Pathfinding::findthewaynow(void) { int Knoten=0; PFPoint t; PFPoint temppoint; while(unbearbeiteteKnotenanzahl>=1) // Schleife bis keine Knotenpunkte in der Liste sind { for(int i=0;i<unbearbeiteteKnotenanzahl;i++) //Bester Knotenpunkt als Aktuknotenpunkt inizialiesieren { if(unbearbeiteteKnotenanzahl==1) Aktuknotenpunkt=unbearbeiteteKnoten[i]; else if(unbearbeiteteKnoten[i]->returnschaetzweg()<unbearbeiteteKnoten[i+1]->returnschaetzweg()); Aktuknotenpunkt=unbearbeiteteKnoten[i]; } t=Aktuknotenpunkt->returnkoordinaten(); if(t.x==End.x&&t.y==End.y) // Wenn der beste Knotenpunkt gleich der gesuchte Punkt abbrechen break; for(int i=(t.x-1);i<=(t.x+1);i++) { for(int a=(t.y-1);a<=(t.y+1);a++) { temppoint.x=i; temppoint.y=a; schaetzweg=abs(temppoint.x-End.x)+abs(temppoint.y-End.y); Knotenpunkte *tempp=new Knotenpunkte(temppoint,schaetzweg,Aktuknotenpunkt); Knoten++; unbearbeiteteKnoten.resize(unbearbeiteteKnotenanzahl+Knoten); unbearbeiteteKnoten[unbearbeiteteKnotenanzahl-1]=tempp; // Setze neu erstellten Knotenpunkt auf die unbearbeitete Liste delete tempp; } unbearbeiteteKnotenanzahl+=Knoten; } }//while(unbearbeiteteKnotenanzahl>=1) cout << "close"; return(weg); }
-
Ich mache auch gerade mal nebenbei bissel einen A Star. Was mir jetzt beim ersten mal durchgehen aufgefallen ist (bin nicht gut in anderen Quelltexten unterwegs) ist dein schätzweg. Die Formal an sich ist ja ok, aber soweit ich weis sollte in die Wegberechnung nicht nur der schätzweg einfliesen, sonder auch die Entfernung zum Start. Is bissel blöd beschrieben ich versucs mit Beispiel. Alle knoten die vom Starknoten erstellt werden erhalten +1 auf den Schätzweg. Alle Knoten die von den Childknoten des Startknodens erstellt wurden erhalten +2 auf den Schätzweg. Die Childs davon +3 usws. So ist mir das zumindest bekannt.
2. Das habe ich jetzt nicht so genau KOntrolliert, weil mirs zuviel Quelltext war aber das wichtigste bei der Sache ist eine Regel. Ein Knotenpunkt mit der gleichen Koordinate darf nie zweimal erstellt werden, ein Knotenpunk darf niemals auserhalb der map erstellt werden und ein Knotenpunkt darf auch nicht auf nicht zugänglichen Objekten erstellt werden.
Und ich hab bei dir nirgenswo was gesehen wo vermerkt wird welcher Knoten bereits abgearbeitet wurde und welche nicht und wie diese vergleichen werden. Kanns abre auch übersehen haben.
-
stimmt daran kann es liegen, ich hab extra ne variable dafür eingebaut aber nicht benutzt,) bool *Knotenpunkt , ich versuch mal obs dann klappt
du hast aber nicht zufällig nen code der funktioniert=?
-
Doch aber ich arbeite noch dran, soll noch bissel schneller werden.
Im moment läuft (bzw. wird es laufen) über einer AVLBaum, der die noch nicht abgearbeiten Knotenpunkte enthält (das optimiert die Suche nach dem Knotenpunkt mit der kleinsten Entfernung und ein Vector² der mir die Eigenschaften der Map verwaltet und einem Vector² der die abgearbeiten knotenpunkte aufnimmt. Is aber noch net ganz fertig - Urlaub geht vor :).
Italien ich komme.
-
Bigwill-u schrieb:
Im moment läuft (bzw. wird es laufen) über einer AVLBaum, der die noch nicht abgearbeiten Knotenpunkte enthält (das optimiert die Suche nach dem Knotenpunkt mit der kleinsten Entfernung
dann vergiß multithreading nicht.
-
Volkard, das versteh ich nicht, wozu brauch ich da Multithreading?
War das ernst gemeint oder willst du mich nur auf die Schippe nehmen?
-
Bigwill-u schrieb:
Volkard, das versteh ich nicht, wozu brauch ich da Multithreading?
War das ernst gemeint oder willst du mich nur auf die Schippe nehmen?schippe.
multithreading ist hier noch ein wenig deplazierter als ein avl-baum. ein heap ist die struktur, die zum abwechselnden "beliebig einfügen" und "kleinsten rausnehmen" da ist.
-
Danke für die Info aber dann sag das das nächste mal doch bitte gleich so.
Aus so einer Multithreadingbemerkung kann ich nix lernen, wobei ich mir natürlich denken konnte, dass das Ironie werden sollte..Ich hab bevor ich mit dem AVL Baum angefangen habe auch mit einem Heap gearbeitet. Nur habe ich mir dann gedacht, wenn ich immer den kleinsten wieder entnehme, wird irgendwann die linke Seite des Heaps (wos immer kleiner wird) leer werden , also bis zum Root hoch und dann muss ich das ganze sowieso umhängen. Also wollte ichs dann gleich mit einem AVL Baum probieren. Falls das nicht schneller ist kann ich immer noch den Heap benutzen. Schließlich lernt man ausm probieren.
-
Bigwill-u schrieb:
Ich hab bevor ich mit dem AVL Baum angefangen habe auch mit einem Heap gearbeitet. Nur habe ich mir dann gedacht, wenn ich immer den kleinsten wieder entnehme, wird irgendwann die linke Seite des Heaps (wos immer kleiner wird) leer werden , also bis zum Root hoch und dann muss ich das ganze sowieso umhängen.
der heap kann ständig ballanciert gehalten werden. beim heap gilt ja nur: kinder sind größer als der papa.
und dann paßt er prima in ein array rein. man sagt einfach, die kinder von arr[i] stehen an arr[2*i] und arr[2*i+1]. lücken müssen im array nicht entstehen, man füllt immer zuerst was ins linke und dann erst ins rechte kind. dadurch ist der heap auch noch fein platzsparend.#ifndef VHLIB_HEAP_H #define VHLIB_HEAP_H #pragma once #include <assert.h> /*template<class T> void swap(T &a,T &b) { T tmp(a); a=b; b=tmp; };*/ template<class T> class DefaultComparator { public: bool lessThan(const T &a,const T &b) const { return a<b; }; }; template<class T> class Heap {//Ein Heap ist ein Binõrbaum mit der Bedingung, da▀ jeder //Knoten kleinergleich seinen beiden Kindern (falls //vorhanden) ist. Diese Implementierung als Array //garantiert au▀erdem, da▀ der Baum ballanciert ist. //Einf³gen eines beliebeigen Elements und Ausf³gen //des kleinsten haben nur logarhitmischen Zeitbedarf. //Weil die Integritõtsbedingung schwõcher als beim //normalen Binõrbaum ist, ist der Heap auch ein wenig //schneller. private: int size; T *data; int maxSize; DefaultComparator<T> comparator; Heap &operator=(const Heap &h); public: Heap(int s=300) { data=new T[maxSize=s]; size=0; }; Heap(const Heap &h) { size=h.size; maxSize=h.maxSize; data=new T[maxSize]; for(int i=0;i<size;++i) data[i]=h.data[i]; }; ~Heap(void) { delete[] data; }; void flush() { while(!isEmpty()) pop(); }; operator bool(void) const { return size!=0; }; void grow() { maxSize=maxSize*3/2; T *oldData=data; data=new T[maxSize]; for(int i=0;i<size;++i) data[i]=oldData[i]; delete[] oldData; }; void push(const T &t) { if(size>=maxSize) grow(); int pos=size++; //Ganz hinten einf³gen data[pos]=t; while(comparator.lessThan(data[pos],data[pos/2])) {//Solange ich kleiner als mein Papa bin, darf ich //ihn verdrõngen. Spõtestens beim ersten Element //h÷rt die Schleife auf, weil es sein eigener Papa //ist. swap(data[pos/2],data[pos]); pos/=2; }; }; const T &peek(void) const { return data[0]; }; void pop() { assert(size>0); if(--size) { int p=1,c1,c2; data[0]=data[1]; while(c1=p*2,c2=c1+1,c1<size) {//Wenn der Papa verschwindet, dann mu▀ das kleinere //Kind seinen Platz einnehmen, dessen kleineres //Kind seinen, solange, bis jemand keine Kinder //mehr hat if(comparator.lessThan(data[c2],data[c1])) c1=c2; data[p]=data[c1]; p=c1; }; //Und in die L³cke wird das letzte Element ganz //normal eingef³gt. data[p]=data[size]; while(comparator.lessThan(data[p],data[p/2])) { swap(data[p/2],data[p]); p/=2; }; }; }; }; #endif
-
Danke für die ausfrlichen Infos. ich werd mir das dann irgendwann nächste Woche an der ital. Adria mal mit zu Gemüte führen. Wenn mir die Sonne nicht ganz den Verstand vernebelt.