BSP implementation

Jak tam idzie implementacja Binary Space Partitioning?

Całkiem całkiem, pierwsza wersja już śmiga.

Pierwsza? To będzie więcej?

Prawdopodobnie…
Ale zanim do tego przejdziemy spójrzmy na to co już mamy.

Zasadę działania BSP opisywałem wcześniej więc wejdziemy od razu do kodu.

W kwestii architektonicznej pojawiła się wcześniej przestrzeń “rl-engine.dungeon-generator”.
Dodajmy więc nasz nowy generator do API.

(def generators
  {"empty" rl-engine.dungeon-generator.empty/generate-dungeon
   "bsp" rl-engine.dungeon-generator.bsp/generate-dungeon})

BSP

Mimo, iż sam koncept jest prosty to już implementacja okazuje się troszeczkę bardziej skomplikowana.

Rozbijmy algorytm na mniejsze kawałki:

1. Sprawdź czy możesz wygenerować poziom dla podanych wymiarów
2. Wygeneruj binarne drzewo pokoi
3. Drzewo musi zawierać współrzędne oraz rozmiar
4. Przepisz drzewo na dwuwymiarową tablicę

Generowanie drzewa

(defn split-room
  [root randomizer]
  (let [height (:height root)
        width (:width root)
        top (:top root)
        left (:left root)
        ratio (randomizer)]
    (if (can-split-room? height width ratio)
      (let [split-dimension (get-split-dimension height width ratio randomizer)]
        {:height height
         :width  width
         :top    top
         :left   left
         :leaf-a (split-room (get-leaf-a root split-dimension ratio) randomizer)
         :leaf-b (split-room (get-leaf-b root split-dimension ratio) randomizer)})
      root)))

(defn generate-rooms-tree
  "Generates tree of rooms."
  ([height width]
   (generate-rooms-tree height width (rand)))
  ([height width randomizer]
   (if (is-space-for-room? height width)
     (let [root {:height height
                 :width  width
                 :left   0
                 :top    0}]
       (split-room root randomizer))
     {})))

Najpierw sprawdzamy, czy mamy miejsce na pokój (minimum 3×3)

(is-space-for-room? height width)

Jeżeli tak to tworzymy pierwszy korzeń (z maksymalnymi rozmiarami) i dzielimy go:

(let [root {:height height
            :width  width
            :left   0
            :top    0}]
     (split-room root randomizer))

Potem losujemy stosunek podziału (ratio)

  (let [..
        ratio (randomizer)]

randomizer jest funkcją generującą losowe liczby rzeczywiste z przedziału 0 – 1.

Jeżeli pokój po podziale nie jest za mały to losujemy wymiar w jakim dzielimy (wysokość albo szerokość) i dzielimy korzeń na dwa liście. (Oczywiście liście również rekurencyjnie dzielimy przed przypisaniem)

(if (can-split-room? height width ratio)
      (let [split-dimension (get-split-dimension height width ratio randomizer)]
        {:height height
         :width  width
         :top    top
         :left   left
         :leaf-a (split-room (get-leaf-a root split-dimension ratio) randomizer)
         :leaf-b (split-room (get-leaf-b root split-dimension ratio) randomizer)})
      root))

Jeżeli nie możemy podzielić – zwracamy obecny korzeń.

Generowanie poziomu na bazie drzewa

(defn generate-floor-from-tree
  [tree]
  (let [max-height (:height tree)
        max-width (:width tree)
        leaf-a (:leaf-a tree)
        leaf-b (:leaf-b tree)
        tree-root-map (generate-floor
                        max-height
                        max-width
                        #(get-empty-room-cell %1 %2 max-height max-width))]
    (if (and (nil? leaf-a) (nil? leaf-b))
      tree-root-map
      (sum-tree-floors [{:floor (generate-floor-from-tree leaf-a)
                         :tree  leaf-a},
                        {:floor (generate-floor-from-tree leaf-b)
                         :tree  leaf-b}]
                       max-height
                       max-width))))

(defn generate-dungeon
  "Generates new dungeon floor."
  ([height width]
   (generate-dungeon height width #(generate-rooms-tree height width)))
  ([height width tree-generator]
   (let [tree (tree-generator)]
     (if (= {} tree)
       (generate-empty-floor height width)
       (generate-floor-from-tree tree)))))

Najpierw generujemy drzewo za pomocą podanej funkcji tree-generator.

(let [tree (tree-generator)]
..)

Potem dla korzenia w drzewie generujemy pokój (podobnie jak w algorytmie pustego pokoju)

(let [max-height (:height tree)
        max-width (:width tree)
        leaf-a (:leaf-a tree)
        leaf-b (:leaf-b tree)
        tree-root-map (generate-floor
                        max-height
                        max-width
                        #(get-empty-room-cell %1 %2 max-height max-width))]
..)

Następnie jeżeli korzeń ma liście (tak, wiem brzmi absurdalnie) to generujemy pokoje dla liści i je sumujemy.

Sumowanie pokoi polega na wybraniu wszystkich ścian z obydwu pomieszczeń.

Jeśli korzeń nie posiada liści – kończymy generowanie.

    (if (and (nil? leaf-a) (nil? leaf-b))
      tree-root-map
      (sum-tree-floors [{:floor (generate-floor-from-tree leaf-a)
                         :tree  leaf-a},
                        {:floor (generate-floor-from-tree leaf-b)
                         :tree  leaf-b}]
                       max-height
                       max-width))))

Oczywiście do każdego komponentu mamy testy.

Drzewo:

(deftest generates-tree-with-two-rooms
  (testing "when space allows for two rooms"
    (testing "when randomizer allows for room split")
    (let [randomizer (constantly 0.5)]
      (testing "room number is 2"
        ;1 1 1
        ;1 0 1
        ;1 1 1
        ;1 0 1
        ;1 1 1
        (is (= 2 (rooms-count (generate-rooms-tree 3 5 randomizer))))
        ;1 1 1 1 1
        ;1 0 1 0 1
        ;1 1 1 1 1
        (is (= 2 (rooms-count (generate-rooms-tree 5 3 randomizer)))))

Poziom:

(deftest correctly-renders-tree
  (testing "empty tree"
    (is (= [[0, 0],
            [0, 0]]
           (generate-dungeon 2 2 (constantly {}))))
    (is (= [[0]]
           (generate-dungeon 1 1 (constantly {})))))
  (testing "one room tree"
    (is (= [[1, 1, 1],
            [1, 0, 1],
            [1, 1, 1]]
           (generate-dungeon 3 3 (constantly
                                   {:height 3
                                    :width  3
                                    :left   0
                                    :top    0}))))

A tutaj kilka efektów obecnej implementacji:

Wszystko fajnie ale dalej nie odpowiedziałeś dlaczego jest to “pierwsza” wersja…

No cóż, do pełnego algorytmu potrzebujemy jeszcze wygenerowane pokoje połączyć oraz lekko poprzycinać – bo w tej chwili zajmują maksymalną powierzchnię.

Poza tym w środku implementacji leży mały problem…