3A: World Generation

Deadlines

Warning: There are 3 deadlines for this project, and some deadlines require you to submit multiple deliverables. Please double-check that you submitted everything!

Assignment	Tasks	Deliverable	Points	Due Date
Team Formation	- Task 0: Partnerships	Pre-Project Google Form	5	Mon, Nov 11 11:59pm PT
Project 3A	- Task 1: Setup - Task 2: World Generation	World Screenshots on Gradescope	10	Mon, Nov 18 11:59pm PT
		Mid-Project Google Form	5
Project 3B	- Task 3: Main Menu - Task 4: Interactivity - Task 5: Saving and Loading - Task 6: Ambition Features	Code on Gradescope (0 pts, but required for checkoff)	0	Tue, Nov 26 11:59pm PT
		Live Checkoff with TA (Checkoffs will happen Dec 2–6)	100
		Post-Project Google Form	5

Code Overview

Skeleton Code

A walkthrough of the new skeleton code is available here. This is also from a past semester, so some terms may be outdated (e.g. “Phase 1” is now “Project 3A”).

In the TileEngine package, you’ll find the following useful files:

• TERenderer.java contains rendering-related methods.
• TETile.java represents a tile.
• Tileset.java has some pre-made tile designs that you can use.

In the Utils package, you’ll find the following useful files:

• RandomUtils.java has methods for generating randomness for your world.
• FileUtils.java has methods for writing to a file and reading from a file.

In the Core package, you’ll write code for your game. We recommend putting all your code in this package (though this is not required).

• AutograderBuddy.java lets your code interact with the optional autograder. Filling it out is optional.
• Main.java is how your user starts the entire system.
• World.java represents your world!
• You can add other classes of your own, too!

This project makes heavy use of StdDraw, which is a package that has basic graphics rendering capabilities. Additionally, it supports user interaction with keyboard and mouse clicks. You will likely need to consult the API specification for StdDraw at some points in the project. See here for the API specification.

Imports

Your project should only use standard Java libraries (any import starting with import java.* is okay) or any libraries we provided with your repo and library-fa24.

Here is a non-comprehensive list of allowed imports:

• java.util.List, java.util.ArrayList, java.awt.*, or anything else starting with java.* is fine.
• edu.princeton.cs.algs4.StdDraw, edu.princeton.cs.algs4.StdAudio, or anything else starting with edu.princeton.cs.algs4.* is fine, because this is in library-fa24.
• tileengine.TETile, utils.RandomUtils, or anything else starting with tileengine. or utils. is fine, because these are the starter code.

Conceptual Overview

Creating a Tile Array

At a high level, your goal is to create a 2D array of TETile objects, and fill in the array with different tiles, to create a nice-looking world. Then, you can call one of our library functions to display this world to the user.

Important notes on orientation:

• world[0][0] corresponds to the bottom-left tile of the world.
• The first coordinate is the x-coordinate. For example, world[8][0] is 8 spaces to the right of the bottom-left tile.
• The second coordinate is the y-coordinate. For example, world[0][3] is 3 spaces above the bottom-left tile.

If you’re unsure of the tile layout, write some short sample programs that draw sample grids to deepen your understanding. If you confuse x/y or up/down, you’re going to be incredibly confused when debugging.

Each entry of the 2D array can be filled in with a tile from our default library of tiles in Tileset.java.

Here’s a snippet of code that creates a world with width 5 and height 3, and fills in a few squares:

private static final int WIDTH = 5;
private static final int HEIGHT = 3;

// Create grid of tiles (all null to begin with).
TETile[][] world = new TETile[WIDTH][HEIGHT];

// Fill grid with NOTHING tiles.
for (int x = 0; x < WIDTH; x++) {
    for (int y = 0; y < HEIGHT; y++) {
        world[x][y] = Tileset.NOTHING;
    }
}

// Add some tiles to the grid.
world[0][1] = Tileset.WALL;     // The # sign.
world[3][0] = Tileset.FLOWER;   // The pink flower.
world[2][2] = Tileset.MOUNTAIN; // The gray triangle.

The resulting world would look like this when it’s rendered:

Notice that we had to explicitly assign unused squares to Tileset.NOTHING, the pure black tile. If you don’t initialize unused squares, you’ll get a NullPointerException when you try to draw the world.

Rendering Tiles

Once you have your 2D world array, it’s time to show it to the user!

Here’s a snippet of code that takes in a 2D world array, and displays it to the user:

// Initialize the tile rendering engine with a window of size WIDTH x HEIGHT. Call this only once.
TERenderer ter = new TERenderer();
ter.initialize(WIDTH, HEIGHT);

// Create and fill grid of tiles (all null to begin with).
// Omitted: Code to fill the grid with tiles.
TETile[][] world = new TETile[WIDTH][HEIGHT];
...

// Draw the 2D grid to the screen. Call this every time you re-draw the world.
ter.renderFrame(world);

Note: Later in the project, you’ll be animating the game (displaying different worlds as the user moves around). Be sure to call initialize only once, to set up the window. Then, you can call render as many times as you want.

