[Alg] Controleren of een doolhof 'dicht' is

[Jabbah]

Ik ben aan het denken hoe ik kan controleren of een doolhof geen 'gaten' heeft waardoor je naar buiten kan. D.w.z. stel je begint aan de buitenkant van een doolhof. Je loopt langs de muur, en als je geen gaten tegenkomt, dan kom je weer op je beginpunt uit. In mijn geval is een doolhof altijd gesloten en heeft dus geen in- of uitgang.

Even een plaatje ter demonstratie:



De witte vakjes mag je lopen. De grijze vakjes zijn buiten het doolhof. Als ik langs de blauwe vakjes ga (de muren van het doolhof), moet ik een rondje kunnen maken. De gele vakjes hier zijn 'gaten' waardoor ik buiten het doolhof kom. Ik wil via een bepaald algoritme kunnen controleren of een doolhof 'dicht' is (het gaat me niet om de implementatie in een specifieke programmeertaal). In bovenstaande voorbeeld is het doolhof dus niet dicht.

Ikzelf dacht het volgende: Stel je begint op een bepaalde plek op de rand van het doolhof. Vervolgens controleer je of er een aanliggende muur (blauw vakje) tekenkomt (diagonaal mag ook! zie paarse vakje). Dit herhaal je tot je weer op je beginpunt komt. Alleen kom je met deze methode in de knoop bij situaties bij de groene vakjes waar een muur ophoudt in het doolhof. Ook situaties zoals bij de rode vakjes zijn mogelijk.

Google levert genoeg informatie over algoritmes om bij een doolhof de uitgang te vinden of doolhoven te genereren, maar niet wat ik wil.

Ter info: The doolhof is opgeslagen in een simpele 2-dimensionele array waarbij elk item in een doolhof (muur, vloer, etc.) een bepaalde char is.

Wie heeft er ideeen over hoe je kan checken of een doolhof gesloten is?

[pjvandesande]

Als het goed is moet elk wit vakje omringt zijn door witte of blauwe vakjes. Is dit niet het geval, dan is er ergens een uitgang.

Je kunt dus alle witte vakjes nalopen en kijken of deze grenst aan een niet-wit of niet-blauw vakje.

[kasper_vk]

Volgens mij kan het nog simpeler: als je de buitenste randen van je matrix kunt bereiken vanaf het startpunt, is ie niet dicht.
Toch?

[Janoz]

Ik denk dat die kleurtjes er met de hand ingezet zijn om bepaalde situaties aan te geven .

Is het niet makkelijker om je doolhof generator script altijd een muur om het complete domein te laten zetten zodat er altijd een omsluitende muur is?

[Jabbah]

questa: In mijn applicatie is de char voor een 'lege ruimte' hetzelfde voor een ruimte zowel binnen als buiten het doolhof. Simpel gezegd heb je dus een item 'muur' en een item 'geen muur'.

Janoz: Ik ben gebonden aan een bestand waarin de layout van het doolhof is gedefinieerd

kasper: ik geloof niet dat ik begrijp wat je bedoelt..

[ Voor 35% gewijzigd door Jabbah op 17-01-2005 13:22 ]

[pjvandesande]

kasper_vk schreef op maandag 17 januari 2005 @ 13:15:
Volgens mij kan het nog simpeler: als je de buitenste randen van je matrix kunt bereiken vanaf het startpunt, is ie niet dicht.
Toch?

Klopt, zolang je buitenste rand altijd een blauw blokje aan ze zijde heeft is het dicht. Als dit 1x niet zo is is hij open. Dus je zou inderdaad beter uit kunnen gaan van de buitenste rand!

[BolkeBeer]

Hoe sla je het doolhof op? Multidimensionale array? oid.

[pjvandesande]

Janoz schreef op maandag 17 januari 2005 @ 13:16:
Ik denk dat die kleurtjes er met de hand ingezet zijn om bepaalde situaties aan te geven .

Is het niet makkelijker om je doolhof generator script altijd een muur om het complete domein te laten zetten zodat er altijd een omsluitende muur is?

