Idiomatic Clojure? Performant & functional enough?

Question

Problem

Disclaimer: This is my first clojure function & I'm still busy finishing the last chapters of "Programming Clojure". Thanks! :)

I am writing a function to randomly flood-fill parts of a game's map (i.e. this is not a traditional flood-fill that can recursively fill all available space). The idea is to create a random-shaped island, and inside that island create a random-shaped mountain. (i.e. pass the set of island points as a filter to the next flood fill function, so the mountain will be created only within the island's tiles).

This is what my code currently produces (You'll notice the window / drawing code stolen from the snake game in PragProg's Programming Clojure. ;))

Clojure Style

This is my code:

(def dirs2 '([-1 0] [1 0] [0 -1] [0 1]))

(defn neighbours [pt]
  (for [dir dirs2]
    (vec (map + pt dir))))

(defn flood-fill2 
  "start -> point to start filling from
   n -> number of tiles to create
   filter-fn -> a fn that must return true for new points"
    ([start n]
      (flood-fill2 start n (fn [& _] true)))
    ([start n filter-fn]
     (loop [result #{}
      candidates #{start}
      i n]
      (if (or (zero? i) (empty? candidates))
        result 
        (let [current (rand-nth (seq candidates))]
          (if (and (filter-fn current) (not (result current)))
            (recur 
              (conj result current) 
              (apply conj (disj candidates current) (neighbours current))
              (dec i))
            (recur result (disj candidates current) i)))))))

• Is this idiomatic clojure code? The loop construct in there feels like standard iterative code I learned to write in Java / C++. Do you see a shorter way to write this?

• Could I implement this as a lazy-seq somehow? (take 600 (lazy-fill [25 25] optional-src-set)) looks much cooler than (flood-fill2 [25 25] 600 island).

• I tried to write an anonymous function that returns true for any argument(s) using this notation #() but had to eventually give up and wrote it using fn: (fn [& _] true). Could I have used #() somehow?

Performance

My intial (naive) implementation looked like this:

(defn flood-fill [filled n]
  (if (zero? n)
    filled
    (let [start-point (rand-nth filled)
      next-point (rand-nth (neighbours start-point))] 
      (if (contains? (set filled) next-point)
        (recur filled n)
        (recur (cons next-point filled) (dec n))))))

But:

user=> (time (flood-fill [[25 25]] 1250))
(time (flood-fill [[25 25]] 1250))
"Elapsed time: 8430.56 msecs"
([8 18] [43 40] [23 9] [38 40] ...

My flood-fill2 does much better:

user=> (time (flood-fill2 [25 25] 1250))
(time (flood-fill2 [25 25] 1250))
"Elapsed time: 257.361 msecs"
#{[34 33] [35 34] [36 3] [36 35] [38 5] [10 9] ...

But using (time (flood-fill2 [500 500] 500000)) to fill 50% of a 1000 * 1000 tiles map takes forever (@ 100% CPU). I ended up killing that REPL.

Any performance suggestions? I tried to avoid many conversions from Sets to Vectors/Lists, but rand-nth needs a sequence and I couldn't find a nice "random set element" function.

Thanks for reading all of this.

Answer 1

I am a journeyman myself in clojure, and I don't have answers for all of your questions, but I have some input.

I am not sure I fully understand your algorithm, but it seems you really have two loops rolled in to one. You have an inner loop looking for what could be the next tile to paint (without counting i), and an outer loop actually filling pixels and counting i down from n. Maybe it could be clearer if you separated these two somehow.

And since you choose candidates on random, it will be random how long it takes for you to fill n tiles.

I have found that when I do:

(loop [result ()
       input input-seq]
    (let [item (computation input)]
        (recur (conj result item) (rest input)))

It can often be re-written as:

(reduce computation input-seq)

(But I can't immediately see if this applies to your function)

Have you considered implementing this using a 2d array of tiles, instead of a list of coordinates?

A couple of other issues:

• you can create a function which always returns true with: (constantly true)
• I really like the use of (for (map +)) for vector addition, but you can use (mapv) instead of (vector (map))