# A\* (#98)

**URL:** <https://www.ruby-forum.com/t/a-98/225925>\
**Category:** Ruby\
**Created:** [October 15, 2006, 10:43pm UTC](https://www.ruby-forum.com/t/a-98/225925 "2006-10-15T22:43:12Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![Boris\_P](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/eada6e/32.png) [@Boris\_P](https://www.ruby-forum.com/u/Boris_P)\
**Post date:** [October 15, 2006, 10:43pm UTC](https://www.ruby-forum.com/t/a-98/225925/1 "2006-10-15T22:43:12Z")

</div>

Hi,

I finally unterstood the algorithm when I read this page:  
[http://www.policyalmanac.org/games/aStarTutorial.htm](http://www.policyalmanac.org/games/aStarTutorial.htm)

Best regards,  
Boris

# A node represents a tile in the game

class Node  
include Comparable # by total\_cost

class \<\< self  
# each node class is defined by a “map letter” and a cost (1, 2, 3)  
attr\_accessor :letter, :cost  
end

attr\_accessor :position, :parent, :cost, :cost\_estimated

def initialize(position)  
@position = position  
@cost = 0  
@cost\_estimated = 0  
@on\_path = false  
@parent = nil  
end

def mark\_path  
@on\_path = true  
@parent.mark\_path if @parent  
end

def walkable?  
true # except Water  
end

def total\_cost  
cost + cost\_estimated  
end

def \<=\> other  
total\_cost \<=\> other.total\_cost  
end

def == other  
position == other.position  
end

def to\_s  
@on\_path ? ‘#’ : self.class.letter  
end  
end

class Flatland \< Node  
self.letter = ‘.’  
self.cost = 1  
end

class Start \< Flatland  
self.letter = ‘@’  
end

class Goal \< Flatland  
self.letter = ‘X’  
end

class Water \< Node  
self.letter = ‘~’  
def walkable?  
false  
end  
end

class Forest \< Node  
self.letter = ‘\*’  
self.cost = 2  
end

class Mountain \< Node  
self.letter = ‘^’  
self.cost = 3  
end

NodeClassByLetter = {}  
[Flatland, Start, Goal, Water, Forest, Mountain].each do |klass|  
NodeClassByLetter[klass.letter] = klass  
end

# An (x, y) position on the map

class Position  
attr\_accessor :x, :y

def initialize(x, y)  
@x, @y = x, y  
end

def ==(other)  
return false unless Position===other  
@x == other.x and @y == other.y  
end

# Manhattan

def distance(other)  
(@x - other.x).abs + (@y - other.y).abs  
end

# Get a position relative to this

def relative(xr, yr)  
Position.new(x + xr, y + yr)  
end  
end

# A map contains a two-dimensional array of nodes

class Map  
include Enumerable # for find

def initialize(io)  
@nodes = []  
y = 0  
io.each\_line do |line|  
x = 0  
@nodes[y] = []  
line.chomp.split(//).each do |letter|  
@nodes[y] \<\< NodeClassByLetter[letter].new(Position.new(x, y))  
x += 1  
end  
y += 1  
@width = x  
end  
@height = y  
end

# Returns true if the given position is on the map

def contains?(pos)  
pos.x \>= 0 and pos.x \< @width and pos.y \>= 0 and pos.y \< @height  
end

# Return node at position

def at(pos)  
@nodes[pos.y][pos.x]  
end

# Iterate all nodes

def each  
@nodes.each do |row|  
row.each do |node|  
yield(node)  
end  
end  
end

# Iterates through all adjacent nodes

def each\_neighbour(node)  
pos = node.position  
yield\_it = lambda{|p| yield(at(p)) if contains? p} # just a  
shortcut  
yield\_it.call(pos.relative(-1, -1))  
yield\_it.call(pos.relative( 0, -1))  
yield\_it.call(pos.relative( 1, -1))  
yield\_it.call(pos.relative(-1, 0))  
yield\_it.call(pos.relative( 1, 0))  
yield\_it.call(pos.relative(-1, 1))  
yield\_it.call(pos.relative( 0, 1))  
yield\_it.call(pos.relative( 1, 1))  
end

def to\_s  
@nodes.collect{|row|  
row.collect{|node| node.to\_s}.join(‘’)  
}.join(“\n”)  
end  
end

# see [http://www.policyalmanac.org/games/aStarTutorial.htm](http://www.policyalmanac.org/games/aStarTutorial.htm)

class PathFinder  
def find\_path(map)  
start = map.find{|node| Start === node}  
goal = map.find{|node| Goal === node}  
open\_set = [start] # all nodes that are still worth examining  
closed\_set = [] # nodes we have already visited

```
 loop do
   current = open_set.min # find node with minimum cost
   raise "There is no path from #{start} to #{goal}" unless current
   map.each_neighbour(current) do |node|
     if node == goal # we made it!
       node.parent = current
       node.mark_path
       return
     end
     next unless node.walkable?
     next if closed_set.include? node
     cost = current.cost + node.class.cost
     if open_set.include? node
       if cost < node.cost # but it's cheaper from current node!
         node.parent = current
         node.cost = cost
       end
     else # we haven't seen this node
       open_set << node
       node.parent = current
       node.cost = cost
       node.cost_estimated = node.position.distance(goal.position)
     end
   end
   # move "current" from open to closed set:
   closed_set << open_set.delete(current)
 end

```

end  
end

abort “usage: #$0 ” unless ARGV.size == 1  
map = Map.new(File.open(ARGV[0]))  
finder = PathFinder.new  
finder.find\_path(map)  
puts map