13 Comments

From Ruby to Crystal: A Quick Look

In my dabbles into game development, I’ve loved the expressiveness of Ruby, but longed for the performance of a compiled language. (Anyone else in that boat?) I recently heard about a newer language that promised “The beauty of Ruby with the speed of C.” Its name is Crystal.

Crystal has been around since 2013 and made its first official release in 2014. Its standard library is quite complete and well-documented. Crystal is statically typed and has support for macros, type inference, union types, and a concurrency model based off Go (fibers and channels)—and best of all, it compiles down to native code.

It also comes with its own package manager, Shards (get it? crystal… shards) that allows for dependency tracking. Since it’s based on LLVM, it allows the use of some neat tools (like Instruments on OS X).

From its website, the primary design goals are to:

  • Have a similar syntax to Ruby (not 100% compatible)
  • Be statically type–checked with good type inference
  • Have compile-time evaluation/code generation
  • Compile to native code

To play around with Crystal, I decided to port over an A* path finding algorithm from Ruby to Crystal. This seemed like a large enough piece of code to get my feet wet in Crystal and allow meaningful benchmarks compared to Ruby. I’ve attached both versions of the code at the bottom of this post, but here are the main gotchas that I encountered while porting my A* code to Crystal:

  • Types. Duh. This was not as bad as I thought it’d be. The type inference works well. I only had to specify a handful of types.
  • Nil checks. This is a huge win for Crystal. If a var can be nil, the compiler enforces that you are nil-safe and don’t use any methods on a nil.
  • The need to use double quotes for all strings.
  • Named args syntax (all args are available as named args without the colon needed in Ruby).
  • class << self is not allowed. Use def self.foo.
  • attr_accessor becomes property.
  • I ran into a bug that was already reported about nil block params. A simple workaround is to use method overloading.
  • Block arg splatting is not implicit and requires parens.
  • STDOUT.write does not exist; change to STDOUT.print. The Crystal folks really hate on method aliases.

There are lots of other little inconsistencies with Ruby, but the Crystal team has documented them and their rationale on their website.

Performance

To test my completely unoptimized version of A*, I used a 180x50 grid to generate 1000 paths in both Ruby and Crystal (compiled with --release flag). Over a handful of manual runs on my MacBookPro, Crystal ran almost 70 times faster!

Takeaways

I'll definitely keep an eye on Crystal as it comes out of its beta phase. The syntax is familiar and easy to pick up, and there's good documentation. The performance is great (especially compared to Ruby). Static types and compiled native code are big wins. Once they get Windows support, I'll definitely be looking into Crystal for my hobby game development.

A* Snippet in Ruby


# Ideal choice of fixed-point equivalent to 1.0 that can almost perfectly represent sqrt(2) and (sqrt(2) - 1) in whole numbers
# 1.000000000 = 2378
# 0.414213624 = 985 / 2378
# 1.414213625 = 3363 / 2378
# 1.414213562 = Actual sqrt(2)
# 0.00000006252 = Difference between actual sqrt(2) and fixed-point sqrt(2)
COST_STRAIGHT = 2378
COST_DIAG = 3363

class Node
  include Comparable

  attr_accessor :location, :cost, :dist, :estimated_total, :parent, :state
  def initialize(location:,cost:,dist:,estimated_total:,parent:nil)
    @location = location
    @cost = cost
    @dist = dist
    @estimated_total = estimated_total
    @parent = parent
  end

  def <=>(b)
    a = self
    if a.estimated_total < b.estimated_total
      return -1
    elsif a.estimated_total > b.estimated_total
      return 1
    else
      0
    end
  end

  def ==(other)
    return false if other.nil? || !other.is_a?(Node)
    @location == other.location
  end
end

NEIGHBORS = [
  [1,0,COST_STRAIGHT],
  [-1,0,COST_STRAIGHT],
  [0,1,COST_STRAIGHT],
  [0,-1,COST_STRAIGHT], 
  [1,1,COST_DIAG], 
  [1,-1,COST_DIAG],
  [-1,1,COST_DIAG],
  [-1,-1,COST_DIAG],
]
class UnsortedPriorityQueue
  def initialize
    @array = []
  end
  def <<(item)
    @array << item
  end
  def include?(item)
    @array.include? item
  end
  def empty?
    @array.empty?
  end
  def pop_smallest
    @array.delete @array.min_by(&:estimated_total)
  end
end

class AStar
  class << self
    def find_path(board, from, to)
      h = board.size
      w = board.first.size
      nodes = {}

      open = UnsortedPriorityQueue.new
      fast_stack = []

      dist = heuristic(from, to)
      node = Node.new(location: from, cost: 0, dist: dist, estimated_total: dist)
      open << node 

      until (fast_stack.empty? && open.empty?)
        current = fast_stack.pop
        current ||= open.pop_smallest

        nodes[current.location] ||= current

        if current.location == to
          return nodes, build_path(current)
        else
          current.state = :closed

          NEIGHBORS.each do |dx,dy,travel_cost|
            n_loc = [current.location[0]+dx, current.location[1]+dy]
            next if blocked?(board, n_loc)

            n_node = nodes[n_loc]
            next if n_node && n_node.state == :closed

            dist = heuristic(n_loc, to)
            cost = current.cost + travel_cost
            estimated_total = cost + dist

            if n_node
              n_node = nodes[n_loc]
              next if estimated_total >= n_node.estimated_total

              n_node.cost = cost
              n_node.estimated_total = estimated_total
              n_node.parent = current
            else 
              n_node = Node.new(location: n_loc, cost: cost, dist: dist, 
                                estimated_total: estimated_total, parent: current)
              nodes[n_node.location] = n_node

              n_node.state = :open
              if n_node.estimated_total <= current.estimated_total
                fast_stack << n_node
              else
                open << n_node
              end
            end

          end
        end
      end

      return nodes, nil
    end

    def build_path(node)
      [].tap do |path|
        while node.parent
          path.unshift node.location
          node = node.parent
        end
      end
    end

    def blocked?(board, loc)
      loc[1] > (board.size-1) || loc[1] < 0 ||
        loc[0] > (board[0].size-1) ||  loc[0] < 0 ||
        board[loc[1]][loc[0]] > 0
    end

    def heuristic(from, to)
      dx = (to[0]-from[0]).abs
      dy = (to[1]-from[1]).abs
      COST_STRAIGHT * (dx + dy) + (COST_DIAG - 2 * COST_STRAIGHT) * min(dx,dy)
    end

    def max(a,b)
      a < b ? b : a
    end

    def min(a,b)
      a > b ? b : a
    end

  end
end

def generate_board(w,h,density)
  board = []
  h.times do
    board << ([0]*w)
  end
  (w*h*density).round.times do 
    board[rand(h)][rand(w)] = 1
  end
  wall_i = (h/2).round
  w.times do |i|
    board[wall_i][i] = 1 unless i == 0 || i == w-1
  end
  wall_j = (w/2).round
  h.times do |j|
    board[j][wall_j] = 1 unless j == 0 || j == h-1
  end
  board
end

def run_scenario(w,h,density)
  if ARGV[0]
    srand ARGV[0].to_i
  end

  puts "generating board"
  board = generate_board w, h, density
  from = [rand(w),rand(h)]
  to = [rand(w),rand(h)]

  board[from[1]][from[0]] = 0
  board[to[1]][to[0]] = 0
  puts "looking...#{from.inspect} -> #{to.inspect}"
  path = nil
  nodes = nil
  1000.times do
    nodes, path = AStar.find_path(board, from, to) || []
  end
  puts path.inspect

  if ARGV[1]
    board.each.with_index do |row, y|
      puts
      row.each.with_index do |val, x|
        if val == 1
          STDOUT.write "\u{2588}"
        else
          loc = [x,y]
          if loc == from
            STDOUT.write 'S' 
          elsif loc == to
            STDOUT.write "X"
          elsif path.include?(loc)
            STDOUT.write "\u{25ab}"
          else
            if(nodes[loc] && nodes[loc].state == :closed)
              STDOUT.write "\u{25a8}"
            else
              STDOUT.write "\u{2592}"
            end
          end

        end
      end
    end
    puts
  end
end

run_scenario 180, 50, 0.05
 

 

A* Snippet in Crystal


COST_STRAIGHT = 2378
COST_DIAG = 3363

class Node
  include Comparable(Node)

  property :location, :cost, :dist, :estimated_total, :parent, :state
  def initialize(location : Array(Int32),cost : Int32 ,dist : Int32, estimated_total : Int32, parent : (Node|Nil)=nil)
    @location = location
    @cost = cost
    @dist = dist
    @estimated_total = estimated_total.as(Int32)
    @state = :unknown
    @parent = parent
  end

  def <=>(b)
    a = self
    if a.estimated_total < b.estimated_total
      return -1
    elsif a.estimated_total > b.estimated_total
      return 1
    else
      0
    end
  end

  def ==(other)
    return false if other.nil?
    @location == other.location
  end
end

