From: "Tristram Gräbener" <tristramg@...>
Date: 2006-10-16T07:40:08+09:00
Subject: [QUIZ] Re: A* (#98)

Hi,

Here is my first submission to a ruby quiz :)
I tried to make the A* algorithm as re-usable as possible (class
A_star).

As a parameter it gets an instance of the class Problem that need to
implement :
- neighbors(node) that returns a list of the neighbor nodes and their
distance to that node
- heuristic(node) that give to heuristical distance to the goal
- end_node?(node) that returns true if node is the goal

Thus the A_star class doesn't need to know anything about the problem
(it doesn't even care about what are nodes)

To run it just call the script with the map in stdio; it will print the
solution.

The implementation is rather simple and not optimized (the heuristic
and A_star#add_to_open are critical), and not very nice.

However, here is the code :

class Problem
  attr_reader :start, :goal

  def initialize
    @data = []
    STDIN.readlines.each do |line|
      @data << line.chomp
      start = line =~ /@/
      @start = [start, @data.length-1] if start != nil
      goal = line =~ /X/
      @goal = [goal, @data.length-1] if goal != nil
    end
  end

  def cost(x,y)
    if x < 0 || x >= @data.length || y < 0 || y >= @data[0].length
      nil
    elsif @data[x][y..y].match(/[@\.X]/)
      1
    elsif @data[x][y..y] == '*'
      2
    elsif @data[x][y..y] == '^'
      3
    else
      nil
    end
  end

  # Returns the list of all the neighbors
  def neighbors node
    neighbors_list = []
    x,y = node
    for i in -1..1 do
      for j in -1..1 do
	if i != 0 || j != 0
	  cost = cost(x+i, y+j)
	  neighbors_list << [[x+i, y+j],cost] unless cost == nil
	end
      end
    end
    neighbors_list
  end

  def heuristic node
    x, y = node
    gx, gy = @goal
    (gx-x)**2 + (gy-y)**2
  end

  def end_node? node; node == @goal; end

  def print_solution path
    data = @data
    path.each{|x,y| data[x][y] = '#'}
    data.each{|line| puts line}
  end
end

class A_star
  attr_reader :closed

  def initialize problem
    @problem = problem
    @open = [problem.start]
    @closed = []
    @f = {problem.start => 0} # Estimated cost
    @g = {problem.start => 0} # Cost so far
  end

  def run
    while @open != []
      node = @open.pop
      @closed << node
      return @closed if @problem.end_node? node

      @problem.neighbors(node).each do |n|
	neighbor, cost = n
	add_to_open(neighbor, @g[node] + cost)
      end
    end
    return nil
  end

  def add_to_open(node, cost)
    unless @closed.include? node
      if @open.include? node
	@g[node] = cost if cost < @g[node]
      else
	@open << node
	@g[node] = cost
      end
      @f[node] = @g[node] + @problem.heuristic(node)
      @open.sort! {|a,b| @f[b] <=> @f[a]}
    end
  end
end

pb = Problem.new
test = A_star.new pb
pb.print_solution test.run



Ruby Quiz wrote:
> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz message,
> if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> by Steven Davidovitz
>
> The A* (A-Star) search algorithm is a path-finding algorithm with many uses,
> including Artificial Intelligence for games. The search builds the route from
> tile to tile until it reaches the goal. To help choose the best possible tile
> the algorithm will use an equation that takes into account the distance from the
> tile to the goal and the cost of moving to that tile.
>
> Let's work through an example, so you can see how this comes together.
>
> 	Movement Cost for Terrain:
> 	  Non-walkable:
> 	    N/A = Water (~)
> 	  Walkable:
> 	    1 = Flatlands (. or @ or X)
> 	    2 = Forest (*)
> 	    3 = Mountain (^)
>
> 	Test Map:
> 	  @*^^^    @ = User start
> 	  ~~*~.    X = The goal tile
> 	  **...
> 	  ^..*~
> 	  ~~*~X
>
> Step 1:  Search the surrounding tiles for walkable choices.
>
> The only possible tile for the fist step is to the right: a forest (*) tile.
>
> Step 2:  Go through that list finding the cost of movement for each of those
> choice tiles.  The cost of movement is the path cost so far, plus the cost to
> move to the tile being considered.
>
> Our cost so far is 0, since we just started.  The cost of a forest is 2 so the
> total cost of this move is 2 (0 + 2).
>
> Step 3:  Determine the distance from the choice tiles to the goal and add that
> to the cost from Step 2 to find the score for each tile.
>
> You can calculate the distance from the tile to the goal using Manhattan
> distance formula |x1 - x2| + |y1 - y2|.  For our example that is:
>
> 	|1 - 4| + |0 - 4| = |-3| + |-4| = 7
>
> Knowing that we can produce the final score for this move:
>
> 	score = cost (2) + distance to goal (7) = 9
>
> Step 4: Choose the best tile to move to by comparing the score of the
> surrounding tiles and choosing the lowest.
>
> Step 6:  Repeat Steps 1-4 until you reach the goal tile.  Be careful to prevent
> checking tiles twice and/or circling back.
>
> 	Test Map Solution:
> 	  ##^^^    # = Best path
> 	  ~~#~.
> 	  **.#.
> 	  ^..#~
> 	  ~~*~#
>
> When you have a working solution, try it out on this move involved map:
> 
> 	http://www.rubyquiz.com/large_map.txt