Road to BSP

Zanim skoczymy prosto w implementację BSP może wypadało by zrobić małą rozgrzewkę?
Weźmy zatem ołówek i zakreślmy ramy architektoniczne.

Architektura

BSP jest algorytmem generowania poziomów – potrzebujemy więc fragmentu API przez który ów algorytm będzie dostępny dla klienta.

Zaszkicujmy nasze API dostępowe:

(def generators
  {"empty" rl-engine.dungeon-generator.empty/generate-dungeon})
 
(defn list-generators
  "Returns vector with names of all available dungeon generators."
  []
  (keys generators))
 
(defn get-generator
  "Returns generator with given name."
  [name]
  (get generators name))

Mamy tutaj dwie funkcje odpowiadające za:

• Dostęp do listy nazw wszystkich algorytmów
• Dostęp do wybranego algorytmu po nazwie

A dlaczego tak? Nie można by było udostępnić po prostu funkcji dla każdego algorytmu?

Ależ oczywiście, że można by było – kwestia w tym, że ich ilość będzie się zmieniać. Więc jeżeli wystawimy naszym klientom np. metodę per algorytm to będą oni bardzo niepocieszeni, jeżeli w kolejnej wersji biblioteki metoda to zmieni swoją nazwę bądź argumenty (szczególnie w dynamicznie typowanym języku).

Struktura danych

Ok, mamy pierwsze API – teraz zabierzemy się za strukturę danych.

Tutaj nie będziemy wymyślać nic nadzwyczajnego – poziom w rougelike’ach najnaturalniej zobrazować w dwuwymiarowej tablicy np:

Dla uproszczenia w naszej wersji oznaczymy sobie:

• Podłoga – 0
• Ściana – 1

Czyli przykładowy poziom będzie wyglądał tak:

1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1

Prosta implementacja

Jaki jest najprostszy algorytm generowania poziomów?

Pusty!

Dokładnie. Napiszmy więc algorytm generujący jeden pusty pokój.

(ns rl-engine.dungeon-generator.empty)

(def FLOOR 0)
(def WALL 1)

(defn get-cell [current-height current-width max-height max-width]
  (cond
    (= 0 current-height) WALL
    (= 0 current-width) WALL
    (= (dec max-height) current-height) WALL
    (= (dec max-width) current-width) WALL
    :else FLOOR))

(defn get-row [current-height max-height max-width]
  (map
    #(if (or (< max-height 3) (< max-width 3))
      FLOOR
      (get-cell current-height % max-height max-width))
    (take max-width (range))))

(defn generate-dungeon
  "Generates new dungeon floor."
  [height width]
  (map
    #(get-row % height width)
    (take height (range))))

Warto zauważyć, że pojawia nam się tutaj kolejny fragment architektoniczny – definiujemy interfejs między klientem a algorytmem.
Będziemy wymagać od klienta aby podał nam wymaganą wysokość i szerokość poziomu.

Ok, a teraz przejdźmy po kodzie.

Zacznijmy od końca:

(take height (range))

Generujemy tutaj listę liczb całkowitych o ilości height za pomocą wbudowanej funkcji range.
Będzie to nasza lista wysokości.

[0, 1, 2, 3, 4]

Teraz dla każdego elementu w tej liście generujemy wiersz kolejnych liczb (get-row).
Będzie to nasza lista szerokości.

  (map
    #(get-row % height width)
    (take height (range))))

(% jest tutaj elementem w kolekcji a height i width są stałymi)

[[0, 1, 2, 3, 4],
 [0, 1, 2, 3, 4],
 [0, 1, 2, 3, 4],
 [0, 1, 2, 3, 4],
 [0, 1, 2, 3, 4]]

Jest to nasza tablica wynikowa. (Wektor wektorów gwoli ścisłości)

Funkcja get-row powinna wyglądać tak:

  (map
    (get-cell current-height % max-height max-width)
    (take max-width (range)))

Czyli dla każdego elementu w wierszu wymieniamy go na odpowiednią wartość komórki poziomu (podłoga bądź ściana).

Ale dodajmy jej jeszcze warunek brzegowy – pokój musi mieć minimalną wielkość 3×3, w innym wypadku nie ma żadnych ścian.

(defn get-row [current-height max-height max-width]
  (map
    #(if (or (< max-height 3) (< max-width 3))
      FLOOR
      (get-cell current-height % max-height max-width))
    (take max-width (range))))

Teraz pozostaje sprawdzić czy dana komórka powinna być ścianą (czy ma index minimalny lub maksymalny na wysokości bądź szerokości).

(defn get-cell [current-height current-width max-height max-width]
  (cond
    (= 0 current-height) WALL
    (= 0 current-width) WALL
    (= (dec max-height) current-height) WALL
    (= (dec max-width) current-width) WALL
    :else FLOOR))

Oczywiście razem z implementacją dbamy o unit testy:

(deftest dungeon-has-outer-wall
  (testing "when dungeon size is less then 3x3 all cells have 0"
    (is (= [[0]] (generate-dungeon 1 1)))
    (is (= [[0,0],
            [0,0]] (generate-dungeon 2 2)))
    (is (= [[0,0,0],
            [0,0,0]] (generate-dungeon 2 3)))
    (is (= [[0,0],
            [0,0],
            [0,0]] (generate-dungeon 3 2))))
  (testing "dungeon floor have single wall along edges"
     (is (= [[1, 1, 1],
             [1, 0, 1],
             [1, 1, 1]] (generate-dungeon 3 3)))

     (is (= [[1, 1, 1, 1, 1],
             [1, 0, 0, 0, 1],
             [1, 1, 1, 1, 1]] (generate-dungeon 3 5)))

     (is (= [[1, 1, 1, 1, 1],
             [1, 0, 0, 0, 1],
             [1, 0, 0, 0, 1],
             [1, 0, 0, 0, 1],
             [1, 1, 1, 1, 1]] (generate-dungeon 5 5)))))

Uff, trochę tego się nazbierało…
Chociaż kod sam w sobie jest bardzo krótki…

Widać, że clojure jest bardzo zwięzły a przy tym nie traci na czytelności – po odpowiednim przestawieniu kolejności czytania oczywiście 🙂