[VB] Recursie-probleempje Mijnenveger - Softwareontwikkeling

dinsdag 6 november 2012 13:59

Acties:

Topicstarter

Hallo Allemaal,

Ik moet voor een vak Mijnenveger programmeren in Visual Basic. Zoals je misschien weet is het zo, dat als je in Mijnenveger op een 0 klikt, alle nullen in de omgeving getoond worden. Hiervoor had ik gedacht om gebruik te maken van het floodfill-algoritme. Ik heb dit proberen te implenteren in mijn programma maar wanneer ik op een nul klik, en de Sub wordt opgeroepen, krijg ik een error "StackOverflowException was unhandled". Dus ik veronderstel dat er in mijn recursie geen grens zit, hoewel ik vrij zeker ben van wel.

Ter verduidelijking:
- De array 'field_value' is van het type String
- De verschillende If-Else cases zijn om niet buiten mijn rij-domein te komen (bijvoorbeeld als ik een 0 aanklik langs de rand van mijn venster, dat hij niet gaat controleren naar nulllen die niet in het venster behoren, want dan krijg je uiteraard een error)

Ik hoop dat jullie me kunnen helpen

Alvast bedankt

Hier is een link naar mijn code in PasteBin
Gebruik gewoon code tags a.u.b. wanneer je code post. Links naar externe sites gaan vandaag of morgen stuk en dan is je topic onbruikbaar voor mensen die later (m.b.v. de search bijvoorbeeld voor een soortgelijk probleem) op je topic stuiten.

Visual Basic .NET:

Private Sub zerocheck(ByVal kolom As Integer, ByVal rij As Integer)
    ' Deze code toont alle nullen in de omgeving
    If (field_value(kolom, rij) = "0") Then

        ' If ( waarde van het element van die rij = 0), => Text van de button = 0 + oproepen van de recursie
        field(kolom, rij).Text = field_value(kolom, rij)


        If (kolom = 0 And rij = 0) Then
            ' Case 1: Links boven
            Call zerocheck(kolom, rij + 1)
            Call zerocheck(kolom + 1, rij)
            Call zerocheck(kolom + 1, rij + 1)

        ElseIf (kolom = AANTAL_KOLOMMEN - 1 And rij = 0) Then
            ' Case 2: Rechts boven
            Call zerocheck(kolom, rij + 1)
            Call zerocheck(kolom - 1, rij)
            Call zerocheck(kolom - 1, rij + 1)

        ElseIf (kolom = AANTAL_KOLOMMEN - 1 And rij = AANTAL_RIJEN - 1) Then
            ' Case 3: Rechts onder
            Call zerocheck(kolom, rij - 1)
            Call zerocheck(kolom - 1, rij)
            Call zerocheck(kolom - 1, rij - 1)

        ElseIf (kolom = 0 And rij = AANTAL_RIJEN - 1) Then
            ' Case 4: Links onder
            Call zerocheck(kolom, rij - 1)
            Call zerocheck(kolom + 1, rij)
            Call zerocheck(kolom + 1, rij - 1)

        ElseIf (kolom = 0) Then
            ' Case 5: Linkerkant
            Call zerocheck(kolom, rij + 1)
            Call zerocheck(kolom, rij - 1)
            Call zerocheck(kolom + 1, rij)
            Call zerocheck(kolom + 1, rij + 1)
            Call zerocheck(kolom + 1, rij - 1)

        ElseIf (kolom = AANTAL_KOLOMMEN - 1) Then
            ' Case 6: Rechterkant
            Call zerocheck(kolom, rij + 1)
            Call zerocheck(kolom, rij - 1)
            Call zerocheck(kolom - 1, rij)
            Call zerocheck(kolom - 1, rij + 1)
            Call zerocheck(kolom - 1, rij - 1)

        ElseIf (rij = 0) Then
            ' Case 7: Bovenkant
            Call zerocheck(kolom, rij + 1)
            Call zerocheck(kolom + 1, rij)
            Call zerocheck(kolom - 1, rij)
            Call zerocheck(kolom + 1, rij + 1)
            Call zerocheck(kolom - 1, rij + 1)

        ElseIf (rij = AANTAL_RIJEN - 1) Then
            ' Case 8: Onderkant
            Call zerocheck(kolom, rij - 1)
            Call zerocheck(kolom + 1, rij)
            Call zerocheck(kolom - 1, rij)
            Call zerocheck(kolom + 1, rij - 1)
            Call zerocheck(kolom - 1, rij - 1)

        Else
            ' Case 9: Ergens in het veld (weg van de kanten)
            Call zerocheck(kolom, rij + 1)
            Call zerocheck(kolom, rij - 1)
            Call zerocheck(kolom + 1, rij)
            Call zerocheck(kolom - 1, rij)
            Call zerocheck(kolom + 1, rij + 1)
            Call zerocheck(kolom + 1, rij - 1)
            Call zerocheck(kolom - 1, rij + 1)
            Call zerocheck(kolom - 1, rij - 1)

        End If

    End If

