Depth-First Search

ja, das habe ich gemacht.

Jester

Also, Anzahl Knoten reicht als obere schranke für die stackgröße. Wenn das zu Problemen führt, dann liegt das an der Implementierung. Um dir da weiterzuhelfen müßtest du allerdings ein paar mehr Infos rausrücken. Ich hab nicht vor den fehler jetzt mittels ja-nein-fragen zu erraten.

#define maze_width 16
#define maze_height 12

int walls_all_up  ( int a ); // rückgabe bool character 1: all walls are up 0, at least one wall is not up.
int random ( int from, int to );
int break_wall_north ( int* a );
int break_wall_south ( int* a );
int break_wall_east ( int* a );
int break_wall_west ( int* a );

void create_maze_test(void)
{
    int i, j, k, x, y, visited;
    int maze [ maze_width * maze_height ] = {0}; // speichert die labyrinth daten
    int stack [ 4  * maze_width * maze_height ] = {0}; // create a CellStack (LIFO) to hold a list of cell location
	int total = maze_width * maze_height; // set TotalCells = number of cells in grid

    for( i = 0;  i < total; i++ )
		maze[i] = 0xF; // all walls up

    srand((unsigned)time(NULL));
    x = random (0, maze_width-1);
    y = random (0, maze_height-1);
    j = y * maze_width + x; // choose a cell at random and call it CurrentCell
    visited = 1; // set VisitedCells = 1

    while ( visited < total ) // while VisitedCells < TotalCells
    {
        int neighbour[4];
        int xn, yn, index;
        k = 0;
        if ( walls_all_up ( maze [ y * maze_width + x + 1 ] ))
			neighbour[k++] = y * maze_width + x + 1;
        if ( walls_all_up ( maze [ y * maze_width + x - 1 ] ))
			neighbour[k++] = y * maze_width + x - 1;
        if ( walls_all_up ( maze [ ( y + 1 ) * maze_width + x ] ))
			neighbour[k++] = ( y + 1 ) * maze_width + x;
        if ( walls_all_up ( maze [ ( y - 1 ) * maze_width + x ] ))
			neighbour[k++] = ( y - 1 ) * maze_width + x;

        if ( k )
        {
            if ( k > 1 )
				index = neighbour [ random ( 0, k-1 ) ];
            else
				index = neighbour [ 0 ];

            xn = index % maze_width, yn = (index-xn)/maze_width;
            if ( xn > x )
            {
                break_wall_east ( &maze [ y * maze_width + x ] );
                break_wall_west ( &maze [ yn * maze_width + xn ] );
            }
            else if ( xn < x )
            {
                break_wall_west ( &maze [ y * maze_width + x ] );
                break_wall_east ( &maze [ yn * maze_width + xn ] );
            }
            else if ( yn > y )
            {
                break_wall_south ( &maze [ y * maze_width + x ] );
                break_wall_north ( &maze [ yn * maze_width + xn ] );
            }
            else
            {
                break_wall_north ( &maze [ y * maze_width + x ] );
                break_wall_south ( &maze [ yn * maze_width + xn ] );
            }

            stack[i++] = y * maze_width + x; // push index on stack
            x = xn, y = yn, visited++;
        }
        else
        {
            k = stack[--i]; // pop the most recent cell entry off the CellStack
            x = k % maze_width, y = (k-x)/maze_width; // make it CurrentCell
        }
    }
}

wie kann einer allein nur soo doof/blind sein?
hab vergessen i = 0 zu setzten.
kann geschlossen werden, danke.

Jester

Dann passt ja alles. Trotzdem noch ein paar tips zum code.

Statt dir die walls zu merken, kannst du einfach ein bool-feld mit besucht/nicht besucht verwenden. Das ist absoluter standard.
statt mit x und xn zu hantieren, arbeite mehr mit dem stack. Lege anfangs den startknoten auf den Stack. Die Schleife geht dann so:

solange stack nicht leer:
a) Lies obersten knotem vom stack (drauf lassen!)
b) hat dieser Knoten noch unbesuchte Nachbarn, so wähle einen davon, markiere ihn als besucht und lege ihn oben auf den stack
C) anderenfalls entferne den obersten knoten vom stack

Damit brauchst du weniger Variablen und hast einen klarere kontrollfluß. Wenn du stattdessen mal irgendwann eine breitensuche haben willst, ersetzt du den stack durch ne queue und du bist fertig.

