Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Problem mit Vector-StackOverflow bei FloodFill-Methode

Werbeanzeige

AintLarry

Frischling

  • »AintLarry« ist der Autor dieses Themas

Beiträge: 58

Wohnort: Hamburg

Beruf: Kaufmann für Versicherungen und Finanzen

  • Private Nachricht senden

1

10.09.2016, 14:03

Problem mit Vector-StackOverflow bei FloodFill-Methode

Halo Leute,

zur Überprüfung von Zufallsgenerierten Karten habe ich nun eine FloodFill-Methode geschrieben. Leider habe ich bei jedem Debug einen Stackoverflow, wenn der Vector 320 Elemente erreicht.

Dabei lösche ich nach jeden Schleifendurchlauf die dann "überflüssig" gewordenen Elemente.

Hier mein Code.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

    std::vector<std::vector<int> > stack;
    std::vector<int> row;

    row.clear();
    row.push_back(xCoord);
    row.push_back(yCoord);
    stack.push_back(row);

    while (stack.empty() == false)
    {
        row.clear();
        row = stack.back();
        xCoord = row[0];
        yCoord = row[1];
        stack.pop_back();

        if (layer.getCoord(xCoord, yCoord).getUndergroundID() != 0 && layer.getCoord(xCoord, yCoord).getUndergroundID() != 1 && layer.getCoord(xCoord, yCoord).getUndergroundID() != 6 && layer.getCoord(xCoord, yCoord).getFunctionID() != 99)
        {
            layer.getCoord(xCoord, yCoord).setFunctionID(99);
            std::cout << stack.size() << std::endl;

            if (layer.getCoord(xCoord + 1, yCoord).getFunctionID() != 99)
            {
                row.clear();
                row.push_back(xCoord + 1);
                row.push_back(yCoord);
                stack.push_back(row);
            }

            if (layer.getCoord(xCoord, yCoord + 1).getFunctionID() != 99)
            {
                row.clear();
                row.push_back(xCoord);
                row.push_back(yCoord + 1);
                stack.push_back(row);
            }

            if (layer.getCoord(xCoord - 1, yCoord).getFunctionID() != 99)
            {
                row.clear();
                row.push_back(xCoord - 1);
                row.push_back(yCoord);
                stack.push_back(row);
            }

            if (layer.getCoord(xCoord, yCoord - 1).getFunctionID() != 99)
            {
                row.clear();
                row.push_back(xCoord);
                row.push_back(yCoord - 1);
                stack.push_back(row);
            }

        }
    }


Ich habe schon im Internet geschaut, aber leider nichts passendes gefunden.

Fällt euch auf Anhieb etwas auf an dem Code?

Danke im Voraus für eure Hilfe.

Henrik

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

2

10.09.2016, 16:00

Hast du wirklich einen Stack Overflow? Ich bezweifle das, da es hier keine Rekursion gibt, die ihn auslösen könnte. Bitte mach mal einen Screenshot.

Zudem benutzt du nun schon wieder einen std::vector für ein 2-elementiges Array anstelle eines struct mit x und y. Dass dies Quatsch ist, hatte ich dir doch schon im anderen Thread ausführlich erklärt ...

while (stack.empty() == false) lässt sich einfacher schreiben: while (!stack.empty())

Ein paar unnötige if-Konstrukte hast du auch drin. Entweder prüfst du, ob die Bedingung für das neu hinzuzufügende Feld zutrifft, bevor du es in den Stack packst, oder nachdem du es von dort herausnimmst. Du tust beides, aber einmal testest du nur auf 99 und einmal auf eine ganze Reihe zusätzlicher Zahlen.

Außerdem: Statt fest vergebener Zahlen solltest du hier zumindest ein enum benutzen, denn dann hast du sprechende Namen statt kryptischer Zahlen, wo niemand weiß, was sie bedeuten (du selbst in ein paar Wochen möglicherweise auch nicht mehr).
David Scherfgens Website | Konzentrationstest Polizei

AintLarry

Frischling

  • »AintLarry« ist der Autor dieses Themas

Beiträge: 58

Wohnort: Hamburg

Beruf: Kaufmann für Versicherungen und Finanzen

  • Private Nachricht senden

3

10.09.2016, 16:18

