#!/usr/bin/ruby

require "io/console"

# Tile indices.
SPACE = 0
WALL = 1
ITEM_BLACK = 2
ITEM_WHITE = 3
PLAYER_HEAD = 4
PLAYER_TAIL1 = 5
PLAYER_TAIL2 = 6
PLAYER_TAIL3 = 7
PLAYER_TOMBSTONE = 8
PLAYER_BLACK = 0
PLAYER_WHITE = 2

# Direction constants.
DIRECTION_UP = 0
DIRECTION_DOWN = 1
DIRECTION_RIGHT = 2
DIRECTION_LEFT = 3

# Color palette.
COLOR_SPACE = "\e[30;44m"              # Black on dark blue.
COLOR_WALL = "\e[34;104m"              # Dark blue on bright blue.
COLOR_BLACK0 = "\e[90;40m"             # Dark gray on black.
COLOR_BLACK1 = "\e[96;40m"             # Bright cyan on black.
COLOR_WHITE0 = "\e[30;107m"            # Black on white.
COLOR_WHITE1 = "\e[96;107m"            # Bright cyan on white.
COLOR_BLACK_TAIL = "\e[30;100m"        # Black on dark gray.
COLOR_WHITE_TAIL = "\e[97;47m"         # White on light gray.
COLOR_BLACK_TAIL1 = "\e[36;100m"       # Cyan on dark gray.
COLOR_WHITE_TAIL1 = "\e[96;47m"        # Bright cyan on light gray.
COLOR_BLACK_TOMBSTONE = "\e[91;40m"    # Bright red on black.
COLOR_WHITE_TOMBSTONE = "\e[97;41m"    # Bright white on dark red.
COLOR_SHORT_CHAIN = "\e[97;46m"        # Bright white on dark cyan.
COLOR_MAX_CHAIN = "\e[30;106m"         # Black on bright cyan.

# Tile images:
# - First index is grid cell value (matches tile indices constants).
# - Second index is player color (0 or 2) plus current frame (0 or 1).
TILES = [
   [COLOR_SPACE + "  "] * 4,
   [COLOR_WALL + "##"] * 4,
   # Make the items blink when they match player's current color.
   [COLOR_BLACK0 + "[]", COLOR_BLACK1 + "[]"] + [COLOR_BLACK0 + "[]"] * 2,
   [COLOR_WHITE0 + "()"] * 2 + [COLOR_WHITE0 + "()", COLOR_WHITE1 + "()"],
   # Draw player with current color.  Do not blink.
   [COLOR_BLACK1 + "@@"] * 2 + [COLOR_WHITE1 + "OO"] * 2,
   # Draw player tail with a slightly different color from the items,
   # otherwise it's difficult to tell the player apart from the items.
   #
   # We used to also use different tiles for different turn directions,
   # but that honestly did not improve the visuals by much.  It might
   # have been useful if we use unicode line drawing characters, but for
   # compatibility reasons we don't use those.
   [COLOR_BLACK_TAIL1 + "%%"] * 2 + [COLOR_WHITE_TAIL1 + "##"] * 2,
   [COLOR_BLACK_TAIL + "%%"] * 2 + [COLOR_WHITE_TAIL + "##"] * 2,
   [COLOR_BLACK_TAIL + "XX"] * 2 + [COLOR_WHITE_TAIL + "++"] * 2,
   [COLOR_BLACK_TOMBSTONE + "@@"] * 2 + [COLOR_WHITE_TOMBSTONE + "OO"] * 2
]

# Item chain images:
# - First index is chain length (0..3)
# - Second index is last item color (0 or 2) plus current frame (0 or 1).
CHAIN_TILES = [
   [],
   [COLOR_BLACK0 + "[]\e[0m    "] * 2 +
   [COLOR_WHITE0 + "()\e[0m    "] * 2,
   [COLOR_BLACK0 + "[][]\e[0m  "] * 2 +
   [COLOR_WHITE0 + "()()\e[0m  "] * 2,
   [COLOR_BLACK0 + "[][][]\e[0m", COLOR_BLACK1 + "[][][]\e[0m",
    COLOR_WHITE0 + "()()()\e[0m", COLOR_WHITE1 + "()()()\e[0m"],
]


# We would like a bit of delay between each frame so that we don't peg
# the CPU, but on windows this causes a significant drop in frame
# rate.  Thus we do a small measurement here, and for systems that
# don't have the sleep resolution needed, we just render in a busy
# loop without sleeps.
frame_delay = 0.01
start_time = Time::now
8.times{ sleep frame_delay }
frame_delay = Time::now - start_time > 0.1 ? 0 : frame_delay

# 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

# Clear window.
print "\n" * height

