A* (#98)

[bbazzarrakk]

The three rules of Ruby Q.:

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 Q. 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 T. follow the discussion. Please reply to the original quiz
message,
if you can.

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

by Steven D.

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

[bbazzarrakk]

Just FYI, the summary for this quiz will be a little early. I will
post it sometime Wednesday.

James Edward G. II

[bbazzarrakk]

Step #5 is missing. Should it be ‘???’ or ‘Profit!’?

…

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.

…

[bbazzarrakk]

Step 1:

snip

Step 3:

Slight concern- aren’t you actually here giving us a solution to a
problem, and then just asking to implement the algorithm you’ve
already explained? Where’s the fun in that.

Part of the joy should be in doing some research and applying some
thought to find the best algorithm. It slightly ruins it if you give
us an answer in the problem.

Martin

[bbazzarrakk]

On Oct 13, 2006, at 9:30 AM, jason r tibbetts wrote:

Step #5 is missing. Should it be ‘???’ or ‘Profit!’?

Oops. That’s my fault. I consolidated two of the steps in the
original quiz and obviously forgot to renumber. I’ll fix it on the
web site.

James Edward G. II

[bbazzarrakk]

Part of the joy should be in doing some research and applying some
thought to find the best algorithm. It slightly ruins it if you give
us an answer in the problem.

Well, A* is a dreadful algorithm for route finding, so there’s plenty
of scope for finding a way better approach Field Guidance, Ho!

[bbazzarrakk]

On 10/13/06, Martin C. [email protected] wrote:

Slight concern- aren’t you actually here giving us a solution to a
problem, and then just asking to implement the algorithm you’ve
already explained? Where’s the fun in that.

Actually, the basic algorithm he explained isn’t quite A-star (I’m
guessing on purpose). There’s lots of room for improvement in both
algorithm and heuristic. I’m guessing that’s where the fun and variety
of this quiz will be.

Jacob F.

[bbazzarrakk]

Part of the joy should be in doing some research and applying some
thought to find the best algorithm. It slightly ruins it if you give
us an answer in the problem.

Well, A* is a dreadful algorithm for route finding, so there’s plenty
of scope for finding a way better approach Field Guidance, Ho!

I wonder if I can revisit my Rubik Cube solver I wrote years ago. It’s
written in Matlab.

Martin

[bbazzarrakk]

I wrote:

Well, A* is a dreadful algorithm for route finding, so there’s plenty
of scope for finding a way better approach Field Guidance, Ho!

If no one minds too much, I’d like to reject what I said about 20
minutes ago about A*. I said it from an uninformed position.

It sounds like it’s more of a general search algorithm for finiding
optimal paths. It may be applied to route finding, but can be used for
other search problems. The huristic (in the quiz, the Manhaton distance
is suggested) is very important and has a great impact on its
performance (it can also break the algorithm if it over estimates cost).

It’s discussed on wonderful wikipedia:
A* search algorithm - Wikipedia

Field guidance is also a wonderful approach, and can give much more
“human” route planning. It’s also great for allowing incomplete
knowledge to be handled, and it’s nice at doing things like having a
unit of troops march in formation, but gracefully avoiding tree stumps,
and breaking formation near a wall, etc.

Cheers,
Benjohn

[bbazzarrakk]

On 10/13/06, Jacob F. [email protected] wrote:

Actually, the basic algorithm he explained isn’t quite A-star (I’m
guessing on purpose). There’s lots of room for improvement in both
algorithm and heuristic. I’m guessing that’s where the fun and variety
of this quiz will be.

Jacob F.

Isn’t he just explaining a greedy search without backtracking?
Also, this algorithm seems to go wrong even on the small map:

##^^^
~~#~.
**.#.
^…~
~~~X

##^^^
~~#~.
**.##
^…~
~~~X

[bbazzarrakk]

On Oct 13, 2006, at 9:36 AM, Martin C. wrote:

Step 1:

snip

Step 3:

Slight concern- aren’t you actually here giving us a solution to a
problem, and then just asking to implement the algorithm you’ve
already explained? Where’s the fun in that.

I do encourage quiz creators to do this, yes. It’s being done here
and this isn’t the first quiz to do it.

I feel it lowers the bar for people to play with the quiz. No one is
forced to use the described algorithm and it helps some people decide
where to start.

I feel there are still plenty of interesting things to see in just
how people actually code it up.

James Edward G. II

[bbazzarrakk]

On Oct 13, 2006, at 11:15 AM, Jacob F. wrote:

4. if the queue emptied without finding a solution, there is no
   solution

The priority queue is the major aspect not really touched on by the
quiz, yes. If you need help with this, a past Ruby Q. about heaps
had code you could borrow:

http://www.rubyquiz.com/quiz40.html

Just be sure to read the summary where I fix a couple of bugs in the
code.

James Edward G. II

[bbazzarrakk]

On 10/13/06, Sander L. [email protected] wrote:

On 10/13/06, Jacob F. [email protected] wrote:

Actually, the basic algorithm he explained isn’t quite A-star (I’m
guessing on purpose). There’s lots of room for improvement in both
algorithm and heuristic. I’m guessing that’s where the fun and variety
of this quiz will be.

Jacob F.

Isn’t he just explaining a greedy search without backtracking?
Also, this algorithm seems to go wrong even on the small map:

Pretty much, yes. Hoping it’s not a spoiler, here’s how you really do
A*:

1. use a priority queue (prioritized by estimated cost)
2. initialize the queue with the start state(s)
3. while the queue is not empty
   a) shift the head off the queue (cheapest state found so far)
   b) return the path to the current state if the state is a goal state
   b) expand that state by finding neighbors and calculating their costs
   c) push each neighbor onto the queue
4. if the queue emptied without finding a solution, there is no solution

For the sake of both brevity and challenge, I’ve left some details out,
such as:

• How do you prevent cycles and backtracking?
• How do you calculate costs for a new state?
• How do you manage your priority queue?
• How do you keep track of the path so you can return it when you hit a
  goal?

Happy hacking!

[bbazzarrakk]

Ruby Q. [email protected] writes:

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:

No you can’t. A* works IF AND ONLY IF the estimation function is
guaranteed to be less than or equal to the true cost of following a
particular choice. In this quiz, the estimation function we’re using
is basically to use what the cost would be if we could travel the rest
of the way on the best terrain possible. Since the easiest terrain
has a cost of 1, this is just the distance.

This would be fine, except that since apparently in this game you can
travel by diagonal moves, the distance used CAN’T be the manhattan
distance, but rather
max(|x1 - x2|, |y1 - y2|)

As a simple example where using the manhattan distance leads one
astray, consider this:

…*…
…~…
@.^.X

Now, clearly the best path is:

…#…
.#~#.
#.^.#

Since it costs less to move through a forest than a mountain, and it’s
the same number of steps either way. However, if you use Manhattan
distance, the mountain appears more attractive because it appears that
the forest is 4 steps away from the goal (when in reality it’s only
two away, just as the mountain is).

[bbazzarrakk]

James Edward G. II wrote:

costs
Just be sure to read the summary where I fix a couple of bugs in the
code.

James Edward G. II

My solution for last week’s quiz used an A* search with a priority
queue if anybody wants to see some live code. The queue was, however,
designed for adding large numbers of new states in batches and would
need to be adapted.

By complete coincidence I’ve actually attempted something almost
identical to this before, attempting top move from any cell on the left
side to any cell on the right. I found that for larger grids an A*
search cell-by-cell becomes unacceptably slow.

I think the real challenge in this quiz will be forming intelligent
methods of reducing the number of states that must be searched. I never
actually did this for the left-to-right problem but have several ideas
for this quiz. Don’t worry, they haven’t given us the answers to the
real problems

[bbazzarrakk]

Here’s my solution, first submission to ruby quiz, I hope is not 100%
rubbish. I use a * 2 calculating the distance to avoid some noisy
movements when approaching the ending point (so when the simple cost
of terrain is about the same dimension of the distance).
You can try the small map of the quiz without the *2 to see this
behaviour. When the distance from the end point is >> than the terrain
costs the *1 and *2 version act more or less the same way
whell, here’s the code.

http://pastie.caboo.se/17815

Thanks

Paolo

[bbazzarrakk]

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 S.

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(" ")

[bbazzarrakk]

“Paolo N.” [email protected] writes:

Here’s my solution, first submission to ruby quiz, I hope is not 100%
rubbish. I use a * 2 calculating the distance to avoid some noisy
movements when approaching the ending point (so when the simple cost
of terrain is about the same dimension of the distance).
You can try the small map of the quiz without the *2 to see this
behaviour. When the distance from the end point is >> than the terrain
costs the *1 and *2 version act more or less the same way
whell, here’s the code.

Parked at Loopia

Unfortunately, the A* algorithm depends on the fact that the estimate
of cost being added to each point (in this case, distance to goal) is
always less than or equal to the actual cost of getting to the goal
from that point.

By doubling the distance you violate this constraint, and so your
solution computes the wrong path given this map:

@……
…~…
…~~~
…^X

Your solution with the *2 in it does this:

####…
…~##.
…~~~#
…^X

For a total cost of 10 (counting both the start and goal, and going
over two forests)

Your solution with the *2 bit removed gets closer to the correct path,
but there’s still something off:

###…
…#~…
…#~~~
…###X

Looking over your solution, I think you’ve fallen victim to the fact
that the quiz author failed to explain A* clearly. The excellent
online tutorials and wikipedia article already cited here on the list
are a better introduction.

On the plus side, yours is the only solution besides mine posted so
far that manages to get this path right:

@.*…
…~…
…^.X

That’s because you wisely didn’t use the manhattan distance quoted in
the puzzle statement.

[bbazzarrakk]

On 16/10/06, Daniel M. [email protected] wrote:

@…*…

…^.X

That’s because you wisely didn’t use the manhattan distance quoted in
the puzzle statement.

–
s=%q( Daniel M. – [email protected]
puts “s=%q(#{s})”,s.map{|i|i}[1] )
puts “s=%q(#{s})”,s.map{|i|i}[1]

The problem of my *1 version is how the choice among tiles with the
same price is done. The *2 is really rubbish and was just based on a
specific map, sorry.

to have a better view of what happens is interesting to print out all
the costs of the points on the map, here’s a diff to avoid the *2 and
print the final result with cost.

59c59
< (point1.zip(point2).map {|c| (c[0] - c[1]).abs}).max

(point1.zip(point2).map {|c| (c[0] - c[1]).abs}).max*2

103d102
< (0…(line.size - 1)).each {|n| out << cost([n, line_n]).to_s}

If I’ll have the time to work on it I’ll submit some improvements.

Thanks

Paolo

[bbazzarrakk]

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