代写program、代做Java/c++设计编程

日期：2025-04-09 09:22

Assignment 5: Markov Chain for Procedural Level

Generation

The purpose of this assignment is to make you familiar with procedural content generation for

level design. Markov Chains are one of the earliest Procedural Content Generation via Machine

Learning (sometimes called “Generative AI”) approaches, with example applications dating back

to 1957, they were the first approach applied to game level models, and has been used in tools

for game developers. In this assignment you’ll implement a Markov Chain for level generation.

Specifically, in this assignment we’ll pretend that you’re the Game AI lead at a company making

a roguelike/procedural Pacman clone (the game you’ve been working on all term). The level

designer for the game wants you to create a procedural level generation system, and has given

you 20 levels in a tile-based representation (see below) as examples. But they’re kind of weird

(both the levels and the designer). Your goal is to use these 20 levels to learn a final Markov

Level Generator that can successfully replicate this designer’s distinct style. Notably these 20

levels are unique to you.

What’s actually happened here is that I have generated a secret Pacman Markov Chain Level

Generator, unique to each of you, with its own probabilities, and its own state representation.

This is where your 20 given levels (and several withheld test levels) come from. Your job is to

replicate this Markov Chain from only the given 20 output levels. I have verified this is possible

for all students in all cases.

Above you can see an example level generated for this assignment with a simple L-shaped

Markov Chain generator that would get 7/10 on this assignment.

What you need to know

There’s only one script that you’ll be editing for this assignment (MarkovLevelGenerator.cs),

unless you go for the extra credit. You’ll also be working with a helper script to a very minor

extent (TXTtoLevel.cs) and a data structure representation for Pacman levels (Level.cs). If you

go for the Extra Credit, it’ll be worth digging deeper into Level.cs, and one route to the extra

credit would benefit from taking a look at LevelOptimizer.cs. Your job will be to alter

MarkovLevelGenerator.cs to implement a Markov Chain and then improve that Markov

Chain so it can better model your specific levels.

Pacman Representation

This first bit is not a script but the “tile” representation used in this assignment.

Above left is the original Pacman level (Assets > HW5 > Original Pacman Levels > Original >

pacman.jpg). In the middle is the “tile” representation of the level (Assets > HW5 > Original

Pacman Levels > Processed > pacman.txt), and to the right is the level loaded into the Unity

project for Assignment 5 (yes this is an intentional simplification).

In this “tile” representation, levels are translated into characters, with each character

representing a certain type of in-game cell. You can find a list of these tiles in (Assets > HW5 >

Original Pacman Levels > pacman.json), which I’ve also described in raw text below. You do

not need to understand all of these to do the assignment, they’re here as a reference.

● G : Ghost spawn position cell

● S : Player spawn position cell

● - : A completely empty cell (tend to be around the ghost spawn in real Pacman levels)

● . : A cell with a pellet in it

● o : A cell with a power pellet in it

● X : A cell with a square obstacle inside it exactly the size of the cell

● [ : A cell where the left side is an obstacle line

● ] : A cell where the right side is an obstacle line

● ' : A cell where the top side is an obstacle line

● _ : A cell where the bottom side is an obstacle line

● P : A cell where the top and left sides are obstacle lines

● R : A cell where the top and right sides are obstacle lines

● L : A cell where the bottom and left sides are obstacle lines

● D : A cell where the bottom and right sides are obstacle lines

● = : A cell where the top and bottom sides are obstacle lines

● T : A cell where the left and right sides are obstacle lines

● C : A cell where the top, left, and bottom sides are obstacle lines

● Q : A cell where the top, right, and bottom sides are obstacle lines

MarkovLevelGenerator.cs

This is the only script you will have to edit for the assignment (unless you do the extra credit) in

order to implement a basic “L-shaped” Markov Chain (though more of a rotated L in this case)

and then to further improve that to better model your assigned levels. This generator generates

tile-by-tile from the top left to the bottom right.

Member variables:

● markovChain: A Dictionary with string keys (representing states) and Dictionary values

representing actions (AKA next tiles) as strings (key) to the probability of each action

represented as a float (value). You will be responsible for ensuring this variable

represents your final Markov Chain.

● MarkovChain: A public getter for markovChain

● nullToken: A string to represent a null tile for if we lack some state information

● levelChars: An array of chars representing each possible tile (see above). You can likely

ignore this!

● obstacleColours: An array of colours, used to randomly colour a generated level. Also

ignorable, unless you want to change your output colours for aesthetic reasons. It’s

largely here as an example that might be relevant to the extra credit.

Member functions:

● TrainMarkovChain (TextAsset[] levels): This is the function you will primarily be modifying

for this assignment. You will need to update this so it matches the pseudocode

provided during the lecture and given below.

