content/blog/2012/10/caves-of-clojure-07-1.markdown @ 88f0e0d8b891
Typo
| author | Steve Losh <steve@stevelosh.com> |
|---|---|
| date | Mon, 19 Dec 2016 13:21:27 -0500 |
| parents | fdf01e99fd51 |
| children | f5556130bda1 |
+++ title = "The Caves of Clojure: Part 7.1" snip = "Region mapping." date = 2012-10-15T09:50:00Z draft = false +++ This post is part of an ongoing series. If you haven't already done so, you should probably start at [the beginning][]. This entry corresponds to the beginning of [post seven in Trystan's tutorial][trystan-tut]. If you want to follow along, the code for the series is [on Bitbucket][bb] and [on GitHub][gh]. Update to the `entry-07-1` tag to see the code as it stands after this post. It's been a while since the last post, but I've been taking care of things and hopefully should be able to write a bit more now. This post is going to be short. It'll cover a relatively self-contained but interesting bit of Trystan's seventh post. The rest of it will be covered in the next entry. [the beginning]: /blog/2012/07/caves-of-clojure-01/ [trystan-tut]: http://trystans.blogspot.com/2011/09/roguelike-tutorial-07-z-levels-and.html [bb]: http://bitbucket.org/sjl/caves/ [gh]: http://github.com/sjl/caves/ <div id="toc"></div> Summary ------- In Trystan's seventh post he adds vertical levels and stairs connecting them. I'm going to cover the first part of that now: mapping out regions. There's been a bit of refactoring since my last post which I'm not going to cover. If you want to see what changed, diff the tags in your VCS of choice. Region Mapping -------------- In order to decide where to place stairs, Trystan maps out "regions" of contiguous, walkable tiles after he generates and smooths the world. I'm going to do the same thing. My goal is to create a "region map", which is a map of coordinates to region numbers. For example, consider the following tiny world map: ```text ..##.. ..#... ..#.## ..#.#. ``` There are three distinct regions in this map: ```text 11##22 11#222 11#2## 11#2#3 ``` So the region map would look like: ```clojure ; x y region {[0 0] 1 [1 0] 1 [4 0] 2 [5 0] 2 ... [5 3] 3} ``` This makes it easy to tell which region a particular tile is in (if any). As usual, I'll start with a few helper functions. These two functions are just for convenience and readability: ```clojure (def all-coords (let [[cols rows] world-size] (for [x (range cols) y (range rows)] [x y]))) (defn get-tile-from-level [level [x y]] (get-in level [y x] (:bound tiles))) ``` The `all-coords` function simply returns a lazy sequence of `[x y]` coordinates representing every coordinate in a level. `get-tile-from-level` encapsulates the act of pulling out a tile from a level given an `[x y]` coordinate. This is helpful because of the way I'm storing tiles (note the ugly `[y x]`). Next up is a function that filters a set of coordinates to only contain those that are actually walkable in the given level (i.e.: those that don't contain a wall tile): ```clojure (defn filter-walkable "Filter the given coordinates to include only walkable ones." [level coords] (set (filter #(tile-walkable? (get-tile-from-level level %)) coords))) ``` This uses the `get-tile-from-level` function as well as `tile-walkable?` from `world.core`. Next is a function to take a coordinate and return which of its neighboring coordinates are walkable: ```clojure (defn walkable-neighbors "Return the neighboring coordinates walkable from the given coord." [level coord] (filter-walkable level (neighbors coord))) ``` This one is almost trivial, but I like building up functions in small steps like this because it's easier for me to read. Now we come to a function with a bit more meat. This is the core of the "flood fill" algorithm I'm going to use to fill in the region map. ```clojure (defn walkable-from "Return all coordinates walkable from the given coord (including itself)." [level coord] (loop [walked #{} to-walk #{coord}] (if (empty? to-walk) walked (let [current (first to-walk) walked (conj walked current) to-walk (disj to-walk current) candidates (walkable-neighbors level current) to-walk (union to-walk (difference candidates walked))] (recur walked to-walk))))) ``` In a nutshell, this function loops over two sets: `walked` and `to-walk`. Each iteration it grabs a coordinate from `to-walk` and sticks it into the `walked` set. It then finds all the coordinates it can walk to from that coordinate using a helper function. It uses `clojure.set/difference` to determine which of those are new (i.e.: still need to be walked) and sticks them into the `to-walk` set. Then it recurs. The code for this is surprisingly simple and easy to read. It's mostly just shuffling things between sets. Eventually the `to-walk` set will be empty and `walked` will contain all the coordinates that we want. Finally comes the function to create the region map for an entire level: ```clojure (defn get-region-map [level] (loop [remaining (filter-walkable level all-coords) region-map {} n 0] (if (empty? remaining) region-map (let [next-coord (first remaining) next-region-coords (walkable-from level next-coord)] (recur (difference remaining next-region-coords) (into region-map (map vector next-region-coords (repeat n))) (inc n)))))) ``` This function also uses Clojure sets to its advantage. Once again, I loop over a couple of variables. `remaining` is a set containing all the coordinates whose regions has not yet been determined. Each iteration it pulls off one of the remaining coordinates. Note that I'm using `first` to do this. `remaining` is a set, which is unordered, so `first` effectively could return any element in the set. For this loop that doesn't matter, but it's important to be aware of if you're going to use the same strategy. After pulling off a coordinate, it finds all coordinates walkable from that coordinate with the `walkable-from` flood-fill function. It removes all of those from the `remaining` set, shoves them into the region map, and increments the region number before recurring. Visualization ------------- I'm going to save the rest of Trystan's seventh post for another entry, but since this one ended up pretty short I'm also going to go over visualizing the region map I've just created. First I need to generate the region map when I create the world, and attach it to the world itself so we can access it from other places: ```clojure (defn random-world [] (let [world (->World (random-tiles) {}) world (nth (iterate smooth-world world) 3) world (populate-world world) world (assoc world :regions (get-region-map (:tiles world)))] world)) ``` The last line in the `let` is where it gets generated. It's pretty straightforward. I'd like to be able to toggle the visualization of regions off and on, so I'm going to introduce a new concept to the game: "debug flags". I updated the `Game` record to include a slot for these flags: ```clojure (defrecord Game [world uis input debug-flags]) ``` I then updated the `new-game` function to initialize them (currently there's only one) to default values: ```clojure (defn new-game [] (map->Game {:world nil :uis [(->UI :start)] :input nil :debug-flags {:show-regions false}})) ``` The user needs a way to toggle them. For now I'll just bind it to a key. In the future I could make a debug UI with a nice menu. ```clojure (defmethod process-input :play [game input] (case input :enter (assoc game :uis [(->UI :win)]) :backspace (assoc game :uis [(->UI :lose)]) \q (assoc game :uis []) \h (update-in game [:world] move-player :w) \j (update-in game [:world] move-player :s) ; ... \R (update-in game [:debug-flags :show-regions] not) game)) ``` Now when the user presses `R` (Shift and R) it will toggle the state of the `:show-regions` debug flag in the game. All that's left is to actually *draw* the regions somehow. First, we only want to do this if `:show-regions` is `true`. I edited the `:play` UI's drawing function to do this: ```clojure (defmethod draw-ui :play [ui game screen] (let [world (:world game) {:keys [tiles entities regions]} world player (:player entities) [cols rows] (s/get-size screen) vcols cols vrows (dec rows) origin (get-viewport-coords game (:location player) vcols vrows)] (draw-world screen vrows vcols origin tiles) ; ****************** (when (get-in game [:debug-flags :show-regions]) (draw-regions screen regions vrows vcols origin)) ; ****************** (doseq [entity (vals entities)] (draw-entity screen origin vrows vcols entity)) (draw-hud screen game) (draw-messages screen (:messages player)) (highlight-player screen origin player))) ``` The marked lines are the only new ones. I'm going to draw regions after/above the world tiles (so they'll show up at all) but before/below the entities (so we can still see what's going on). Drawing the regions is fairly simple, if a bit tedious: ```clojure (defn draw-regions [screen region-map vrows vcols [ox oy]] (letfn [(get-region-glyph [region-number] (str (nth "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" region-number)))] (doseq [x (range ox (+ ox vcols)) y (range oy (+ oy vrows))] (let [region-number (region-map [x y])] (when region-number (s/put-string screen (- x ox) (- y oy) (get-region-glyph region-number) {:fg :blue})))))) ``` For now, bad things will happen if we have more than 62 regions in a single level. In practice I usually end up with about 20 to 30, so it's not a big deal. To sum up this function: it iterates through every coordinate in the level that's displayed in the viewport, looks up its region number in the region map, and draws the appropriate letter if it has a region number. Results ------- Now that I've got a way to visualize regions it becomes much easier to check whether they're getting set correctly. Here's an example of what it looks like when you toggle `:show-regions` with `R`:   As you can see, the small, closed off areas have their own numbers, while the larger regions sprawl across the map. You can view the code [on GitHub][result-code] if you want to see the end result. [result-code]: https://github.com/sjl/caves/tree/entry-07-1/src/caves The next article will finish Trystan's seventh post by adding multiple z-levels to the caves.