Hallo David,

zu der Verwendung des 2d-Arrays hast du recht. Dies habe ich auch soeben geändert.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

std::vector<Coord> stack;
    
    Coord coord;
    coord.x = xCoord;
    coord.y = yCoord;

    stack.push_back(coord);

    while (stack.empty() == false)
    {
        Coord currentCoord;
        currentCoord = stack.back();
        xCoord = currentCoord.x;
        yCoord = currentCoord.y;

        if (layer.getCoord(xCoord, yCoord).getUndergroundID() != 0 && layer.getCoord(xCoord, yCoord).getUndergroundID() != 1 && layer.getCoord(xCoord, yCoord).getUndergroundID() != 6 && layer.getCoord(xCoord, yCoord).getFunctionID() != 99)
        {
            layer.getCoord(xCoord, yCoord).setFunctionID(99);
            std::cout << stack.size() << std::endl;

            Coord c;

            if (layer.getCoord(xCoord + 1, yCoord).getFunctionID() != 99)
            {   
                c.x = xCoord + 1;
                c.y = yCoord;
                stack.push_back(c);
            }

            if (layer.getCoord(xCoord, yCoord + 1).getFunctionID() != 99)
            {
                c.x = xCoord;
                c.y = yCoord + 1;
                stack.push_back(c);
            }

            if (layer.getCoord(xCoord - 1, yCoord).getFunctionID() != 99)
            {
                c.x = xCoord - 1;
                c.y = yCoord;
                stack.push_back(c);
            }

            if (layer.getCoord(xCoord, yCoord - 1).getFunctionID() != 99)
            {
                c.x = xCoord;
                c.y = yCoord - 1;
                stack.push_back(c);
            }

        }

        stack.pop_back();
    }


An dem Fehler ändert dies natürlich nichts.

Ich war von einem StackOverflow ausgegangen, da der Fehler immer bei dem 320 Element aufkam, nun variert dies aber.



Im Hintergrund zu sehen die Anzahl der Elemente im Stack in dem jeweiligen Durchlauf der While-Schleife.

EDIT:

Die "Umstellung" des gesamten Codes auf Enum, bzw. die Einrichtung in dem MapCoord-Element ist noch geplant, hat aber nichts mit diesem Fehler zu tun. Trotzdem danke für den erneuten Hinweis.

Die Überprüfung auf die ID 99 erfolgt zwei mal, stimmt. Das ist natürlich nicht korrekt, dies habe ich gerade geändert. Aber auch dieser Umstand wirkt sich nicht auf den Fehler aus.

Ob nun "!stack.empty" oder "stack.empty == false" ist im Prinzip die gleiche Abfrage, hier handelt es sich also um reine Geschnackssache.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »AintLarry« (10.09.2016, 16:24)

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

4

10.09.2016, 16:24

Aha, da hast du also selber irgendwas in den Fehler reininterpretiert und uns als Fakt aufgetischt, was gar nicht wahr ist, anstatt einfach den Originalfehler zu posten ;) Einen Stack-Overflow kann es hier gar nicht geben, da dein "Stack"-Inhalt nicht auf dem Stack liegt, sondern auf dem Heap (wenn dir die Begriffe Stack und Heap nichts sagen, dann solltest du diese Lücke füllen ...).

Der Fehler sagt dir, dass du versuchst, auf den Vektor an einer Stelle zuzugreifen, die außerhalb des gültigen Index-Bereichs liegt.

Du hast außerdem noch eine Änderung durchgeführt, von der du nichts gesagt hast. Dein stack.pop_back(); steht nun ganz unten in der while-Schleife und löscht damit direkt wieder das letzte hinzugefügte Element, bevor es überhaupt verarbeitet wurde. Wenn ein neues hinzugefügt wurde, dann wird das verarbeitete Element nicht entfernt. Das willst du doch sicher nicht, also pack diese Anweisung wieder dahin, wo sie vorher stand!

Und dann klickst du mal, wie das Dialogfenster dir vorschlägt, auf "Wiederholen", wodurch du in den Debugger kommst. Dann siehst du, nachdem du im Stack-Fenster deine Funktion ausgewählt hast, wo genau es scheitert. Deine Variablen kannst du dann ebenfalls einsehen. Eine gute Gelegenheit, um den Umgang mit dem Debugger zu üben!
David Scherfgens Website | Konzentrationstest Polizei

