Beaver's Day Out

Overview

Beaver's Day Out is a Sokoban (box pushing puzzle) type game, with endless randomly generated levels. The player controls the character Justin Beaver to push logs into whirlpools to complete the level.

Key Features

• Infinite Gameplay - Endless procedurally generated levels for unlimited puzzle-solving
• Smart Level Generation - Dynamic programming algorithm ensures all levels are solvable
• Pure Java Implementation - Built entirely with Java Swing without external game engines
• Efficient Memory Usage - Custom data structure using integer masks for optimized performance

Technologies Used

Java, Java Swing, PixilArt

Results

• Successfully generates infinite unique, solvable puzzle levels
• Implemented BFS algorithm preventing impossible level generation (0% unsolvable levels)
• Lightweight implementation using only built-in Java libraries
• Smooth gameplay with responsive controls and intuitive UI

Demo

Algorithm Design

Procedural Level Generation

Levels are generated using a reverse-placement algorithm: starting from a solved state and working backwards to create the puzzle. This guarantees every generated level has at least one valid solution.

BFS Solvability Verification

Each generated level is verified using a Breadth-First Search (BFS) algorithm that explores all possible game states. The state space is represented using integer bitmasks for efficient memory usage — each board configuration (player position + box positions) is encoded as a single integer, enabling O(1) state lookups in a HashSet.

Complexity Analysis

Aspect	Complexity
Time (BFS verification)	O(N × M × 2^B) where N×M is grid size, B is number of boxes
Space (state storage)	O(2^B) unique states stored as integer bitmasks
Generation	O(K) per level where K is the number of reverse moves applied

The bitmask representation reduces memory usage by ~90% compared to storing full board arrays, enabling verification of larger puzzles in real-time.

How to Run

Prerequisites

• Java 8 or higher installed on your system

Running the Game

1. Clone this repository
2. Navigate to the project directory
3. Compile: javac *.java
4. Run: java GameModel

Or open in your preferred Java IDE (IntelliJ, Eclipse) and run GameModel.java