Denkanstoß gesucht ("verkettetes Labyrinth"/zusammenhängender Graph)



  • Ich hab so eine art zusammenhengenden Graphen, von jedem Knoten gehen maximal vier, minimal 1 KanteN aus. Das ganze soll ein Labyrinth darstellen.
    Beispiel:

    |---|
    |  #|
    |   |
    |---|
    

    '|' und '-' stellen Wände dar, '#' ein Hindernis. Als graph:

    +
    |
    +-+
    

    '+' soll ein Knoten sein, '-' und '|' Kanten.
    Im Code hab ich das in etwa so realisiert:

    struct node
    {
        node* left;
        node* right;
        node* front;
        node* back;
    };
    

    Nullzeiger bedeuten angrenzende Wände oder Hindernise...
    Das Problem ist jetzt die Ausgabefunktion: ich speichere einen Zeiger auf einen Knoten (links oben). Da es ein zusammenhängender Graph ist sind von ihm aus alle anderen Knoten zu erreichen. Nur weiß ich nicht wie...
    In diesem Beispiel ginge es, indem ich den Kanten nach rechts und unten folge...
    Aber wenn es so aussieht, habe ich ein Problem

    |-----|
    |  #  |
    |  #  |
    |     |
    |-----|
    

    Woher soll ich wissen, dass ich rechts unten wieder hoch gehen muss?



  • ness schrieb:

    Woher soll ich wissen, dass ich rechts unten wieder hoch gehen muss?

    Du meinst, weil Du mit ISO-Mitteln keine Ausgabezeile hochhüpfen kannst?

    Vorschlag: Zuerst ein zweidimensionales Feld erzeugen, dann die Karte da 'hineinmalen' und dann dieses Feld ausgeben.



  • Nullpointer für hindernis ist vielleicht auch nicht so geschickt oo



  • Daniel E. schrieb:

    Du meinst, weil Du mit ISO-Mitteln keine Ausgabezeile hochhüpfen kannst?

    Ne, weil ich nicht weiß ob ich hochhüpfen soll...

    life schrieb:

    Nullpointer für hindernis ist vielleicht auch nicht so geschickt oo

    Dessen bin ich mir jetzt auch bewusst, hab das design umgestellt...



  • Mit Breitensuche findest du das ganz leicht heraus.



  • ness schrieb:

    Daniel E. schrieb:

    Du meinst, weil Du mit ISO-Mitteln keine Ausgabezeile hochhüpfen kannst?

    Ne, weil ich nicht weiß ob ich hochhüpfen soll...

    eh?

    if (mynode.front != 0) {
      // huepf hoch!
    } else {
      // lauf nicht vor die wand ;-)
    }
    

    ness schrieb:

    life schrieb:

    Nullpointer für hindernis ist vielleicht auch nicht so geschickt oo

    Dessen bin ich mir jetzt auch bewusst, hab das design umgestellt...

    Kommt drauf an was du machen willst. Wenn du in jedem Algo erst prüfen musst ob eine Kante deines Graphs eine Kante ist oder nicht ist vielleicht auch nicht so geschickt.

    Ansonsten vlt wie Rindding meinte Breiten- oder Tiefensuche, alternativ evtl Union-Find auf einer Menge, |M| = Breite * Höhe.



  • Also, nur um das noch mal klar zu stellen mit dem Hochhüpfen: Es kann ja sein, dass die Stelle schon gezeichnet wurde...



  • du machst ein feld[x][y], initialisierst alles mit -1. später wollen wir überall eine 0 stehen haben wo eine wand ist und eine 1 wo ein weg ist. also gehen wir deinen graphen ähnlich wie bei einem binärbaum durch:

    printInArray( node *n, x = 0, y = 0 )
    {
      if( x > 0 && n->left != NULL && feld[x-1][y] == -1 )
      {
        feld[x-1][y] = 1;
        printInArray( n->left, x-1, y );
      }
      else if( x > 0 && n->left == NULL && feld[x-1][y] == -1 )
        feld[x-1][y] = 0;
    
      if( x < feldlaenge-1 && n->right != NULL && feld[x+1][y] == -1 )
      {
        feld[x+1][y] = 1;
        printInArray( n->right, x+1, y );
      }
      else if( x < feldlaenge-1 && n->right == NULL && feld[x+1][y] == -1 )
        feld[x+1][y] = 0;
    
      if( ..->front ) ..
      if( ..->back ) ..
    }
    

    alles was jetzt im feld noch -1 ist, ist nicht erreichbar.



  • finix schrieb:

    ness schrieb:

    life schrieb:

    Nullpointer für hindernis ist vielleicht auch nicht so geschickt oo

    Dessen bin ich mir jetzt auch bewusst, hab das design umgestellt...

    Kommt drauf an was du machen willst. Wenn du in jedem Algo erst prüfen musst ob eine Kante deines Graphs eine Kante ist oder nicht ist vielleicht auch nicht so geschickt.

    muss er ja eh. Hier muss er dann halt auf nullpointer prüfen..



  • life schrieb:

    finix schrieb:

    ness schrieb:

    life schrieb:

    Nullpointer für hindernis ist vielleicht auch nicht so geschickt oo

    Dessen bin ich mir jetzt auch bewusst, hab das design umgestellt...

    Kommt drauf an was du machen willst. Wenn du in jedem Algo erst prüfen musst ob eine Kante deines Graphs eine Kante ist oder nicht ist vielleicht auch nicht so geschickt.

    muss er ja eh. Hier muss er dann halt auf nullpointer prüfen..

    Naja, kommt halt drauf an ob sich der Aufwand lohnt, du brauchst pro node zusätzliches byte (oder eine virtuelle Methode), und falls du nicht trotzdem noch auf Nullpointer prüfen willst nochmal sizeof(node)*(2*h+2*b+4) bytes.



  • Fuer Baeume in Compilern etc. nimmt man m.E. am besten Rekursionen. Sollte auch hier funktionieren. Bevor Du einen Zweig gehst, markierst Du ihn, damit Du weisst, ob Du schonmal dagewesen bist. Dann kannst Du geschlossene Graphen parsen.

    class GraphNode {
       public:
       enum DIR { UP, DOWN, LEFT, RIGHT, NUMDIRS };
       GraphNode* branch[NUMDIRS];
       bool       here;
       // ...
       GraphNode( void ) { 
          for ( int i=0; i < NUMDIRS; ++i ) branch[i] = 0;
          here = false;
       }
       // ...
       void parseNode( void ) {
           if ( here ) return;
           here = true;
           for ( int i=0; i < NUMDIRS; ++i ) {
              if ( branch[i] ) branch[i]->parseNode();
           }
           here = false;    
       }
    

    Wenn sich's nur um Labyrinthe und nicht um eine Baum-Uebung dreht, dann kannst Du auch ein Array (Vektor), wie bereits vorgeschlagen, nehmen.

    Wen ich sowas programmiere, z.B. fuer 2D-Spiele, nehm ich immer eine Bitmap, in der nur die Waende markiert sind. Kollisionspruefungen sind damit einfach und schnell.

    Falls es sich nur darum geht, Graphen und Baeume zu implementieren, wuerde ich Dir vorschlagen, dass Du Dich mal mit Rekursionen auseinandersetzt -- sehr praktische Angelegenheit! 🙂


Anmelden zum Antworten