# 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 = nil         # Color of last item eaten (2 or 3).
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.

# Movement speed in number of units moved per second.  Use command line
# argument if that's specified, otherwise default to 5 cells per second.
speed = ARGV[0].to_f
movement_delay = speed > 0 ? 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.
#
# Basically we generate items with the same color in groups of 3s.
#
# First item is ITEM_WHITE, since player start off in white.
#
# During endgame phase, items are always generated with the same color,
# which is whatever color was that was the majority when grid was 80%
# covered.
next_item_tile = -> { 3 - generated_item_count % 6 / 3 }

# Initialize game field.
grid = []
height.times{grid += [[SPACE] * width]}
width.times{|i| grid[0][i] = grid[height - 1][i] = WALL}
height.times{|i| grid[i][0] = grid[i][width - 1] = 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

# Try assigning initial set of items.
positions.each{|x, y|
   # Avoid the rows near player's starting position.
   next if (y - py).abs < 2

   # Unconditionally skip some of the cells, otherwise the initial
   # grid is too dense.
   next if rand > 0.1

   # Check neighbor cells of the candidate position.  New tiles can be
   # placed if either all neighbors are empty, or if they are adjacent
   # to items with the same color.  The second constraint is to avoid
   # placing items of different colors next to each other, since that
   # will make it difficult to form chains.
   selected_tile = next_item_tile.call
   eligible = true
   same_neighbor_count = 0
   [*-1..1].each{|dx|
      [*-1..1].each{|dy|
         if grid[y + dy][x + dx] == selected_tile
            same_neighbor_count += 1
         else
            eligible &= grid[y + dy][x + dx] == SPACE
         end
      }
   }

   # We allow new items to be placed next to items of the same color,
   # but only if there aren't already more than a few such items
   # nearby.  This is to avoid creating excessively large clusters of
   # the same color.
   eligible &= same_neighbor_count <= 1
   next if not eligible

   grid[y][x] = selected_tile
   generated_item_count += 1
}

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

# Render function.  This is a lambda so that we can just access
# everything as globals.
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.
   if chain_item_count > 0
      fail unless last_item_color == ITEM_BLACK || last_item_color == ITEM_WHITE
      fail unless chain_item_count <= 3
      current_chain =
         CHAIN_TILES[chain_item_count][(last_item_color - 2) * 2 + frame_parity]
   else
      current_chain = "\e[0m" + "  " * 3
   end

   score_status = " " + score.to_s

   if chain_length > 0
      chain_status = "  %-#{width * 2 - 8 - score_status.size}s" %
                     "#{chain_length} chain"
      if chain_length > 9
         prefix = COLOR_MAX_CHAIN
         chain_status.upcase!
      else
         prefix = COLOR_SHORT_CHAIN
      end
      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

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

   # Build grid image.
   #
   # Within the loop, we update two parity bits such that the items
   # blink in a checkerboard fashion.  Alternatively, we can do away
   # with the parity bits and just use frame_parity for all cells, which
   # means all items blink synchronously, but it doesn't look as nice.
   parity0 = frame_parity
   image +=
      grid.map{|row|
         parity1 = parity0 ^= 1
         row.map{|cell| TILES[cell][color + (parity1 ^= 1)]} * ""
      } * "\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 true
      # 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
      if not running
         break
      end

      # Change color if we are going in the exact opposite direction
      # of where we are currently going.
      new_direction = nil
      case key
      when "A", "w"; new_direction = DIRECTION_UP
      when "B", "s"; new_direction = DIRECTION_DOWN
      when "C", "d"; new_direction = DIRECTION_RIGHT
      when "D", "a"; new_direction = DIRECTION_LEFT
      when "q"; running = false; break
      when "\e", "[";  # Silently ignore partial escape sequences.
      else; new_direction = -1  # Treat most keys as color change.
      end

      # 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 no 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[input_write_index] = new_direction
         input_write_index = (input_write_index + 1) % input_buffer.size
      end
   end
}

# Disable echo and hide cursor.
STDIN.echo = false
print "\e[?25l"

