Module: TinyFill

Defined in:
lib/tiny_fill.rb

Overview

TinyFill is a module that implements a flood fill algorithm. It’s useful in games for detecting enclosed areas within a 2D map.

usage:

map = [
  [false, false, true,  false, false],
  [false, false, true,  false, false],
  [false, false, true,  false, false],
  [true,  true,  true,  false, false],
  [false, false, false, false, false],
]

# fill any enclosed area starting at [1, 1], max search of 10 cells

TinyFill.fill!(
  map: map,
  start_x: 1,
  start_y: 1,
  max_search: 10
)

=> [
  [true,  true,  true,  false, false],
  [true,  true,  true,  false, false],
  [true,  true,  true,  false, false],
  [true,  true,  true,  false, false],
  [false, false, false, false, false],
]

Class Method Summary collapse

Class Method Details

.fill!(map:, start_x:, start_y:, max_search:) ⇒ Object 



34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/tiny_fill.rb', line 34

def self.fill!(map:, start_x:, start_y:, max_search:)
  wid = map.first.length
  hgt = map.length
  return nil unless start_x >= 0
  return nil unless start_y >= 0
  return nil unless start_x < wid
  return nil unless start_y < hgt
  return nil if max_search <= 0

  return nil if map[start_y][start_x]   # starting point is already on a border
  search_queue = [[start_x, start_y]]
  map[start_y][start_x] = true
  cells_checked = 1

  loop do
    break nil if cells_checked > max_search
    break map if search_queue.length == 0

    cx, cy = search_queue.shift

    [
      [cx    , cy - 1],
      [cx + 1, cy - 1],
      [cx + 1, cy    ],
      [cx + 1, cy + 1],
      [cx    , cy + 1],
      [cx - 1, cy + 1],
      [cx - 1, cy    ],
      [cx - 1, cy - 1],
    ].each do |next_cell|
      nx, ny = next_cell

      next if nx < 0
      next if ny < 0
      next if nx >= wid
      next if ny >= hgt
      next if map[ny][nx]

      map[ny][nx] = true
      cells_checked += 1
      search_queue << [nx, ny]
    end
  end
end