clojure-rica/maize — pull request #11 by chrishunt (2014-03-02 20:20:49+00:00)
Title: Allow depth-first or breadth-first search

This adds a `search-algorithm` parameter to `search-maze` that can be set to either to [`depth-first`](https://github.com/clojure-rica/maize/blob/104158a77eae9ecabf49df14f857ca5de3b1636e/src-cljs/maze/core.cljs#L47-48) (default) or [`breadth-first`](https://github.com/clojure-rica/maize/blob/104158a77eae9ecabf49df14f857ca5de3b1636e/src-cljs/maze/core.cljs#L50-51). This PR does not add a GUI for changing the search algorithm, but we can take care of that in another PR.

In order to make this possible, I made a bit of a change in how we calculate the maze path.

Instead of keeping track of a single path and backtracking when we hit a dead end, we now keep track of all possible paths and pull one path out for each iteration. In the case of depth-first search, this collection of paths is treated like a stack. Breath-first search treats it as a queue. This allows us use the same search algorithm for both depth-first and breadth-first search.

Highly accurate and [scientific benchmarks](#benchmarks) show that this is a bit faster as well.

Check out these examples!

## Example DB (seizure)
- **Generation:** Depth-first
- **Solve:** Breadth-first

```clojure
(defn generate-maze [maze]
(search-maze (merge maze {:search-algorithm depth-first
:walls (outer-walls maze)
:finished-fn all-locations-visited?})))

(defn solve-maze [maze]
(search-maze (merge maze {:search-algorithm breadth-first
:finished-fn solved?})))
```

![b01](https://f.cloud.github.com/assets/65323/2305008/ba9e165e-a241-11e3-88a5-4dc6b7711d7e.gif)

## Example BB (sweeping)
- **Generation:** Breadth-first
- **Solve:** Breadth-first

```clojure
(defn generate-maze [maze]
(search-maze (merge maze {:search-algorithm breadth-first
:walls (outer-walls maze)
:finished-fn all-locations-visited?})))

(defn solve-maze [maze]
(search-maze (merge maze {:search-algorithm breadth-first
:finished-fn solved?})))
```

![b02](https://f.cloud.github.com/assets/65323/2305009/c29603f8-a241-11e3-9922-0770febb56e2.gif)

## Example BD (idiot)
- **Generation:** Breadth-first
- **Solve:** Breadth-first

```clojure
(defn generate-maze [maze]
(search-maze (merge maze {:search-algorithm breadth-first
:walls (outer-walls maze)
:finished-fn all-locations-visited?})))

(defn solve-maze [maze]
(search-maze (merge maze {:search-algorithm depth-first
:finished-fn solved?})))
```

![d01](https://f.cloud.github.com/assets/65323/2305011/c98b7170-a241-11e3-8eb5-6c824873d9ba.gif)

## Example DD (classic)
- **Generation:** Breadth-first
- **Solve:** Breadth-first

```clojure
(defn generate-maze [maze]
(search-maze (merge maze {:search-algorithm depth-first
:walls (outer-walls maze)
:finished-fn all-locations-visited?})))

(defn solve-maze [maze]
(search-maze (merge maze {:search-algorithm depth-first
:finished-fn solved?})))
```

![d02](https://f.cloud.github.com/assets/65323/2305012/cf529b9c-a241-11e3-8996-8da3f303c034.gif)

## Benchmarks

These benchmarks are created using a highly sophisticated benchmark function.

```clojure
(ns maze.utils)

(defn benchmark [name times fn]
(.log js/console "Benching" name times "times...")
(let [start (js/Date.)]
(dotimes [_ times] (fn))
(let [end (js/Date.)
duration (- (.getTime end) (.getTime start))]
(.log js/console (/ duration times)))))
```

We run the benchmark on the old maze implementation and the new maze implementation 100 times.

```clojure
(utils/benchmark "maze" 100
#(core/solve-maze {:walls (:walls (new-maze))
:size draw/maze-size})))
```

### Development

```clojure
; project.clj
:compiler { :optimizations :whitespace }
```

**Before:**

```
Benching maze 100 times...
727.72
```

**After:**

```
Benching maze 100 times...
674.41
```

### Production

```clojure
; project.clj
:compiler { :optimizations :advanced }
```

**Before:**

```
Benching maze 100 times...
213.86
```

**After:**

```
Benching maze 100 times...
198.03
```