Procedural Content Generation in Computer Games (Summer 2020/21)

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 use some elementary knowledge of Java/Kotlin and Python (no prior knowledge of the languages required, with willingness you can learn as you go). The course is taught at MFF UK as NAIL123.

Permalink: bit.ly/mff-pcg-2020


News

Follow the appropriate channel at Gamedev Discord!
https://discord.gg/Zts98PGw6z


Dates (SIS)

Lectures will be interwoven with Labs on even / odd weeks, but the course starts with two consecutive lectures.

Due to the pandemic, all teaching will be remote. The lectures will be pre-recorded and you can watch them in your own time, but the labs will have an interactive online session. This session serves as a Q&A and will also introduce the homework.

Every session will start at 9:00, please disregard the confusing schedule in SIS.


Course Exam

There will be an oral examination done during the examination period, either in-person or online, depending on the situation. 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

This years lectures are pre-recorded, watch them at your leisure, but preferably before the interactive “labs” session, such that you can ask questions and understand homework!

Please, do not share the lectures publicly.

Lectures Schedule

No. Date Topic Lecturer Content Slides Video
0 2.3.2021 Introduction Vojtěch Černý What is Procedural Content Generation
Reason to use PCG
Brief history
Interesting implementations
Course structure
PDF (with notes) YouTube
1 8.3.2021 Terrain Vojtěch Černý Procedural terrain
Noise functions
Biomes
PDF (with notes) YouTube
2 23.3.2021 Search & Evaluation Vojtěch Černý Search-based approach to PCG
Template search
How to evaluate generated content
PDF (with notes) YouTube
3 6.4.2021 Procedural Art Vojtěch Černý Cellular automata
Graph & shape grammars
Art toys
Visual art
Procedural effects
Music
PDF (with notes) YouTube
4 20.4.2021 Constraints in PCG Vojtěch Černý Answer set programming
Procedural game rules
Mixed initiative approaches
Wave function collapse
PDF (with notes) YouTube
5 4.5.2021 Mazes & Dungeons Vojtěch Černý Mazes
Dungeons
Loot Systems
Puzzles
PDF (with notes) YouTube

Labs

The labs will consist of short introductions to specific PCG contexts (usually games) and homeworks.

A total of 5 homeworks worth 18 points total will be presented during the semester. 13 points are required for admittance to the exam, and any above 13 will be transferred to the exam points (Exam has a 50 point maximum and 40 points are needed to pass, so extra points are significant).

For the 1st practical please have 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 6 points. You should submit the first part, receive feedback, incorporate it and extend your work with the second part of the assignment.

Labs Schedule

No. Date Topic Lecturer Slides Prerequisites Homework HW pts Standard Deadline
1 16.3. 2020 Terrain Generation Vojtěch Černý PDF, PPTX Java (11+)
Git client
(basically necessary) IntelliJ IDEA
HW1 – Minecraft 3 29.3. 23:59
2 30.3.2020 Level Generation Vojtěch Černý PDF, PPTX Java
Python 3
(recommended) IntelliJ IDEA
HW2 – Mario 3 12.4. 23:59
3 13.4.2020 Music Vojtěch Černý PDF, PPTX Python 3 HW3 – Music 3 26.4. 23:59
4 27.4.2020 Murder Mystery Vojtěch Černý PDF, PPTX Python 3, Clingo HW4 – Murder Mystery 3 11.5. 23:59
5 11.5.2020 Dungeon Vojtěch Černý PDF, PPTX Java
(recommended) IntelliJ IDEA
HW5.1 – Dungeon 3 24.5. 23:59
6 25.5.2020 Roguelike Vojtěch Černý PDF, PPTX Java
(recommended) IntelliJ IDEA
HW5.2 – Roguelike 3 6.7.2021 23:59

Table with points

Author Album Title Link
Michaela Štolová Birthday Special Soundcloud
Martina Fusková Lively Icicle Soundcloud
Robert Wiesner PGM fit for old school dungeon crawling Soundcloud

https://gamedev.cuni.cz/wp-content/uploads/2018/10/logolink_OP_VVV_hor_barva_eng.jpg