End Sub

[ Voor 66% gewijzigd door RobIII op 06-11-2012 14:09 ]

dinsdag 6 november 2012 14:10

Acties:

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

Heb je al ge-debugged (Debuggen: Hoe doe ik dat?) en wat kwam daar uit?

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij

dinsdag 6 november 2012 14:11

Acties:

Janoz

Moderator Devschuur®

!litemod

Je bent er vrij zeker van dat je een grens gesteld hebt. Zou je mij kunnen vertellen op welke manier jij die denkt geimplementeerd te hebben?

Je code kan trouwens een stuk korter door gewoon de buren aan te roepen, en pas in de aanroep zelf te controleren of de coordinaten wel op het veld liggen.

[ Voor 36% gewijzigd door Janoz op 06-11-2012 14:12 ]

Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'

dinsdag 6 november 2012 14:11

Acties:

steveman

Comfortabel ten onder

Wat gebeurt er als je de kolom en rij afdrukt bij aanroep van zeroCheck ?

Ik vermoed dat meermaals hetzelfde vakje wordt benaderd namelijk.

bv. (5,4) -> (5,5) -> (5,4) -> (5,5) .... ----> stack is vol.

"Take the risk of thinking for yourself. Much more happiness, truth, beauty, and wisdom will come to you that way." -Christopher Hitchens | In memoriam? 🏁 ipv kruis!

dinsdag 6 november 2012 14:14

Acties:

Wixed

Topicstarter

Ah ja inderdaad, wat steveman zegt is waar, meermaals hetzelfde vakje wordt benaderd. ;S Iemand een goed idee om hier omheen te geraken ? ;o

dinsdag 6 november 2012 14:15

Acties:

HuHu

Gebruik een niet-recursief algoritme middels een queue: Wikipedia: Flood fill

dinsdag 6 november 2012 14:17

Acties:

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

Wixed schreef op dinsdag 06 november 2012 @ 14:14:
Iemand een goed idee om hier omheen te geraken ? ;o

Again; debug eens voordat je vragen stelt. Het is niet dat we niet willen helpen maar we verwachten wél dat je zelf ook meedenkt; anders loopt 't al gauw uit op een Kan iemand even...?

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij

dinsdag 6 november 2012 14:19

Acties:

Janoz

Moderator Devschuur®

!litemod

Ik neem aan dat het juist de bedoeling is van de opdracht om het recursief te doen, dus een nonrecursive oplossing zal waarschijnlijk niet wenselijk zijn (daarnaast vraag ik me af of de topicstarter al wel met structuren als Stacks in aanraking gekomen is)

Wat je zutl moeten doen is zorgen dat je weet wanneer een vakje al behandeld is. en deze dan niet nogmaals gaan behandelen. Bij mijnenveger is dat redelijk simpel. Een vakje wleke al 'geopend' is is al behandeld.

Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'

dinsdag 6 november 2012 14:20

Acties:

Wixed

Topicstarter

HuHu schreef op dinsdag 06 november 2012 @ 14:15:
Gebruik een niet-recursief algoritme middels een queue: Wikipedia: Flood fill

okido ik zal eens kijken naar een queue

Ik heb de debugger gebruikt, heb er zelf lang op gezocht, maar kon het niet vinden. De geavanceerde functies van debugger ken ik wel nog niet gezien het feit ik nieuw ben in Visual Basic

dinsdag 6 november 2012 14:22

Acties:

Wixed

Topicstarter

Janoz schreef op dinsdag 06 november 2012 @ 14:19:
Ik neem aan dat het juist de bedoeling is van de opdracht om het recursief te doen, dus een nonrecursive oplossing zal waarschijnlijk niet wenselijk zijn (daarnaast vraag ik me af of de topicstarter al wel met structuren als Stacks in aanraking gekomen is)

Wat je zutl moeten doen is zorgen dat je weet wanneer een vakje al behandeld is. en deze dan niet nogmaals gaan behandelen. Bij mijnenveger is dat redelijk simpel. Een vakje wleke al 'geopend' is is al behandeld.

