6
\$\begingroup\$

(EDIT: I incorporated a lot of the feedback from the answers, and posted a follow-up question here: Codingame: Great Escape bot in Ruby - Follow-up)

I started working on some code challenges at CodinGame to learn Ruby, and this is my first big Ruby project. It's a bot for their Great Escape contest (here is a sample gameplay video).

Screenshot of a 3-player game of the Great Escape

Each player starts at one side of the board and must reach the opposite side. Each turn, a player can either move along the grid, or try to block their opponents by placing a wall somewhere. It is illegal to completely cut an opponent off from their goal side.

My bot maintains the distance to the goal and next step along the shortest path for each grid cell for each player and follows that. In addition, it tries to block the opponent who is closest to victory by placing walls across their shortest path.

Communication goes through console gets / puts. Each turn, my bot receives player and wall coordinates and outputs a single command to either move or place a new wall.

As I said, this is my first big Ruby project, so all comments on coding style, code organisation, naming conventions, performance, etc., are welcome. The only constraints are that the contest system requires everything to be in one file and has a limited set of libraries (I'm not actually sure which ones).

#!/usr/bin/env ruby STDOUT.sync = true # DO NOT REMOVE require 'set' class BinaryHeap def initialize @elements = [] end def size @elements.size end def empty? @elements.empty? end def clear @elements.clear self end def push(element) @elements << element bubble_up(@elements.size - 1) self end alias :<< :push def pop return nil if empty? root = @elements[0] @elements[0] = @elements[@elements.size - 1] @elements.pop trickle_down(0) root end def peek return nil if empty? @elements[0] end def inspect "<#{self.class}: size=#{size}, peek=#{peek || "nil"}>" end private def bubble_up(i) p = parent(i) while (i > 0 && comp(i, p) < 0) do swap(i, p) i, p = p, parent(p) end end def trickle_down(i) begin j, r, l = -1, right_child(i), left_child(i) if (r < @elements.size && comp(r, i) < 0) j = comp(l, r) < 0 ? l : r elsif (l < @elements.size && comp(l, i) < 0) j = l; end swap(i, j) unless j < 0 i = j end while i >= 0 end def left_child(i) 2 * i + 1 end def right_child(i) 2 * i + 2 end def parent(i) (i - 1) / 2 end def swap(i, j) @elements[i], @elements[j] = @elements[j], @elements[i] end def comp(i, j) @elements[i] <=> @elements[j] end end Player = Struct.new(:id, :row, :col, :walls_left) Wall = Struct.new(:row, :col, :dir) Node = Struct.new(:row, :col, :left, :right, :up, :down, :dists, :successors) do def to_s "(#{row}, #{col})" end def inspect "(#{row}, #{col})" end def neighbours [left, right, up, down].compact end def successorString(id) case successors[id] when nil then "nil" when left then "LEFT" when right then "RIGHT" when up then "UP" when down then "DOWN" end end end NodeWrapper = Struct.new(:node, :player_id) do def <=> (other) node.dists[player_id] <=> other.node.dists[player_id] end end # w: width of the board # h: height of the board # player_count: number of players (2 or 3) # my_id: id of my player (0 = 1st player, 1 = 2nd player, ...) $w, $h, @player_count, @my_id = gets.split(" ").collect {|x| x.to_i} #init grid @grid = Array.new($h){Array.new($w){Node.new()}} for row in 0..$h-1 do for col in 0..$w-1 do @grid[row][col].row = row @grid[row][col].col = col @grid[row][col].left = @grid[row][col - 1] unless col == 0 @grid[row][col].right = @grid[row][col + 1] unless col == $w - 1 @grid[row][col].up = @grid[row - 1][col] unless row == 0 @grid[row][col].down = @grid[row + 1][col] unless row == $h - 1 @grid[row][col].dists = [$w - col - 1, col, $h - row - 1] @grid[row][col].successors = [@grid[row][col].right, @grid[row][col].left, @grid[row][col].down] end end @walls = [] @players = [] # Breaks the connections in the grid between these cells # Returns the list of invalidated cells def breakConnection(row1, col1, row2, col2) invalid = []; if row1 == row2 r = row1 c1 = (col1 < col2 ? col1 : col2) c2 = (col1 < col2 ? col2 : col1) if @grid[r][c1].right @grid[r][c1].right = nil @grid[r][c2].left = nil for id in 0..@player_count-1 do if @grid[r][c1].successors[id] == @grid[r][c2] invalid += invalidateCell(@grid[r][c1], id) end if @grid[r][c2].successors[id] == @grid[r][c1] invalid += invalidateCell(@grid[r][c2], id) end end end else c = col1 r1 = (row1 < row2 ? row1 : row2) r2 = (row1 < row2 ? row2 : row1) if @grid[r1][c].down @grid[r1][c].down = nil @grid[r2][c].up = nil for id in 0..@player_count-1 do if @grid[r1][c].successors[id] == @grid[r2][c] invalid += invalidateCell(@grid[r1][c], id) end if @grid[r2][c].successors[id] == @grid[r1][c] invalid += invalidateCell(@grid[r2][c], id) end end end end return invalid end # Breaks the connections in the grid crossing this wall # Returns the list of invalidated cells def addWall(wall) invalid = [] if wall.dir == "V" # Wall starts at the top left corner of (row, col) and continues down for 2 cells invalid += breakConnection(wall.row, wall.col - 1, wall.row, wall.col) invalid += breakConnection(wall.row + 1, wall.col - 1, wall.row + 1, wall.col) else # H # Wall starts at the top left corner of (row, col) and continues right for 2 cells invalid += breakConnection(wall.row - 1, wall.col, wall.row, wall.col) invalid += breakConnection(wall.row - 1, wall.col + 1, wall.row, wall.col + 1) end return invalid end # Invalidates the given node and all nodes whose shortest path go through it # Returns the list of invalidated cells def invalidateCell(node, player_id) STDERR.puts "Invalidating #{node.to_s} for player #{player_id}" node.successors[player_id] = nil # Check if we can reroute node.neighbours.each do |n| if n.dists[player_id] == node.dists[player_id] - 1 node.successors[player_id] = n STDERR.puts "Rerouting successful" return [] end end STDERR.puts "No rerouting possible" # No rerouting possible. Invalidate this and predecessors. node.dists[player_id] = nil invalid = [[node, player_id]] node.neighbours.each do |n| invalid += invalidateCell(n, player_id) if n.successors[player_id] == node end STDERR.puts "Finished invalidating #{node.to_s} for player #{player_id}" STDERR.puts invalid.to_s return invalid end # Updates the shortest paths of the given cells def computeNewPaths(invalid) playerCells = Array.new(@player_count){[]} invalid.each do |node, id| playerCells[id] << node end for id in 0..@player_count-1 do computeNewPathsForPlayer(playerCells[id], id) end end # Updates the shortest paths of the given cells def computeNewPathsForPlayer(invalid, player_id) frontier = BinaryHeap.new() # Add all non-invalidated neighbours to our frontier invalid.each do |node| node.neighbours.each do |neighbour| frontier << NodeWrapper.new(neighbour, player_id) if neighbour.dists[player_id] end end # Expand the closest frontier node until they're out until frontier.empty? do node = frontier.pop.node node.neighbours.each do |neighbour| if neighbour.dists[player_id].nil? || neighbour.dists[player_id] > node.dists[player_id] + 1 neighbour.dists[player_id] = node.dists[player_id] + 1 neighbour.successors[player_id] = node frontier << NodeWrapper.new(neighbour, player_id) end end end end def block(opponent) STDERR.puts "Trying to block #{opponent}" # Try to block each move of the upcoming shortest path blocked = false node = @grid[opponent.row][opponent.col] succ = node.successors[opponent.id] until (blocked || succ.nil?) do blocked = blockConnection(node, succ) node = succ succ = node.successors[opponent.id] end return blocked end def blockConnection(node, succ) STDERR.puts "Trying to block the connection between #{node} and #{succ}" if node.row == succ.row dir = "V" col = [node.col, succ.col].max return tryWall(node.row, col, dir) || tryWall(node.row - 1, col, dir) else dir = "H" row = [node.row, succ.row].max return tryWall(row, node.col, dir) || tryWall(row, node.col - 1, dir) end end def tryWall(row, col, dir) if isValidWall(row, col, dir) puts "#{col} #{row} #{dir}" return true else return false end end def isValidWall(row, col, dir) # Within the grid return false if row < 0 || row > $h-1 return false if col < 0 || col > $w-1 return false if dir == "V" && row == $h-1 return false if dir == "H" && col == $w-1 # Does not intersect existing walls @walls.each do |wall| if wall.dir == dir return false if dir == "V" && col == wall.col && (row - wall.row).abs < 2 return false if dir == "H" && row == wall.row && (col - wall.col).abs < 2 else return false if dir == "V" && col == wall.col + 1 && row == wall.row - 1 return false if dir == "H" && col == wall.col - 1 && row == wall.row + 1 end end # Does not cut off a player's last path (0..@player_count-1).each do |player_id| return false unless verifyDestinationStillReachableWithWall(row, col, dir, player_id) end return true end def verifyDestinationStillReachableWithWall(row, col, dir, player_id) return explore(@players[player_id].row, @players[player_id].col, player_id, row, col, dir, Set.new()) end # DFS with preference towards the destination side def explore(row, col, player_id, wall_row, wall_col, wall_dir, marked) node = @grid[row][col] return true if node.dists[player_id] == 0 marked << node neighbours = case player_id when 0 [node.right, node.up, node.down, node.left] when 1 [node.left, node.up, node.down, node.right] when 2 [node.down, node.left, node.right, node.up] end neighbours.compact.each do |n| unless (wallBlocks(wall_row, wall_col, wall_dir, node, n) || marked.include?(n)) return true if explore(n.row, n.col, player_id, wall_row, wall_col, wall_dir, marked) end end return false end def wallBlocks(wall_row, wall_col, wall_dir, node, neighbour) if node.row == neighbour.row wall_dir == "V" && wall_col == [node.col, neighbour.col].max && (wall_row == node.row || wall_row == node.row - 1) else wall_dir == "H" && wall_row == [node.row, neighbour.row].max && (wall_col == node.col || wall_col == node.col - 1) end end # game loop loop do @players = [] @player_count.times do |id| # x: x-coordinate of the player # y: y-coordinate of the player # walls_left: number of walls available for the player col, row, walls_left = gets.split(" ").collect {|x| x.to_i} @players << Player.new(id, row, col, walls_left) end invalid = [] @walls = [] wall_count = gets.to_i # number of walls on the board wall_count.times do # wall_x: x-coordinate of the wall # wall_y: y-coordinate of the wall # wall_orientation: wall orientation ('H' or 'V') wall_x, wall_y, wall_orientation = gets.split(" ") wall = Wall.new(wall_y.to_i, wall_x.to_i, wall_orientation) @walls << wall invalid += addWall(wall) end computeNewPaths(invalid) unless invalid.empty? me = @players[@my_id] myDist = @grid[me.row][me.col].dists[@my_id] tookAction = false if me.walls_left > 0 opponents = (0..@player_count-1).to_a - [@my_id] opponents.map! { |id| @players[id] } opponents.select! { |o| o.row > -1 } opponents.shuffle! if opponents.length >= 2 opponents.sort_by! { |o| @grid[o.row][o.col].dists[o.id] } if opponents.length >= 2 opponents.each do |o| dist = @grid[o.row][o.col].dists[o.id] if !tookAction && dist <= 3 && (dist < myDist || (dist == myDist && o.id < @my_id)) # This opponent will beat me if I don't block them tookAction = block(o) end end end # Follow the shortest path puts @grid[me.row][me.col].successorString(@my_id) unless tookAction end

EDIT: If you want to run the program, try the following input:

9 9 2 0 0 7 10 8 3 10 0

The first line of the input is given once at the start of the game and sets these variables:

  • w: width of the board
  • h: height of the board
  • player_count: number of players (2 or 3)
  • my_id: id of my player (0 = 1st player, 1 = 2nd player, ...)

Every game turn, my program expects the following input:

  • One line per player, containing:
    • col: x-coordinate of the player
    • row: y-coordinate of the player
    • walls_left: number of walls available for the player
  • A line containing the number of walls present
  • One line per wall, containing:
    • wall_col: x-coordinate of the wall
    • wall_row: y-coordinate of the wall
    • wall_orientation: wall orientation ('H' or 'V')

The program gives one line of output, either:

  • A direction to move in (LEFT, RIGHT, UP, or DOWN); or
  • A new wall placement putX putY putOrientation
\$\endgroup\$

2 Answers 2

Reset to default
5
\$\begingroup\$

A few things to improve the game experience:

  1. Add a shebang: #!/usr/bin/env ruby, this will help the users run your code from the console like this: ./great_escape_bot.rb.
  2. Add a banner or anything to let the user know that input is required and what he should do next an example here.
  3. I don't know your experience with testing, but for a program that's small as this it would be worth to have a small test suite to check that everything will work as expected, you can try minitest. This will not affect your game submission but it will help you refactor your code easily without and with confidence.
    This is a good tutorial to get you started with minitest: link. The main idea being that you have a file that test your implementation to make sure your code is working as expected without having to check it manually (this is an example):

```

def test_it_turns_left assert_equal Game.move_to(9), 'Robot moved to 9,0' end

  1. Use the recommended code style for ruby, one thing that you can do to help it be more ruby-like is to use 2 spaces instead of tabs to align your code.

  2. Consider adding everything inside a module and use more classes (while still keeping everything in the same class), that will increase the readability.
    Example:

```

#!/usr/bin/env ruby module Game class BinaryHeap # Code end class Runner # Code end class ErrorChecker # Code end end Game::Runner.run

That's all I can say for now since I can't run the program, maybe write in the beginning of the file if there are any restrictions to the environment, or maybe force the restriction when the file is ran.

Depending on my time I'll decide to debug it later, without unit tests I don't know if my environment or the code is at fault.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the tips! I added the shebang and example input. I can't print anything else to the console, because the contest system will reject it. I hadn't seen the style guide, that's a great resource! Could you expand a little on numbers #3 and #5? \$\endgroup\$ Commented Jul 4, 2017 at 19:44
  • \$\begingroup\$ I have updated my answer to give you examples. After I'll have time to look more closely at the code and make it run I'll get back to you. \$\endgroup\$ Commented Jul 5, 2017 at 13:00
4
\$\begingroup\$

Consider the forwardable library

Consider using the built-in forwardable library to build forwarding methods. Instead of this:

class BinaryHeap ... def size @elements.size end def empty? @elements.empty? end

You can do this:

require "forwardable" class BinaryHeap extend Forwardable ... def_delegators :@elements, :size, :empty?

Use $stderr instead of STDERR

Consider writing to $stderr instead of STDERR. The difference is that STDERR is a constant, whereas $stderr is a global variable that, by default, refers to STDERR. Among other things, code writing to $stderr is easier to test than code writing to STDERR, because the test can temporarily reassign $stderr to a StringIO in order to caputre the output.

Don't use return at the end of a method

When returning a value at the end of a method:

 return false end

Omit the return:

 false end

The value of a method is the value of the last expression evaluated by the method.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.