This is an archived copy of a previous semester's site.

Please see the current semester's site.

MP8
Distributed Maze
Due dates may be found on the schedule.

FAQ

Do I have to code the front-end?
No, we provide that in the starter code.
What .py files do I edit?

None of those we provide; they all work as-is.

Create new files for your two maze generators, then add them to generators.json.

What URL should I use for the middleware?

For testing, wherever you ran that flask app; probably http://localhost:34000

In the in-class checkoff we’ll give you a different URL (a port on the sp24-cs304-adm VM); you can either set up your code to make it easy to change or edit your code during the checkoff to use the new URL.

Do I need to host my code on my VM?

For the automated tests, no.

For the in-class checkoff, yes. And you’ll need to make sure the PUT to /addMG on the middleware uses your VM’s URL too. We recommend setting that up in advance of the in-class checkoff.

Can you give me code so I can focus on my maze, not on the hex string format?

After some discussion among the staff, and with some objecting votes, yes.

mazelib.py updated 2024-04-15 08:57 CDT

You don’t need to use it, but you may. If you do, include it in your github repo.

You can learn how it works by running python -m pydoc mazelib from the directory containing mazelib.py

Can I use someone else’s data structure in my code?

Yes.

If it’s in the Python standard library (for example, in collections) you can use it freely.

If it’s in the Python Package Index (for example, dset) you need to add it to your project’s requirements.txt. Note that we review the requirements.txt files and if you add something that does the entire job of maze-creation for you you will lose points.

last updated 2024-04-11 17:16 CDT

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 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

3 Initial Files

In your CS 340 directory, merge the initial starting files with the following commands:

git fetch release
git merge release/mp8 --allow-unrelated-histories -m "Merging initial files"

4 Part 1: Running the Provided Code

The middleware and frontend are completed and provided for you.

You will implement the backend microservices called Maze Generators or MGs that generate maze segments. Your MGs will be combined with other students’ MGs to create a global, course maze live in lecture on April 18.

5 Part 2: Technical Requirement for MGs

For MP8, you are required to create at least two MGs: at least one static MG and at least one dynamic MG. The MGs should be interesting and inspiring.

Mazes are related to several algorithms you’ve learned in other classes.

Every cell of a maze is reachable from every other cell of the maze if and only if the maze consists of a single connected component.

Any spanning tree of the cells in a maze will be a classic single-path many-dead-ends hard maze.

Each MG should be in its own folder; we recommend a new subfolder of mp8/MGs for each MG. Each MG must have a global Flask variable named app (as all our example flask apps have thus far).

The paths you pick should be entered into generators.json as importable paths. For example, if your static MG is in MGs/static/app.py and your dynamic MG is in MGs/dynamic/app.py your generators.json would look like

{
  "static":"MGs.static.app",
  "dynamic":"MGs.dynamic.app"
}

5.1 Generating a New Maze Tile: GET /generate

Each MG will respond to requests from the middleware via a response to the GET /generate route. This route returns a JSON that must contain geom that contains the geometry of the maze segment. The geometry is a array of strings, where each string is one row of the maze and each character is a single cell in the maze. For example:

Each character is a hex digit that encodes the walls of that cell.

The maze must have matching walls: that is, if one cell has a wall on its north side, the cell to the north of it must have a wall on its south side.

This format was selected because it makes the maze server and front-end efficient and easy to code, and that’s the part of this system that has to keep up with hundreds of clients connected at once. It’s not a very good format for maze generation. You will probably want to use a different format for maze generation and then export it to this format once the maze is fully generated.

5.2 Start and Connecting to the Maze Server: PUT /addMG

Your code should have special logic for when it is run as a program (as opposed to being imported). This can be implemented by adding a block

if __name__ == '__main__':
    ... # your conditional code here

In that block you should do (at least) two things:

  1. Tell the maze server that your MG exists.

    This is done via a PUT /addMG request sent to the maze server. This request must include a JSON with keys name, url, and author. For example:

    {
  "name": "generator1",
  "url": "http://127.0.0.1:34000/",
  "author": "Your NetID"
}

    • The name value is displayed in the API’s list of available servers.

    • The url value will be used the URL to communicate with your MG when sending a GET /generate request.

    • The author must be your NetID if you want to get credit for the MP! :)

    The maze server /addMG endpoint will respond with an HTTP/400 if the JSON is malformed.

  2. Run the flask app on a port of your choosing. We recommend using a different port for each MG so you can test them working together.

    app.run(host="0.0.0.0", port=34000)

    This will mean you can run your MG via python3 app.py instead of the usual python3 -m flask run --host=0.0.0.0 --port=34000.

If the MG server has already been added, sending a second identical request to /addMG will have no effect so it’s okay to restart your maze and re-send the /addMG.

6 Part 3: Local Tests

6.1 Message format

The provided test_basics.py verifies that your MGs follow the basic protocol expected. You can run them with python3 -m pytest. These are also tested by the github autograding action and contribute half of your grade for this MP.

6.2 MG/server connection

If you run the maze server and your two MGs, each on a different port, and then visit the maze server’s website, you should see a fully-operational maze randomly generating tiles from your two generators.

There are not points for it running locally, but if it cannot run locally it also cannot run in the full-class deployment.

7 Part 4: In-lecture deployment on April 18

On April 18 we will run all MGs as part of an in-lecture check-off for the other half of your MP8 grade. Some things you should be ready for:

  1. You’ll run your MGs on your course VM.
  2. We’ll tell you what maze generator server to connect to, and may change it during the lecture.
  3. At different points in lecture we’ll ask you to run just your static MG, just your dynamic MG, both, or neither.
  4. If your mazes are unsolvable (no path between exits) or nearly empty (a big open room with at most a handful of internal walls) you will lose points.
  5. You should be prepared to speak briefly about your MGs.

To prepare for this, once your code passes the github actions, you should

  1. Host both of your MGs on your VM.
  2. Change the url you send to the middleware’s /addMG path to use your VM’s URL (for example, http://sp24-cs340-001.cs.illinois.edu:5001 instead of http://127.0.0.1:5001).
  3. Be prepared to run both dynamic and static servers in class and to change the middleware URL several times; we have multiple middleware implementations with slightly different features which we will have running on various ports of http://sp24-cs340-adm.cs.illinois.edu. If you do not have a machine that can SSH into the VM from the classroom, please let us know.

Some middleware front-ends will display the name fields of each maze tile to whoever enters that tile; thus, we recommend (but do not strictly require) descriptive, likely-unique names that you’re comfortable with the entire class seeing.

In addition to the name of your maze generator as a whole, you may also add a name field to an individual tile’s JSON if you want to display per-tile names instead of per-server names, as e.g.

{
  "geom": ["988088c", "1000004", "1000004", "0000000", "1000004", "1000004", "3220226"],
  "name": "totally empty room"
}

8 Submission

You must commit your MGs to GitHub on the usual deadline using the standard git commit+push commands:

git add -A
git commit -m "MP submission"
git push

8.1 Autograding

The initial grading is done via a manual GitHub Action. You MUST complete this step before the deadline to earn the autograding points for the MP:

8.2 Points

Half of this MPs points are given based on github autograding on the usual MP deadline.

Half of this MPs points are given based on successful participation in the April 18 course-wide maze.