4
\$\begingroup\$

I wrote a random world generator for the classic Snakes and Ladders board game.

Snakes and Ladders is a dice game played over a grid, usually 10x10. You win by reaching the last square first. The board has ladders and snakes that connect specific squares. Land at the base of a ladder and you climb to the ladder's head (good). Land on the head of a snake and you slide down to the snake's tail (bad).

Snakes and ladders are key value pairs; the key represents the start point, and the value represents the end point. Both are identical except that a snake's start point must be greater than its end point, while the opposite is true for a ladder.

World rules:

  1. A snake's head can't be on the last square otherwise you can't win the game.
  2. A ladder's base can't be on the last square since there's no where to go.
  3. A square can not contain the base of a ladder and the head of a snake. You either slide, or climb.
  4. Players start off the board.

A square can technically contain the tail of a snake and the base of a ladder, or head of the snake and head of a ladder. But this could have weird side effects (presumably why I've not seen a board with those characteristics): You slide down a snake only to reach the base of a ladder that takes you to the winning square; or you climb up a ladder only to reach the head of a snake that drags you down. While not fatal, such side effects muddle the role definition of ladders and snakes; in that, ladders are no longer necessarily good, and neither are snakes necessarily bad.

Example World

# snakes
{97=>62, 35=>21, 80=>67, 38=>12, 64=>6, 79=>20, 26=>11, 89=>33, 22=>21, 45=>25} 
# Ladders
{10=>74, 77=>88, 5=>68, 24=>93, 68=>90, 73=>84, 76=>85, 50=>53, 78=>85, 12=>73}

Builder

  class World
    attr_reader :size, :ladders, :snakes

    def initialize(size, ladders = 10, snakes = 10)
      @size = size
      @snakes = place_snakes(snakes)
      @ladders = place_ladders(ladders)
    end

    def place_snakes(count)
      count.times.each_with_object({}) do |_, hash|
        start_point = rand(snake_habitable_range)
        end_point = rand(snake_habitable_range.begin..(start_point - 1))
        hash[start_point] = end_point
      end
    end

    def place_ladders(count)
      count.times.each_with_object({}) do |_, hash|
        begin
          start_point = rand(ladder_habitable_range)
        end while snakes.keys.include?(start_point)

        begin
          end_point = rand((start_point + 1)..ladder_habitable_range.end)
        end while snakes.keys.include?(end_point)

        hash[start_point] = end_point
      end
    end

  private

    def snake_habitable_range
      2..(size - 1)
    end

    def ladder_habitable_range
      1..(size - 1)
    end
  end
\$\endgroup\$
  • \$\begingroup\$ I just noticed a subtle bug in my code. Ladders are not always 10. Sometimes there are only 7 or 8. Must be the begin end while block. \$\endgroup\$ – Mohamad Nov 20 '14 at 16:42
  • \$\begingroup\$ Follow-up question \$\endgroup\$ – 200_success Nov 20 '14 at 23:56
3
\$\begingroup\$

I'm going to be bold and review my own code having spent the last hour refactoring it.

The original implementation had bugs. Sometimes less than 10 ladders were placed. This is because the algorithm did not check to see if there was a ladder already present at the current insertion point.

# Tough luck if start_point is 10 and there's already a ladder there
begin
  start_point = rand(ladder_habitable_range)
end while snakes.keys.include?(start_point)

The best way to ensure a bullet proof implementation is to avoid having a square contain more than one object. For example, there's an edge case where a square can contain a ladder's head and a tail, causing you to progress even further.

To do that, the placement should be delegated to a method that checks if the square is occupied. This requires tweaking the initialize method, but it's worth it:

  def place_point(range = habitable_range)
    begin
      point = rand(range)
    end while occupied?(point)
  end

  def occupied?(number)
    [snakes.keys, snakes.values, ladders.keys, ladders.values].flatten.include?(number)
  end

Doing so means the placement methods for ladders and snakes only have to worry about working out the range and populating their respective hashes, which are the only two differences between them. This reduces duplication.

  def place_snakes(count)
    count.times do
      start_point = place_point
      end_point_range = habitable_range.begin..(start_point - 1)

      snakes[start_point] = place_point(end_point_range)
    end
  end

Finally The habitable range for ladders and snakes is the same, so this can be replaced with a single range 1..(size - 1):

def snake_habitable_range
  2..(size - 1)
end

def ladder_habitable_range
  1..(size - 1)
end

Behold! My new implementation.

class World
  attr_reader :size, :snakes, :ladders

  def initialize(size, snakes = 10, ladders = 10)
    @size = size
    @snakes, @ladders = {}, {}
    place_snakes(snakes)
    place_ladders(ladders)
  end

  def place_snakes(count)
    count.times do
      start_point = place_point
      end_point_range = habitable_range.begin..(start_point - 1)

      snakes[start_point] = place_point(end_point_range)
    end
  end

  def place_ladders(count)
    count.times do
      start_point = place_point
      end_point_range = (start_point + 1)..habitable_range.end

      ladders[start_point] = place_point(end_point_range)
    end
  end

private

  def place_point(range = habitable_range)
    begin
      point = rand(range)
    end while occupied?(point)
  end

  def occupied?(number)
    [snakes.keys, snakes.values, ladders.keys, ladders.values].flatten.include?(number)
  end

  def habitable_range
    1..(size - 1)
  end
end
\$\endgroup\$
  • 2
    \$\begingroup\$ Lol ++ for giving your own code a respectable review. You might want to post a follow up for a review of the new implementation though. \$\endgroup\$ – RubberDuck Nov 20 '14 at 18:49
  • \$\begingroup\$ Considering changingcount.times do... to while ladders.length < count do.... Adds another layer of safety, lets you change your implementation of adding ladders later. \$\endgroup\$ – Devon Parsons Nov 20 '14 at 18:56
  • \$\begingroup\$ I posted a follow up... @DevonParsons thanks for the suggestion. \$\endgroup\$ – Mohamad Nov 20 '14 at 19:01
  • \$\begingroup\$ @DevonParsons I'm not really clear on how it would allow me to add ladders or snakes later. Mind elaborating? \$\endgroup\$ – Mohamad Nov 20 '14 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.