A Start Algorithmus zur Wegfindung

boneghost

Hier habe ich versucht einen A Start Algorithmus programm geschrieben, nur leider weiß ich nicht genau wo der Fehler seinen soll, anscheint ist tritt da irgentwo ein Laufzeitfehler auf, ich würde mich freuen wenn jemand die fehlenden Codezeilen ergänzen könnte, oder hier ein fertiges leicht zu verstehenden algorithmus zur suche posten.

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

(editiert von vh)

ich kann den code nicht lesen

boneghost

ich hab
auf den Knopf als c++ code darstellen angeklickt ging aber nicht);
ich hoffe es kann doch einer lesen);

volkard

boneghost schrieb:

ich hab
auf den Knopf als c++ code darstellen angeklickt ging aber nicht);
ich hoffe es kann doch einer lesen);

schreib in eckigen klammen cpp drüber und in eckigen klammen /cpp drunter, dann klappts auch ohne knopf.

ui jetzt gehts doch;) also ihr habt keine ahnung was da falsch ist oder? oder wie man sonst so ein programm schreiben kann?

hm, frag doch mal im Spieleforum nach, die dürften sich mit Pathfinding häufiger beschäftigen...

Devil

Helium

Nur so 'ne Frage. Du meinst nicht zufällg den A-Stern Algorithmus (auch als A* notiert)?

A Start kenne ich nicht.

ja ich meine A Star, hab mich wohl verschrieben

volkard

threas ist umgezogen nach http://www.c-plusplus.net/forum/viewtopic.php?t=43047&highlight=