From: Daniel Moore <yahivin@...>
Date: 2009-02-08T08:44:24+09:00
Subject: [SUMMARY] Hexagonal Grid Game Board (#190)

There were two solutions to this weeks quiz. One by Sander Land using
[breadth-first search][1], and another by Christopher Dicely using the
[A* search algorithm][2].

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][2]. 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!

[1]: http://en.wikipedia.org/wiki/Breadth-first_search
[2]: http://en.wikipedia.org/wiki/A*_search_algorithm