Stack Overflow bei meinem Maze-Generator



  • Hey Leute,
    also ich habe einen Maze-Generator programmiert, der solche Mazes machen kann (http://puu.sh/cIbJh/5009a64c0c.png). Nun bekomme ich aber fast immer bei der Generierung nach der Hälfte einen Stack Overflow. Ich benutze dafür den Recursive Backtracking Algorithm, dass heißt ich speichere ein paar tausend Listen, liegt das vllt daran?

    MfG



  • Vermutlich liegts an der Rekursion, ja. Kannst du die nicht irgendwie weniger machen oder iterativ nachprogrammieren? Oder versuchen den Stackspace pro Aufruf zu verringern.



  • Hier mal der Code der Rekursiv-Funktion, ist mein erstes größeres Projekt in C++ deswegen weiß ich leider nicht so genau wie man das macht mit dem Stackspace 😕

    void PArray::next(int x, int y)
    {
    	pArray[x][y] = 2;
    	//Sleep(100);
    	//writeIntoTexture();
    	//render();
    	count++;
    	std::cout << count << std::endl;
    	while (unvNeigh(x, y) == true)
    	{
    			std::list<int> *liste = NULL;
    			liste = new std::list<int>;
    			if (pArray[x+2][y] == 1) { liste->push_back(0);}
    			if (pArray[x-2][y] == 1) { liste->push_back(1);}
    			if (pArray[x][y+2] == 1) { liste->push_back(2);}
    			if (pArray[x][y-2] == 1) { liste->push_back(3);}
    
    			//std::cout << "Listengröße nach dem Erstellen: " << liste.size() << std::endl;
    
    			std::list<int>::iterator *it = new std::list<int>::iterator;
    			while(liste->size() > 0)
    			{
    				int rand_zahl = rand() % liste->size();
    				//srand(rand());
    
    				*it = liste->begin();
    				std::advance(*it, rand_zahl);
    
    				if ((**it) == 0)
    				{
    					pArray[x+1][y] = 2;
    					liste->erase(*it);
    					next(x+2, y);
    					//giveOut();
    					updateListe(liste, x, y);
    					//giveOut();
    					//std::cout << "Listengroesse: " << liste.size() << std::endl;
    				}
    				else if (**it == 1)
    				{
    					pArray[x-1][y] = 2;
    					liste->erase(*it);
    					next(x-2, y);
    					//giveOut();
    					updateListe(liste, x, y);
    					//giveOut();
    					//std::cout << "Listengroesse: " << liste.size() << std::endl;
    				}
    				else if (**it == 2)
    				{
    					pArray[x][y+1] = 2;
    					liste->erase(*it);
    					next(x, y+2);
    					//giveOut();
    					updateListe(liste, x, y);
    					//giveOut();
    					//std::cout << "Listengroesse: " << liste.size() << std::endl;
    				}
    				else if (**it == 3)
    				{
    					pArray[x][y-1] = 2;
    					liste->erase(*it);
    					next(x, y-2);
    					//giveOut();
    					updateListe(liste, x, y);
    					//giveOut();
    					//std::cout << "Listengroesse: " << liste.size() << std::endl;
    				}		
    			}
    			delete it;
    			delete liste;
    			liste = NULL;
    		}
    }
    


  • Ist bei dem Algorithmus sichergestellt, dass die Grenzen des Array nicht überschritten werden?
    Da scheinen Pfade per Zufallszahl abgelaufen zu werden. Jeder Schritt ist eine Rekursionsebene. Wie lang kann ein Pfad werden?

    List und insbesondere Iterator mit new? Ist das ein Versuch, Stackspace einzusparen oder machst du Java?



  • void PArray::next(int x, int y)
    {
    	assert(x >= 0 && x < sizeX);
    	assert(y >= 0 && y < sizeY);
    
        pArray[x][y] = 2;
    
        count++;
    
        while (unvNeigh(x, y)) // == true ist redundant
    	{
    		std::list<int> liste;
    
    		if (pArray[x+2][y] == 1) { liste->push_back(0);}
    		if (pArray[x-2][y] == 1) { liste->push_back(1);}
    		if (pArray[x][y+2] == 1) { liste->push_back(2);}
    		if (pArray[x][y-2] == 1) { liste->push_back(3);}
    
    		while(liste->size() > 0)
    		{
    			auto it = liste->begin();			
    			std::advance(it, rand() % liste->size());
    
    			if (*it == 0)
    			{
    				assert(x<sizeX-1);
    				pArray[x+1][y] = 2;
    				liste.erase(it);
    				next(x+2, y);
    				updateListe(&liste, x, y); // hier und beid en anderen updateListe Methoden hab das nur aus 'historischen' gründen mit dem Zeiger behalten, sollte man eher zu ner Referenz machen
    			}
    			else if (*it == 1)
    			{
    				assert(x>0);
    				pArray[x-1][y] = 2;
    				liste.erase(it);
    				next(x-2, y);
    				updateListe(&liste, x, y);
    			}
    			else if (*it == 2)
    			{
    				assert(y<sizeY-1);
    				pArray[x][y+1] = 2;
    				liste.erase(it);
    				next(x, y+2);
    				updateListe(&liste, x, y);
    			}
    			else if (*it == 3)
    			{
    				assert(y>0);
    				pArray[x][y-1] = 2;
    				liste.erase(it);
    				next(x, y-2);
    				updateListe(&liste, x, y);
    			}
    			else
    			{
    				assert(false && "Must not reach here!");
    			}
    		}
    	}
    }
    

    So ungefähr sähe schonmal ein Schritt in die Richtige Richtung aus. Wenn etwas grundlegendes nicht passt, gibts ne Fehlermeldung.



  • Gibt es ueberhaupt einen Grund fuer die Liste? Insgesamt waeren std::vector und std::deque naemlich deutlich performanter.



  • Rekursionen sollte sich eigentlich immer durch einen Software Stack ersetzen lassen - std::stack.
    Bitte verbessert mich sollte ich falsch liegen. 🙂



  • wie meine vorposter schon gesagt haben ist deque / vector (und somit auch stack, der standardmaessig std::vector adaptiert) performanter als eine liste. grund: deine liste fuehrt bei jedem hinzufuegen / loeschen eines elements ein tatsaechlicher new- / delete-aufruf durch.

    wieso du assert statt throw verwendest ist mir schleierhaft. kein grund das programm zu vernichten nur weil die funktion nicht richtig aufgerufen werden konnte.



  • Ethon schrieb:

    Bitte verbessert mich sollte ich falsch liegen. 🙂

    Wieso bist du dir nicht sicher, dass sie stimmt?



  • Bashar schrieb:

    Ethon schrieb:

    Bitte verbessert mich sollte ich falsch liegen. 🙂

    Wieso bist du dir nicht sicher, dass sie stimmt?

    Weil ich kein guter Mathematiker bin. Wie sieht es zB mit der Ackermann Funktion aus?



  • fate schrieb:

    wieso du assert statt throw verwendest ist mir schleierhaft. kein grund das programm zu vernichten nur weil die funktion nicht richtig aufgerufen werden konnte.

    Weil das keine Fehler sind die je nach Konfiguration oder je nach Eingabe auftreten können, sondern weil das Programmierfehler sind. Und die dürfen/sollen nicht weiterleben.

    Weist du überhaupt was assert macht und wofür es da ist?



  • Ethon schrieb:

    Bashar schrieb:

    Ethon schrieb:

    Bitte verbessert mich sollte ich falsch liegen. 🙂

    Wieso bist du dir nicht sicher, dass sie stimmt?

    Weil ich kein guter Mathematiker bin.

    Informatiker. Mathematiker wissen über solche Dinge nicht unbedingt besser Bescheid als Durchschnittsmenschen von der Straße.

    Mal zwei Erklärungsansätze:

    1. Alles, was ein Computer berechnen kann, kann auch eine Turingmaschine berechnen. Und die hat keine Rekursion, sie hat nichtmal Funktionen.
    2. Du kannst einen Emulator für eine CPU schreiben. Die CALL- und RET-Befehle sind ja nicht magisch, sondern pushen/poppen auch nur den Stack und verändern den Programmzähler.

    Das heißt nicht unbedingt, dass es einfach ist, eine iterative Form zu finden, aber es zeigt, dass es möglich sein muss.


  • Mod

    aber es zeigt, dass es möglich sein muss.

    Ja, aber nur garantiert mit polynomialem Overhead.



  • Okay cool habs hinbekommen mit std::vector und std::pair<int, int> um die Position zu speichern, das ist die die Funktion:

    void PArray::nextIterative()
    {
    	std::vector<std::pair<int, int>> pos;
    	std::pair<int, int> paar (2,2);
    	pos.push_back(paar);
    
    	while (pos.size() > 0)
    	{
    		int x = GetIntFromList(&pos, 0, 0);
    		int y = GetIntFromList(&pos, 0, 1);
    		pArray[x][y] = 2;
    		//writeIntoTexture();
    		//render();
    		count++;
    
    		pRenderWindow->setTitle("Lps: " + std::to_string(floor(1/GetFrameTime() + 0.5)));
    
    		std::list<int> *liste = NULL;
    		liste = new std::list<int>;
    		if (pArray[x+2][y] == 1) { liste->push_back(0);}
    		if (pArray[x-2][y] == 1) { liste->push_back(1);}
    		if (pArray[x][y+2] == 1) { liste->push_back(2);}
    		if (pArray[x][y-2] == 1) { liste->push_back(3);}
    
    		std::list<int>::iterator *it = new std::list<int>::iterator;
    		if (liste->size() > 0)
    			{
    				int rand_zahl = rand() % liste->size();
    				//srand(rand());
    
    				*it = liste->begin();
    				std::advance(*it, rand_zahl);
    
    				if ((**it) == 0)
    				{
    					pArray[x+1][y] = 2;
    					std::pair<int, int> p (x+2,y);
    					pos.push_back(p);
    				}
    				else if (**it == 1)
    				{
    					pArray[x-1][y] = 2;
    					std::pair<int, int> p (x-2,y);
    					pos.push_back(p);
    				}
    				else if (**it == 2)
    				{
    					pArray[x][y+1] = 2;
    					std::pair<int, int> p (x,y+2);
    					pos.push_back(p);
    				}
    				else if (**it == 3)
    				{
    					pArray[x][y-1] = 2;
    					std::pair<int, int> p (x,y-2);
    					pos.push_back(p);
    				}		
    			}
    		else
    		{
    			pos.pop_back();
    		}
    	}
    }
    

    Verbesserungsvorschläge für die Performance?



  • Sorry für OT:

    Skym0sh0 schrieb:

    fate schrieb:

    wieso du assert statt throw verwendest ist mir schleierhaft. kein grund das programm zu vernichten nur weil die funktion nicht richtig aufgerufen werden konnte.

    Weil das keine Fehler sind die je nach Konfiguration oder je nach Eingabe auftreten können, sondern weil das Programmierfehler sind. Und die dürfen/sollen nicht weiterleben.

    Weist du überhaupt was assert macht und wofür es da ist?

    Naja, ein abort ist manchmal nicht das was man möchte: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2014/n4135.pdf (Insbesondere Abschnitt 4.2)



  • Bashar schrieb:

    Ethon schrieb:

    Bashar schrieb:

    Ethon schrieb:

    Bitte verbessert mich sollte ich falsch liegen. 🙂

    Wieso bist du dir nicht sicher, dass sie stimmt?

    Weil ich kein guter Mathematiker bin.

    Informatiker. Mathematiker wissen über solche Dinge nicht unbedingt besser Bescheid als Durchschnittsmenschen von der Straße.

    Mal zwei Erklärungsansätze:

    1. Alles, was ein Computer berechnen kann, kann auch eine Turingmaschine berechnen. Und die hat keine Rekursion, sie hat nichtmal Funktionen.
    2. Du kannst einen Emulator für eine CPU schreiben. Die CALL- und RET-Befehle sind ja nicht magisch, sondern pushen/poppen auch nur den Stack und verändern den Programmzähler.

    Das heißt nicht unbedingt, dass es einfach ist, eine iterative Form zu finden, aber es zeigt, dass es möglich sein muss.

    Ich bin Informatiker und finde trotzdem Mathematiker weit schlauer was viele theoretische Dinge angeht. Nachdem ich betrunken bin spare ich mir aber mal weitere Aussagen.



  • Ethon schrieb:

    Ich bin Informatiker und finde trotzdem Mathematiker weit schlauer was viele theoretische Dinge angeht. Nachdem ich betrunken bin spare ich mir aber mal weitere Aussagen.

    In der theoretischen informatik setzt man sich aber mit solchen Dingen viel auseinander, waehrend die Mathematik andere Gebiete, aber mit gleichen Methoden bearbeitet.
    Die praktische Informatik geht aber ganz anders vor und arbeitet eher mit Erfahrungen und Messungen statt theoretischen Modellen.


Log in to reply