..O Deniz's personal pages
/home /about

Island detection / Flood fill with clojure

May 9, 2018

I had already talked about a mutable version of this algorithm for flood filling island detection here. This time I went immutable with clojure The algorithm is a bit different, this we will not have a variable in the outer scope but pass a new instance of a board (which is efficiently managed by clojure) to the function for each iteration/recursion.

The full source is at https://gitlab.com/dendiz/kelimelik-clj/tree/master

there a few helper functions

first-char-on-board scans the board to find the first tile that is not empty split this will split a string such as “abc” into a vector as ["a" "b" "c"]

the basic idea is to keep a list of next slots to visit on the board as we visit slots. the next-frontier function will return a list of next slots. This is basically BFS search on a graph.

(defn flood-fill
  "flood fill the board starting from the first non empty slot.
   the flooded slots will contain '!' empty slots '.'. If there
   are islands they will contain letters.
  (let [[y x] (first-char-on-board board)
        board (mapv split board)
    (loop [board board
           frontier [[x y]]]
      (if (-> frontier count zero?)
        (let [front (first frontier)
              x (first front)
              y (second front)]
           (assoc-in board [y x] "!")
           (concat (next frontier) (next-frontier board [x y]))))))))

the next-frontier code is also worth mentioning

(defn next-frontier
  "return the coordinates of candidate neighbors for flood filling"
  [board [x y]]
  (for [i [(dec y) y (inc y)]
        j [(dec x) x (inc x)]
        :when (and (>= i 0)
                   (>= j 0)
                   (< i 15)
                   (< j 15)
                   (or (= x j) (= y i))
                   (not (and (= x j) (= y i)))
                   (not= "!" (get-in board [i j]))
                   (not= "." (get-in board [i j])))]
    [j i]))

flood-fill will mark visited slots with ! and next-frontier will return a list of the candidate slot from the 8 neighbors of the current slot. if the neighbor is visited or empty it’s not included in the list.

if the starting board was like this


the flood would start with a and the next-frontier would return only b from the neighbors and mark a as !. b would return c and e and d. a would be marked as ! so it would not be included. After the fill the board would be like


this algorithm is useful when detecting if the scrabble board is connected.

Tags: #programming