The rendering engine calls all the necessary StdDraw methods for you. We recommend against using StdDraw commands like setXScale or setYScale unless you really know what you’re doing, as you may considerably alter or damage the a e s t h e t i c of the system otherwise.

Pseudo-Randomness

To generate random numbers in Java, we can use create a Random object, which represents a random number generator:

Random r = new Random(); // Totally random. Don't do this in Project 3.
System.out.println(r.nextInt());
System.out.println(r.nextInt());
System.out.println(r.nextInt());

Every time you run this program, you’ll get 3 totally random integers.

What if we want to control the output of the random number generator (e.g. for debugging purposes)? In that case, we can provide a seed to the constructor:

Random r = new Random(1000); // Pseudorandom. Do this in Project 3.
System.out.println(r.nextInt());
System.out.println(r.nextInt());
System.out.println(r.nextInt());

r is now a pseudorandom number generator, because it generates a deterministic sequence of random-looking numbers based on the seed you provide.

If you provide the same seed, you will get the same sequence of values. For example, every time you run this program, you will get the same 3 integers.

Here’s another example:

Random r = new Random(82731);
System.out.println(r.nextInt());
r = new Random(82731);
System.out.println(r.nextInt());

This code snippet will always print out the same number twice. If you run this program multiple times, you’ll still get the same number twice.

In Project 3, you should always seed your Random objects, so that your worlds look random, but you can re-create them consistently for debugging and grading purposes.

World Requirements

Your goal in Project 3A is to write a world generator that can create pseudorandom worlds with hallways and floors.

Here are some examples of valid worlds, where # is wall, dot/quote is floor, and the empty square is the empty space (outside the world).

Requirements for a valid world:

1. The world must include distinct rooms and hallways. For any floor square, it should be obvious whether that square belongs to a room or a hallway.

   It’s okay if you occasionally generate some worlds where a few squares are ambiguous, but the vast majority (>90%) of floor squares should be clearly identifiable as a room or a hallway.

   Overlapping rooms are fine, as long as it’s clear that the squares belong to rooms, not hallways.

   (click to expand) Examples of invalid worlds, because we can't tell where rooms and hallways are.

   

2. At least some rooms should be rectangular. You can optionally support rooms of other shapes as well.

3. Hallways should be width-1.

   It’s okay if width-2 hallways appear on rare occasions, as long as the hallways are still distinct from rooms.

   (click to expand) Examples of hallway widths.

   
   Below is a width 1 hallway (most/all hallways should look like this):
   
   Below is a width 2 hallway (can only appear rarely):
   

4. Your world generator must be capable of generating hallways that include turns (or equivalently, straight hallways that intersect). Random worlds should generate a turning hallway with moderate frequency (20% of worlds or more).

5. The world should not have any dead-end hallways. Hallways should always lead into rooms.

   (click to expand) Example of an invalid world, because it has a dead-end hallway.

   

6. Walls, floors, and empty spaces should all be visually distinct.

   The easiest way to do this is to use three different tile types: one for walls, one for floors, and one for empty spaces.

   (click to expand) Example of an invalid world, because we can't distinguish between walls and floors.

   

7. Walls in the corners of rooms are optional.

   (click to expand) As an example, both of these rooms are valid (though this world itself is invalid because the two rooms are disconnected).

   

8. All floor tiles (rooms and hallways) should be reachable from each other.

   In other words, it should be possible to trace a path of floor tiles between any pair of floor tiles.

9. All the space “inside” the walls should be floor tiles, and all the space “outside” the walls should be empty space tiles.

   In other words, a floor tile should only be bordered by floor tiles or wall tiles.

10. Rooms cannot clip off the edge of the world. In other words, there should be no floor tiles on the edge of the world.

    (click to expand) Example of an invalid world, because it clips off the world.

    

11. The world must not have excess unused space. There’s no strict requirement, but try to consistently fill at least 50% of the world with rooms and hallways.

    (click to expand) Example of an invalid world, because there are too few rooms.

    

Requirements for a pseudorandom world:

1. The world must be pseudorandom.

   If the user chooses the same seed twice, the resulting world must be identical.

   If the user chooses two different seeds, the resulting worlds should be different.

2. Different worlds should different numbers of rooms and hallways.

   A range of numbers is okay, e.g. it’s okay if all worlds have between 8 and 12 rooms, as long as different worlds have different numbers of rooms.

3. Different worlds should have rooms and hallways in different locations.

   For example, if every world you generate has a room in the exact same place, that’s not sufficiently random.

4. Different rooms should have different widths and heights.

5. Different hallways should have different lengths.

6. The world should be substantially different each time, i.e. you should not have the same basic layout with easily predictable features.

7. You can pick any window size you want, as long as the window size is reasonable (e.g. not something tiny like 3×3), and the entire window is visible on your computer. For example, a fixed, non-random window size is fine.

Note on grading: We know that some of these requirements are subjective, and we’ll try to be generous as long as your worlds follow the spirit of the requirements.

