190 Hexagonal Grid Game Board

Description

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 obstructions. I’ve provided a couple of classes to help you get 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

 # This will print the board out to the console to let you
 # 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 [](row)
   @board[row]
 end
end

board = HexBoard.new
board.draw

Summary

There were two solutions to this weeks quiz. One by Sander Land using breadth-first search, and another by Christopher Dicely 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 the current level, skipping hexes that have already had their distance 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!

Hexagonal Grid Game Board (#190) - Solutions


Saturday, February 07, 2009