Kirjoitellaanpa tänne fooruminkin puolelle välillä.
Olen tässä viime viikkoina lueskellut jonkin verran teoriaa ja algoritmia roguelike-pelin luolastongeneroinnista. Ajattelin siis kysyä että onko täällä Ohjelmointiputkassa kuinka moni kirjoitellut omia luolastokoodejaan, ja jos on niin millä periaatteella? Aina on hyvästä oppia uutta ja miettiä mitä ja miten tekee.
ERKKI-engineen kirjoitin hyvin yksinkertaisen algoritmin joka toimii seuraavalla periaatteella:
1. Sijoita kenttään X huonetta (kokoa ja paikkaa arvotaan jatkuvasti kunnes huone ei ole minkään muun huoneen kanssa päällekkäin tai sivukontaktissa);
2. Merkitse kaikki huoneet paitsi ensimmäinen ei-liitetyiksi (connected, unconnected)
3. Valitse satunnainen ei-yhdistetty huone lähtöpaikaksi ja satunnainen yhdistetty huone kohteeksi (jos ei-yhdistettyjä ei löydy lopetetaan generointi; kaikki huoneet on yhdistetty).
4. Kaiva tunnelia alkaen lähtöhuoneen satunnaiselta seinältä kohti kohdesijaintia (kohdehuoneen keskusta).
5. Mikäli kaivaessa törmätään huoneeseen, merkitään se löydetyksi ja jatketaan matkaa.
6. Mikäli kaivaessa löydetään tunneli, merkitään lähtöhuone löydetyksi ja palataan kohtaan 3.
7. Löydettäessä kohdesijainti merkitään lähtöhuone löydetyksi ja palataan kohtaan 3.
Edellisessä yksinkertaisessa metodissa on kuitenkin seuraava rasittava ominaisuus: kun tunnelia kaivetaan suoraan huoneen vierestä, avautuu koko huoneen yksi sivu mikä on epäesteettistä. Samoin silloin jos tunneli käy kääntymässä ihan huoneen nurkassa:
###########:############# ###########:############# ###........:####....##### ###........:####....##### ###........:####....##### ###........:####....##### ###........:########::::: ###........:########:#### ###........:########:#### ###########:########:#### ###########:########:#### . = huone, : = tunneli
Olen näihin tapauksiin koettanut miettiä joitain ratkaisuja mutta kovin yksinkertaisesti ei ratkea. Onko muilla putkalaisilla ollut vastaavia ongelmia? Niistä ja mahdollisista ratkaisuista voisi keskustella tässä langassa.
Jos pitäydytään tunnelin kaivamisessa niin voithan siinäkin tarkistaa tuleeko tyhjiä vastaan vierus-ruuduissa.
Miksi tunneli on : eikä . ? Lattia on usein ihan sama asia ja tuossa tapauksessa tunneli olisi vain harmiton huoneen laajennus :)
1 lähestymistapa on rakentaa huoneita puu-mallilla. Yksi huone alussa josta suoraan vedät tunnelin johonkin satunnaiseen suuntaan ja sen päätteeksi uusi huone. Rekursiivisella funktiolla toteutettuna voit aloittaa samasta huoneesta useampiakin tunneleita ja lopettaa ne satunnaisessa paikassa kesken. Tai jos ei rekursiivista niin valitset satunnaisesti yhden huoneen josta jatkaa laajennusta, koska tulee tilanne vastaan ettei jostain mahdu laajentamaan mihinkään ja joudut etsimään huoneen josta mahtuu... niin kauan kuin koko kartan tietty vaadittu tiheys % tulee täyteen.
Tunneli ja huone erikseen siksi että kentän kaivamisen jälkeen ne voidaan erottaa toisistaan arvottaessa paikkoja luolaston muille ominaisuuksille (portaat, hyllyt, tms.).
Ajattelin kiertää tuon huoneiden ohittamisen sillä että käytävänkaivaja tarkistaa jos se puhkaisee itsensä huoneeseen; tällöin se lopettaa senhetkisen kaivamisensa ja jatkaa matkaansa puhkaistun huoneen jostain toisesta seinästä.
sqwiik kirjoitti:
Tunneli ja huone – – voidaan erottaa toisistaan arvottaessa paikkoja luolaston muille ominaisuuksille (portaat, hyllyt, tms.).
Ei kai ole yhtään sen parempi tukkia huone hyllyillä laidasta laitaan kuin tukkia käytävä aivan samalla tavalla? Minusta ratkaiseva seikka on ympäröivän tilan koko riippumatta siitä, onko kyseessä huone vai käytävä.
User137:n ehdottamalla rekursiolla päästäisiin täsmälleen samaan tulokseen (joka huoneesta vähintään yksi tunneli) paljon vähemmällä vaivalla: ei tarvitsisi pitää kirjaa, minne on jo vedetty käytävä. Arvottavaksi jäisivät huoneiden sijainnit sekä aina se, vedetäänkö käytävä nykyisestä huoneesta vai palataanko rekursiossa ylemmälle tasolle.
Yksi kokeilemistani algoritmeista on jossain määrin samanlainen kuin kuvaamasi. Se eroaa siten, että jokainen uusi huone yhdistetään heti luomisensa jälkeen johonkin jo aiemmin luotuun huoneeseen (tai käytävään).
sqwiik kirjoitti:
kun tunnelia kaivetaan suoraan huoneen vierestä, avautuu koko huoneen yksi sivu mikä on epäesteettistä. Samoin silloin jos tunneli käy kääntymässä ihan huoneen nurkassa:
Tämän olen ratkaissut yksinkertaisesti tarkistamalla etukäteen, tapahtuuko tuollainen huoneen sivuaminen. Jos tapahtuu, käytävä arvotaan uudelleen.
Edit: Lisäongelmia syntyy tietty, mikäli huone sijaitsee siten, että kaikki siitä lähtevät käytävät tuottavat epäesteettisen tuloksen. Algoritmini totetus onkin itse asiassa kokonaan rekursiivinen, jotta tässä tilanteessa (riittävän monen käytäväyrityksen jälkeen) huonekin voidaan perua ja arpoa uudelleen (sekä tarvittaessa vielä sitäkin edeltäviä käytäviä ja huoneita)
sqwiik kirjoitti:
Ajattelin siis kysyä että onko täällä Ohjelmointiputkassa kuinka moni kirjoitellut omia luolastokoodejaan, ja jos on niin millä periaatteella?
En ole, mutta aika moni muu on kirjoitellut.
Juup, olen kyllä käynyt läpi noita sourceforgen ja roguebasinin artikkeleja/pseudokoodeja. Osa on todella hienoja mutta menevät turhan mutkikkaiksi, ajattelin yhden tai kaksi yksinkertaista laittaa mukaan omaan engineen että sen kanssa pääsisi suht nopeasti alkuun.
Tein pienen muunnelman alkuperäiseen algoritmiini jolla saa jo nätin näköisiä sekasolmuja - huoneet arvotaan yksi kerrallaan kentälle jonka jälkeen niistä vedetään tunnelia kohti aiemmin kentälle asetettua huonetta. Jos tunneli osuu minkäänlaiseen kontaktiin aiemmin piirretyn tunnelin/huoneen kanssa, kaivuu lopetetaan. Tässä hivenen haittaa nurkasta läpi kaivaminen (siihen ei saa laitettua ovea) mutta se ei ole liian tärkeää.
Aihe on jo aika vanha, joten et voi enää vastata siihen.