Staff cannot answer questions like “is my world valid” or “is my world good enough” on Ed or in office hours. In Project 3A, you’ll turn in some worlds for us to grade, and if they aren’t valid, we’ll give you a second chance to fix any problems for full credit.

Optional: Design Doc

Before you begin writing any code, we highly suggest writing a design document! This lets you plan out the overall design of your codebase, so that you can organize your code into smaller pieces and tackle one thing at a time.

Warning: We won’t be grading this document, it is required to request staff help. If you request help on Ed or in office hours, we will need to see your design document before we can start helping you.

In your design document, you can identify what data structures you’ll be using in your implementation. You can also write pseudocode or a general English overview of the algorithms you plan to use.

You can format your document however you like. Here’s a template that you can use or borrow some inspiration from.

Here are some example sections you could have in your document:

1. Classes and Data Structures: List out all the classes you’re using. For each class, list the instance variables (if any). Include a brief description of each variable and its purpose in the class.

2. Algorithms: This is where you describe how your code works. For each class, include a high-level description of the methods in that class. That is, do not include a line-by-line breakdown of your code, but something you would write in a javadoc comment above a method, including any edge cases you are accounting for.

   Try to keep your explanations clear and short. Include all the components your program interacts with - classes, specific methods, and files you may create.

You can also have separate sections for each of the different tasks: World Generation (Task 2), Interactivity (Task 4), Saving & Loading (Task 5), and Extra Features (Task 6).

Task 2: World Generation

With your design document completed, it’s time to generate some worlds!

Implement code that takes in a seed, generates a pseudo-random 2D world array, and displays that world back to the user.

For Project 3A, when the user runs the main method in Main.java, they should see a world pop up. For now, you can hard-code the seed in the main method (and change the code to see the output of different seeds).

Besides the Main.main requirement, your world generation code can live anywhere in the repo (we suggest making your own files in the Core package).

Deliverables

World Screenshots

1. Go to this Java Visualizer link to generate 5 seeds. Remember to replace 1270 with your group ID.

2. Use your code to generate the 5 worlds corresponding to these seeds.

   You may need to add an “L” after the seed so that Java recognizes it as a long number, e.g. 6578897764558030256L.

3. Take screenshots of each world. Your screenshots should look like the other world screenshots throughout this spec.

4. Upload these 5 screenshots to Gradescope. You should submit one screenshot per question.

5. In your terminal, navigate to your group repo, and type git show --summary. Make sure that the latest commit you see corresponds to the code you used to generate these worlds:

   

6. Take a screenshot of the git show --summary output and upload it to Gradescope.

   Warning: All 5 of your worlds should be generated with the same code. You shouldn’t submit 3 worlds from one algorithm, and 2 worlds from another one. We will use your commit log to check this.

7. Make sure that only one partner submits, and then tags the other partner on Gradescope. Each group should only have one submission.

Warning: Don’t hard-code worlds in your code. Your world generation code should generate pseudo-random worlds for any seed we provide, not just the 5 seeds. Again, we will use your commit log to check this.

Grading:

We will grade your worlds after the Project 3A deadline, but before the Project 3B deadline. It can take up to a week to grade your world (especially if you have an extension), so please be patient.

If your worlds do not receive full credit, you can submit a regrade request on Gradescope.

In your regrade request, please include:

• A screenshot of git show --summary with the commit of the new code you used to generate your fixed worlds.
• The 5 worlds you generated with your fixed code. Use the same seeds as you did originally.

It can take up to a week to respond to your regrade request, so please be patient.

Mid-Project Partnership Form

Submit the Project 3 Mid-Project Partnership Form.

You will receive an email receipt to confirm that you’ve submitted it.

Warning: Don’t forget the form! Students every semester forget this form and they are sad.

Optional: Autograder

We have provided an optional autograder on Gradescope for you to validate your world generation algorithm. The autograder mainly checks that entering the same seed twice leads to the same world, and entering different seeds leads to different worlds. It won’t check the room/hallway requirements listed above.

The autograder (and AutograderBuddy.java) is completely optional: There is no extra credit for submitting to it, and there is no penalty for not submitting to it. Because the autograder is optional, we won’t offer any staff debugging support for it.

The autograder has no eyes and cannot look at your world. To help the autograder see your world, you would need to fill out the getWorldFromInput method in AutograderBuddy.java. This method takes in a string of characters, and returns the 2D tile array that would have been displayed if the user had typed in this string.

For Project 3A, you can assume all input strings are of the form N####S, where the #### is replaced with the user’s chosen seed. For example, AutograderBuddy.getWorldFromInput("N3893205S") should return the 2D tile array corresponding to the world generated from seed 3893205.

Because the autograder cannot look at your world, this also means that the autograder does not support any StdDraw methods. You can support this in two ways:

1. Organize your code so that human running Main.java call the StdDraw methods to render worlds, while autograders running AutograderBuddy.java do not call the StdDraw methods to render worlds. For example, you could create an instance variable to track if the world is being built by a human or an autograder.

2. Comment out all the StdDraw methods temporarily when submitting to the autograder, so that the autograder never tries to render a graphical window.