Laden...

Irrgartengenerator: StackOverflow

Erstellt von m0rius vor 14 Jahren Letzter Beitrag vor 14 Jahren 1.574 Views
m0rius Themenstarter:in
1.002 Beiträge seit 2007
vor 14 Jahren
Irrgartengenerator: StackOverflow

Hallo,

ich schreibe gerade an einer Anwendung, die zur Erstellung von Irrgärten regen Gebrauch von Rekursion macht und damit entsprechend viel Speicher im Stack benötigt. Ab einer gewisseen Größe bzw. Zellenanzahl ist Schluss. Natürlich könnte ich eine Art Obergrenze festlegen, aber die müsste relativ niedrig liegen, um die StackOverflowException zu vermeiden ...

Ist eine iterative Lösung wesentlich speichersparender als die rekursive?
Edit: Oder ist der Code im folgenden Post ungünstig in Hinblick auf Rekursion geschrieben?

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

m0rius Themenstarter:in
1.002 Beiträge seit 2007
vor 14 Jahren

Hier noch ein Screenshot und der Code der rekursiven Methode (hoffe, er ist dennoch verständlich).

/// <summary>
/// Expands the way from a given cell.
/// </summary>
private void Expand(Cell currentCell)
{
    if (_visitedCells >= TotalCells)
    {
        return;
    }
            
    Cell neighborCell = null;
    int[] directions = RandomHelper.GetDirections();
    bool connected = false;

    for (int index = 0; index < directions.Length; index++)
    {
        neighborCell = GetNeighborCell(currentCell, directions[index]);

        if (neighborCell != null && !neighborCell.Visited)
        {
            currentCell.Connect(neighborCell);
            connected = true;

            _visitedCells++;
            _cellStack.Push(neighborCell);

            break;
        }
    }

    if (!connected)
    {
        neighborCell = _cellStack.Pop();
    }

    Expand(neighborCell);
}

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

Gelöschter Account
vor 14 Jahren

du könntest die rekursive version zu einer flachen do-while schleife umbauen.

m0rius Themenstarter:in
1.002 Beiträge seit 2007
vor 14 Jahren

Hallo JAck30lena,

genau, das war meine Überlegung, aber ist diese Lösung wesentlich speichersparender?

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

Gelöschter Account
vor 14 Jahren

um speicher geht es hierbei nicht. es geht um den stack und wenn du rekursion vermeidest, hast du auch keine probleme mit dem stack.

5.657 Beiträge seit 2006
vor 14 Jahren

Es gibt die Möglichkeit, mit dem Stack-Objekt aus dem Framework zu arbeiten: Logikproblem beim Füllen einer fläche

Christian

Weeks of programming can save you hours of planning

m0rius Themenstarter:in
1.002 Beiträge seit 2007
vor 14 Jahren

Hallo JAck30lena,

gut, dann schreibe ich halt eine iterative Variante. Danke!

Hallo MrSparkle,

ich verwende bereits Stack<Cell>!

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

Gelöschter Account
vor 14 Jahren

noch etwas um eine verwechslung auszuschließen. ich sprach die ganze zeit vom callstack und nicht von der stackliste.

5.657 Beiträge seit 2006
vor 14 Jahren

ich verwende bereits Stack<Cell>!

Aber eben nicht so, wie ich meinte. Mein Vorschlag war ein Ersatz für den rekursiven Aufruf der Expand-Methode!

Weeks of programming can save you hours of planning

m0rius Themenstarter:in
1.002 Beiträge seit 2007
vor 14 Jahren

Hallo MrSparkle,

huhu, der 1000. Beitrag 😉.

Ah, jetzt verstehe ich ... Ich glaube, das mache ich ...

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

3.971 Beiträge seit 2006
vor 14 Jahren

Zu Testzwecken könntest du auch die StackSize hochschraubben. Thread Constructor (ThreadStart, Int32)

Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...

1.361 Beiträge seit 2007
vor 14 Jahren

Hi m0rius,

Da deine Funktion sogar endrekursiv ist, kannst du es wirklich ganz einfach in eine Schleife umformen. Ohne irgendwelchen zusätzlichen Speicherplatz.


private void Expand(Cell currentCell)
{
  while(true)
  {
    if (_visitedCells >= TotalCells)
    {
        return;
    }

    Cell neighborCell = null;
    int[] directions = RandomHelper.GetDirections();
    bool connected = false;

    for (int index = 0; index < directions.Length; index++)
    {
        neighborCell = GetNeighborCell(currentCell, directions[index]);

        if (neighborCell != null && !neighborCell.Visited)
        {
            currentCell.Connect(neighborCell);
            connected = true;

            _visitedCells++;
            _cellStack.Push(neighborCell);

            break;
        }
    }

    if (!connected)
    {
        neighborCell = _cellStack.Pop();
    }
   
    //Expand(neighborCell);
    currentCell = neighborCell;
  }
}

natürlich kannst du dann den Code auch wieder vereinfachen:


private void Expand(Cell currentCell)
{
  while(_visitedCells < TotalCells)
  {
    Cell neighborCell = null;
    int[] directions = RandomHelper.GetDirections();
    bool connected = false;

    for (int index = 0; index < directions.Length; index++)
    {
        neighborCell = GetNeighborCell(currentCell, directions[index]);

        if (neighborCell != null && !neighborCell.Visited)
        {
            currentCell.Connect(neighborCell);
            connected = true;

            _visitedCells++;
            _cellStack.Push(neighborCell);

            break;
        }
    }

    currentCell = (connected) ? neighborCell : _cellStack.Pop();
  }
}

beste Grüße
zommi

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo m0rius,

eine Rechtsrekursion ist doch total simpel in eine Schleife umzusetzen? Wo ist dein Problem?

herbivore

PS: Ein bisschen zu spät.

m0rius Themenstarter:in
1.002 Beiträge seit 2007
vor 14 Jahren

Hallo zommi,

bis auf die beiden Klammern in der drittletzten Zeile hast du gerade das gepostet, was ich im Programm stehen habe 😉.

Hallo herbivore,

das habe ich auch nie abgestritten!

Edit: Mein Problem war eher dieser Gedankenfehler:

um speicher geht es hierbei nicht. es geht um den stack und wenn du rekursion vermeidest, hast du auch keine probleme mit dem stack.

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

m0rius Themenstarter:in
1.002 Beiträge seit 2007
vor 14 Jahren

Hallo nochmal,

jetzt könnt ihr sehen, wofür sich die Mühe gelohnt hat 😉 ...
YAMG - Yet Another Maze Generator

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg