aMAZEing

Kruskal's algorithm mindmap
logo

Inspiration and Background

Fueled by our passion for the intricate designs of mazes, we embraced the challenge of maze generation. We seized this chance to delve into maze generation, leveraging the classic Kruskal's algorithm. This algorithm, typically used for creating a minimum spanning tree (MST) for a graph, was adapted for our purposes. We crafted mazes as 2d grids with random edge selection (edges being the “wall” cells in the maze), resulting in a complex labyrinth of short cul-de-sacs, while the path maintaining the properties of a tree due to the nature of Kruskal’s algorithm (i.e. no cycles). This unique take on maze creation positions our approach just below the sophistication of Eller’s algorithm in terms of complexity.

What it does

We created an algorithm that works by randomly joining disjoint cells (separated by “walls”) to form a tree, which eventually results in a maze. The maze, visualized by JavaFX, presents a playable game in a dungeon setting with fun features! The user needs to find the chest.

How does it work?

We initiated with JavaFX to construct the grid, creating a matrix of ImageViews that alternate between wall and path tiles. Using Kruskal's algorithm, we transformed the grid, visualized as a graph, into a tree, which is the maze. We then enriched the visual appeal by introducing characters and enabling their movement. Finally, we integrated screen scrolling to emulate the effect of navigating a maze from a limited perspective.

Challenges we ran into

Our first technical hurdle was the initialization of path and edge tiles within the maze's data structure. The core objective was to achieve an optimal data structure that could support the necessary randomization, particularly since our generation algorithm hinged on randomized cell selection. After extensive technical discussions, we settled on using HashSets for each path tile. Hashsets provided us with an efficient means to maintain and quickly check the adjacency of path tiles without duplication when breaking walls (edge tiles) to create the path.

For the edge tiles, we first engineered a custom 'pair' class. This class was designed to hold and manage the two-dimensional positions of edge tiles for later selection. To realize the essential randomization aspect of Kruskal's algorithm, we then placed these pairs into an array. The use of an array was strategic, allowing us to leverage the Collections framework to shuffle the edge tiles, thereby injecting the desired stochastic element into the maze layout.

When it came to the identification and selection of edge tiles, we faced the additional complexity of doing so without resorting to intricate weight parameters traditionally used in Kruskal's algorithm. We used a more innovative approach and implemented an algorithm that could iterate through the grid and classify tiles based on their spatial relationships.

Accomplishments that we're proud of

We've adeptly applied Kruskal's algorithm, drawing inspiration from the patterns of Minimum Spanning Trees (MST), to innovate our maze generation process for enhanced efficiency. This advanced approach affords us expansive control in creating mazes with numerous intersections and cul-de-sacs, markedly increasing the complexity and challenge level. Additionally, we've developed a user interface via JavaFX (incidentally, it was our first time using it). It allowed us to craft an immersive dungeon-themed game environment enriched with complex features including scrolling.

What we learned

Maze Generation: We've gained a comprehensive understanding of various algorithms for maze generation, appreciating the abstract nature and underlying logic of each. These include Kruskal's algorithm, Prim’s Algorithm, and Recursive Backtracking—concepts familiar from data structure courses, which we've now practically applied in our own innovative way with added features to create an engaging game.

JavaFX: This project marked our first try using JavaFX effects, which significantly enhanced our front-end development skills. We learned the importance of big-picture thinking in UI design, considering the flexibility needed to create intuitive visual cues for gamers. For example, this led us to design and draw a character with four distinct sides, adding to the visual dynamics and improving the overall gameplay experience beyond mere functional movement. We also had to go through rounds of trial and error to find the perfect size of the “player view” to be shown (in conjunction with the screen scrolling) such that the view was intuitive enough without giving away the path to the goal.

What's next for aMAZEing

Our vision for aMAZEing is expansive, with plans to introduce a spectrum of difficulty settings and innovative features like teleportation portals that add unpredictability and excitement. For instance, one future prospect is to have those portals connecting a multi-leveled maze, where the player has to map out the destinations of each portal to solve the maze (sort of a maze inception problem). We aim to delve deeper into user interface design, tailoring experiences that strike the perfect balance between fun and mental stimulation.

Additionally, we're excited about the prospects of integrating 2D maze designs onto 3D objects, combining art with mathematics for a uniquely engaging gameplay experience. Our journey ahead is filled with potential, and we are eager to explore these new dimensions!