Upea kieli tämä Clojure. Tulokset ovat enemmän kuin tyydyttäviä, ja sellainen alkukantainen lisp-häkkäilyn maku on suussa. Ja Javan ansiosta kaikkea tätä on helppo hyödyntää mitä erilaisimmissa sovelluksissa.
Miinaharava kartanluojana
Aikoinaan miinaharavaa enemmän pelatessani näin pelin generoimat satunnaiset ruudukot eräänlaisina karttoina. Tyhjiä ruutuja, joita yleensä oli paljon röykkiöinä, saattoi samaistaa mereksi tai järviksi, ja miinaruutuja ympärystöineen ajatteli maaksi. Taustalla piilevä teknologia on äärimmäisen yksinkertainen, joten se on helppo muuntaa kartanluontialgoritmiksi.
Alunperin, olisiko ollut vuonna 2007, kirjoitin kasaan PHP-purkan. Se loi luonnollisesti HTML-version satunnaiskartoista. Koska karttageneraattorilla ei ollut kummemmin käyttöä, jäi se sitten pölyttymään. Eikä tätä varsinaisesti olisi tarvinnutkaan kirjoittaa uudestaan: minullahan oli toimiva PHP-viritelmä. Jos sattuisi vaikka joku rope tarvitsemaan satunnaiskarttaa, siitä vain jauhamaan.
Mutta nytpä minulla on tämä uusi kielirakkaus, Clojure. Kirjoitin Clojurella jo uuden lukujärjestysjäsentelijän ja sen jälkeen hiipui innostus. Pelkästään siitä syystä, etten keksinyt mitään, mitä kokeilla. Onneksi sattumalta tämä vanha miinaharavaviritelmä kävi mielessä, ja se kuulosti mitä oivimmalta projektilta soveltaa funktionaalisia ideoita. Lopputuloskin on jo valmis, mitä nyt aina pientä viilaamista saa suorittaa. Tutkitaanpa, mitä olen tehnytkään. Mielestäni funktionaalinen lähestymistapa toimii tässä yhteydessä oikein hyvin, vaikka imperatiivinen 2D-taulukontäyttö toimii hyvin sekin.
Miinoja kentälle
Ensin tarvitsemme miinoja kentälle. Ilman miinoja ei ole miinojen ympäristöjäkään. Taisinpa aloittaa projektin aivan alkeellisimmasta yksiköstä, eli koordinaattien arpomisesta:
(defn rand-coords "Give us a pair of [x y] by given limits." [x y] [(rand-int x) (rand-int y)])
Ei pöllömpää. Haskell ei yrittäisikään tarjota valmiita satunnaislukutoimintoja ytimessään, koska ne eivät satu olemaan puhtaita funktioita. Ovatpa ne toiminnot tietysti sielläkin lisäkirjaston päässä. Koodi voi näyttää omituiselta, mutta käytännössä palautamme suoraan vektorin ilman kummempia kommervenkkejä. Koodin toiminnallisuus on “upotettu” suoraan tietorakenteeseen.
Mennään sitten suoraan asiaan, eli niitä miinoja kentälle. Algoritmiksi valitsin naiivin arpomisen, jonka suoritukselle ei taata ylärajaa. Kyseessä on siis ordo-ääretön.
(defn generate-mines-set
"Set given amount of randomly placed 'mines' into a sorted set."
[width height mines]
(loop [acc (sorted-set)
mines-left mines]
(if (zero? mines-left)
acc
(let [cand (rand-coords width height)]
(if (contains? acc cand) ; we'll take an extra spin if multiple hits
(recur acc mines-left)
(recur (conj acc cand)
(dec mines-left)))))))
Jos vähän puretaan auki tätä, niin se luonnollisesti käyttää rekursiota iteroimiseensa. Miinoja annetaan mines kappaletta ja rajoitukset kartalle arvojen width ja height avulla. Muuttujanimi acc vastaa kertymärakennetta (accumulator). Yleinen nimitys. Rekursion lopetusehto on ensin: hieman sanajärjestystä muuttamalla rivi muuttuu tavalliseksi englanniksi: “if the number of mines left is zero, …”
Jos kentälle pitää upottaa uusi miina, arvomme yhden kandidaatin cand, ja tsekkaamme, löytyykö se ennestään. Tämä on siis se naivi tapa toteuttaa arpominen, eikä välttämättä pysähdy koskaan. Palaamme rekursiosilmukkaan tavalla tai toisella, toisessa tapauksessa kertymämuuttujaa ei kerrytetä. Tuloksena ei ole kuvaus (map), vaan järjestetty joukko koordinaatteja. Niissä koordinaateissa tulee siis miinat löytymään.
Tätä joukkoa tarvitsemme sitten oikeastaan emme missään. Se joukko nimittäin muutetaan kuvaukseksi seuraavan funktion kohdalla. Ajattelin kuitenkin jättää sen joukoksi toistaiseksi. Voihan sille keksiä jotain muuta käyttöä.
Naapureiden laskeminen
Miinoille pitäisi siis löytää naapurit. Jos jollakin ruudun kahdeksasta naapuriruudusta löytyy miina, ruudun numeroarvo kasvaa yhdellä. Näin perinteisessä toteutuksessa kullakin ruudulla on arvo 0-8, joka siis ilmaisee miinanaapureiden lukumäärän. Tämän voi tehdä monella tavalla, minä otin käyttöön sekä bruteforcetusta että funktionaalista lähestymistapaa. Seuraava funktio, calculate-neighbours, ottaa vastaan joukon miinoja ja palauttaa kuvauksen, jossa on jo kaikki miinaharavan elementit kasassa. Tutkitaan tätä kahdessa palassa. Ensin ratkaisun ydin:
(defn calculate-neighbours
"Given set, transform it a map and calculate the number of neighbours to each
mine."
[width height mine-set]
(letfn [(neighbours [x y] ...toteutus myöhemmälle...)]
(let [mine-map (zipmap mine-set (repeat 1))] ; we just converted set->map!
(reduce #(merge-with + % %2)
mine-map
(for [[[x y] _] mine-map] (neighbours x y))))))
No onkos tässä sulateltavaa! Määrittelemme funktion neighbours, mutta kerron sen toteutuksen kohta. Se joka tapauksessa palauttaa joukon, jossa on kaikki kartalle mahtuvat miinojen naapuriruudut. Esimerkiksi jos ruutu (4, 3) on miinoitettu, niin sen naapuriruudut saavat ainakin arvon 1.
1 1 1 1 x 1 1 1 1
Mutta koska miinoja voi olla vierekkäinkin, tai sopivasti lähekkäin, tarvitsemme yllämainittua nokkeluutta. Ensin (rivillä, joka alkaa let-lausekkeella) muokkaamme miina-joukon miina-kuvaukseksi. Tätä varten keksin käyttää zipmap-funktiota, joka käytännössä iteroi tässä tapauksessa kahta joukkoa vieretysten. Funktiokutsu (repeat 1) luo äärettömän joukon ykkösiä, eli kutakin miinakoordinaattia vastaa tästä eteenpäin lukuarvo yksi. Sen voi vaihtaa, jos karttojen geografia niin paranee.
Seuraavaksi vanhaa kunnon reduce-magiaa! Kuvauksien yhdistelemiseen löytyy upea apulainen, merge-with, joka osaa fuusioida päällekäisiä entryjä käyttäjän määrittelemällä funktiolla. Nyt meille riittää plus-operaatio, koska naapurisolut olivat ykkösiä. Yksi naapuri siellä, yksi naapuri tuolla, plussalla saamme oikean tuloksen: kaksi naapuria.
Naapurit lasketaan listaksi joukkoja. for-rakenne tuottaa meille listan niitä. Tämän syvällisemmin en nyt ehdi käymään asiaa.
Naapurit ruudulle
Meiltä jäi neighbours-funktio käsittelemättä. PHP-aikoihin tekemäni bruteforcetus saa luvan toimia täälläkin. Luon siis käsipelillä (helppoa kaksiulotteisessa tapauksessa, vain kahdeksan vaihtoehtoa) listan naapureita. Mutta entä, jos miina on kentän reunalla? Sitä varten suodatamme epäkelvot koordinaatit pois:
(letfn [(neighbours [x y]
(filter
(fn [[[x* y*] _]]
(and (not (neg? x*))
(not (neg? y*))
(< x* width)
(< y* height)))
{[(dec x) (dec y)] 1
[ x (dec y)] 1
[(inc x) (dec y)] 1
[(dec x) y] 1
[(inc x) y] 1
[(dec x) (inc y)] 1
[ x (inc y)] 1
[(inc x) (inc y)] 1}))]
... )
Ruma funktio, mutta toimii. Käytännössä luomme tyhjästä pienen 8-sanaisen kuvauksen ja filtteröimme siitä huonot pois. Tämä toimii, ja calculate-neighbours on itsessään toimintakunnossa.
Yhdistellään tulokset
Ikäväähän se olisi aina kutsua molempia noista saadakseen miinaharavaa vastaavia tauluja aikaiseksi, joten kootaan ne yhdeksi abstraktioksi:
(defn generate-random-map
"Given width, height and number of 'mines', generate and return a random
mapping describing 2D landmap."
[width height mines]
(let [mines (generate-mines-set width height mines)]
(into (sorted-map)
(merge (calculate-neighbours width height mines)
(zipmap mines (repeat \x))))))
Tässä on vielä yksi lisäbonus. Ensin luomme miinat. Sitten lisäämme siihen naapurit. Sen jälkeen vielä lisäämme miinat takaisin, koska naapurit ovat luultavimmin sekoittaneet pakan. Tämä on lähinnä debuggausta varten, mutta myös näyttää hyvältä. Nyt käytämme tavallista kuvauksenyhdistelijää, mergeä. Se ylikirjoittaa kaikki päällekäiset entryt viimeisimmällä. Nyt merkitsen miinoja kirjaimella x (viimeinen rivi).
Miinojen lukumäärä olisi kiva esittää prosentuaalisena lukuna. No eipä ole hankalaa:
(defn generate-random-map-perc
"Don't specify the number of mines but a percentage."
[width height perc]
(let [mines (* (* width height)
(/ perc 100))]
(generate-random-map width height mines)))
Nyt kutsu (generate-random-map-perc 10 10 5) luo satunnaisen 10×10 -miinakentän naapureineen siten, että miinoja on viisi prosenttia kentästä. Ei järin montaa. Mutta jo 20 prosenttia tekee paljon.
Tulosten esittäminen nätisti
Edelläesitellyt funktiot tuottavat kyllä miinakentän, mutta se on pelkkä lista ryhmiteltyjä numeroita, välillä satunnainen äks-kirjain siellä vilahtaa. Ei järin hyvä tapa tutkia tuotoksia, vaikka se tietokoneelle sitten kelpaa oikein mainiosti. Ensin kirjoitin graafisen apumetodin tulostamaan numeroina kentän.
(defn print-minemap
"Prints a mine map for fun"
[width height mines]
; map printing is done imperatically looping through y first, and then x
(doseq [y (range height)]
(println (apply str
(for [x (range width)]
(if (contains? mines [x y])
(str (mines [x y]))
\.))))))
Koodin rakenne on tässä tapauksessa identtinen vastaavaan imperatiiviseen ratkaisuun. Looppaamme ensin y-koordinaatin suhteen (koska tekstiä voi tulostaa rivi kerrallaan, ei satunnaishakuna) ja sitten x-koordinaatin suhteen. Tulostamme pisteitä ja numeroita tarpeen tullen. Näyttää tältä:
user=> (minemap.core/print-minemap 10 10 *1) ..111..... .12x1..... 12x21.111. 2x21..1x1. x21...1121 1211....1x .1x1....11 .11211.... 1111x1.... 1x1111....
Siitä osaa jo ihminen lukea. Mutta entäs jos pistetään PHP:tä paremmaksi, tehdään graafisia kuvatiedostoja?
Karttojen generoiminen PNG-kuviksi
Tässä postauksessa olemme jo Clojuren vahvuuksia nähneet puolin ja toisin, mutta vielä yksi vahvuus on läpikäymättä: Java-puolen hyödyntäminen. Javalla on helppoa piirrellä kuvia. Kuka ei ole sitä kokeillut, niin se onnistuu samalla Graphics2D-luokan oliolla kuin appletien piirtelyssä. Perusidea javana vaikkapa StackOverflow-kysymyksestä. Tämän kääntäminen Clojurelle on ääliömäisen helppoa! Ensin REPL-ympäristössä kokeillaan ja sormeillaan. Kuvia tallentui. Bonuksena kuvankatseluohjelma GQView uudelleenlataa automaattisesti kuvat, jos ne muuttuvat.
Tuosta SO-vastauksesta ja Javan API-sivujen lukemisella saadaan parsittua kasaan suora koodi, joka ei ole täysin funktionaalista alusta loppuun saakka, mutta kompromissejä on otettava. Olen tyytyväinen tuloksiin ilman puhdasta funktionaalisuuttakin.
Ensin viitteeksi, mitä Clojurekoodi kaipaa Javan puolelta:
(ns minemap.graphics (require minemap.core) (import java.io.File) (import java.awt.Color) (import java.awt.image.BufferedImage) (import javax.imageio.ImageIO))
Ei siis paljoa. Sketsailin REPLissä peruspohjan kuvan luomiselle, piirtämiselle ja tallentamiselle. Voitte huomata, että se täsmää Javakoodia aika hyvin.
;; luodaan kuva ja piirtokahva (def bi (BufferedImage. 16 16 BufferedImage/TYPE_INT_ARGB)) (def g (.createGraphics bi)) ;; piirtelyt tässä (.drawLine g 0 0 10 10) (.drawLine g 0 15 15 0) ;; tallennus: (ImageIO/write bi "png" (File. "test.png"))
Okei, suoraan sitten koodin kimppuun. Tai ei ihan vielä. Ensin määritellään värejä. Java.awt.Color on väriluokka, joka ei ole aivan toivoton clojuren seassa:
(def *colors*
{1 (Color. 0xFBFFB6)
2 (Color. 0xFFD178)
3 (Color. 0xFF9F78)
4 (Color. 0xA0FF78)
5 (Color. 0x7BDE52)
6 (Color. 0x65B244)
7 (Color. 0xB24495)
\x Color/red
:background (Color. 0xB5CEFF)})
Siinä on joitain huonoja värejä, joita on onneksi helppo värivalitsimen kanssa vaihtaa. Kuvaukseen on valittu avaimet tietenkin sen mukaan, minkälainen ruutu on kyseessä. Windowsin miinaharavastahan olisi toki voinut ottaa testin vuoksi värit tähän. Kuvauksissa voi näppärästi laittaa kaikkia tietotyyppejä sekaisin, jonka ansiosta vältyimme turhalta näpräilyltä.
Ja sitten se imperatiivinen koodi. Common Lispihän (taikka Emacs Lisp) on aika hyvä imperatiivinen kieli, joten Lisp-syntaksi ei ole mikään huono ratkaisu. Se näyttää luonnolliselta ja jotenkin vain “oikealta”, hyvältä.
(defn draw-png
"Take width, height, and the map of mines. Save to a file.
Supposed to take a generate-random-map{,-perc} mapping."
[width height minemap file]
(let [block 5 ;block size
bi (BufferedImage. (* block width) (* block height) BufferedImage/TYPE_INT_ARGB)
g (.createGraphics bi)]
(do
(.setColor g (*colors* :background))
(.fillRect g 0 0 (* block width) (* block height))
(doseq [[[x y] high] minemap]
(.setColor g (*colors* high))
(.fillRect g (* block x) (* block y) block block))
(ImageIO/write bi "png" (File. file)))))
Eli tätä funktiota kannattaa tarkastella puhtaasti proseduurina. Tietysti se on notkeampaa kuin Java tai C. Ehkä Scala tai Python olisi luontevin vastine? Clojuren (do ...) -rakenne vastaa listaa eri toiminnoista, jotka suoritetaan peräkkäin. Juuri suunniteltu Java-kutsuja kuten tätä varten.
Ensinnäkin luomme tarvittavat oliot. Piirtokahva g on tietenkin tärkein. Maalaamme koko kankaan taustavärillä. Kuka tahansa Graphics2D:tä käyttänyt osaa sen päätellä. Ja ainakin me osaamme. Minulla oli lukiossa sekä yliopiston peruskursseilla lähinnä näiden käyttämistä. Kaikki java koodattiin appleteiksi.
Tarvitsemme silmukkaa, apua! Javassa on for() { .. } -rakenne, täällä on (doseq [] ... ) -rakenne. Puramme kuvauksen palasiksi, valitsemme sopivan värin ruudulle ja pyöräytämme sopivankokoisen neliön kentälle. Ääliömäisen tiivistä ja oudon hyvin luettavissa olevaa.
Viimeinen vaihe on käyttää tallennusta. Ja … se on siinä. Lopputulokset näyttävät esimerkiksi tältä:
Koko kokemus tämän rustailussa oli hyvin positiivinen. Etenkin kun Javalla kuvanpiirtely osoittautui helpommaksi kuin osasin toivoakaan. Ja ihana käyttöympäristö on kruunannut kaiken. Ehkä kuvaruutukaappauksesta välittyy kaikki se tunnelma:
