Contents
This is a course for students interested in methods of procedural content generation (PCG) in computer games. An overview of PCG methods is presented and a variety of approaches is investigated more thoroughly. The labs focus on the practical usage of PCG in more-or-less developed computer games and uses some elementary knowledge of Java and Python. The course is taught at MFF UK as NAIL123.
Permalink: bit.ly/mff-pcg-2019
News
Follow the appropriate channel at Gamedev Discord!
https://discord.gg/c49DHBJ
Dates (SIS)
Lectures will be interwoven with Labs on even / odd weeks, but the course starts with two consecutive lectures.
Tuesdays, 14:00, SW1 (we start 18.2.2020)
Course Exam
There will be an oral examination done during the examination period. The exam will be a mixture of direct question on the topics below and open questions where you will be describing a procedural approach for given content.
Exam topics
Classification of PCG: Reasons for PCG in games. Design-time vs runtime. Teleological vs ontogenetic. Direct vs indirect.
Terrain: Simple approaches for terrain generation. The diamond-square algorithm.
Noise: Value vs. gradient noise. Octaves. Perlin noise. Advantages of simplex noise. Domain warping. Use-cases for analytical derivatives. Billow and ridge noise. Cellular (Worley) noise. 3D approaches. Perlin worms.
Search-based: Pros/cons of various content representations. Building blocks. Template search. Evolutionary algorithms – differences when using for PCG. Types of evaluation functions. Assessing quality of generators.
Methods: Cellular automata. L-systems. Shape and graph grammars.
Visual art: Art toys (what are they, what are they for). Procedural effects.
Musical art: Approaches for music. Melody. Harmonization.
Constraint-based programming: Answer set programming – description, use-cases. AnsProlog. Wave function collapse.
Mixed-initiative approaches: Definition. Three initiatives (of dialogue). Pros/cons.
Mazes: Types. Attributes. Objectives. Solving (computer/human methods). Perfect maze generation (Kruskal’s algorithm, backtracking).
Dungeons: Combining maze algorithms with rooms. Space division methods. Mission graphs + space layout options. Enemy placement. Spawning waves.
Loot: Methods. Affixes. Loot tables. Variability. Player interaction with loot system.
Puzzles: Approaches.
Lectures
Lectures Schedule
No. | Date | Topic | Lecturer | Content | Slides |
0 | 18.2.2020 | Introduction | Vojtěch Černý | What is Procedural Content Generation Reason to use PCG Brief history Interesting implementations Course structure |
PPTX |
1 | 25.2.2020 | Terrain Generation | Vojtěch Černý | Terrain Generation Approaches Noise functions |
PPTX |
2 | 10.3.2020 | Search and evaluation | Vojtěch Černý | Different approach to PCG Content representation Search algorithms Fitness functions Evaluating procedural content |
PPTX |
3 | 24.3.2020 | Procedural art | Vojtěch Černý | Cellular automata L-Systems Graph grammars, shape grammars Visual art Art toys Procedural effects Generating music |
PPTX PDF with notes |
4 | 7.4.2020 | Constraints in PCG | Vojtěch Černý | Answer set programming Mixed-initative approaches Generating game rules Wave function collapse |
PPTX PDF with notes |
5 | 21.4.2020 | Dungeons | Vojtěch Černý | Maze generation Dungeon generation Generating items Procedural encounters Generating puzzles |
PPTX PDF with notes |
Labs
The labs will consist of short introductions to specific PCG contexts (usually games) and homeworks.
A total of 5 homeworks worth 30 points total will be presented during the semester. 21 points are required for admittance to the exam.
For the 1st practical please bring your laptop with preinstalled Java (JDK) 11+. Modify PATH and JAVA_HOME environment variables such that it is your default. Also (for your comfort), IntelliJ IDEA is recommended – community edition is sufficient, but as a student you can get ultimate edition for free – basically by just asking for it on their site.
For the 2nd practical, you will need the setup from above, and also Python 3 installed and added to your PATH.
The 5th and 6th practicals will consist of one large homework, worth 10 points. You should submit the first part, receive feedback, incorporate it and extend your work with the second part of the assignment. Your points will count towards credit only if they will be non-zero in both parts.
Labs Schedule
No. | Date | Topic | Lecturer | Slides | Prerequisites | Homework | HW pts | Deadline |
1 | 3.3. 2020 | Terrain Generation | Vojtěch Černý | PPTX Pitfalls |
Java (11+) Git shell (Win – Git Bash) (recommended) IntelliJ IDEA |
HW1 – Minecraft | 5 | 16.3. 23:59 |
2 | 17.3. 2020 | Platformer Levels Generation | Vojtěch Černý | PPTX |
Java (11+) Python 3 (recommended) IntelliJ IDEA |
HW2 – Mario | 5 | 30.3. 23:59 |
3 | 31.3. 2020 | Music Generation | Vojtěch Černý | PPTX |
Python 3 | HW3 – Music | 5 | 14.4. 23:59 |
4 | 14.4. 2020 | Answer Set Programming | Vojtěch Černý | PPTX |
Python 3 Clingo (instructions in slides) |
HW4 – Murder Mystery | 5 | 27.4. 23:59 |
5 | 28.4. 2020 | Roguelike – dungeon (part 1 / 2) | Vojtěch Černý | PPTX |
Java (11+) (recommended) IntelliJ IDEA |
HW5.1 – Dungeon | 5 | 11.5. 23:59 |
6 | 12.5. 2020 | Roguelike – game (part 2 / 2) | Vojtěch Černý | PPTX |
Java (11+) (recommended) IntelliJ IDEA |
HW5.2 – Rogue-like | 5 | 25.5. 23:59 |
Featured procedural music of students
Author | Album Title | Link |
Jiří Berný | Free Pixels | Soundcloud |
Jan Holan | Normal Anxiety | Soundcloud |
Ondřej Černý | Bear Snake | Soundcloud |
Karel Vlachovský | popular_kitty | Soundcloud |