From Ruby to Crystal: A Quick Look

March 24, 2017

Article summary

Performance
Takeaways
A* Snippet in Ruby
A* Snippet in Crystal

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

Conversation

Todd says:

March 24, 2017

“Once they get Windows support…”

Any chance you could give the game industry some support, and not make it a Microsoft-first world anymore? Its a rather circular argument, that “for good games, you need Windows,” since the only reason for that is developers developing a Windows-first world. Platform independence, FTW. Linux-first for the top score ;)

berwyn says:

March 24, 2017

It’s not even a matter of making it “Microsoft-first”, it’s a matter of Windows being the most common desktop OS on the planet, and therefore it exists as a baseline requirement for a game to support in order to be viable on the market.

Shawn Anderson says:

March 24, 2017

Thanks for the comment, Todd. While I entirely agree that Windows-first world is unfortunate, most of the game dev I do is for game jams (especially http://www.ludumdare.com/compo/). To get other people to play them and rate them, you need to either put out a windows build or a browser build.

So while I’ll definitely keep playing with Crystal, I won’t be switching over my game dev hobby until they get some form of Windows support.

Max says:

March 24, 2017

>To get other people to play them and rate them, you need to either put out a windows build or a browser build.
Shawn did you see at Cocos2d-x game framework (that include Cocos2d-js)?
its a great Spider Monkey (browser in your therm) 2D framework (they also starts 3D development) that support not only Windows desktop but also Windows Phone, iOS, MacOS, Android, Linux.
Actually Cocos2d-x not support Ruby – only JavaScript, Lua, C++ – but it have very wide platform coverage.

Shawn Anderson says:

March 25, 2017

I have seen some of the Cocos2d-x stuff. It looks really nice. I’m also interested in playing more with Love2D now that it can target Android / iOS.

Tim Uckun says:

March 24, 2017

BTW you can save some typing in your initialize method like this

class Person
def initialize(@name : String, @age = 0)
end

def printit
puts “#{@name} #{@age}”
end
end

tim = Person.new(name: “Tim”)
tim.printit

Shawn Anderson says:

March 25, 2017

Good point TIm. I missed the opportunity to use that trick (probably from starting with Ruby code and only fixing what was broken).

Thomas says:

March 25, 2017

Why is the heuristic logic implemented differently between the Ruby and the Crystal version?

Ruby: COST_STRAIGHT * (dx + dy) + (COST_DIAG – 2 * COST_STRAIGHT) * min(dx,dy)
Crystal: COST_STRAIGHT * max( dx, dy) + COST_DIAG * min(dx, dy)

This indicates that the comparison might not be fair.

Shawn Anderson says:

March 26, 2017

Ah, good catch Thomas. I had updated one heuristic but not the other. I’ve since updated the code and reran the comparison and found very similar results.
- Benoit Daloze says:
  
  March 29, 2017
  
  I also noticed that the PRNG in Ruby and Crystal are not the same.
  Therefore, runs with the same seed are different.
  Hardcoding the search to [54, 25] -> [155, 28] gives on my laptop:
  2.67s Crystal release
  90.42s Ruby 2.4.0
  That’s still 33.9 times faster, but not 70 times.
  - Shawn Anderson says:
    
    March 29, 2017
    
    Thanks for the comment Benoit. I didn’t draw attention to the different PRNG, but you are correct. I used seeds that caused a similar amount of nodes to be explored.
    
    A better benchmarking approach would be to generate the maps out to some yml file and loaded them from each Ruby and Crystal to get around the issue. I haven’t dug into the joys of importing YAML or JSON into a typed language like Crystal yet. So, the benchmarks that I ran did vary from 50 to 100 times faster depending on the test cases ran.
    
    If anyone in the Crystal community wants to build on this, feel free. I’d love to see the results. For now, I have a few other projects on my plate.

peter marien says:

April 1, 2017

I’m looking forward to try Crystal, but absolutely need Windows support (not for games though) . Windows support for programming languages other than .Net is still a problem, a huge waste of potential ! After 4 year it’s time and otherwise too late I am afraid. And to counter comments, I wish I had the level to contribute but I don’t..