● GenerateLevel: Queries the Markov Chain for a level in the tile representation, converts

it to the Level representation (below) and then sets all its obstacles to a random colour.

This generates levels from the top left to the bottom right.

● GetMarkovState(string level, int x, int y): Returns a state: currently the default L-shaped

state, grabbing the left, above, and left and above tiles to represent the state. You will

need to update this so that your Markov Chain does a better job modelling your

individual data.

TXTtoLevel.cs

This is just a helper script for converting strings of levels in the tile representation to the Level

representation (see below).

Level.cs

This script holds the Level class, which is the basic representation of a specific level. You will

not make any changes to this script as it’s only for storing level data, but you will work with it. A

particular Level object will specify a particular level. You can get pretty out there with this (see

examples below). Both of the below are extra credit submissions from Winter 2024 that received

the max possible points.

Member public variables:

● pellets: A list of ProtoPellet objects that represent the pellets in this level in terms of their

location (Vector3 worldPosition) and whether or not it is a power pellet (bool

powerPellet). Your code will be changing this value in LevelOptimizer.

● obstacles: A list of ProtoObstacle objects that represent the obstacles in this level. For

the base assignment you only need to specify these in terms of their location (Vector3

WorldPosition) and shape (Vector2[] shape), but you have the option to impact the

obstacle colour (lineColor) and line width (lineWidth) as well, which may be helpful for

extra credit.

● ghostStartPos: The start positions of the ghosts for this level. It is not necessary to

change this value, but it may be helpful for the extra credit.

● pacmanStartPos: The start position of Pacman for this level. It is not necessary to

change this value, but you may find it helpful for certain Evaluators, and it may be helpful

for the extra credit.

● fitness: Used only for the Reduce function in LevelOptimizer, meant to store the fitness

for this level. You will not need to interact with this variable at all.

Member functions:

● Level: There are many constructors for Level, which basically determine how much

information will be specified. You do not need to use any of them in your implementation,

but you may find it helpful.

● Level Clone(): Returns a clone of this level. Useful for the Mutate function in

LevelOptimizer.

● Vector2[][] GetObstaclePoints(): Returns all of the obstacle points of this level, which can

be used in rendering this level. You will not need to interact with this function at all.

ExtraCreditLevelGenerator.cs

This script is solely for the extra credit and is largely empty to start. It has only a single function

(GenerateLevel()) as you have a massive amount of freedom in terms of how you’d like to tackle

the extra credit. More on this below.

LevelOptimizer.cs

LevelOptimizer is an example of implementing a search-based approach for level generation. It

is only presented as an example of one incomplete route to the extra credit (not necessarily

the best and not necessarily one you should use).

Member variables:

● width: Half of the width of each level.

● height: Half of the height of each level.

● gridSize:The standard grid size for each level

● POPULATION_SIZE: A variable you could use to track the size of your population.

● MUTATION_RATE: A variable you could use to determine with what probability to mutate

a member of your population.

● NUM_CROSSOVERS: A variable you could use to determine how many crossovers

you’ll have (equivalent to how many children to produce) in each iteration.

● MAX_ATTEMPTS: A variable that you could use to track the max number of attempts for

your genetic algorithm (maximum number of generations).

● squareObstacle: A simple set of points that can be used to define a square obstacle

exactly the size of a grid cell.

Member functions:

● Level GetLevel(): The main function of this assignment, and where you could implement

a genetic algorithm. It takes in an evaluator and goalValue that can be used to determine

the quality (fitness) of a particular level. It returns the best possible level according to a

fitness function.

● float Fitness(): A basic fitness function for this assignment. Simply prefers levels made

up of all pellets.

● Level Mutate(Level level): Takes in a level object and returns a neighbour, a slightly

different (or mutated) level. You will have to use this function or similar code in GetLevel.

● Level Crossover(Level parent1, Level parent2): Takes in two levels and outputs a level

that is a mix or “child” of these two levels. You will have to use this function or similar

code in GetLevel. You may find it helpful to modify this function, though there are ways

to complete the assignment without doing so (though it may be helpful for the extra

credit).

● Level Sample(List<Level> population): Grabs a value from the passed in population by

sampling based on the different Level fitness values. You may have to use this function

or similar code in GetLevel. It probably should not be modified.

● List<Level> Reduce(List<Level> population, int populationSize, Evaluator evaluator, float

goalValue) Takes in a population and a populationSize and passes back a List of

populationSize of only the best levels in terms of their fitness. You will have to use this

function or similar code in GetLevel. It probably should not be modified.

● Level GetRandomLevel(): Generates a random level. You will likely have to use this

function or similar code for a search-based approach. You may find it helpful to modify

this function, but it is not necessary for this assignment (though it may be helpful for the

extra credit). You may want to modify this function.

