#!/usr/bin/ruby

require "io/console"

# Tile indices.
WALL = 5
SPACE = 6
ITEM_BLACK = 7
ITEM_WHITE = 8
PLAYER_HEAD = 9
PLAYER_TAIL1 = 10
PLAYER_TAIL2 = 11
PLAYER_TAIL3 = 12
PLAYER_TOMBSTONE = 13
HINT_BLACK = 14
HINT_WHITE = 15
PLAYER_BLACK = 0
PLAYER_WHITE = 1

# Direction constants.
DIRECTION_UP = 0
DIRECTION_DOWN = 1
DIRECTION_RIGHT = 2
DIRECTION_LEFT = 3
DIRECTIONS = [[0, -1], [0, 1], [1, 0], [-1, 0], nil]

palette = ["\e[0m", "\e[1m"] +
          "#,'h_(e(#kek#df/)de/`(f)f.#j".scan(/../).map{|x|
            "\e[#{x.ord-5};#{x[1].ord}m"
          } +
          "##  []()@@OO%%XX++".scan(/../)

last_sprite = ""
SPRITES =
   "arrrzzesarrzgtarrzessarzgttarzfsssazhtttazesssazgtttazdqzzcrzzfszeszgtzhtzfuzhvzkwzlqziwzjqzixzjyzmuznvzdszzdtzza".split(/z/).map{|x|
      x == "" ? last_sprite
              : last_sprite = x.bytes.map{|y| palette[y - 'a'.ord]} * ""
   }


# Check window dimensions.  Game grid will be sized accordingly.
#
# We need at least enough columns to hold the status bar, and enough
# rows such that there will be room to place items.
#
# By the way, you might think that a really small grid will make an easy
# game, but what that really provides is a short game.  It's actually
# more difficult to score long chains with a small grid because there is
# less room to maneuver.
height, width = IO.console.winsize
if height < 12 || width < 40
   print "Window size too small, need at least 12 rows and 40 columns.\n"
   exit
end


# Convert console dimensions to game grid dimensions.
# - Width minus 1 is to avoid margins, otherwise things may wrap poorly.
# - Height minus 2 is to account for for margin and status bar.
#
# The divide by 2 is to account for 1:2 aspect ratio of the character
# cell.  Well, my terminal fonts are close enough to 1:2, yours might
# be vastly different, but there isn't a cheap way to detect and
# adjust for this.
width = (width - 1) / 2
height -= 2

# Game states.
running = true                # True if game is still in progress.
color = PLAYER_WHITE          # Current player color.
direction = DIRECTION_RIGHT   # Current direction.
px = width / 4                # Player position.
py = height / 2
history = []                  # Previous player positions.
growth_target = 2             # Desired length of player.
score = 0                     # Player score.
last_item_color = ITEM_WHITE  # Color of last item eaten (7 or 8).
chain_item_count = 0          # Number of items in current chain.
chain_length = 0              # Current chain length.
max_chain_length = 0          # Maximum achieved chain length.
generated_item_count = 0      # Number of items generated.
frame_parity = 0              # 1 bit frame counter, for blinking effect.
new_item = nil                # Next item to be placed.
endgame = false               # True if endgame is in effect.

# Movement speed in number of units moved per second.  Use command line
# argument if that's specified, otherwise default to 5 cells per second.
#
# Note that slowest allowed speed is 0.1 cells per second, so players can
# wait up to 10 seconds to make a move.  We used to allow even longer
# delays when there is an explicit quit function, but since that's
# removed and player must rely on death to end the game, we want to put
# some bounds on how long the player must wait for games to end.
speed = ARGV[0].to_f
movement_delay = speed >= 0.1 ? 1 / speed : 0.2

# Ring buffer of next directions, written by input_thread and read by
# main thread.  We buffer inputs so that quick consecutive keystrokes
# are not lost.
input_buffer = [0] * 8
input_write_index = 0      # Next position to write to.
input_read_index = 0       # Next position to read from.

# Shuffled list of positions, used for item generation.
positions = [*1..(width - 2)].product([*1..(height - 2)]).shuffle
position_index = 0

# Function to determine next item tile based on number of items
# generated so far.  Returns ITEM_BLACK or ITEM_WHITE.
#
# We essentially only generate items with the same color in groups of 3s.
# This means if player has never broken a chain before the endgame, they
# will be able to maintain chains all the way to the end.
#
# First item is ITEM_WHITE, since player start off in white.
next_item_tile = -> { 8 - generated_item_count % 6 / 3 }

# Initialize game field.
grid = []
height.times{|i|
   grid += [[WALL] +
            [i > 0 && i < height - 1 ? SPACE : WALL] * (width - 2) +
            [WALL]]
}

# Place the first item just in front of the player.  This guarantees that
# there is at least one item.
grid[py][width - px] = next_item_tile.call
generated_item_count += 1

# Check if a position is sufficiently far from player's head, returns true
# if so.
far_away_position = ->(x, y) {
   (x - px).abs > 3 || (y - py).abs > 3
}

# Check if a position is eligible for placing new items, based on whether
# it's near the player's head and whether it is adjacent to items of
# the same color.
#
# Note that the heuristics here will also cause us to avoid placing
# new items near walls, or near player's tail.
#
# Sets new_item to be the next item to be generated.
eligible_for_placement = ->(x, y) {
   new_item = next_item_tile.call
   far_away_position.call(x, y) &&
   [*-1..1].product([*-1..1]).all?{|dx, dy|
      i = grid[y + dy][x + dx]
      i == new_item || i == SPACE
   }
}

# Try assigning initial set of items.
#
# Here we might try to generate items such that we end up with with a
# multiple of 3.   This means players who maintained chain status
# perfectly will not be forced to break any chains during endgame
# regardless of which color is chosen.  But this requires that player
# plays perfectly and also that endgame triggers when item count is a
# multiple of 3.  Since we can't guarantee both to be true, we make a best
# effort selection of item color at endgame to avoid breaking chains.
positions.each{|x, y|
   if
      # Avoid the rows near player's starting position.
      (y - py).abs > 1 &&
      # Unconditionally skip some of the cells, otherwise the initial
      # grid is too dense.
      rand < 0.1 &&
      # Update new_item, and verify that the selected position is eligible.
      #
      # We used to also enforce that the initial set of items do not
      # form excessively large clusters, but that is mostly covered by
      # "rand < 0.1" constraint above.
      eligible_for_placement.call(x, y)

      grid[y][x] = new_item
      generated_item_count += 1
   end
}

# Mark initial player location.
grid[py][px] = PLAYER_HEAD


# Render function.
render = -> {
   # Build status line.
   # 1. Draw current chain status (6 characters wide) on the left.
   # 2. Draw score on the right (right-aligned).
   # 3. Fill the middle bits with current chain length.
   #
   # The middle bit used to only grow up to 9 units (i.e. max chain length),
   # but it looks nicer to make use of the full width, so that's what we have
   # done.  To indicate that the max chain has been reached, the bar color
   # changes from cyan to bright cyan, and chain text changes to uppercase.
   current_chain = SPRITES[chain_item_count * 2 + (last_item_color - 7)]
   score_status = " " + score.to_s

   if chain_length > 0
      chain_status = "  %-#{width * 2 - 8 - score_status.size}s" %
                     "#{chain_length} chain"
      prefix = palette[chain_length > 9 ? (chain_status.upcase!; 15)
                                        : 14]
      i = [chain_status.size, chain_length * 2].min
      chain_status = prefix + chain_status[0, i] +
                     "\e[0m" + chain_status[i, chain_status.size]
   else
      chain_status = " " * (width * 2 - 6 - score_status.size)
   end

   image = "\e[#{height + 1}A\r" + current_chain + chain_status +
           "\e[1m" + score_status + "\e[0m\n\r"

   # Build grid image.
   image +=
      grid.map{|row|
         row.map{|cell| SPRITES[cell * 2 + color]} * ""
      } * "\e[0m\n\r" +
      "\n"
   print image
}


# Input loop.  This happens in a separate thread so that the main
# display loop runs more or less at constant rate.
input_thread = Thread.new{
   while running
      # Wait for keystroke.
      #
      # Alternatively, can read this without a timeout so that we can
      # poll for game status once in a while (and thus exit cleanly
      # when game has ended), but on windows that causes a serious
      # input lag, so now we just do a blocking read.
      #
      # But this leads to a separate problem where if we just kill the
      # input thread while it's waiting for keystroke, the terminal
      # might be left in a bad state (e.g. with echo off), so we force
      # the player to feed an extra keystroke on exit.
      key = STDIN.getch
      new_direction = "\e[".index(key) ? nil : ("AwBsCdDa".index(key) || 8) / 2

      # Add input to ring buffer.  We used to try to apply the action
      # right away, but no matter how fast we do it, some keys just
      # always get lost, so now we buffer them.
      #
      # Also, it used to be that moving in the same direction causes
      # player to change color, but that leads to some unpredictable
      # color changes, so now we require the dedicated key for that
      # purpose.  (Previously this was a nice feature because it made
      # it easier to play one-handed, but I suppose that's still
      # possible depending on keyboard layout).
      if new_direction
         input_buffer[n = -~input_write_index % input_buffer.size] =
            new_direction
         # Update index after array element has been written, to avoid a
         # race with reading the array contents.
         input_write_index = n
      end
   end
}


# Disable echo, hide cursor, and clear window.
STDIN.echo = false
print "\e[?25l\n" * height


# Draw initial frame.
render.call

# Game loop.
last_movement = Time::now
while running
   # Make chain status blink if we are currently at max chain.
   if chain_item_count == 3
      image = "\e[#{height + 1}A\r" +
              SPRITES[6 + (last_item_color - 7) + frame_parity] +
              "\e[#{height + 1}B"
      print image
      frame_parity ^= 2
   end

   # Apply buffered action.
   if input_read_index != input_write_index
      next_action = input_buffer[
         input_read_index = -~input_read_index % input_buffer.size]
      d = DIRECTIONS[next_action]
      next_cell = d ? grid[py + d[1]][px + d[0]] : (color ^= 1)

      # Do not allow player to turn back onto themselves, or into a wall.
      # For a color change, next_cell evaluates to 0 or 2, which is outside
      # of the range of the allowed turn destinations.
      if next_cell >= SPACE && next_cell <= ITEM_WHITE
         direction = next_action

         # Cause direction changes to take effect right away.
         last_movement = Time.at(0)
      else
         # Force immediate redraw on color change.
         render.call
      end
   end

   # Apply movement based on elapsed time, as opposed to using the
   # frame counter.  This appears to be more reliable than trying to
   # maintain a constant frame rate via sleep.
   #
   # On the other hand, not doing any sleep means this script will peg
   # one CPU core, which is unfortunate.  Again, blame it on windows,
   # where any kind of sleep or timeout just don't get the same level
   # of precision we get with linux.
   current_time = Time::now
   if current_time - last_movement < movement_delay
      # Wait a bit before polling input queue again.
      sleep 0.02
      next
   end

   last_movement = current_time

   # Mark old player positions.
   history += [[px, py]]
   dirty_pixels = [[px, py]]
   grid[py][px] = PLAYER_TAIL1
   i = history[history.size / 2]
   dirty_pixels += [i]
   grid[i[1]][i[0]] = PLAYER_TAIL2
   i = history[history.size / 4]
   dirty_pixels += [i]
   grid[i[1]][i[0]] = PLAYER_TAIL3

   # Update player position.
   d = DIRECTIONS[direction]
   px += d[0]
   py += d[1]

   i = grid[py][px]
   if i != SPACE
      # Collision check.
      if (i == ITEM_WHITE && color == PLAYER_WHITE) ||
         (i == ITEM_BLACK && color == PLAYER_BLACK)
         # Update score.
         score += 10

         chain_item_count = (chain_item_count % 3 > 0 ? last_item_color == i ? chain_item_count == 2 ? (chain_length += 1; max_chain_length = [max_chain_length, chain_length].max; score += 2 ** [chain_length - 1, 8].min * 100; 3) : chain_item_count + 1 : (last_item_color = i; chain_length = 0; 1) : (last_item_color = i; 1))

         growth_target += 2

         # Mark new player position.  This also removes the item from
         # current cell.
         grid[py][px] = PLAYER_HEAD

         # Add new item.  Do this in three passes:
         # - First pass avoids placing items near the player head or
         #   existing items.
         # - Second pass avoids placing items near the player head.
         # - Third pass takes whatever spot is available.
         item_has_not_been_placed_yet = true
         3.times{|pass|
            positions.size.times{
               position_index = -~position_index % positions.size
               x, y = positions[position_index]

               # Conditions for accepting new position:
               # [0] Item has not been placed yet.
               # [1] Grid cell is space.
               # [2] New position is not near player (pass 0 and pass 1).
               # [3] New position is not near existing items (pass 0).
               if [item_has_not_been_placed_yet,
                   grid[y][x] == SPACE,
                   far_away_position.call(x, y),
                   eligible_for_placement.call(x, y)].take(4 - pass).all?
                  # Enter endgame if position is assigned in pass 1 or 2,
                  # and update hint display.
                  #
                  # If we are already in endgame, these steps would be
                  # redundant, but it's OK since item color would already
                  # be fixed.
                  endgame ||= pass > 0 &&
                              (grid[height - 1][width - 1] = new_item + 7)

                  # Place item.
                  grid[y][x] = new_item
                  item_has_not_been_placed_yet = false

                  # Increase generated item count if we have not entered
                  # endgame yet.  This means item colors will alternate
                  # every 3 items before endgame, and remain fixed during
                  # endgame.
                  generated_item_count += endgame ? 0 : 1
               end
            }
         }

         # Redraw grid after applying movement.
         render.call

      else
         # Mark mark tombstone.
         grid[py][px] = PLAYER_TOMBSTONE
         render.call

         # Game over.
         print "\e[#{height / 2 + 2}A\r\e[#{width - 8}C\e[0m    GAME OVER    ",
               "\n\n\r\e[#{width - 8}C (press any key) ",
               "\n\r" * (height / 2 - 1)
         running = false
      end
   else
      # Mark new player position.
      grid[py][px] = PLAYER_HEAD
      dirty_pixels += [[px, py]]

      # Grow player.
      if history.size > growth_target
         erase_x, erase_y = history.shift
         grid[erase_y][erase_x] = SPACE
         dirty_pixels += [[erase_x, erase_y]]

         # Stop flashing chain status once player has stopped growing.
         if chain_item_count == 3
            chain_item_count = 0

            # Need to do a full redraw to clear the status line.
            render.call

            # Don't need to draw the dirty pixels since we did a full redraw.
            next
         end
      end

      # Redraw only the dirty pixels.
      image = "\e[#{height}A"
      dirty_pixels.each{|x, y|
         image += "\e[#{y}B\r\e[#{x * 2}C" +
                  SPRITES[grid[y][x] * 2 + color] +
                  "\e[#{y}A"
      }
      image += "\e[#{height}B"
      print image
   end
