# HG changeset patch # User Steve Losh # Date 1350160233 14400 # Node ID c35f9bfbfcae4f5c1b2565421ea1d824602a5456 # Parent 6432040d5154d7591ee292bc3e82346b7b87d265 Caves of Clojure part 7.1. diff -r 6432040d5154 -r c35f9bfbfcae content/blog/2012/10/caves-of-clojure-07-1.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/content/blog/2012/10/caves-of-clojure-07-1.html Sat Oct 13 16:30:33 2012 -0400 @@ -0,0 +1,329 @@ + {% extends "_post.html" %} + + {% hyde + title: "The Caves of Clojure: Part 7.1" + snip: "Region mapping." + created: 2012-10-15 09:50:00 + flattr: true + %} + +{% block article %} + +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/ + +[TOC] + +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`: + +![Screenshot without Regions](/media/images{{ parent_url }}/caves-07-1-1.png) + +![Screenshot with Regions](/media/images{{ parent_url }}/caves-07-1-2.png) + +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. + +{% endblock article %} diff -r 6432040d5154 -r c35f9bfbfcae media/images/blog/2012/10/caves-07-1-1.png Binary file media/images/blog/2012/10/caves-07-1-1.png has changed diff -r 6432040d5154 -r c35f9bfbfcae media/images/blog/2012/10/caves-07-1-2.png Binary file media/images/blog/2012/10/caves-07-1-2.png has changed