# Game loop.
last_movement = Time::now
while running
   # Draw image.
   #
   # Given that we are basically alternating between two frames most
   # of the time (until next player action is applied), we could
   # conceivably cache the two frames instead of having to reassemble
   # each frame from scratch every time.  Doing that costs merely a
   # few extra lines of code (and thus few extra lines of complexity),
   # but we found zero advantage in doing so -- the CPU costs weren't
   # lower and the flashing dots weren't glittering harder.
   render.call
   sleep frame_delay
   frame_parity ^= 1

   # Apply buffered action.
   if input_read_index != input_write_index
      next_action = input_buffer[input_read_index]
      input_read_index = (input_read_index + 1) % input_buffer.size
      next_cell = PLAYER_TAIL1
      case next_action
      when DIRECTION_UP; next_cell = grid[py - 1][px]
      when DIRECTION_DOWN; next_cell = grid[py + 1][px]
      when DIRECTION_RIGHT; next_cell = grid[py][px + 1]
      when DIRECTION_LEFT; next_cell = grid[py][px - 1]
      when -1; color ^= 2
      end

      # Do not allow player to turn back onto themselves.
      if next_cell != PLAYER_TAIL1 &&
         next_cell != PLAYER_TAIL2 &&
         next_cell != PLAYER_TAIL3 &&
         next_cell != WALL &&
         direction = next_action

         # Cause direction changes to take effect right away.
         last_movement = Time.at(0)
      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
   next if current_time - last_movement < movement_delay

   last_movement = current_time

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

   # Update player position.
   case direction
   when DIRECTION_UP; py -= 1
   when DIRECTION_DOWN; py += 1
   when DIRECTION_RIGHT; px += 1
   when DIRECTION_LEFT; px -= 1
   end

   if grid[py][px] != SPACE
      # Collision check.
      if (grid[py][px] == ITEM_WHITE && color == PLAYER_WHITE) ||
         (grid[py][px] == ITEM_BLACK && color == PLAYER_BLACK)
         # Update score.
         score += 10
         if chain_item_count == 0 || chain_item_count == 3
            # Starting chain.
            last_item_color = grid[py][px]
            chain_item_count = 1
         else
            if last_item_color == grid[py][px]
               # Continuing current chain.
               chain_item_count += 1
               if chain_item_count == 3
                  chain_length += 1
                  max_chain_length = [max_chain_length, chain_length].max
                  score += 2 ** [chain_length - 1, 8].min * 100
               end
            else
               # Broke current chain.
               last_item_color = grid[py][px]
               chain_item_count = 1
               chain_length = 0
            end
         end
         growth_target += 2

         # Add new item.  Do this in two passes: first pass avoids
         # placing items near the player head or existing items, and
         # second pass just take whatever spot that is available.
         new_item = next_item_tile.call
         new_item_position = nil
         2.times{|pass|
            if not new_item_position
               positions.size.times{
                  position_index = (position_index + 1) % positions.size
                  x, y = positions[position_index]
                  next if grid[y][x] != SPACE

                  if pass == 0
                     # Avoid generating items near player head.
                     next if (x - px).abs < 4 && (y - py).abs < 4

                     # Avoid creating clusters of non-matching color.
                     eligible = true
                     [*-1..1].each{|dx|
                        [*-1..1].each{|dy|
                           eligible &= grid[y + dy][x + dx] == SPACE ||
                                       grid[y + dy][x + dx] == new_item
                        }
                     }
                     next if not eligible
                  else
                     # If we couldn't generate items that are sufficiently
                     # distant from player, it's likely that we are in the
                     # endgame phase.  In this phase, always generate
                     # items that are the majority color, break ties
                     # by matching player color.
                     vote = 0
                     grid.each{|row|
                        row.each{|cell|
                           vote += cell == ITEM_BLACK ? -1 :
                                   cell == ITEM_WHITE ? 1 : 0
                        }
                     }
                     new_item = vote < 0 ? ITEM_BLACK :
                                vote > 0 ? ITEM_WHITE :
                                color == PLAYER_BLACK ? ITEM_BLACK
                                                      : ITEM_WHITE
                  end
                  new_item_position = [x, y]
                  break
               }
            end
         }
         if new_item_position
            grid[new_item_position[1]][new_item_position[0]] = new_item
            generated_item_count += 1
         end

         # Mark new player position.
         grid[py][px] = PLAYER_HEAD

      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
         frame_parity = 0
      end
   else
      # Mark new player position.
      grid[py][px] = PLAYER_HEAD

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

         # Stop flashing chain status once player has stopped growing.
         if chain_item_count == 3
            chain_item_count = 0
         end
      end
   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

# Restore echo and show cursor.
STDIN.echo = true
print "\e[0m\e[?25h\n"

# 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.
max_area = (height - 2) * (width - 2)
max_items = max_area / 2
grade = "C"
if history.size > max_area * 0.2 ||
   score > max_items * 10 + (max_items / 3) * 200
   grade = "B"
   if history.size > max_area * 0.5 ||
      score > max_items * 10 + (max_items / 3) * 1600
      grade = "A"
      if history.size > max_area * 0.8 ||
         score > max_items * 10 + (max_items / 3) * 12800
         grade = "S"
      end
   end
end

# Players who did not make any chains are always assigned "dot eater" grade.
if max_chain_length == 0
   grade = "Dot eater"
end

# Output final game stats.
print "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"