Quick implementation of A* in Ruby

astar.rb

#!/usr/bin/env ruby
# encoding: utf-8

class AStar
  def initialize(width, height, max_cost)
    @grid  = create_random(width, height, max_cost)
    @start = @grid[0][0]
    @end   = @grid[height - 1][width - 1]
    @open, @closed = [], [@start]
  end

  def run
    find_path
    mark_path
  end

  def print
    @grid.each do |row|
      puts row.map(&:cost).join(' ')
    end
  end

  private
  def create_random(width, height, max_cost)
    Array.new((y = -1) && height) { (y += 1) && (x = -1) && Array.new(width) { Node.new(x += 1, y, rand(max_cost) + 1) } }
  end

  def find_path
    current = @start
    while current != @end
      current = expand(current)
    end
  end

  def mark_path
    current = @end
    @start.toggle_path

    while current != @start
      current.toggle_path
      current = current.parent
    end
  end

  def expand(current)
    x, y = current.x, current.y
    width, height = @grid.size, @grid[0].size

    neighbors = [[x - 1, y], [x, y - 1], [x + 1, y], [x, y + 1] ]
      .select { |c| c[0] >= 0 && c[1] >= 0 && c[0] < width && c[1] < height }
      .map    { |c| @grid[c[1]][c[0]] }
      .reject { |n| @closed.include?(n) }

    neighbors.each { |n| n.find_cost(current, @end) }

    @open << neighbors
    @open.flatten!
    @closed << @open.delete(current)
    @open.min { |n| n.f }
  end
end

class Node
  attr_reader :x, :y, :f, :g, :cost, :parent

  def initialize(x, y, cost)
    @x = x
    @y = y
    @cost = cost
    @g = 0
  end

  def find_cost(node, end_node)
    g = node.g + @cost
    h = estimate_to(end_node)

    if @f.nil? || g + h < @f
      @f = g + h
      @g = g
      @parent = node
    end
  end

  def toggle_path
    @cost = 'X'
  end

  private
  def estimate_to(node)
    (@x - node.x).abs + (@y - node.y).abs
  end
end

astar = AStar.new(5, 5, 3)
astar.print
astar.run
puts '========='
astar.print

Sample run:

2 3 2 1 1
1 1 1 2 3
3 2 1 1 3
2 3 3 3 1
3 2 3 1 2
=========
X 3 2 1 1
X X X 2 3
3 2 X X X
2 3 3 3 X
3 2 3 1 X