Hexagonal Grid Game Board (#190)

Summary of quiz #189 coming in a day or two.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have elapsed from the time this message was
sent.

2. Support Ruby Q. by submitting ideas and responses
as often as you can! Visit: http://rubyquiz.strd6.com

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Hexagonal Grid Game Board

This week’s quiz is to create the distance computation methods for a
hexagonal game board. In addition to implementing the simple
unobstructed distance you will also implement an obstructed_distance
method: the distance between two positions where you must go around
started. The print method on HexBoard prints out a board where each
hex displays it’s distance from position [4,4].

Partial solutions are welcome! Team solutions are welcome! I want to
see everyone on ruby-talk give this one a shot!

class Hex
def obstructed?
false
end
end

class HexBoard
def initialize(rows=9, cols=9)
@rows, @cols = rows, cols
@board = Array.new(@rows) do |row|
Array.new(@cols) do |col|
Hex.new
end
end
end

def distance(position1, position2)
# Distance between two hexes on the board
end

def obstructed_distance(position1, position2, &block)
# Distance between two hexes on the board having to navigate
obstructions
# Obstructions are detected by passing the hex in question into the
block
# block will return true if the yielded hex should be counted as
obstructed
# EX: dist = obstructed_distance(a, b) { |hex| hex.obstructed? }
end

know if you’re on the right track

def draw
@rows.times do |row|
line = ‘’
line << “#{row}:”
(@cols - row).times {line << ’ '}

``````  @cols.times do |col|
line << (distance([4,4], [row,col]) || 'X').to_s
line << ' '
end

puts line
end
``````

end

def
@board[row]
end
end

board = HexBoard.new
board.draw

Example Output of print:
0: 4 4 4 4 4 5 6 7 8
1: 4 3 3 3 3 4 5 6 7
2: 4 3 2 2 2 3 4 5 6
3: 4 3 2 1 1 2 3 4 5
4: 4 3 2 1 0 1 2 3 4
5: 5 4 3 2 1 1 2 3 4
6: 6 5 4 3 2 2 2 3 4
7: 7 6 5 4 3 3 3 3 4
8: 8 7 6 5 4 4 4 4 4

On Jan 30, 2009, at 11:06 AM, Daniel M. wrote:

Hexagonal Grid Game Board

Ooo, I like this problem. Nice one Daniel!

James Edward G. II

On Fri, Jan 30, 2009 at 6:15 PM, James G. [email protected]
wrote:

On Jan 30, 2009, at 11:06 AM, Daniel M. wrote:

Hexagonal Grid Game Board

Ooo, I like this problem. Nice one Daniel!

Me too, crossing my fingers to have some time to make a try…

Jesus.

Here is my solution.
Pastie: http://pastie.org/377536
The pastie still has the comment on the distances function as
returning the distance between two hexes, but I changed this to return
an array of all distances from some position, since the breadth-first
search was already calculating this anyway.

class Hex
attr_accessor :neighbours,:distance
def initialize(row,col,rows,cols)
@neighbours =
[[-1,-1],[-1,0],[0,-1],[0,1],[1,0],[1,1]].map{|r,c|[row+r,col+c]}.select{|r,c|
r>=0 && c>=0 && r<rows && c<cols}
@obstructed = col==3 && row!=rows-1 || col==6 && row!=0 # double
barrier
end
def obstructed?; @obstructed ;end
end

class HexBoard < Array
def initialize(rows=9, cols=9)
super(rows) {|row| Array.new(cols) {|col| Hex.new(row,col, rows,cols)
}}
end

Distance from position to each hex

def distances(position,&block)
each{|row| row.each{|hex| hex.distance = nil } }
bfs_distance([position],0, &block);
map{|row| row.map &:distance }
end

def bfs_distance(hexes,dist, &block)
q = []
hexes.map{|r,c| self[r][c] }.each{|hex|
next if hex.distance || block_given? && yield(hex)
hex.distance = dist
q += hex.neighbours
}
bfs_distance(q.uniq,dist+1, &block) unless hexes.empty?
end

Draw solution

def draw(from=[4,4],&block)
distances(from,&block).each_with_index{|dists,row| puts “#{row}:#{’
‘*(size - row)}#{dists.map{|x|x||’#'}.join ’ '}\n” }
end
end

board = HexBoard.new
board.draw
board.draw([0,0],&:obstructed?)

Here’s my solution. The request for the unobstructed distance and then
the obstructed distance immediately suggested the A* algorithm (since
the unobstructed distance is clearly an admissible heuristic.) Though
I knew an algorithm to use, I had to look up the algorithm itself.

—[main.rb]
require ‘hex_board’

1. }

board = HexBoard.new(9, 9) { |row,col| [row,col]==[4,4] ? true :

rand(6)==0 }
board = HexBoard.new(9, 9) { |row,col| [row,col]==[4,4] ? false :
rand(6)==0 }
board.draw
board.draw_map
board.draw_obstructed

—[hex_board.rb]
require ‘set’
require ‘hex’

class HexBoard
def initialize(rows=9, cols=9)
@rows, @cols = rows, cols
@board = Array.new(@rows) do |row|
Array.new(@cols) do |col|
Hex.new(:obstructed => (block_given? && yield(row,col)))
end
end
end

def distance(start, goal)
if ((start[0]-goal[0]) < 0) == ((start[1]-goal[1]) < 0)
[(start[0]-goal[0]).abs, (start[1]-goal[1]).abs].max
else
(start[0]-goal[0]).abs+(start[1]-goal[1]).abs
end
end

def neighbors(position)
[
[position[0], position[1]-1],
[position[0]-1, position[1]-1],
[position[0]-1, position[1]],
[position[0], position[1]+1],
[position[0]+1, position[1]+1],
[position[0]+1, position[1]]
].delete_if {|x,y| x<0 || y <0 || x>@rows || y>@cols}
end

obstructions

block

obstructed

EX: dist = obstructed_distance(a, b) { |hex| hex.obstructed? }

def obstructed_distance(start, goal)
return nil if (yield(@board[goal[0]][goal[1]]) ||
yield(@board[start[0]][start[1]]))
closed_set = Set.new
@board.size.times {|row|
row.size.times {|col|
if yield @board[row][col]
closed_set << [row,col]
end
}
}
open_set = [start]
actual_distance_to = {start=>0}
estimated_distance_from = {start=>distance(start,goal)}
estimated_distance_through = {start=>estimated_distance_from[start]}

``````while !(open_set.empty?)
node = open_set.first
return actual_distance_to[node] if node == goal
open_set.delete node
closed_set << node
neighbors(node).each { |neighbor|
next if closed_set.include? neighbor
distance_this_route = actual_distance_to[node] + 1
this_route_good = false
if !open_set.include?(neighbor)
open_set << neighbor
estimated_distance_from[neighbor] = distance(neighbor,goal)
this_route_good = true
elsif distance_this_route < actual_distance_to[neighbor]
this_route_good = true
end
if this_route_good
actual_distance_to[neighbor] = distance_this_route
estimated_distance_through[neighbor] = distance_this_route +
``````

estimated_distance_from[neighbor]
open_set.sort! {|x,y|
estimated_distance_through[x]<=>estimated_distance_through[y]}
end
}
end
return nil
end

know if you’re on the right track

def draw
@rows.times do |row|
line = ‘’
line << “#{row}:”
(@cols - row).times {line << ’ '}

``````  @cols.times do |col|
line << (distance([4,4], [row,col]) || 'X').to_s
line << ' '
end

puts line
end
``````

end

def draw_map
@rows.times do |row|
line = ‘’
line << “#{row}:”
(@cols - row).times {line << ’ '}

``````  @cols.times do |col|
line << (@board[row][col].obstructed? ? 'X' : 'O')
line << ' '
end

puts line
end
``````

end

def draw_obstructed
@rows.times do |row|
line = ‘’
line << “#{row}:”
(@cols - row).times {line << ’ '}

``````  @cols.times do |col|
line << (obstructed_distance([4,4], [row,col]) {|hex|
``````

hex.obstructed?} || ‘X’).to_s
line << ’ ’
end

``````  puts line
end
``````

end

def
@board[row]
end
end

—[hex.rb]
class Hex
def initialize(opts={})
@obstructed = !!opts[:obstructed]
end

def obstructed?
@obstructed
end
end

There were two solutions to this weeks quiz. One by Sander L. using
breadth-first search, and another by Christopher D. using the
A* search algorithm.

Both of the solutions added a similar concept of neighboring hexes.
Let’s examine Sander’s code in the `initialize` method of the `Hex`
class (I’ve modified the formatting slightly):

``````@neighbors =
[[-1,-1],[-1,0],[0,-1],[0,1],[1,0],[1,1]].map do |r, c|
[row+r, col+c]
end
``````

Here we take an array of the six positions around this hex and map it
to world coordinates by adding the the deltas (differences in
position) to row and column values to get the position of the
neighboring hex.

``````  .select do |r, c|
r >= 0 && c >= 0 && r < rows && c < cols
end
``````

In order to prevent having neighbors that are off the board or out of
range we select the ones that are valid positions.

Christopher’s method is very similar, except instead of computing the
neighbors at the creation of each hex they are computed as needed via
a method of the `HexBoard` class.

For the simple distance Christopher uses the following formula:

``````def distance(start, goal)
if ((start[0]-goal[0]) < 0) == ((start[1]-goal[1]) < 0)
[(start[0]-goal[0]).abs, (start[1]-goal[1]).abs].max
else
(start[0]-goal[0]).abs+(start[1]-goal[1]).abs
end
end
``````

Here is an equivalent distance formula that found (though I can’t
remember where) and converted to Ruby:

``````def distance(pos1, pos2)
dx = pos2[0] - pos1[0]
dy = pos2[1] - pos1[1]
return (dx.abs + dy.abs + (dx - dy).abs) / 2
end
``````

The deeper meaning behind these distance methods is still somewhat of
a mystery to me. I see that they work, but I’m not fully sure of the
why. I also don’t see how to alter them to change the orientation of
the grid (maybe a future quiz?).

For the obstructed distance Christopher uses the A* search
algorithm
. The essence of the A* algorithm is that it searches the
most promising paths first. In order to know which nodes are most
promising a heuristic function is used, in this case the simple
distance. We maintain a list (priority queue) of the nodes available
to explore. As we remove the best node from the list we examine it’s
neighbors and insert them into the list, most promising first. If we
find the goal node we return the distance to it and are done. There is
much more that can be said about A* than I can say here, so check it
out.

In fact, breadth-first search is a special case of A* where the
heuristic function always returns 0 and the priority queue is replaced
with a regular (FIFO) queue. Sander’s solution uses recursion instead
of a queue. It sets the distance to each hex based to the distance at
set or are obstructed, and adding the neighbors to a list to compute
the distance on the next recursive call. Once the list of remaining
nodes is empty it returns, having set the distance for all reachable
nodes.

Let’s look at the results:

Sander creates a board that has two long walls with just one gap each:

``````0:         0 1 2 # 17 18 19 20 21
1:        1 1 2 # 16 17 # 20 21
2:       2 2 2 # 15 16 # 21 21
3:      3 3 3 # 14 15 # 22 22
4:     4 4 4 # 13 14 # 23 23
5:    5 5 5 # 12 13 # 24 24
6:   6 6 6 # 11 12 # 25 25
7:  7 7 7 # 10 11 # 26 26
8: 8 8 8 8 9 10 # 27 27
``````

Christopher generates random obstructions and provides a map view
which shows what is open and what is blocked:

``````0:         O X O X O O O O O
1:        O X O X O O O X O
2:       O O O O O O O X O
3:      O O O O O O O O O
4:     O X O O O O X O O
5:    O O X O O O X O X
6:   O O O O O O O O O
7:  O O O O O O O O O
8: O O X X O O O X O

0:         5 X 4 X 4 5 6 7 8
1:        4 X 3 X 3 4 5 X 7
2:       4 3 2 2 2 3 4 X 6
3:      4 3 2 1 1 2 3 4 5
4:     5 X 2 1 0 1 X 3 4
5:    6 5 X 2 1 1 X 3 X
6:   6 5 4 3 2 2 2 3 4
7:  7 6 5 4 3 3 3 3 4
8: 8 7 X X 4 4 4 X 4
``````

Both solutions to this week’s quiz provide interesting ways to solve
distance computations on a hexagonal game board. I hope they come in
handy when you build your next hex based board game!

There were two solutions to this weeks quiz. One by Sander L. using
breadth-first search, and another by Christopher D. using the
A* search algorithm.

Both of the solutions added a similar concept of neighboring hexes.
Let’s examine Sander’s code in the `initialize` method of the `Hex`
class (I’ve modified the formatting slightly):

``````@neighbors =
[[-1,-1],[-1,0],[0,-1],[0,1],[1,0],[1,1]].map do |r, c|
[row+r, col+c]
end
``````

Here we take an array of the six positions around this hex and map it
to world coordinates by adding the the deltas (differences in
position) to row and column values to get the position of the
neighboring hex.

``````  .select do |r, c|
r >= 0 && c >= 0 && r < rows && c < cols
end
``````

In order to prevent having neighbors that are off the board or out of
range we select the ones that are valid positions.

Christopher’s method is very similar, except instead of computing the
neighbors at the creation of each hex they are computed as needed via
a method of the `HexBoard` class.

For the simple distance Christopher uses the following formula:

``````def distance(start, goal)
if ((start[0]-goal[0]) < 0) == ((start[1]-goal[1]) < 0)
[(start[0]-goal[0]).abs, (start[1]-goal[1]).abs].max
else
(start[0]-goal[0]).abs+(start[1]-goal[1]).abs
end
end
``````

Here is an equivalent distance formula that found (though I can’t
remember where) and converted to Ruby:

``````def distance(pos1, pos2)
dx = pos2[0] - pos1[0]
dy = pos2[1] - pos1[1]
return (dx.abs + dy.abs + (dx - dy).abs) / 2
end
``````

The deeper meaning behind these distance methods is still somewhat of
a mystery to me. I see that they work, but I’m not fully sure of the
why. I also don’t see how to alter them to change the orientation of
the grid (maybe a future quiz?).

For the obstructed distance Christopher uses the A* search
algorithm
. The essence of the A* algorithm is that it searches the
most promising paths first. In order to know which nodes are most
promising a heuristic function is used, in this case the simple
distance. We maintain a list (priority queue) of the nodes available
to explore. As we remove the best node from the list we examine it’s
neighbors and insert them into the list, most promising first. If we
find the goal node we return the distance to it and are done. There is
much more that can be said about A* than I can say here, so check it
out.

In fact, breadth-first search is a special case of A* where the
heuristic function always returns 0 and the priority queue is replaced
with a regular (FIFO) queue. Sander’s solution uses recursion instead
of a queue. It sets the distance to each hex based to the distance at
set or are obstructed, and adding the neighbors to a list to compute
the distance on the next recursive call. Once the list of remaining
nodes is empty it returns, having set the distance for all reachable
nodes.

Let’s look at the results:

Sander creates a board that has two long walls with just one gap each:

``````0:         0 1 2 # 17 18 19 20 21
1:        1 1 2 # 16 17 # 20 21
2:       2 2 2 # 15 16 # 21 21
3:      3 3 3 # 14 15 # 22 22
4:     4 4 4 # 13 14 # 23 23
5:    5 5 5 # 12 13 # 24 24
6:   6 6 6 # 11 12 # 25 25
7:  7 7 7 # 10 11 # 26 26
8: 8 8 8 8 9 10 # 27 27
``````

Christopher generates random obstructions and provides a map view
which shows what is open and what is blocked:

``````0:         O X O X O O O O O
1:        O X O X O O O X O
2:       O O O O O O O X O
3:      O O O O O O O O O
4:     O X O O O O X O O
5:    O O X O O O X O X
6:   O O O O O O O O O
7:  O O O O O O O O O
8: O O X X O O O X O

0:         5 X 4 X 4 5 6 7 8
1:        4 X 3 X 3 4 5 X 7
2:       4 3 2 2 2 3 4 X 6
3:      4 3 2 1 1 2 3 4 5
4:     5 X 2 1 0 1 X 3 4
5:    6 5 X 2 1 1 X 3 X
6:   6 5 4 3 2 2 2 3 4
7:  7 6 5 4 3 3 3 3 4
8: 8 7 X X 4 4 4 X 4
``````

Both solutions to this week’s quiz provide interesting ways to solve
distance computations on a hexagonal game board. I hope they come in
handy when you build your next hex based board game!