Zuguterletzt, würde ich das Nachbarn finden rausziehen in eine eigene funktion, u d die random-Fkt. So umbauen, dass die sie auch bei from=to funktioniert.

Jester schrieb:

statt mit x und xn zu hantieren, arbeite mehr mit dem stack. Lege anfangs den startknoten auf den Stack. Die Schleife geht dann so:

naja, die x und y werte brauche ich ja, um an die nachbarn ranzukommen, da komme ich nicht drum herum sie zu benutzen.
die random funktion kann auch from = to verarbeiten aber ich wollte mir den sinnlosen aufruf sparen.

irgendwie doof, wegen eines so banalen fehlers das forum vollzuposten, aber ich habe die letzten wochen zu viele stunden am pc verbracht und dann den bekannten wald vor lauter bäumen nicht gesehen.

lg

Jester

~2deep schrieb:

Jester schrieb:

statt mit x und xn zu hantieren, arbeite mehr mit dem stack. Lege anfangs den startknoten auf den Stack. Die Schleife geht dann so:

naja, die x und y werte brauche ich ja, um an die nachbarn ranzukommen, da komme ich nicht drum herum sie zu benutzen.

Ja, aber wenn du dafür lokale variablen nimmst, die du vom stack runter liest, dann hast du deutlich weniger variablen, die den Gesamtablauf steurn und bist dadurch eeniger fehleranfällig. Dann wird auch die struktur einer DFS im Code klarer erkennbar. Da muß man nämlich imo grad schon genau hinschaun. Wenn du dann noch std::stack benutzt (oder deinen eigenen stack mit fester größe aber coolem interface baust), kann dir das was dir hier passiert ist, nicht mehr passieren.

Der funktionsaufruf für random wird bestimmt geinlined

Jester schrieb:

Dann wird auch die struktur einer DFS im Code klarer erkennbar. Da muß man nämlich imo grad schon genau hinschaun. Wenn du dann noch std::stack benutzt (oder deinen eigenen stack mit fester größe aber coolem interface baust), kann dir das was dir hier passiert ist, nicht mehr passieren.

eine index-variable wie int i brauche ich hin und wieder auch wenn ich std:stack oder ein cooles selbstgeschriebenes interface benutze.
im prinzip gebe ich dir aber recht und ich habe auch eine eigenes cooles und universelles stack modul in c für beliebige datentypen.
hätte ich es gleich benutzt, dann hätte ich mir diese peinlichkeit hier vllt sparen können
ich probiere aber neue dinge gern ohne unnötigen ballast aus...

Jester schrieb:

Ja, aber wenn du dafür lokale variablen nimmst, die du vom stack runter liest, dann hast du deutlich weniger variablen, die den Gesamtablauf steurn und bist dadurch eeniger fehleranfällig.

da kann ich dir gerade echt nicht folgen. die varialbe maze, x, xn etc. sind doch alle schon lokal in der funktion create_maze_test. oder meinst du das so, dass jedes array element auf dem stack seine eigenen x- und y-werte speichert?
dann würde ich aber die nachbarn auch irgendwie per koordinaten etc. berechnen müssen

Jester

Ja, die sind lokale variablen. Aber irgendwie halt auch nicht. Du benutzt sie eher wie globale variablen. Ich würde die in die schleife reinschieben und auch das i nicht mehrfach benutzen, sondern jeweils da anlegen (und initialisieren) wo ichs brauche.

Der aktuelle zustand der dfs besteht bei dir aus stack, walls-feld, x und y. Ich schlage vor, das auf stack und walls-feld zu reduzieren. Wegen mir speicher die x- und y- koordinaten auf den stack, oder berechne die koordinaten aus dem Index, das ist nicht wirklich der Punkt. Imo ost der. Ode für das was er tut zu kompliziert.

btw, wie fängst du ab, dass die suche oben / unten aus dem feld rausläuft, bzw. Man links rausgeht und ne zeile höher rechts wieder reinkommt?

Jester schrieb:

Der aktuelle zustand der dfs besteht bei dir aus stack, walls-feld, x und y. Ich schlage vor, das auf stack und walls-feld zu reduzieren.

gut, die berechnung des index könnte ich auslagern, dann hätte ich das x und das y eben in einer anderen funktion drin.

Jester schrieb:

btw, wie fängst du ab, dass die suche oben / unten aus dem feld rausläuft, bzw. Man links rausgeht und ne zeile höher rechts wieder reinkommt?

das macht ne extra funktion, die das prüft, hatte ich zur vereinfachung weggelassen.