There are many different algorithms to generate a random and solvable maze. I chose Randomized depth-first search algorithm, because it's one of the easiest to implement. Moreover it uses recursion and stacks, concepts that I recentely studied into depth at University.

Randomized depth-first search operates as follow:

• The maze is represented as grid of cells (like a large chess board), each cell starts with four walls.
• A random cell is choosen and a random neighbouring selected, this has not yet been visited. The wall between the two cells is removed and the neighbour is marked as visited. The neighbour is finally added to the stack in order to make backtracking possible.
• This process continues and when a cell has no unvisited neighbours is considered a dead-end. At this point the algorithm backtracks through the path to the first cell with an unvisited neighbour.
• This algorithm keeps running until each cell of the grid has been visited. The result is a maze which is solvable and characterized by long corridors (because the recursion goes on until every neighbour has been visited).

The algorithm can be visualized as follows:

The game is a React web app built on the top of a RESTfull API developed with ExpressJS, using Firebase as Database.

In order to start playing, a user has to create a new maze by going to: /mazes/new. In this page when the Generate new Maze button is clicked a new maze is generated on the server side. The newly generated maze is stored on Firebase and sent to the client as a JSON response. Then the user is redirected to /mazes/:id and the maze is painted on a HTML canvas. Moreover, a circle representing the current player is painted over the first cell of the maze.

Any other player can be invited by sharing the link of the maze page.

Once the player has been displayed, the user is able to move it by clicking on the arrow buttons underneath the canvas. At every click the position is updated and a position-update-request is emitted on the websocket channel initialized with the server when the maze has been received. In this way current player's position is updated in realtime for every other player.

Even if the player refresh the page it will still be painted in his last position becuase, the coordinates have been stored both on localStorage and on Firebase to ensure maximum continuity of the game. Moreover, as soon as a client disconnect from the websocket server, it is removed from the maze of the other players.

• When I started I wanted to build the whole game just as a client-side app. I planned to use Firebase firestore to handle realtime updates. Unfortunately this has not been possible because of Firebase limitations related to the maximum document updates per second Learn more here . These limitations complictes the use of Firebase to handle high frequency updates necessary to ensure realtime player interactions.
• Once, I realized I could not rely on Firebase document realtime updates feature, I tried to use Ably to implement realtime communication between clients (emulating what websockets do). I also needed database to make sure each player could access the maze to paint. Unfortunately the client-side integration: Ably-Firebase turned out to be too clunky and difficult to handle.
• After two weeks of experiments and debugging I decided that the only way to build the game in the most understandable and mantainable way was to handle realtime communication using websockets. Unfortunately by doing so I needed a custom backend. I built it using ExpressJS and Firebase as Database. By doing so generating the maze, displaying on the client side and handle realtime updates turned out to be very easy.

• This project let me learn more about HTML Canvas, in particulare how to visualize complex 2d shapes modeled by algorithms like the ones generating mazes.
• I also learned how to build a project on the top of an existing algorithm. This requires learning how the algorithm works under the hood and trying to implement it by yourself following pseudo code. After that it's neccessary to think about creative ways to leverage that algorithm in order to do something very concrete, in this cas powering a game.
• Extreme Mazes consolidated in myself the mindset that every software developer should embrace. This is about starting a project from an interesting idea (which can be realistically built): planning, building and delivering it. Unfortunately, many times things don't smoothly and plans need to be changed because of unexpected challenges. Like the ones I previously discussed in this page, but the most crucial aspect of this mindset is not to give up when facing difficulties. Instead, it's neccessary to understand state and goals of the project in order to find the best way to cope with challenges to complete the project.