I've finally completed my parallel flood filling algorithm in Clojure. It's purpose is to fill the game map with weights, telling how far it is from this particular node to the goal. Using this information, the enemies can just ask the cell beneath them where to go next. Kind of like following the trail of bread crumbs to find home. Here is a video (with a sleep between every iteration, else it doesn't get caught on video) demonstrating it. Every blue cell represents where a current thread (because it's multi threaded by a ExecutorService) is working right now. You can probably figure out what the rest means.

We start of with this function, which uses a help function called flood-loop, which recurs upon itself for as long as the queue is not empty. This is probably not very idiomatic Clojure and I'd love to hear your thoughts if you have any suggestions. As you can see, the heart of the function is the priority-map, which works like a sorted-map, but sorts on value rather than key.

(defn flood-map [hmap pos]
  (dosync (ref-set flooding true)
      (ref-set ac {})
      (ref-set nruns 0))
  (let [que (ref (priority-map))]
    (dosync (alter que assoc pos 0))
    (flood-loop hmap que)))

This is the before mentioned helper function, which partitions the current queue and gives every worker thread something to do. Chunking helps the performance because it reduces threads requesting more work.

(defn flood-loop [hmap que]
  (when @flooding
    (let [floods (for [partial (partition-all 5 @que)]
           #(doseq [[pos depth] partial]
             (dosync (alter que dissoc pos))
             (flood-cell hmap pos depth que)))]
      (.invokeAll ^ExecutorService pool floods)
      (when (> (count @que) 0)
    (recur hmap que)))))

This is the big one, which finds every "child" (cell with a larger weight, which needs updating) of the cell, updates a cell with information about it's parents (the opposite of children) and adds the children's positions to the queue to the processed.

(defn flood-cell [hmap pos depth que]
  (dosync (commute nruns inc)
      (alter active-cells assoc (. Thread currentThread) pos))
  (when @flooding
        ;(Thread/sleep 10) 
    (let [me (get-cell hmap pos)
      neighbors (for [cell (adj-cells hmap pos)
              :when (walkable? cell)] cell)
      parents (best-parents neighbors)
      children (for [n neighbors :when (deeper? n me)] n)]
      (when (< depth (:distance @me))        
        (dosync (alter me assoc :distance depth)
          (alter me assoc :parents parents))
        (doseq [cell children]
          (dosync (alter que assoc (:pos @cell) (inc depth))))))))

The complexity of this algorithm is now O(#cells) with a semi high constant, but after JIT warmup it still finishes in under 50 msec in the average case, which is good enough for me. The original version worked in O(god knows what) due to using a stack (the recursion stack) and having to redo a bunch of calculations instead of a proper queue.

Functional programming is very different from OOP-style, which is something I find fun and challenging, but also frustrating at times when my inexperience with the paradigm renders me unable to complete simple tasks such as this.

All in all I'm very pleased with the results. The original version took almost 3 seconds to complete and required over 13000 iterations (that's quite horrid for a 768 cell map) due to it having to update most cells multiple times in a single thread.

So remember kids; First you make it work and THEN you make it fast.