Invader Detector

Background. This app takes in an ASCII representation of space invaders and a radar sample, and does pattern recognition to locate them.

Walkthrough

If you're using this program, sadly you know we have no time to waste.

cd /path/to/invader-detector

./detect-invaders.sh \
  --radar-sample-file resources/spec-radar-sample-2-guys.txt \
  --invader-files resources/spec-invader-1.txt:resources/spec-invader-2.txt \
  --print-ascii

---╭84%─────╮------o-╭91%────────╮-
-oo│---oo---│-o--o-o-│--o-----o--│-
-o-│--oooo--│---oo---│-------o---│-
---│oooooooo│--o-----│--oooo-oo--│-
---│oo-oo--o│-o--o---│----ooo-oo-│-
o--│-ooooooo│--------│o--oooooo-o│-
o--│--o--ooo│--o----o│o-o-ooooo-o│-
---│-o-oo---│-----o-o│o-o-----o-o│-
---│oo--oo-o│-----o--│---oo-oo---│-
---╰────────╯------o-╰───────────╯-
---o----o------o-----╰────────╯──╯-

Let's clarify that image with --output-ascii-on-char "█" and --output-ascii-off-char " ":

./detect-invaders.sh \
  --radar-sample-file resources/spec-radar-sample-2-guys.txt \
  --invader-files resources/spec-invader-1.txt:resources/spec-invader-2.txt \
  --print-ascii \
  --output-ascii-on-char "█" --output-ascii-off-char " "

   ╭84%─────╮      █ ╭91%────────╮ 
 ██│   ██   │ █  █ █ │  █     █  │ 
 █ │  ████  │   ██   │       █   │ 
   │████████│  █     │  ████ ██  │ 
   │██ ██  █│ █  █   │    ███ ██ │ 
█  │ ███████│        │█  ██████ █│ 
█  │  █  ███│  █    █│█ █ █████ █│ 
   │ █ ██   │     █ █│█ █     █ █│ 
   │██  ██ █│     █  │   ██ ██   │ 
   ╰────────╯      █ ╰───────────╯ 
   █    █      █     ╰────────╯──╯ 

If you prefer images, try --save-images two-invaders.png:

./detect-invaders.sh \
  --radar-sample-file resources/spec-radar-sample-2-guys.txt \
  --invader-files resources/spec-invader-1.txt:resources/spec-invader-2.txt \
  --save-images two-invaders.png

Shell-shocked veterans who've seen too many invaders appreciate --output-ascii-opaque-fill:

./detect-invaders.sh \
  --radar-sample-file resources/spec-radar-sample-2-guys.txt \
  --invader-files resources/spec-invader-1.txt:resources/spec-invader-2.txt \
  --print-ascii \
  --output-ascii-on-char "█" \
  --output-ascii-off-char " " \
  --output-ascii-opaque-fill

   ╭84%─────╮      █ ╭91%────────╮ 
 ██│        │ █  █ █ │           │ 
 █ │        │   ██   │           │ 
   │        │  █     │           │ 
   │        │ █  █   │           │ 
█  │        │        │           │ 
█  │        │  █    █│           │ 
   │        │     █ █│           │ 
   │        │     █  │           │ 
   ╰────────╯      █ ╰───────────╯ 
   █    █      █     ╰────────╯──╯ 

The default match score is 70%. The radar gets crowded with --score-threshold 60:

./detect-invaders.sh \
  --radar-sample-file resources/spec-radar-sample-2-guys.txt \
  --invader-files resources/spec-invader-1.txt:resources/spec-invader-2.txt \
  --print-ascii \
  --output-ascii-on-char "█" \
  --output-ascii-off-char " " \
  --output-ascii-opaque-fill \
  --score-threshold 60

│6╭╭84%─────╮─╮─╮╮ █ ╭91%────────╮─
│ ││        │ │ ││ █ │           │ 
│ ││        │ │ ││   │           │ 
│ ││        │ │ ││   │           │ 
│ ││        │ │ ││   │           │ 
│ ││        │ │ ││   │           │ 
│ ││        │ │ ││  █│           │ 
│ ││        │ │ ││█ █│           │ 
╰─││        │ │ ││█  │           │ 
  ╰╰────────╯─╯─╯╯ █ ╰───────────╯─
  ╰────────╯─╯ █     ╰────────╯──╯─

