Class: Grid

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/pathfinding/core/grid.rb

Overview

Represents the grid as a 2d-list of nodes.

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(matrix) ⇒ Grid

Creates a grid from a matrix:

  • 0 (or less) represents a walkable node

  • A number greater than 0 does not represents a walkable node

The width represents the number of columns whereas the height is the number of rows of the grid. The node attribute is the list of nodes.



26
27
28
29
30
 
# File 'lib/pathfinding/core/grid.rb', line 26

def initialize(matrix)
  @height = matrix.length
  @width = matrix[0].length
  @nodes = Grid.build_nodes(@width, @height, matrix)
end

Class Method Details

.build_nodes(width, height, matrix) ⇒ Object

Builds and returns the nodes.



176
177
178
179
180
181
182
183
184
185
186
 
# File 'lib/pathfinding/core/grid.rb', line 176

def self.build_nodes(width, height, matrix)
  nodes = []
  height.times do |y|
    nodes << []
    width.times do |x|
      walkable = matrix[y][x] <= 0
      nodes[y] << Node.new(x, y, walkable)
    end
  end
  nodes
end

Instance Method Details

#each_node ⇒ Object

Yields all nodes of the grid.



42
43
44
45
46
47
48
 
# File 'lib/pathfinding/core/grid.rb', line 42

def each_node
  @height.times do |y|
    @width.times do |x|
      yield node(x, y)
    end
  end
end

#inside?(x, y) ⇒ Boolean

Returns if the (x, y) position is in the grid.

Returns:



96
97
98
 
# File 'lib/pathfinding/core/grid.rb', line 96

def inside?(x, y)
  x >= 0 && x < @width && y >= 0 && y < @height
end

#neighbors(node, diagonal_movement = DiagonalMovement::NEVER) ⇒ Object

Get all neighbors of a node.



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
 
# File 'lib/pathfinding/core/grid.rb', line 110

def neighbors(node, diagonal_movement=DiagonalMovement::NEVER)
  x = node.x
  y = node.y
  neighbors = []
  s0 = d0 = s1 = d1 = s2 = d2 = s3 = d3 = false

  # ↑

  if walkable?(x, y - 1)
    neighbors << node(x, y - 1)
    s0 = true
  end

  # →

  if walkable?(x + 1, y)
    neighbors << node(x + 1, y)
    s1 = true
  end

  # ↓

  if walkable?(x, y + 1)
    neighbors << node(x, y + 1)
    s2 = true
  end

  # ←

  if walkable?(x - 1, y)
    neighbors << node(x - 1, y)
    s3 = true
  end

  return neighbors if diagonal_movement == DiagonalMovement::NEVER

  if diagonal_movement == DiagonalMovement::ONLY_WHEN_NO_OBSTACLE
    d0 = s3 && s0
    d1 = s0 && s1
    d2 = s1 && s2
    d3 = s2 && s3
  elsif diagonal_movement == DiagonalMovement::IF_AT_MOST_ONE_OBSTACLE
    d0 = s3 || s0
    d1 = s0 || s1
    d2 = s1 || s2
    d3 = s2 || s3
  elsif diagonal_movement == DiagonalMovement::ALWAYS
    d0 = d1 = d2 = d3 = true
  else
    raise 'Incorrect value of diagonal_movement'
  end

  # ↖

  neighbors << node(x - 1, y - 1) if d0 && walkable?(x - 1, y - 1)

  # ↗

  neighbors << node(x + 1, y - 1) if d1 && walkable?(x + 1, y - 1)

  # ↘

  neighbors << node(x + 1, y + 1) if d2 && walkable?(x + 1, y + 1)

  # ↙

  neighbors << node(x - 1, y + 1) if d3 && walkable?(x - 1, y + 1)

  neighbors
end

#node(x, y) ⇒ Object

Gets the node at position (x, y).



35
36
37
 
# File 'lib/pathfinding/core/grid.rb', line 35

def node(x, y)
  @nodes[y][x]
end

#to_s(path = nil, start_node = nil, end_node = nil, border = true, start_chr = 's', end_chr = 'e', path_chr = 'x', empty_chr = ' ', block_chr = '#') ⇒ Object

Creates a printable string from the grid using ASCII characters. Params:

path

list of nodes that show the path

start_node

start node

end_node

end node

border

create a border around the grid

start_chr

character for the start (default “s”)

end_chr

character for the end (default “e”)

path_chr

character for the path (default “x”)

empty_chr

character for the empty fields (default “ ”)

block_chr

character for the blocking elements (default “#”)



63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/pathfinding/core/grid.rb', line 63

def to_s(
  path = nil, start_node = nil, end_node = nil, border = true,
  start_chr = 's', end_chr = 'e', path_chr = 'x', empty_chr = ' ', block_chr = '#'
)
  data = []
  data << '+' + '-' * @width + '+' if border
  @height.times do |y|
    line = ''
    line += '|' if border
    @width.times do |x|
      current = node(x, y)
      if current == start_node
        line += start_chr
      elsif current == end_node
        line += end_chr
      elsif path&.include?(current)
        line += path_chr
      elsif current.walkable
        line += empty_chr
      else
        line += block_chr
      end
    end
    line += '|' if border
    data << line
  end
  data << '+' + '-' * @width + '+' if border
  data.join("\n")
end

#walkable?(x, y) ⇒ Boolean

Returns if a node at position (x, y) is walkable.

Returns:



103
104
105
 
# File 'lib/pathfinding/core/grid.rb', line 103

def walkable?(x, y)
  inside?(x, y) && node(x, y).walkable
end