Je moet het inderdaad niet later controleren, maar je moet er voor zorgen dat de generator nooit een doolhof genereerd zonder dat deze geheel gesloten is.

[pjvandesande]

BolkeBeer schreef op maandag 17 januari 2005 @ 13:19:
Hoe sla je het doolhof op? Multidimensionale array? oid.

Ter info: The doolhof is opgeslagen in een simpele 2-dimensionele array waarbij elk item in een doolhof (muur, vloer, etc.) een bepaalde char is.

Staat in de startpost.

[Jabbah]

questa schreef op maandag 17 januari 2005 @ 13:19:
[...]


Je moet het inderdaad niet later controleren, maar je moet er voor zorgen dat de generator nooit een doolhof genereerd zonder dat deze geheel gesloten is.

Geen optie.. de layout vh doolhof voorgedefinieerd in een (tekst)bestand. Andere mogelijkheid is een grafische app. waarin je zelf een layout van een doolhof kan ontwerpen.

[Woy]

Je zou iets met een soort fill kunnen doen. Dus net zo iets als bij paint. Je pakt een willekeurig vakje waar geen muur is en markeert die. Daarna ga je alle aangrenzende vakjes waar geen muur staat controleren, als je op een gegeven moment op de buitenste rand van je array komt dan weet je dat je doolfhof niet gesloten is.

[Alarmnummer]

1 woord: backtracken.

De oplossing voor 'doolhof' problemen

[edit]
Als je alle mogelijke uitgangen kunt bepalen van een doolhof (en dat kan met backtracking), dan kan je ook bepalen of er geen uitgang is.

[ Voor 57% gewijzigd door Alarmnummer op 17-01-2005 14:16 ]

[.oisyn]

Het algoritme dat questa voorstelt lijkt me dan handiger, met een fill algoritme vind je namelijk alleen de blokjes die bereikbaar zijn vanaf waar je begon. Als je dus een doolhof hebt met twee afzonderlijke delen dan zul je beide delen moeten fillen. Daarnaast kost het imlpementeren van een fill algoritme simpelweg meer moeite

[Woy]

Ja maar zoals ik het lees kan hij dus geen verschil zien tussen vakjes die buiten een doolhof liggen of niet dus je zult toch alle aparte delen moeten testen of ze compleet omsloten zijn of niet.

Je kan dus niet simpelweg over alle interne blokjes itereren en kijken of ze in het doolhof liggen want dat weet je dus niet.
Dan denk ik dat Questa's algoritme niet meer werkt. Als je een fill algoritme gebruikt kan je dan net zolang opnieuw beginnen met fillen totdat je alle vakjes een keer hebt gehad. Je hebt dan meteen alle aparte segmenten en kan per segment aangeven of het compleet omsloten is.

[ Voor 31% gewijzigd door Woy op 17-01-2005 14:00 ]

[Verwijderd]

.oisyn: een fill algoritme hoeft toch helemaal niet veel werk te zijn?

code:

backup de array
indien er array elementen zijn die "vloer" zijn, 
neem een array element dat waarde "vloer" heeft

   voor daarop de volgende functie uit:
   check of element aan rand van array ligt. Als dit zo is, is het doolhof niet gesloten
   verander de waarde van dit element naar "muur"
   check 1 voor 1 omringende elementen (alleen direct aangrenzende dus) waarde "muur" hebben
   if not, voer deze functie recursief uit voor elk element dat "vloer" is

indien er geen elementen die "vloer"zijn meer zijn, is het doolhof gesloten.

[ Voor 30% gewijzigd door Verwijderd op 17-01-2005 14:30 ]

[Verwijderd]

Als je eens gaat fillen vanaf de buitenrand?

That is:

code:

foreach vakje in randvakjes do
  if (not wall) and (not fillcolor) then
    floodfill(vakje, fillcolor)
  fi
od

Alle vakjes die aan het niet gekleurd zijn (en geen muur, natuurlijk), behoren tot het gesloten doolhof.

