Multidimensional Virtual Arcade

Space Invaders is a popular retro game made in 1978 by Taito. It featured a simple game design with a small set of player inputs.

Implement the class SpaceInvaders, which holds the core gameplay logic of Space Invaders on a 2D grid without rendering, randomness, or I/O. Your game will be judged by our custom judge in a fully deterministic and tick-based manner.

You do not need to write any input/output parsing.

---

Board Encoding

The game lives on an H x W grid (row-major):

• Rows: r = 0 (top) to r = H-1 (bottom)
• Columns: c = 0 (left) to c = W-1 (right)

Cell values:

• 0 — empty
• 1 — player
• 2 — alien
• 3 — player bullet
• 4 — alien bullet

Invariants

• There is exactly one player (1) unless the game has ended.
• There may be many aliens and bullets.
• Multiple entities may attempt to move into the same cell in the same tick; resolution rules define the outcome.

---

Constructor

SpaceInvaders(board, lives)

• board is an initial H x W grid with values in {0, 1, 2} only.
• lives is a positive integer indicating how many lives the player starts with.

---

Player Movement

moveLeft()
moveRight()
moveUp()
moveDown()

Moves the player by one cell in the requested direction if within bounds.

If the destination cell contains:

• 0:
  • Player moves normally.
• 2 (alien):
  • Player loses 1 life.
  • Alien is removed.
  • Player moves into the cell.
• 3 or 4 (bullet):
  • Treat as self-inflicted hit.
  • Player loses 1 life.
  • Bullet is removed.
  • Player moves into the cell.

If after losing a life lives == 0, the game becomes LOSE immediately.

---

Player Shooting

shoot()

• Spawns a player bullet (3) in the cell directly above the player: (pr - 1, pc).

If the target cell is:

• Out of bounds:
  • Nothing happens.
• 0:
  • Place bullet.
• 2 (alien):
  • Alien is destroyed immediately.
  • Cell becomes 0.
  • Bullet does not remain.
• 4 (alien bullet):
  • Both bullets are destroyed.
  • Cell becomes 0.
• 3 (player bullet):
  • Do nothing (no bullet stacking).

---

Alien Shooting

alienShoot(col)

• col must satisfy 0 ≤ col < W.
• Find the lowest alien (2) in column col
  (the alien with the maximum row index).
• If no alien exists in that column: nothing happens.

The alien attempts to shoot directly downward from (r + 1, col).

If the target cell is:

• Out of bounds:
  • Nothing happens.
• 0:
  • Place an alien bullet (4).
• 1 (player):
  • Player loses 1 life.
  • Bullet does not remain.
  • If lives == 0, the game becomes LOSE immediately.
• 3 (player bullet):
  • Both bullets are destroyed.
  • Cell becomes 0.
• 4 (alien bullet):
  • Do nothing (no bullet stacking).
• 2 (alien):
  • Should never happen; do nothing.

---

Game State Queries

getBoard()

• Returns the current board state.

getLives()

• Returns the current number of lives.

isGameOver()

• Returns true if the game is no longer running
  (i.e., result is WIN or LOSE).

getResult()

• Returns one of:
  • RUNNING: 0
  • WIN: 1
  • LOSE: 2

---

tick(): Game Progression

tick()

Advances the game by one discrete time-step.
All steps below occur in this exact order.

---

1. Move Bullets

All bullets move simultaneously:

• Player bullets (3): (r, c) → (r - 1, c)
• Alien bullets (4): (r, c) → (r + 1, c)

Bullets that move out of bounds are removed.

---

2. Resolve Collisions (After Bullet Movement)

If a cell contains:

• 3 and 2:
  • Alien dies.
  • Bullet dies.
  • Cell becomes 0.
• 4 and 1:
  • Player loses 1 life.
  • Bullet dies.
  • Cell becomes 1.
• 3 and 1:
  • Player loses 1 life.
  • Bullet dies.
  • Cell becomes 1.
• 3 and 4:
  • Both bullets die.
  • Cell becomes 0.

If multiple entities land in the same cell during this tick, resolve with priority:

1. Alien bullet (4) hits player
2. Player bullet (3) hits player
3. Player bullet (3) hits alien
4. Bullet–bullet annihilation

If lives == 0 during this step, the game becomes LOSE immediately.

---

3. Move Aliens

Aliens move as a formation, sharing a global horizontal direction dir:

• Initial dir = +1 (right)

Rules:

• Check if moving all aliens by (0, dir) would cause any alien to leave the board.
• If yes:
  • Do not move horizontally.
  • Move all aliens down by 1 row.
  • Flip direction: dir = -dir.
• If no:
  • Move all aliens horizontally by (0, dir).

---

4. Lose Conditions After Alien Move

After aliens move:

• If any alien is on the bottom row (r == H - 1):
  → LOSE
• If an alien moves into the player’s cell:
  • Player loses 1 life
  • Alien is removed
  • If lives == 0:
    → LOSE
• If an alien moves into a cell containing a bullet (3), the alien is destroyed and the bullet is removed.

---

5. Win Condition

• If no aliens remain on the board:
  → WIN

If both WIN and LOSE would occur in the same tick, the result is LOSE.

---

Notes

• All movement within a tick is simultaneous, not sequential.
• Do not resolve collisions while iterating entities individually.
• The game is a deterministic state machine, not a graphical game.