Instructions

Step 1: Download the “W25 Game AI Assignment 5.zip” file from eclass, unzip it, and open it via

Unity. You can open it by either selecting the unzipped folder from Unity or double clicking the

“Game” scene.

Step 2: Open “Game” located inside Assets/HW5. Hit the play button. You should see the

“simplified” original Pacman level above.

Step 3: Find and remove the original Pacman level from Admin’s Level Handler component (see

below). Run the code again. This will cause the Level Handler to instead query the Markov

Chain for a level. Since there’s no Markov Chain currently the level generator will just output the

“default” pellet in all positions.

Before removal:

After removal:

Step 4 (Optional): Import your own previous GridHandler, AStarPathFinder, and Custom Ghost

code from the prior assignments, using the instructions from those assignments to do so. The

only one of these that would be relevant to the assignment is your Custom Ghost code, and

even then only for the extra credit.

Step 5: Update the TrainMarkovChain function in MarkovLevelGenerator.cs so that it correctly

implements the Markov Chain training psuedocode given in the lecture and below:

for state, action in data:

counts[state][action] +=1

stateCounts[state] +=1

for state, action in counts:

markovChain[state][action] = counts[state][action]/stateCounts[state]

Step 6: Swap out the levels on the MarkovLevelGenerator component of the “Markov Level

Generator” game object in Unity. Currently it has the 17 original Pacman levels found in Assets

> HW5 > Original Pacman Levels > Processed. You’ll need to replace these with the 20 levels

found in the folder with your Canvas name on it inside Assets > HW5 > Assignment 5 Data.

Step 7: Update the GetMarkovState function inside MarkovLevelGenerator.cs to better reflect

your assigned levels. Each level secretly was generated based on a state with 2-4 additional

features. The full list of all possible additional state features is given below. You can use the

instructor and example levels to determine if your approach for finding the correct state features

works.

● X-symmetry Value: An additional feature that adds the symmetrical tile along the x-axis

to the state when on the right-half of the level. So if we were in the top-right corner, it’d

add the tile in the top-left corner.

● Y-symmetry Value: Same thing as the X-symmetry Value, but along the y-axis, when

we’re in the lower half it’ll be set to the symmetrical tile in the upper half. So if we were

picking the bottom-right corner tile, it’d add the top-right corner tile.

● Generated Ghost Spawn: Adds a boolean feature that’s 1 if we’ve added the ghost

spawn and 0 otherwise.

● Generated Player Spawn: Same thing as Generated Ghost Spawn but for the player

spawn.

● Power Pellets Count: Appends the current count of generated power pellets to the

state.

● Y-third Counted: Covers the current “third” that we’re in, in terms of the Y-values, so

rows 1-4 would be 0, 5-8 would be 1, and 9-12 would be 2

● X-half Counted: Covers if we’re in the left (0) or right (1) side of the level (the middle

column counts as the right half)

● Tenth Unobstructed: Counts every 10 pellet (“.”) or empty (“-”) tiles, so 0-9 would be 0,

10-19 would be 1 and so on.

● Tenth Solid: Counts every 10 wall tiles, so 0-9 would be 0, 10-19 would be 1 and so on.

● Two Left: Adds the tile two the the left of the current position, if available.

● Two Up: Adds the tile two up from the current position, if available.

● Two Left, One Up: Same thing, but two to the left and one up, if available.

● One Left, Two Up: Same thing, but one left and two up, if available.

● Two Left, Two Up: Same thing, but two left and two up, if available.

Note that you can use the “Train” button to test with what probability your current Markov Chain

would generate your set of training levels.

Step 8 (Optional, Extra Credit): Optionally, you may choose to fill out the GenerateLevel

function of ExtraCreditLevelGenerator.cs however you like.

Grading

This homework assignment is worth 10 points. Your solution will be graded by an autograder.

The whole assignment is about how well your Markov Chain learns the desired level design

style. The point breakdown is as follows:

7 points: If you have correctly implemented the basic Markov Chain without any updates to the

state, you’ll receive 7 points. This’ll be checked by ensuring that (1) your Markov Chain can

generate levels, 0 otherwise, and that (2) your Markov Chain achieves at least an average 65%

probability of generating withheld test levels (this can be approximated by leaving out test levels

from the provided training levels).

3 points: The remaining 3 points come from improving the GetMarkovState function such that

your Markov Chain can accurately model your specific 20 provided levels. This will be verified

by your Markov Chain achieving at least an average 80% probability of generating the withheld

test levels.

If your code does not compile you will get a 0. If you use any additional “using”

lines/import additional libraries, your code will get a 0.

In addition you can receive up to 2 extra credit points on this assignment. The formula for the

bonus looks like this:

Bonus = Diversity * (Playability + Style)