Maar er zijn wat randgevallen waarvoor je definitie van `gesloten' belangrijk is, en dat heeft natuurlijk ook invloed op het algoritme.

Bijvoorbeeld:



Wat doe je hiermee?

[pjvandesande]

Deels gesloten kan niet. Het bestaat maar uit 2 soorten. Muur of geen muur geeft de TS aan.

[.oisyn]

Verwijderd schreef op maandag 17 januari 2005 @ 14:28:
.oisyn: een fill algoritme hoeft toch helemaal niet veel werk te zijn?

code:

backup de array
indien er array elementen zijn die "vloer" zijn, 
neem een array element dat waarde "vloer" heeft

   voor daarop de volgende functie uit:
   check of element aan rand van array ligt. Als dit zo is, is het doolhof niet gesloten
   verander de waarde van dit element naar "muur"
   check 1 voor 1 omringende elementen (alleen direct aangrenzende dus) waarde "muur" hebben
   if not, voer deze functie recursief uit voor elk element dat "vloer" is

indien er geen elementen die "vloer"zijn meer zijn, is het doolhof gesloten.

Ja ik heb weleens een fill algoritme geimplementeerd (zie bijvoorbeeld Pelle's PellePaint), maar ik zei meer werk dan een algoritme waarbij je gewoon over alle blokjes itereert

[Verwijderd]

questa schreef op maandag 17 januari 2005 @ 14:36:
Deels gesloten kan niet. Het bestaat maar uit 2 soorten. Muur of geen muur geeft de TS aan.

Wat ik bedoel is: het doolhof ziet er uit of sommige delen gesloten hadden moeten zijn, maar dat zijn ze niet.

Hoe betitel je die situatie? (En nog erger: als je die situatie apart wilt betitelen, hoe ontdek je hem dan... )

[pjvandesande]

Verwijderd schreef op maandag 17 januari 2005 @ 14:28:
.oisyn: een fill algoritme hoeft toch helemaal niet veel werk te zijn?

code:

backup de array
indien er array elementen zijn die "vloer" zijn, 
neem een array element dat waarde "vloer" heeft

   voor daarop de volgende functie uit:
   check of element aan rand van array ligt. Als dit zo is, is het doolhof niet gesloten
   verander de waarde van dit element naar "muur"
   check 1 voor 1 omringende elementen (alleen direct aangrenzende dus) waarde "muur" hebben
   if not, voer deze functie recursief uit voor elk element dat "vloer" is

indien er geen elementen die "vloer"zijn meer zijn, is het doolhof gesloten.

Succes

Verwijderd schreef op maandag 17 januari 2005 @ 14:51:
[...]


Wat ik bedoel is: het doolhof ziet er uit of sommige delen gesloten hadden moeten zijn, maar dat zijn ze niet.

Hoe betitel je die situatie? (En nog erger: als je die situatie apart wilt betitelen, hoe ontdek je hem dan... )

Hier heb je zeker gelijk in! Heb ik over het hoofdgezien. Dan kun je toch beter het eerste opzetje gebruiken wat ik aangaf.

Dan moet je niet uitgaan van de muren maar juist vanaf de open ruimte, dus de ruimte waar je loopt.

[.oisyn]

rwb schreef op maandag 17 januari 2005 @ 13:57:
Ja maar zoals ik het lees kan hij dus geen verschil zien tussen vakjes die buiten een doolhof liggen of niet dus je zult toch alle aparte delen moeten testen of ze compleet omsloten zijn of niet.

Je kan dus niet simpelweg over alle interne blokjes itereren en kijken of ze in het doolhof liggen want dat weet je dus niet.

Ah, daar had ik even overheen gelezen, maar dat geldt natuurlijk net zo goed als je gaat fillen. Je weet namelijk niet waar je moet beginnen. Tenzij je dat wel weet, dan heb je namelijk een referentiepunt waarvan je weet dat dat binnen het doolhof ligt.

[Jabbah]

In de 2 voorbeelden van OneOfBorg zijn in mijn geval beide doolhoven gesloten. Immers, de muren om de witte vakjes hebben geen gaten. De rest van de muren doen er dan niet meer toe.

Het meest handige lijkt me zover de fill methode. Je moet inderdaad een referentiepunt hebben vanwaar je verder gaat en je moet zeker weten dat dit referentiepunt binnen het doolhof ligt. Je kan hiervoor natuurlijk de start positie van de speler nemen. Deze kan nooit buiten het doolhof liggen. Vervolgens ga je vanuit dit punt alle aangrenzende vakjes controleren. Als je via deze methode op de eerste/laatste rij/kolom van je 2d array uitkomt, weet je dat het doolhof niet dicht is.

[Woy]

.oisyn schreef op maandag 17 januari 2005 @ 15:00:
[...]


Ah, daar had ik even overheen gelezen, maar dat geldt natuurlijk net zo goed als je gaat fillen. Je weet namelijk niet waar je moet beginnen. Tenzij je dat wel weet, dan heb je namelijk een referentiepunt waarvan je weet dat dat binnen het doolhof ligt.

Ja tuurlijk moet je een referentiepunt hebben. Of je moet gewoon fillen en kijken of er dan nog lege vakjes zijn. Dit is dan een apart segment. Je kan zo doorgaan totdat je alle vakjes die geen muur zijn een keer gefilled is en zo heb je alle segmenten. Dan weet je ook meteen of er meerdere gesloten doolhoven zijn.

[Verwijderd]

Nogmaals mijn oplossing pluggen: je kunt de rand eenvoudig als referentiepunt gebruiken. Immers, van de rand weet je dat hij nooit binnen het doolhof ligt.

En alle vakjes die eraan grenzen dus ook niet.

Op die manier hoef je dus niet te gokken naar startposities etc.

[Soultaker]

De standaardoplossing is zoals rwb en Alarmnummer al zeiden: gewoon opvullen door te backtracken.

In deze situatie is het makkelijker. Als ik het goed begrepen heb, heb je geldige posities (wit), ongeldige posities (grijs) en muren (blauw/groen/etc.). De buitenkant van je doolhof is dus al gemarkeerd (met grijze blokjes). In dat geval hoef je alleen maar te verifiëren dat er geen witte blokjes aan grijze blokjes grenzen en klaar is kees.

[.oisyn]

Als ik het goed begrepen heb, heb je geldige posities (wit), ongeldige posities (grijs) en muren (blauw/groen/etc.).

Dan heb je het niet goed begrepen, want de enige informatie die je hebt is of ergens een muur staat of niet

[Soultaker]

Wat is de vraagstelling nu precies dan? Je hebt alleen maar muren en lege vakjes begrijp ik? En je wil weten of er een afgesloten ruimte is?

Dan kun je nog steeds vullen.

[JeRa]

Waar moet je beginnen met fillen als je niet weet wat afgesloten en wat niet-afgesloten ruimtes zijn? Als dat de startpositie is, dan is een fillmethode inderdaad de beste optie. Dan maakt het namelijk niet uit of er meerdere segmenten zijn, want daar kun je vanuit de startpositie dan toch niet komen.

[ Voor 50% gewijzigd door JeRa op 17-01-2005 20:10 ]

[Hans1990]

Ik denk dat je ook gewoon de muren als een pad kan zien en de grond enzo als muur. Als je dat nou zo doet en je zet er een wat aangepaste pathfinding algoritme op (die bv alleen maar met de klok meegaat in een normaal vierkant). En als er geen route is lijkt het mij dat het vierkant open is. Lijkt mij ook een mogelijkheid ?

[.oisyn]

JeRa schreef op maandag 17 januari 2005 @ 20:09:
Waar moet je beginnen met fillen als je niet weet wat afgesloten en wat niet-afgesloten ruimtes zijn? Als dat de startpositie is, dan is een fillmethode inderdaad de beste optie. Dan maakt het namelijk niet uit of er meerdere segmenten zijn, want daar kun je vanuit de startpositie dan toch niet komen.

Zonder startpositie kan het ook, als je zorgt dat alle buitenste niet-muur vakjes gevuld zijn, dan zijn alle niet-muur vakjes die na dat alles niet gevuld zijn onderdeel van een omsloten doolhof.

[Verwijderd]

Misschien denk ik te simpel hoor, maar je hebt een teken 'muur' en een teken 'niet muur'. Om te zien of je doolhof open of gesloten is, hoef je dus alleen de buitenste vlakjes te controleren. Als daar 'niet muur' staat, is ie dus niet gesloten.

Of hoeft je doolhof niet perse het hele oppervlakte te beslaan?

[Voutloos]

Kan ook Hans1990, met de toevoeging dat je rekening moet houden met losstaande muren en controleren of je pad van muren wel minstens 1 vloertegel omcirkelt.

---

Geldt de rand van de figuur ook als muur? Waarschijnlijk niet, dus gelden de vloertegels in de 1e en laatste rij en 1e en laatste kolom als 'fout'. Deze kan je op een nieuwe manier markeren (je begint met een multidimensonale array met 2 verschillende chars erin, dus je kan best zelf een 3e char in gebruik nemen ).
Markeer alle vloertegels die aan foute tegels grenzen als fout (gebruik minimum en maximum getallen om het rekenwerk te begrenzen en naar het midden te werken). Herhaal deze stap voor elk niveau verder. Als je min en max waarden van bezochte rij/kolom gebruikt, kan je gewoon met een loopje naar binnen cirkelen.
Als dit allemaal gebeurt is, kijk je of er nog een ongewijzigde vloertegel is.

Dit werkt denk ik behoorlijk efficient, als je het loopje slim doet hoef je alleen de aangrenzende tegel te controleren welke dichter bij de rand ligt. In het slechtste geval (alleen vloertegels) bezoek je dus elk vakje 1x met voor elk vakje 1 check.

edit:
Wat .oisyn zegt dus.

[ Voor 3% gewijzigd door Voutloos op 17-01-2005 21:08 ]

[Soultaker]

JeRa schreef op maandag 17 januari 2005 @ 20:09:
Waar moet je beginnen met fillen als je niet weet wat afgesloten en wat niet-afgesloten ruimtes zijn? Als dat de startpositie is, dan is een fillmethode inderdaad de beste optie. Dan maakt het namelijk niet uit of er meerdere segmenten zijn, want daar kun je vanuit de startpositie dan toch niet komen.

Dat maakt dus niet uit! Je vult gewoon vanuit alle vakjes aan de rand (die zijn sowieso illegaal, want vanaf daar kun je de rand overstappen) tot waar je kan vullen. Alle overgebleven, ongevulde vakjes zijn blijkbaar niet van de rand te bereiken, wat betekent dat je daarvanuit ook de rand niet kunt bereiken.

Een stukje code:

C++:

#include <iostream>
using namespace std;

char layout[] = "........#."
                ".###.##.#."
                ".#....#.#."
                ".#########"
                ".........."
                ".####....."
                ".#..######"
                ".#...#.#.."
                ".#####.#.."
                ".....#.#..";

char (*doolhof)[10] = (char(*)[10])layout;

void fill(int row, int col) {
    if(doolhof[row][col] != '.')
        return; // vakje al gevuld of bezet door muur
        
    // Vul huidige vakje...
    doolhof[row][col] = 'x';
    
    // ...en vul alle aangrenzende vakjes (niet diagonaal)
    if(row > 0) fill(row - 1, col); // naar boven
    if(row < 9) fill(row + 1, col); // naar onder
    if(col > 0) fill(row, col - 1); // naar links
    if(col < 9) fill(row, col + 1); // naar rechts
}    

int main() {
    // Vul vanuit elle vakjes aan de rand
    for(int n = 0; n < 10; ++n) {
        fill(0, n); // rand boven
        fill(9, n); // rand onder
        fill(n, 0); // rand links
        fill(n, 9); // rand rechts
    }

    // Geef het resultaat weer
    for(int row = 0; row < 10; ++row) {
        for(int col = 0; col < 10; ++col)
            cout << doolhof[row][col];
        cout << endl;
    }
}

Op deze manier worden alle vakjes aan de buitenkant gevuld. De uitvoer ziet er zo uit:

code:

xxxxxxxx#x
x###x##x#x
x#xxxx#x#x
x#########
xxxxxxxxxx
x####xxxxx
x#..######
x#...#x#xx
x#####x#xx
xxxxx#x#xx

Er is maar één gebied over dat echt onbereikbaar is vanaf de rand (de vijf puntjes linksonder); alleen dat is een geldige doolhof.

Om te zien hoe het algoritme werkt, hoef je alleen maar de weergave-code naar regel 23 te verplaatsen (eventueel met een pauze erbij). Je kunt dan precies zien hoe opvolgende vakjes opgevuld worden.

[ Voor 14% gewijzigd door Soultaker op 17-01-2005 21:47 ]

[Voutloos]

edit:
Ik las het niet goed. nvm.

[ Voor 104% gewijzigd door Voutloos op 17-01-2005 21:36 . Reden: tijd voor bakkie koffie. Ik zag het al. Dank je. Lol :+ ]

[Soultaker]

offtopic:
Goed idee.

[ Voor 135% gewijzigd door Soultaker op 17-01-2005 21:36 ]

[Tomatoman]

Als het aantal doolhoven dat je gebruikt beperkt is, is er een supersnelle manier om te bepalen of het doolhof open of dicht is. Daarvoor moet je eenmalig voor al die veelgebruikte doolhoven via een algoritme bepalen of het doolhof op of dicht is. Voor elk van die doolhoven sla je in een hastable het resultaat op. Dat kost een heleboel rekenwerk om eenmalig al die doolhoven door te rekenen, maar het terugzoeken gaat supersnel.

Het voordeel van deze methode is dat je het rekenwerk verplaatst van de pc van de gebruiker naar de pc van de programmeur, waardoor het programma lekker snel wordt. Het nadeel is dat het alleen werkt als het aantal doolhoven niet groter is dan een paar honderdduizend. Het aantal verschillende doolhoven is 2^{aantal vakjes} als je ervan uitgaat dat een willekeurig aantal blokjes in het doolhof is toegestaan.

Nu je algoritme zelf. Ik zou het op de volgende manier aanpakken.

code:

var
  Gecontroleerd: array[X, Y] of Boolean;
  DoolhofOpen: Boolean;

function IsBuiten(X, Y): Boolean;
{
  // als je aan de rand van het doolhof komt, ben je buiten
  Gecontroleerd[X, Y] := True;
  if [aan de rand van het veld] then
    Result := True
  else
    Result := False
}

// recursieve functie:
function ItereerDoorPad(X, Y)
{
  if IsMuur(X, Y) then
    [procedure verlaten]
  else if IsBuiten(X, Y) then
  {
    DoolhofOpen := True
    [alle recursieve lussen verlaten, bijvoorbeeld met een exception]
  }
  else if Gecontroleerd[X-1, Y] = False then
    ItereerDoorPad(X-1, Y)      // een stap dieper in de recursieve functie
  else if Gecontroleerd[X+1, Y] = False then
    ItereerDoorPad(X+1, Y)
  else if Gecontroleerd[X, Y-1] = False then
    ItereerDoorPad(X, Y-1)
  else if Gecontroleerd[X, Y+1] = False then
    ItereerDoorPad(X, Y+1)
}

// hier start je het controleproces
function CheckOfDoolhofDichtIs
{
  var Xpos, Ypos

  // initialisatie
  (Xpos, Ypos) = [positie ergens 'binnenin' het doolhof]
  [alle elementen van de Gecontroleerd array False maken]
  DoolhofOpen := False;

  // Recursief zoekproces naar de rand beginnen. Dit zoekproces kan 
  // voortijdig worden onderbroken met een exception  
  ItereerDoorPad(Xpos, Ypos)

  if DoolhofOpen then
    ShowMessage('doolhof is open')
  else
    ShowMessage('doolhof is gesloten')
}

Het uitgangspunt is dat je op een positie 'binnenin' het doolhof begint. Daarna zoek je gestructureerd of je de rand van het doolhof kunt bereiken zonder op een muur te stuiten. Als je de rand weet te bereiken, ben je buiten en is het doolhof dus open. Als het doolhof niet open is, kun je vanuit het startpunt nooit de rand bereiken. De Gecontroleerd array is bedoeld om verschillende routes die via hetzelfde tussenpunt lopen niet dubbelop te controleren en om eventuele eindeloze lussen te voorkomen.

Het aardige van deze constructie is dat je heel eenvoudig de gevolgde route zou kunnen bijhouden, zodat je zelfs de route op het scherm zou kunnen weergeven.

[Voutloos]

Volgens mij houd je er nu nog geen rekening mee dat je een startpositie kan kiezen welke een pad heeft naar de rand, terwijl ergens anders wel een gesloten doolhof is. Je stopt zodra je een muur tegenkomt, maar misschien is hetgeen achter die muur ligt wel de gesloten doolhoof.

offtopic:
Als ik nu weer verkeerd lees, kap ik voorlopig met commentaar geven op code.

edit:
Soultaker, regel 41 had ik gezien. Ben allang blij dat ik niet iets over het hoofd zie. Misschien roept hij op regel 41 stiekem jouw implementatie aan zodat hij een '.' kan kiezen

[ Voor 25% gewijzigd door Voutloos op 18-01-2005 00:51 ]

[Soultaker]

Voutloos: dat doet 'ie op regel 41 met [positie ergens 'binnenin' het doolhof], maar je hebt wel gelijk, want dat werkt natuurlijk niet. De reden dat je het algoritme wilde uitvoeren was nu juist dat je wilde bepalen welke vakjes nou echt 'binnenin' liggen. Dan kan je dat algoritme niet beginnen met een vakje waarvan je weet dat het 'binnenin' ligt, want dat moest je nu net gaan uitzoeken!

Wat de hash-table suggestie betreft: dat kan natuurlijk elke willekeurige lookup-table-achtige structuur zijn. Verder lijkt het me sterk dat je als je random doolhoven genereert de kans groot is dat je ze in je hashtable hebt staan, of je moet superkleine doolhoven maken (met maximaal iets van 25 vakjes). Gewoon controleren met het algoritme (O(aantal vakjes); superefficiënt dus) zal voor doolhoven met minder dan een miljoen (!) vakjes gewoon razendsnel zijn.

[Tomatoman]

Als reactie op Voutloos en Soultaker: jullie hebben gelijk dat mijn opzet er geen rekening mee houdt dat je weleens buiten het gesloten doolhof zou kunnen staan en dat het algoritme dan niet signaleert dat er wel degelijk een gesloten doolhof aanwezig is.

Ik was ervan uitgegaan dat je probeert te kijken of er vanuit de beginpositie een mogelijkheid is om uit het doolhof te ontsnappen.

Soultaker schreef op dinsdag 18 januari 2005 @ 00:40:
Wat de hash-table suggestie betreft: dat kan natuurlijk elke willekeurige lookup-table-achtige structuur zijn. Verder lijkt het me sterk dat je als je random doolhoven genereert de kans groot is dat je ze in je hashtable hebt staan, of je moet superkleine doolhoven maken (met maximaal iets van 25 vakjes). Gewoon controleren met het algoritme (O(aantal vakjes); superefficiënt dus) zal voor doolhoven met minder dan een miljoen (!) vakjes gewoon razendsnel zijn.

Als je ze random genereert is dat geen oplossing, maar wel als je een vast aantal doolhoven hebt (bijvoorbeeld een eenvoudige game op een mobiele telefoon, met doolhoven van oplopende moeilijkheidsgraad). Maar ik ben met je eens dat het on-the-fly berekenen niet bepaald een bottleneck voor de applicatie zal vormen.


[Edit]
Nu ik nog eens verder zit te denken, valt het probleem best eenvoudig op te lossen met de gekozen opzet. Je gaat gewoon alle nog niet gecontroleerde punten langs om te kijken of er van daaruit en weg naar buiten is. Als er een punt is waarvandan er geen weg naar buiten is, bevindt dat punt zich in een gesloten doolhof.

code:

// hier start je het controleproces
function CheckOfDoolhofDichtIs
{
  var Xpos, Ypos

  // initialisatie
  [alle elementen van de Gecontroleerd array False maken]

  for Xpos := 0 to [maximum x-waarde voor de array] do
    for Ypos := 0 to [maximum y-waarde voor de array] do
      if Gecontroleerd[Xpos, Ypos] = False then
      {
        DoolhofOpen := False;

        // Recursief zoekproces naar de rand beginnen. Dit zoekproces kan 
        // voortijdig worden onderbroken met een exception. De waarde van
        // DoolhofOpen kan door ItereerDoorPad worden veranderd.  
        ItereerDoorPad(Xpos, Ypos)

        if DoolhofOpen = False then
          ShowMessage('doolhof is gesloten rondom positie [Xpos, Ypos]')
      }
}

Het kan ongetwijfeld efficiënter en eleganter, maar het werkt tenminste

[ Voor 42% gewijzigd door Tomatoman op 19-01-2005 13:15 ]

[Verwijderd]

/me was een oplossing aan het typen maar zag toen dit zinnetje staan van Soultaker;

In dat geval hoef je alleen maar te verifiëren dat er geen witte blokjes aan grijze blokjes grenzen en klaar is kees.

..en dat omschreef de oplossing iets (..) korter dan hetgeen ik aan het typen was (-:

[Woy]

Soultaker schreef op maandag 17 januari 2005 @ 21:28:
[...]

C++:

    // Vul vanuit elle vakjes aan de rand
    for(int n = 0; n < 10; ++n) {
        fill(0, n); // rand boven
        fill(9, n); // rand onder
        fill(n, 0); // rand links
        fill(n, 9); // rand rechts
    }

FF miereneuken hoor, maar zo roep je Fill dubbel aan voor alle hoeken. Niet dat dat veel uitmaakt omdat je toch meteen weer uit de fill methode schiet maar toch

[.oisyn]

Dan ik ook mierenneuken : Het is sowieso inefficient om alle vakjes afzonderlijk te gaan fillen, je kunt beter rondom scannen, en zodra je een niet-muur vakje tegenkomt die fillen, en daarna weer doorscannen. Of iets als alle niet-muur vakjes in een container stoppen, de rand fillen, en als een vakje gevuld moet worden haal je ze uit de container. Dan heb je meteen een lijst van vakjes die overblijven.

[Soultaker]

rwb schreef op dinsdag 18 januari 2005 @ 10:09:
FF miereneuken hoor, maar zo roep je Fill dubbel aan voor alle hoeken. Niet dat dat veel uitmaakt omdat je toch meteen weer uit de fill methode schiet maar toch

Dat maakt inderdaad weinig uit, maar het is toevallig heel makkelijk op te lossen: als je [b]n tot 9 laat lopen (in plaats van 10), dan bezoek je elk vakje aan de rand het precies een keer.

.oisyn schreef op dinsdag 18 januari 2005 @ 11:32:
Dan ik ook mierenneuken : Het is sowieso inefficient om alle vakjes afzonderlijk te gaan fillen, je kunt beter rondom scannen, en zodra je een niet-muur vakje tegenkomt die fillen, en daarna weer doorscannen.

Ik scan ook rondom hoor?

Verder kun je inderdaad wat function calls uitsparen door de controle op lege vakjes voor de call naar fill() uit te voeren (in plaats van in de implementatie van fill()). Maar dat maakt de code een stuk onoverzichtelijker. Dat mag de compiler dus lekker doen, hoewel dat hier wel lastig is, want een recursieve functie kun je normaal gesproken niet inlinen (probeer het maar ). Ik betwijfel of een gangbare compiler slim genoeg is om de functie op te splitsen in een recursief en een niet-recursief deel en het niet-recursieve deel te inlinen.

Je kunt het wel zelf fixen natuurlijk:

C++:

inline void fill(int row, int col) {
    if(doolhof[row][col] == '.') 
        _fill(row, col);
}

void _fill(int row, int col)
{ 
    doolhof[row][col] = 'x'; 
    if(row > 0) fill(row - 1, col);
    if(row < 9) fill(row + 1, col);
    if(col > 0) fill(row, col - 1);
    if(col < 9) fill(row, col + 1);
}

Maar da's ook maar een micro-optimalisatie.

[ Voor 29% gewijzigd door Soultaker op 18-01-2005 14:10 ]