NEIGHBORS = [
  [1,0,COST_STRAIGHT],
  [-1,0,COST_STRAIGHT],
  [0,1,COST_STRAIGHT],
  [0,-1,COST_STRAIGHT],
  [1,1,COST_DIAG],
  [1,-1,COST_DIAG],
  [-1,1,COST_DIAG],
  [-1,-1,COST_DIAG],
]
class UnsortedPriorityQueue
  def initialize
    @array = [] of Node
  end
  def <<(item)
    @array << item
  end
  def include?(item)
    @array.includes? item
  end
  def empty?
    @array.empty?
  end
  def pop_smallest
    # puts "min #{@array.min_by(&:estimated_total).location.inspect}"
    @array.delete @array.min_by{|n|n.estimated_total}
  end
end

class AStar
  def self.find_path(board, from, to)
    h = board.size
    w = board.first.size
    nodes = {} of Array(Int32) => Node

    open = UnsortedPriorityQueue.new #Heap.new
    fast_stack = [] of Node

    dist = heuristic(from, to)
    node = Node.new(location: from, cost: 0, dist: dist, estimated_total: dist)
    open << node 

    until fast_stack.empty? && open.empty?
      current = nil
      current = fast_stack.pop unless fast_stack.empty?
      current ||= open.pop_smallest

      if current && !nodes.has_key? current.location
        nodes[current.location] = current
      end

      if current && current.location == to
        return nodes, build_path(current)
      elsif current
        current.state = :closed

        NEIGHBORS.each do |(dx,dy,travel_cost)|
          n_loc = [current.location[0]+dx, current.location[1]+dy]
          next if blocked?(board, n_loc)

          n_node = nodes[n_loc] if nodes.has_key? n_loc
          next if n_node && n_node.state == :closed

          dist = heuristic(n_loc, to)
          cost = current.cost + travel_cost
          estimated_total = cost + dist

          if n_node
            n_node = nodes[n_loc]
            next if estimated_total >= n_node.estimated_total

            n_node.cost = cost
            n_node.estimated_total = estimated_total
            n_node.parent = current
          else 
            n_node = Node.new(location: n_loc, cost: cost, dist: dist, 
                              estimated_total: estimated_total, parent: current)
            nodes[n_node.location] = n_node

            n_node.state = :open
            if n_node.estimated_total <= current.estimated_total
              fast_stack << n_node
            else
              open << n_node
            end
          end

        end
      end
    end

    return nodes, nil
  end

  def self.build_path(node)
    return if node.nil?

    Array(Array(Int32)).new.tap do |path|
      while node.parent
        path.unshift node.location
        node = node.parent.as(Node)
      end
    end
  end

  def self.blocked?(board, loc)
    loc[1] > (board.size-1) || loc[1] < 0 ||
      loc[0] > (board[0].size-1) ||  loc[0] < 0 ||
      board[loc[1]][loc[0]] > 0
  end

  def self.heuristic(from, to)
    dx = (to[0]-from[0]).abs
    dy = (to[1]-from[1]).abs
    COST_STRAIGHT * (dx + dy) + (COST_DIAG - 2 * COST_STRAIGHT) * min(dx,dy)
  end

  def self.max(a,b)
    a < b ? b : a
  end

  def self.min(a,b)
    a > b ? b : a
  end

end


def generate_board(w,h,density)
  board = Array(Array(Int32)).new
  h.times do
    board << ([0]*w)
  end
  (w*h*density).round.to_i.times do 
    board[rand(h)][rand(w)] = 1
  end
  wall_i = (h/2).round
  w.times do |i|
    board[wall_i][i] = 1 unless i == 0 || i == w-1
  end
  wall_j = (w/2).round
  h.times do |j|
    board[j][wall_j] = 1 unless j == 0 || j == h-1
  end
  board
end

def run_scenario(w,h,density)
  if ARGV.size > 0
    Random::DEFAULT.new_seed [ARGV[0].to_i]*4
  end

  puts "generating board"
  board = generate_board w, h, density
  from = [rand(w),rand(h)]
  to = [rand(w),rand(h)]

  board[from[1]][from[0]] = 0
  board[to[1]][to[0]] = 0
  puts "looking...#{from.inspect} -> #{to.inspect}"
  path = nil
  nodes = nil
  1000.times do
    nodes, path = AStar.find_path(board, from, to)
  end
  puts path.inspect

  if ARGV.size > 1
    board.each.with_index do |row, y|
      puts
      row.each.with_index do |val, x|
        if val == 1
          STDOUT.print "\u{2588}"
        else
          loc = [x,y]
          if loc == from
            STDOUT.print 'S' 
          elsif loc == to
            STDOUT.print "X"
          elsif path && path.includes?(loc)
            STDOUT.print "\u{25ab}"
          else
            if(nodes && nodes.has_key?(loc) && nodes[loc] && nodes[loc].state == :closed)
              STDOUT.print "\u{25a8}"
            else
              STDOUT.print "\u{2592}"
            end
          end

        end
      end
    end
    puts
  end
end

run_scenario 180, 50, 0.05