Where Diversity, Playability, and Style are all metrics that range from 0-1 (inclusive). They will

be calculated by first generating 100 levels with your Extra Credit Level Generator. However,

students will receive 0 extra credit points if any call to the GenerateLevel function in

ExtraCreditLevelGenerator.cs takes more than 30 seconds to return a level.

Diversity is the count of unique levels divided by 100, where unique indicates a difference in

either pellets, obstacles, player spawn location, or ghost spawn location.

Playability is the count of how many levels Pacman can reach all pellets where there are at

least 4 pellets divided by 100.

Style is the most complicated metric, as there are two ways to achieve a perfect 1.0/1.0. Either

you can ensure that your output levels match the level design style of the original Pacman levels

(walls of consistent shapes, lengths, and colour, horizontal symmetry, regular pellet placement,

ghost spawn position unchanged, pacman spawn position unchanged, consistent player

experience compared to the original levels) or you can produce levels entirely distinct from the

original Pacman levels but with a consistent “style” (different from the original for all the features

mentioned above). You can imagine the extra credit as a linear scale with both ends of the scale

worth 1 point and a fully random level receiving 0 points:

For the left side I will be looking to ensure that your levels match the original Pacman in terms of

the features stated above, with points given based on to what extent it matches. For the right

side, I will use the same features as above, but I will check for the consistency of the differences

to the original levels. Those who go for the right side should have generators that produce a

consistent, but entirely distinct, style of level. You can get really creative with this, though

notably you cannot directly change the Pacman mechanics, outside of things like your own

CustomGhost, if you choose to use it. That said you can get to something that basically

becomes a new game. I only gave the two example output levels above that would receive a

perfect 1.0 on this metric but I don’t want students to replicate either of these levels (any

generators that do will get 0 extra credit points).

The Discord server icon for the next iteration of this class will be chosen from the

students who receive the best score on the “creative” side of this scale (as it was for the

current icon), and the student will be honoured at the Games Certificate Awards.

Hints

The initial 7 points of this assignment are not meant to be all that challenging. The remaining 3

points can be brute forced, but you can also study your given levels to help give you ideas.

Specifically I recommend thinking about what kind of levels would be generated if a feature was

or wasn’t included.

I have once again included instructor team and example data where I’ve “given you the

answers” to help with this assignment. Specifically:

● Arghasreee Banerjee: Her levels were generated with the inclusion of the “Generated

Player Spawn” and “Two Left” features.

● Dagmar Lofts: Their levels were generated with the “X-Symmetry Value”, “Generated

Ghost Spawn” and “X-half Counted” features.

● Emily Halina: Her levels were generated with the inclusion of the “Generated Player

Spawn” and “Tenth Solid” features.

● Jawdat Toume: Her levels were generated with the “X-half Counted” and “Two Up”

features.

● Mashfiq Shahriar Zaman: His levels were generated with the “X-Symmetry Value” and

“Generated Ghost Spawn” features

● Matthew Guzdial: His levels were generated with the “Generated Player Spawn” and

“One Left, Two Up” features.

Note that of these six examples, only one has three features. Further, note that in some cases

the above features may not be necessary to model to achieve a sufficient Markov Chain.

It might be helpful to ensure you can achieve >=75% probability of generating these levels when

they’re your training data if you have your Markov Chain training finished and have updated the

state to include the above features.

A reminder that the Pacman Markov Chain level generator goes from top left to bottom right as

opposed to the example Mario Markov Chain level generator that goes from bottom left to top

right.

By “test levels from the provided training levels” in the grading section I mean moving some of

your levels from the “training levels” list to the “test levels” list.

It’s very easy to add too many features and be unable to generate anything. I’d strongly suggest

checking that you can still generate levels or else you’re likely to get 0 points for the test portion

of the assignment.

You have a lot of freedom for the Extra Credit. Consider making things easier for yourself by

picking one of the approaches covered in the PCG lecture or taking a look at the provided

LevelOptimizer.cs (particularly the random level generation function) as a starting point.

You will probably be using a lot of Random values for this assignment if you go for the extra

credit option.

You may alter your Custom Ghost code if you attempt the extra credit and think it would be

beneficial. However, this is not the focus of the assignment. Be careful not to waste time on this!

Submission

To submit your solution, upload your modified MarkovChainLevelGenerator.cs file. If you

attempted the extra credit, also upload your ExtraCreditLevelGenerator.cs file. If you made use

of your own GridHandler.cs, you should submit that as well. If you went for the extra credit and

you believe it’s necessary for your implementation, you may upload your AStarPathFinder and

your code from Assignment 4 (the custom ghost code).

You should not modify or upload any other files in the game engine. You should not import any

additional libraries.

DO NOT upload the entire game engine.