Archief - [PROG][JAVA] Doolhof

Hi,

Voor een deel van men project op school moeten we code schrijven die een doolhof genereert (voorlopig alleen nog maar 1 voor muur en 0 voor gang). Als die doolhof genereert is zou het moeten mogelijk zijn om d.m.v input van de gebruiker te verplaatsen (voorlopig enkel met een variabele 5 die zich beweegt).

Ter illustratie:

111111
151101
101101
100001
111111

Zo iets zou ik moeten krijgen.

Ik dacht een 2 dim. array te declareren, een for-lus door te laten lopen maar dan zit ik eigenlijk vast :/.

Iemand die mij kan helpen?

Mvg

Waar zit je dan juist vast? heb ooit eens een snake gemaakt in vb.net toen ik nog op school zat. Maar ben nu java programmeur geworden

Je hebt nu een dubbele array dit zijn u coordinaten en die hebben een waarde van 1, 0 of 5.

dus inter ziet u object er zo uit

Via een lus in lus kan je nu toch je doolhof tekenen van punt 0,0 tot x,x

Ik heb voorlopig zoiets


Dan krijg ik doolhof die ik in voorbeeld heb gegeven. Maar dat kan volgens mij niet de bedoeling zijn want dat is wel vrij veel werk voor nog andere uitegebreidere doolhoven te maken.
Het bewegen van punt 5 naar 9 weet ik ook nog niet echt goe hoe ik dat moet programmeren.

Is het een algoritme dat je zoekt om een doolhof te genereren ?

In feite wel ja .

google eens op:maze java

krijgt ge wa sites die een maze maken en ook oplossen, ma daswel niet textbased dus ik zou naar de code kijken en zien wat ge kunt gebruiken

We hebben dat nog gezien hoe je zo'n doolhof moet maken.
Zo'n algoritme zorgt ervoor dat er zoveel mogelijk valse gangen zijn.

Maar ik ben vergeten hoe het werkt (en boekje ligt op mijn kot).

Ik veronderstel dat het wel gelijkaardig zal zijn met de source van die maze hierboven.
En anders post ik het principe wel de zondag of maandag hier.

presario zei:

Ik heb voorlopig zoiets

Code:

int a[][]=new int[5][6];
            
            
            for(int i=0;i<a.length;i++){
                for(int f=0;f<a[i].length;f++){
                    
                    
                                        
                    a[0][0]=1;
                    a[0][1]=1;
                    a[0][2]=1;
                    a[0][3]=1;
                    a[0][4]=1;
                    a[0][5]=1;
                    a[1][1]=5;
                    a[1][4]=9;
                    a[1][0]=1;
                    a[2][0]=1;
                    a[3][0]=1;
                    a[4][0]=1;
                    a[4][0]=1;
                    a[4][1]=1;
                    a[4][2]=1;
                    a[4][3]=1;
                    a[4][4]=1;
                    a[4][5]=1;
                    a[3][5]=1;
                    a[2][5]=1;
                    a[1][5]=1;
                    a[1][2]=1;
                    a[2][2]=1;
                    a[2][3]=1;
                    a[1][3]=1;
                    
                    
                
                    
                    System.out.print(a[i][f]);
                    
                }
            System.out.println();

Dan krijg ik doolhof die ik in voorbeeld heb gegeven. Maar dat kan volgens mij niet de bedoeling zijn want dat is wel vrij veel werk voor nog andere uitegebreidere doolhoven te maken.
Het bewegen van punt 5 naar 9 weet ik ook nog niet echt goe hoe ik dat moet programmeren.

Klik om te vergroten...

Ge programmeert nog niet zo lang zeker? Merk aub op hoe je (relatief gezien statische) assignments IN je for loop staan. Elke keer als ge ene gaat uitprinten gaat HEEL je doolhof opnieuw geassigned worden... Daar moet je toch beter naar kijken hoor. Het enige dat in je forloop moet staan zijn dingen die voor _elke_ i en j (of i en f in uw geval) opnieuw moeten gebeuren.

En een algoritme zou leuk zijn ja

Het algoritme moet er dus voor zorgen dat:

a) er geen muren zijn die én evenwijdig zijn én tegen elkaar liggen
b) er geen doolhof wordt gecreëerd zodanig dat er valse gangen ontstaan
c) er een gang bestaat van gegeven coördinaat a naar gegeven coördinaat b

Ik zou iets proberen programmeren met een for lus zodanig dat in elk punt van uw raster (een verbinding van een punt naar een punt links, rechts, boven of onder noem ik een muur) minstens één muur toekomt. Bij het toevoegen van een muur mag er geen valse ruimte onstaan, volgens mij kunt ge iets doen met een tabel van booleans waarbij eerst alles op false staat, en wilt ge ne muur toevoegen en op de nabijgelegen hokjes staat een true, dan moogt ge bvb geen muur meer toevoegen.

Allez ja het zoeken naar zo'n algoritme is tof maar ik heb zelf een Java project dus ik ga het nie voor u zoeken, maar probeer wat dingen uit.

Iemand toevallig al algoritme gevonden ?

presario zei:

Iemand toevallig al algoritme gevonden ?

Klik om te vergroten...

Je kan alvast valse gangen vermijden als volgt.

Telkens je een muur aanmaakt krijgt deze een rangnummer mee.

• Grenst deze muur aan geen enkele andere dan geeft ge hem het grootst gebruikte rangnummer tot nu toe mee, maar opgeteld met 1.
• Grenst deze muur maar aan één "muurconstructie" dan krijgt de nieuwe muur hetzelfde rangnummer van de aangrenzende muur.
• Grenst deze muur aan 2 andere "muurconstructies", en zijn de rangnummers van deze constructies gelijk, dan mag je de nieuwe muur daar niet invoegen want dan bekom je een valse gang. Zijn de rangnummers verschillend, dan krijgen beide constructies én de nieuwe muur hetzelfde rangnummer, bvb. het laagste van de 2.

