From: Roland Swingler <roland.swingler@...>
Date: 2006-10-15T21:50:19+09:00
Subject: Re: A* (#98)

Hi,

Here is my solution - I haven't done much more than implement what was
asked for in the quiz. It produces this path on the large map:

0,0  1,1  2,2  3,3  4,4  5,5  6,6  7,7  8,8  9,9  10,9  11,10  12,11
12,12  13,13  14,14  15,15  15,16  15,17  16,18  17,18  18,19  19,20
20,21  21,22  22,22  23,23  22,24  22,25  23,26  24,27  25,28  26,29
27,29  28,29  29,30  30,31  30,32  31,33  30,34  30,35  31,36  32,37
33,38  34,39  34,40  35,41  36,42  37,43  38,43  39,44  40,44  41,45
42,46  43,46  44,47  45,48  46,48  47,48  48,49  49,49

I've used Brian Schr�der's PriorityQueue implementation, so to run
this you'll need to do gem install priorityqueue first.

In response to Martin about the quiz being "spoiled" - I don't come
from a Computer Science background and finding out about algorithms /
data structures which might be obvious to someone with a more technical
bent is one of the things I like getting out of ruby quiz. I think
there is room for a mix of quizes, some with more vague goals than
others.

Cheers,
Roland Swingler

My solution:

require 'rubygems'
require 'priority_queue'

class String
  # Convenience method so we can iterate over characters easily

  def to_chars
    a = []
    each_byte do |b|
      a << b.chr
    end
    a
  end
end

module TileMap
  # Although start is a plains, its cost is 0

  START  = 0
  PLAINS = 1
  FOREST = 2
  MOUNTAIN = 3
  WATER = nil

  class TilePath < Array
    def initialize(map)
      @map = map
      super([@map.start])
    end

    def cost
      inject(0) {|sum, c| sum + @map.tile(*c) }
    end
  end

  class Map
    attr_reader :start, :goal

    # parse a string contining a tile map into a nested array

    def initialize(map_str)
      @tiles = []
      map_str.each do |line|
        @tiles << []
        line.chomp.to_chars.each do |c|
          @tiles.last << case c
                         when "@"
                           START
                         when ".", "X"
                           PLAINS
                         when "*"
                           FOREST
                         when "^"
                           MOUNTAIN
                         when "~"
                           WATER
                         else
                           raise "Invalid tile type"
                         end
          if '@' == c
            @start = [@tiles.last.length - 1, @tiles.length - 1]
          elsif 'X' == c
            @goal = [@tiles.last.length - 1, @tiles.length - 1]
          end
        end
      end
      unless @start && @goal
        raise "Either position or goal tile are not set"
      end
    end

    def tile(x, y)
      @tiles[y][x]
    end

    def move_choices(x, y)
      if tile(x, y) == WATER
        raise "Illegal tile"
      end
      choices = []
      (-1..1).each do |i|
        ypos = y + i
        if ypos >= 0 && ypos < @tiles.length
          (-1..1).each do |j|
            xpos = x + j
            if xpos >= 0 && xpos < @tiles[i].length
              new_position = [xpos, ypos]
              if new_position != [x, y] && tile(*new_position) != WATER
                choices << new_position
              end
            end
          end
        end
      end
      choices
    end

    def self.manhattan(point1, point2)
      ((point2[0] - point1[0]) + (point2[1] - point1[1])).abs
    end
  end

  def self.a_star_search(map)
    # To store points we have already visited, so we don't repeat
ourselves
    closed = []
    open = PriorityQueue.new
    # Start off the queue with one path, which will contain the start
position
    open.push TilePath.new(map), 0
    while ! open.empty?
      # Get the path with the best cost to expand

      current_path = open.delete_min_return_key
      pos = current_path.last
      unless closed.include?(pos)
        if pos == map.goal
          return current_path
        end
        closed << pos
        # Create new paths and add them to the priority queue

        map.move_choices(*pos).each do |p|
          heuristic = Map.manhattan(p, map.goal)
          new_path = current_path.clone << p
          open.push(new_path, new_path.cost + heuristic)
        end
      end
    end
    raise "Cannot be solved"
  end
end

@m = TileMap::Map.new(File.read('large_map.txt'))
results = TileMap.a_star_search(@m)
puts results.map! {|pos| pos.join(",") }.join("  ")