BYOW: Build Your Own World

A 2D procedural world generation and exploration game demonstrating advanced algorithmic techniques in computational geometry and procedural generation.

Algorithmic Highlights

Efficient Room Generation with Sweep Line Algorithm

The world generation employs a discontinuous sweep line algorithm that eliminates the need for pairwise collision detection between rooms. Instead of O(n²) collision calculations, the algorithm:

• Pre-generates random x-coordinates for room placement
• Maintains a sorted set of active rooms at each sweep line position
• Uses prefix sums on delta arrays to compute valid intervals for room placement
• Achieves O(n log n) complexity by avoiding explicit collision detection

This approach ensures guaranteed minimum spacing between rooms while maintaining optimal performance for large world generation.

Advanced Line-of-Sight with Angular Sweep Line

The lighting system implements an angular sweep line algorithm for visibility calculations:

• Processes points in angular order around each light source using atan2 prioritization
• Eliminates redundant processing using a priority queue to identify and consider only the closest blocker of light
• Achieves O(n log n) complexity where n is the number of points within vision distance

The algorithm processes each point exactly once during the sweep, maintaining a TreeSet of blocking objects to determine visibility without recalculating paths.

Multi-Source BFS for Path Generation

Room connectivity is established through a multi-source breadth-first search that:

• Runs concurrent BFS from each room until collision detection
• Builds adjacency matrices during exploration rather than post-processing
• Uses Union-Find with Kruskal's algorithm for minimal spanning tree generation
• Avoids redundant path calculations by tracking room fringes during BFS

Technical Architecture

The project utilizes a layered architecture to render the underlying tiled world.

• WorldLayer: Handles procedural generation and spatial data structures
• LightLayer: Implements the sweep line visibility algorithm
• PlayerLayer: Manages player state and movement
• HUDLayer: Provides user interface and game information

The world is ultimately generated by applying each Layer to the screen. Some layers apply new tiles to the screen (WorldLayer, HUDLayer, PlayerLayer) but may simply modify tiles in place (LightLayer). Key presses are handled by ScreenLogic classes that forward events to individual layers, which update themselves and indicate whether they need updating.

Some layers are cached with old renders to avoid re-updating their data and backing arrays. WorldLayer only forces a rerender when lighting changes, such as when Lights are turned on and off or the player Light moves.

Performance Characteristics

• Room Generation: O(n log n) where n is the number of rooms
• Line-of-Sight: O(n log n) where n is the number of visible points
• Path Generation: O(n log n) for BFS + O(n log n) for MST
• Memory Usage: O(n) for all major algorithms

This project showcases how computational geometry techniques can be applied to create maintaining optimal performance characteristics.