end

# Wait for input thread to consume the extra keystroke after the game
# over message.
input_thread.join

# Draw extra frame to erase the game over message.
render.call

# Ikaruga gives out a grade at the end of each level purely based on
# score.  We can also do a score-based thing for assigning grades, but:
#
#  - Due to exponential bonus from chains, getting high scores will
#    require maximizing number of consecutive chains.
#
#  - Snakes is hard enough as it is, maximizing for consecutive chains
#    means most players will not survive very long.
#
# In other words, even though we would like to reward both grid
# coverage and high score, those two are somewhat mutually exclusive.
#
# Instead of choosing one, high grades are given if players have a
# high completion ratio *or* a high score.
#
# Players who did not make any chains are always assigned "dot eater"
# grade.  Due to how item colors are fixed in endgame phase, players
# will inevitably form a few chains if they covered enough area, so
# it's impossible to reach 100% while maintaining dot eater grade.
max_area = (height - 2) * (width - 2)
grade = "Dot eater"
if max_chain_length > 0
   max_items = max_area / 2
   4.times{|i|
      if history.size > max_area * (i * 0.3 - 0.1) ||
         score > max_items * 10 + (max_items / 3) * 100 * 2 ** (i * 3 - 2)
         grade = "CBAS"[i]
      end
   }
end

# Restore cursor and output final game stats.
print "\e[0m\e[?25h\n",
      "Area: \e[1m#{history.size * 100 / max_area}%\e[0m\n",
      "Score: \e[1m#{score}\e[0m\n",
      "Max: \e[1m#{max_chain_length} chain\e[0m\n",
      "Grade: \e[1m#{grade}\e[0m\n"

# Restore echo.
STDIN.echo = true