So far, we've focused on human UIs. But naturally we'll need more precise data:

./detect-invaders.sh \
  --radar-sample-file resources/spec-radar-sample-2-guys.txt \
  --invader-files resources/spec-invader-1.txt:resources/spec-invader-2.txt \
  --print-matches

({:invader-id 0,
  :bbox {:x 22, :y 1, :width 11, :height 8},
  :score 90.9090909090909}
 {:invader-id 1,
  :bbox {:x 4, :y 1, :width 8, :height 8},
  :score 84.375}
 {:invader-id 1,
  :bbox {:x 22, :y 2, :width 8, :height 8},
  :score 71.875}
 {:invader-id 1,
  :bbox {:x 25, :y 2, :width 8, :height 8},
  :score 70.3125})

Let's try a bigger radar sample:

./detect-invaders.sh \
  --radar-sample-file resources/spec-radar-sample.txt \
  --invader-files resources/spec-invader-1.txt:resources/spec-invader-2.txt \
  --save-images spec-locations-threshold-70.png

Usage

There's quite a few options. Also, you can use multiple output switches together in a single commandline.

./detect-invaders.sh --help
Detect invaders in radar samples.

Usage: ./invader-detector.sh [options]

Options:
      --radar-sample-file FILE                       Radar sample file
      --invader-files FILES                          Invader files separated by colons
      --input-on-chars CHARS        o,O              Characters denoting 'on', separated by commas
      --input-off-chars CHARS       -                Characters denoting 'off', separated by commas
      --input-lenient-parsing       true             Be lenient when interpreting input files.

      --max-results COUNT                            Maximum number of matches
      --score-threshold PERCENT     70               Minimum match score to include in results. Number from 0 to 100

      --print-ascii                                  Print ascii to screen
      --save-ascii FILE                              Output text file
      --save-images FILES                            Output image files, separated by colons.
      --print-matches                                Print matches to screen
      --save-matches FILE                            File with EDN-encoded matches
      --invader-colors COLORS       #4300ff,#44f20d  Colors to highlight invaders. Recycled if fewer colors than invaders.
      --output-ascii-on-char CHAR   o                For ascii output, character denoting 'on'.
      --output-ascii-off-char CHAR  -                For ascii output, character denoting 'off'.
      --output-ascii-opaque-fill                     For ascii output, make bounding boxes blank inside.
  -h, --help

Design

Where to start?

One place is user.clj, a developer sandbox that's likely more convenient than the CLI. Simply evaluating the whole buffer will print results in the REPL, as well as save images and matches to a temp dir.

It calls run.clj, which coordinates the sources/processors/sinks pipeline:

pixel-matrix is a 2D vector representing a radar sample or pattern:

[[0 0 0 1 1 0 0 0]
 [0 0 1 1 1 1 0 0]
 [0 1 1 1 1 1 1 0]
 [1 1 0 1 1 0 1 1]
 [1 1 1 1 1 1 1 1]
 [0 0 1 0 0 1 0 0]
 [0 1 0 1 1 0 1 0]
 [1 0 1 0 0 1 0 1]]

scorebox is a map representing a bounding box in the radar sample, with a score that estimates the likelihood that an invader's in the bounding box:

{:score 5/8
 :bbox {:x -1, :y -1, :width 6, :height 8}}

Testing

clj -X:test runs tests.

Two testing frameworks:

• Rich Comment Tests: Helps illustrate sourcecode.
• Expectations: More expressive than clojure.test, but compatible with its tooling.

Performance

“The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.”

— Donald Knuth, "Computer Programming as an Art"

This currently uses a O(N²) algorithm. If performance optimization's needed, Criterium (a handy benchmarking library) is included in the :deps alias.

There's many optimization opportunities to consider, if performance is ever needed: improved algorithms, batching, judicious parallelism, CPU cache-friendly datastructures, bit-vector comparisons, pre-processing, etc.

License

Copyright © 2025 Tayssir John Gabbour