1 Concept

In this MP, you will create a web service that works together with other students’ web services to create a collaborative distributed infinite maze.

The maze is organized around tiles or segments, 7×7 mini-mazes. Each tile has (up to) four exits, one on the center of each of its four sides. The infinite maze is generated by requesting new tiles as soon as a given tile is exited. We have an early proof of concept which doesn’t use servers, instead re-using the same tile every time, which we hope will help the idea make more sense.

Some of the points in this MP are handled by automated tests. The remaining points are handled by your code correctly interacting with others’ code in an in-class demo.

2 Technical Overview

There are two web servers
1. A middleware we fully write for you (provided in mazeview.py)
2. A maze generator you write (we provide code to connect it to the middleware)
Each of your maze generators will
1. Define two API endpoints: one generates the same maze every time, the other generates a random maze tile
2. Support registering itself with various middlewares (this is provided for you)

3 Initial Files

Initial files are available in mp9.zip, including two files you’ll edit:

mazegen.py is an aiohttp web service.
mazelib.py is an optional second file where we recommend you put your maze generation code.

The Makefile has a variety of targets:

make run starts mazegen.py on port 5340
make view starts both mazegen.py on port 5340 and mazeview.py on port 34009
make test uses pytest to check your code’s correctness
make background starts mazegen.py on port 5340 as a daemon process; make stop kills that daemon.

4 Specification

In mazegen.py, implement a web service with the following properties:

GET /static returns the same 7×7 maze tile with 4 exists each time it is invoked. We recommend hand-crafting a maze that you think looks cool.

Mazes tiles are returned as JSON arrays of seven seven-character strings; each character is a hexadecimal digit indicating which walls of that cell are present.

A hexadecimal digit has four bits.
- bit 1 is 1 if there’s a wall to the left of the cell;
- bit 2 is 1 if there’s a wall to the bottom of the cell;
- bit 4 is 1 if there’s a wall to the right of the cell;
- bit 8 is 1 if there’s a wall to the top of the cell.
An illustration of the wall labeling

0 1 2 3 4 5 6 7 8 9 A B C D E F

All 16 cell kinds visualized

An empty cell with four exists is encoded as
```
[ "988088c"
, "1000004"
, "1000004"
, "0000000"
, "1000004"
, "1000004"
, "3220226"
]
```
The walls must be two-sided; for example, if one cell has a wall on it’s right then the cell to the right of it must have a wall on its left.
GET /dynamic/0, GET /dynamic/1, …, GET /dynamic/F return random 7×7 mazes with the specified set of exits.

These are in the same JSON format as static maze tiles.

Its exists are indicated with the same hexadecimal code as cells: 0 has all four exits open, 1 has the left exit closed but the other three open, and so on.

The maze must be solvable; that is, there must be a path from each open exit to each other open exit.

While 16 dynamic maze types?

By using the same hex codes for what directions one can go from a cell and what directions one can go from a maze, we can make recursive mazes: generate a maze, and then for each cell generate an entire sub-maze, repeating as many levels as we want.

For example, consider this type-0 maze:

A single 7×7 maze spelling out CS 340 with 2 cells per character

We can replace each of its 49 cells with another maze (for this example, the same maze) with the appropriate exits

A 7×7 grid of 7×7 mazes, each spelling out CS 340, with exits of the mazes matching the walls of a larger maze.

Assuming each of the mazes was distinct and maze-like, this recursive procedure lets us make mazes out of simple pieces that are arbitrarily large and complex.

Note that we don’t actually need the type-F maze with all four exists closed off, but we include it in the MP specification for completeness.

5 Tips

We have a separate page on maze generation.

6 Testing your code

If you run your mazegen.py and visit it in the browser, you will see a visualization of mazes and a field for registering your maze generator with a middleware.

If you run python3 -m pytest you’ll see our estimation of the correctness of your solution.

Automated tests will also be run when you submit your code on the secure upload site.

7 In-lecture deployment on April 24

On April 24 we will run all maze generators as part of an in-lecture check-off for the other half of your MP9 grade.

7.1 Pre-lecture testing

In a terminal, run make view Two ports will be displayed: 34009 and 5340
Open both ports in your browser.
- On your local machine that means http://localhost:5340/ and http://localhost:34009/.
  
  You’re welcome to test on your local machine if you’d like, but you should test on your VM at least once.
- On your VM, that means http://sp25-cs340-###.cs.illinois.edu:5340 and http://sp25-cs340-###.cs.illinois.edu:34009.
In the Middleware service URL field of the 5340 port page, enter the 34009 port URL.

You should see Connected displayed below the middleware URL entry field.
On the 34009 port page, use the arrow keys (or WASD if you prefer that form of directionality) to navigate the maze.

You should start in an empty tile; the next tile should be your /static tile; after that you should see a series of /dynamic/0 tiles.
(optional) With a friend, run all of your apps at once on the VM. Enter one of your 34009 URLs in all of your 5340 pages. All visit the same 34009 page; you should see a maze made of a random selection of all of your solutions.

7.2 In-lecture testing

On April 24, before class starts,
1. Start your VM
2. Make sure you have your latest code on your VM
3. In your VM’s terminal, from the mp9 directory, run make background
4. Log out of your VM (e.g. by shutting VS Code)
5. Ensure that your code’s webpage (http://sp25-cs340-###.cs.illinois.edu:5340) still works
On April 24, during class,
1. We will share a middleware URL for you to all enter into your pages
2. You will collectively explore that maze
3. We will share another middleware URL that uses your code in a different way
4. …
5. Throughout, we will log what each server does and use that to populate the in-class half of your MP9 grade.
  
  These logs must show that your code
  - Supplied both static and several dynamic maze tiles to the larger maze
  - Supplied correct mazes (two-sized walls, can be solved)
  And that you as a user
  - Explored the maze (more than a few tiles of travel)