Recursie was een eigen ideetje, moet niet. En misschien werken met een 2de 2D array van het type Boolian voor open en gesloten is wel een goed idee

Bedankt voor de tip

dinsdag 6 november 2012 14:22

Acties:

HuHu

Wixed schreef op dinsdag 06 november 2012 @ 14:20:
[...]

okido ik zal eens kijken naar een queue

Ik heb de debugger gebruikt, heb er zelf lang op gezocht, maar kon het niet vinden. De geavanceerde functies van debugger ken ik wel nog niet gezien het feit ik nieuw ben in Visual Basic

Met een debugger ga je het probleem ook niet vinden. Deze twee regels, die in elk flood-fill algoritme te vinden zijn, heb je gemist:

1. If the color of node is not equal to target-color, return.
2. Set the color of node to replacement-color.

Punt één doe je wel, je controleert of field_value(kolom,rij)=0, maar je vergeet daarna om die waarde te veranderen in iets anders dan nul.

edit; of zoals je zelf net zegt, een aparte array bijhouden voor de reeds bekeken locaties.

[ Voor 5% gewijzigd door HuHu op 06-11-2012 14:23 ]

dinsdag 6 november 2012 14:29

Acties:

Wixed

Topicstarter

HuHu schreef op dinsdag 06 november 2012 @ 14:22:
[...]

Met een debugger ga je het probleem ook niet vinden. Deze twee regels, die in elk flood-fill algoritme te vinden zijn, heb je gemist:

[...]

Punt één doe je wel, je controleert of field_value(kolom,rij)=0, maar je vergeet daarna om die waarde te veranderen in iets anders dan nul.

edit; of zoals je zelf net zegt, een aparte array bijhouden voor de reeds bekeken locaties.

Inderdaad, het gebruik van een tweede 2D array van het type Boolian heeft het probleem opgelost. Bedankt allemaal, mag gesloten worden! ;3

dinsdag 6 november 2012 14:31

Acties:

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

Een slotje is niet nodig op een topic als je je oplossing hebt. Zie daarvoor ook onze faq betreffende topiceinde

HuHu schreef op dinsdag 06 november 2012 @ 14:22:
[...]

Met een debugger ga je het probleem ook niet vinden.

Mwa; als je het algoritme begrijpt moet je met een debugger tijdens step-thru wel op een gegeven moment een aha-momentje hebben lijkt me zo.

[ Voor 46% gewijzigd door RobIII op 06-11-2012 14:32 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij

dinsdag 6 november 2012 14:33

Acties:

HuHu

Daarnaast zou ik nog een ander probleem oplossen als ik jou was: namelijk die elseif dingen allemaal verwijderen en die hele lap code inkorten tot een regel of tien.

RobIII schreef op dinsdag 06 november 2012 @ 14:31:

[...]

Mwa; als je het algoritme begrijpt moet je met een debugger tijdens step-thru wel op een gegeven moment een aha-momentje hebben lijkt me zo.

Maar als je een beetje pech hebt ben je veel (heel veel) iteraties verder en allang vergeten wat je seedpoint ook alweer was

[ Voor 54% gewijzigd door HuHu op 06-11-2012 14:34 ]

dinsdag 6 november 2012 14:34

Acties:

Janoz

Moderator Devschuur®

!litemod

Wixed schreef op dinsdag 06 november 2012 @ 14:29:
[...]

Inderdaad, het gebruik van een tweede 2D array van het type Boolian heeft het probleem opgelost. Bedankt allemaal, mag gesloten worden! ;3

Euhm... Een tweede array lijkt me ietwat overbodig. Je kunt immers aan de knop ook al zien of hij open gemaakt is toch?

Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'

dinsdag 6 november 2012 14:37

Acties:

Verwijderd

Een "makkelijke" oplossing: zorg ervoor dat je stopt met recursie als de cel al open is. Dat kan je doen door de hele if/elseif/else rits NIET te doorlopen als de text van de cel en de waarde van de cel gelijk zijn (ofwel: de cel is al "open")

dinsdag 6 november 2012 14:48

Acties:

Wixed

Topicstarter

Janoz schreef op dinsdag 06 november 2012 @ 14:34:
[...]

Euhm... Een tweede array lijkt me ietwat overbodig. Je kunt immers aan de knop ook al zien of hij open gemaakt is toch?

Inderdaad, heb het nu kunnen regelen zonder 2de rij, door telkens te controleren of de Tekst van de button al geplaatst is of niet

Pagina: 1

Reageer