Procedural Content Generation in Computer Games (Summer 2019/20)

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
PDF
1 25.2.2020 Terrain Generation Vojtěch Černý Terrain Generation Approaches
Noise functions
PPTX
PDF
2 10.3.2020 Search and evaluation Vojtěch Černý Different approach to PCG
Content representation
Search algorithms
Fitness functions
Evaluating procedural content
PPTX
PDF
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
PDF
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
PDF
Java (11+)
Python 3
(recommended) IntelliJ IDEA
HW2 – Mario 5 30.3. 23:59
3 31.3. 2020 Music Generation Vojtěch Černý PPTX
PDF
Python 3 HW3 – Music 5 14.4. 23:59
4 14.4. 2020 Answer Set Programming Vojtěch Černý PPTX
PDF
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
PDF
 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
PDF
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

Table with points

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