Ik baseer me hier op het algoritme van Prim, als ik me niet vergis, voor het construeren van opspannende bomen. Dit is eigenlijk wiskunde, namelijk Grafentheorie.

Het algoritme dat wij gezien hebben maakt gebruik van de union/find datastructuur.

De map is dus gewoon vierkant/rechthoek met allemaal cellen en je start overal met muren. (uitgenomen begin en einde)

Dan ga je een willekeurige muur gaan selecteren, en wanneer de cellen die door deze muur gescheiden zijn, nog niet verbonden zijn, verwijder je de muur.

Je doet dit tot de begincel en eindcel met elkaar verbonden zijn.

Nog beter is, dit process te herhalen tot alle cellen met elkaar verbonden zijn.
Dit zorgt voor meer valse paden, wat tot een beter (moeilijker) doolhof leidt.

presario zei:

Iemand toevallig al algoritme gevonden ?

Klik om te vergroten...

Misschien moet je eens een basiscursus "hoe gebruik ik search engines" volgen?

Maar soit : http://en.wikipedia.org/wiki/Maze_generation_algorithm

dJeez zei:

Misschien moet je eens een basiscursus "hoe gebruik ik search engines" volgen?

Maar soit : http://en.wikipedia.org/wiki/Maze_generation_algorithm

Klik om te vergroten...

Ja wtf. Het eerste wat ik lees is dat het algoritme van Prim gebruikt wordt voor doolhoven te creëren. Wat ben ik goed zeg (18/20 voor discrete wiskunde)

Nog iets: de conventionele methode is te werken met een rooster van open gebieden, met 4 verbindingen (waarvan sommige afgesloten door een muur) naar de naburige open gebieden. Jij werkt met een rooster waar elk vak zowel als muur kan dienen of als open gebied. Dat maakt het iets complexer. Je zou het kunnen vereenvoudigen door bepaalde cellen altijd gesloten te houden, andere altijd open, en nog andere als muur, in het volgende patroon:
(spatie permanent open, * permanent muur, - muur die opengemaakt kan worden door het algoritme om de open delen te verbinden.

met wat dJeez gegeven heeft zoude toch mee moeten toekomen eh.
't Staat der zelfs letterlijk in(Zelfs in Java):
http://en.wikipedia.org/wiki/Image:Maze.png

Kan je niet gebruik maken van een hash table? Die je dan opvuld met panels.
Dat bekom je een groot (zelf in grootte aan te passen) grid van allemaal vierkante panels. Je kan dan bv de panels die een muur voorstellen rood laten kleuren.

Ik dacht aan zo iets:

Het is wel geen copy pastable voorbeeld dat ik je hier geef. Je zult het moeten aanpassen aan je eigen project maar ik toon je gewoon het principe van de hashtable die panels bevat, waarbij ik sommige posities inkleur.

EDIT: Sorry ik had blijkbaar de post van Blood_Raven over het hooft gezien, blijkbaar bestaat er een kant en klare oplossing. Maar toch is het de moeite waart even met die hashtabels te experimenteren

Succes

hey, ik heb met net hetzelfde probleem gezeten tijdens de creatie van men spel waternet waar de oplossingen van de levels feitelijk een doolhof zijn. Maw als ik een doolhof kon generen kon ik levels genereren.

Nu heb er ook wat achter moeten zoeken maar uiteindelijk ben ik op deze site terecht gekomen :
http://www.mazeworks.com/mazegen/mazetut/index.htm

waar ze u uitleggen in pseudo code hoe je te werk moet gaan. ik moet zeggen het algoritme dat ik op basis van die pseudo code gemaakt heb werkte direct en is nog eens zeer snel bij. Misschien kan je er iets mee doen.

Wat ik gedaan heb is feitelijk een structuur gemaakt voor de levels die bestond uit 4 boolean waarden die een doorgang of geen doorgang voorstellen (4 -> noord, zuid, oost , west).

en ik had dan een array met die structuur gedefinieerd met als breedte / hoogte de maximum size van het te genereren doolhof (kon dus kleiner zijn ook).

Wat je dan doet is gewoon in het begin alle muren als gesloten zetten (alles op true zetten bvb binnen de array van die structuur) en dan neem je een willekeurig punt om te beginnen, je doet gelijdelijk aan muurtjes weg maar je zorgt ervoor dat je nooit hetzelfde punt (kamer) terug neemt. Dit blijf je doen tot wanneer je in elk vakje geweest bent. en alles goed verlopen is heb je je doolhoof.

Voor het tekenen van het doolhof doorloop je gewoon die array check je of een bepaalde muur aan een kant true is (muurtje staat er nog). en teken je een horizontal lijntje of verticaal lijntje afhankelijk van de richting (noord, oosten, ....) dus in het begin heb je gewoon een grid van allemaal vierkantjes aangezien alle muren er nog zijn.

voor er een ventje door te laten lopen / besturen. teken je bvb een rood vierkantje en de X/Y positie dat je bijhoud komt overeen met de positie in die array (positie in het doolhof). Wat je dan doet is als je naar boven bvb duwd kijken of in het huidig vakje het noorder muurdje true of false is, is het true (muur staat er) dan verander je de X/Y positie niet, anders wijzig je je X/Y waarde naargelang de richting dat je koos.

klinkt allemaal vrij moeilijk maar het is echt gemakkelijk hoor. Ik heb er ook zo een spelletje van gemaakt voor de gp2x wat een doolhoof genereerd en waar je door kan lopen. Je moet gewoon goed kijken naar die pseudo code en ze implementeren