AintLarry

Frischling

  • »AintLarry« ist der Autor dieses Themas

Beiträge: 58

Wohnort: Hamburg

Beruf: Kaufmann für Versicherungen und Finanzen

  • Private Nachricht senden

5

10.09.2016, 16:51

Danke für deine Hilfe.

Der Debugger sagt mir, dass der Fehler beim return aus der "getCoord" Methode liegt.
Dies leuchtet mir im Nachhinein auch ein, da ich nicht sichergestellt habe, dass die Floodfill-Methode über meine Map hinaus geht.

Dem habe ich versucht entgegen zu wirken, indem ich vor dem Hinzufügen in den Stack überprüfe, ob sich die Coordinate in Randnähe befindet.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

    Coord coord;
    coord.x = xCoord;
    coord.y = yCoord;

    stack.push_back(coord);

    while (!stack.empty())
    {
        Coord currentCoord;
        currentCoord = stack.back();
        xCoord = currentCoord.x;
        yCoord = currentCoord.y;
        stack.pop_back();

        if (layer.getCoord(xCoord, yCoord).getUndergroundID() != 0 && layer.getCoord(xCoord, yCoord).getUndergroundID() != 1 && layer.getCoord(xCoord, yCoord).getUndergroundID() != 6)
        {
            layer.getCoord(xCoord, yCoord).setFunctionID(99);
            std::cout << stack.size() << std::endl;

            Coord c;

            c.x = xCoord + 1;
            c.y = yCoord;
            if (layer.getCoord(xCoord + 1, yCoord).getFunctionID() != 99 && c.x > 1 && c.x < layerWidth && c.y > 1 && c.y < layerHeight)
            {   
                stack.push_back(c);
            }

            c.x = xCoord;
            c.y = yCoord + 1;
            if (layer.getCoord(xCoord, yCoord + 1).getFunctionID() != 99 && c.x > 1 && c.x < layerWidth && c.y > 1 && c.y < layerHeight)
            {
                stack.push_back(c);
            }

            c.x = xCoord - 1;
            c.y = yCoord;
            if (layer.getCoord(xCoord - 1, yCoord).getFunctionID() != 99 && c.x > 1 && c.x < layerWidth && c.y > 1 && c.y < layerHeight)
            {
                stack.push_back(c);
            }

            c.x = xCoord;
            c.y = yCoord - 1;
            if (layer.getCoord(xCoord, yCoord - 1).getFunctionID() != 99 && c.x > 1 && c.x < layerWidth && c.y > 1 && c.y < layerHeight)
            {
                stack.push_back(c);
            }


Der auftretende Fehler bleibt allerdings der selbe.

Dies dürfte eigentlich nicht passieren.

Ich werde nun mit einigen Testausgaben überprüfen, wo der Fehler liegt.

EDIT: Komisch ist aber trotzdem, warum die Methode aus der Map "hinausläuft", da die Randsteine ja "Mauerwerk" sind, und dies ja berücksichtigt wird, bevor die Coordinate verarbeitet wird.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »AintLarry« (10.09.2016, 16:59)

AintLarry

Frischling

  • »AintLarry« ist der Autor dieses Themas

Beiträge: 58

Wohnort: Hamburg

Beruf: Kaufmann für Versicherungen und Finanzen

  • Private Nachricht senden

6

10.09.2016, 17:07

Problem gelöst!
Thread kann geschlossen werden.

Ich habe den Wald vor lauter Bäumen nicht gesehen.

In der Abfrage, weiter unten in meinem Code, ob noch "nicht geflutete" Felder vorhanden sind, habe ich die Überprüfung bis zur Breite und Höhe vorgenommen. Wobei die letzte zu Überprüfende Coordinate ja "breite-1, höhe-1" sein muss.

Nun funktioniert alles.

Danke noch einmal für deine Hilfe David.

Henrik

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

7

11.09.2016, 09:28

Wieso gleich schliessen? Du bist nicht der erste und wirst wohl auch nicht der letzte sein der einen Floodfill schreibt.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Werbeanzeige

Ähnliche Themen