-
Notifications
You must be signed in to change notification settings - Fork 3
/
level_generation_using_markov_chains.html
114 lines (97 loc) · 5.27 KB
/
level_generation_using_markov_chains.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
<!DOCTYPE html>
<html lang="en">
<head>
<title>Level Generation Using Markov Chains | rxi</title>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=0.45">
<link rel="stylesheet" type="text/css" href="style.css">
</head>
<body>
<a class="logo" href="index.html"></a>
<h1 class="title">Level Generation Using Markov Chains</h1>
<div class="date">2020.08.29</div>
<img src="assets/markov_output2.png">
<div class="sections"><div class="section_item"><a href="#overview">Overview</a></div><div class="section_item"><a href="#introduction">Introduction</a></div><div class="section_item"><a href="#implementation">Implementation</a></div><div class="section_item"><a href="#entity_placement">Entity Placement</a></div><div class="section_item"><a href="#results">Results</a></div></div>
<h2 id="overview" class="section_header">Overview</h2>
<p>
This write-up details the use of <a class="link" href="https://en.wikipedia.org/wiki/Markov_chain">markov chains</a> for tilemap-based level generation in 2D games. The approach detailed here was used in the game <a class="link" href="https://rxi.itch.io/scanline">SCANLINE</a>, a small action platformer written during the 2017 CGA jam.
</p>
<h2 id="introduction" class="section_header">Introduction</h2>
<p>
Despite the simplicity of the implementation <em>(fewer than 100 lines of lua)</em> the use of markov chains can yield reasonable results. The feel and structure of generated levels can be quickly iterated on by simply changing the input map. More complex maps or different variations can be created by using a different or several different input maps.
</p>
<p>
The result is that we end up with interesting variations of maps — changing the feel of the generated map doesn't require any changes to code, only to that of the input.
</p>
<p>
As markov chains operate on one-dimensional sequences, the use of them for level generation is limited to levels that can be represented in such a way; thus even though the maps we're working with are represented by 2d arrays of tiles, we treat the data as a 1d array of tile "rows". This limitation makes the approach unsuitable for something like a traditional roguelike.
</p>
<h2 id="implementation" class="section_header">Implementation</h2>
<p>
The implementation used in this write-up has been written in Lua using the <a class="link" href="https://love2d.org">LÖVE</a> framework; for the purpose of this write-up a simple markov chains lua module was written, the implementation is available <a class="link" href="assets/markov.lua">here</a>.
</p>
<p>
The first requirement for this approach is to convert each <em>row</em> of the input tile map to a string such that it can be used with the module above. The tilemap is iterated and each tile of each row is converted to a byte in a string and pushed to a table; the table of rows can then be fed to the markov chain object.
</p>
<pre class="codeblock">
local markov = require "markov"
local mc = markov.new()
local width, height = 6, 7
local map = {
1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 1,
1, 1, 0, 0, 1, 1,
1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 1,
1, 1, 2, 2, 1, 1,
}
local rows = {}
for y = 0, height - 1 do
local row = ""
for x = 0, width - 1 do
row = row .. string.char(map[x + y * width + 1])
end
table.insert(rows, row)
end
mc:add(rows)
</pre>
<p>
This can be done several times with several pre-constructed input maps which we want the generated map to draw from. The map is generated by calling the the <code>generate</code> function. The simplest means of assuring the resultant map's length is within our desired bounds is to repeatedly generate the map.
</p>
<pre class="codeblock">
local rows
repeat
rows = mc:generate()
until #rows > 5 and #rows < 50
</pre>
<p>
Though a more efficient approach could be taken to guarantee the resultant map's length, due to the speed of generating the map, the brute-force approach works well enough in practise.
</p>
<p>
Once we have the resultant table of rows we can convert the table of row strings back to a tilemap.
</p>
<pre class="codeblock">
local map = {}
for i, row in ipairs(rows) do
local y, x = i - 1, 0
for chr in row:gmatch(".") do
map[x + y * width + 1] = string.byte(chr)
x = x + 1
end
end
</pre>
<h2 id="entity_placement" class="section_header">Entity Placement</h2>
<p>
As all level data is stored in the 2d map, for placement of entities (such as power-ups, enemies or other items) "special" tiles can be used to represent them. Once the map has been generated, we can scan for all these special tiles, remove them from the map and place the given entity at the tile's location.
</p>
<h2 id="results" class="section_header">Results</h2>
<p>Using the following map as our input data:</p>
<img src="assets/markov_input.png">
<p>A handful of resultant maps are generated:</p>
<img src="assets/markov_output.png">
<p>
The maps strike a good balance between randomly generated and handcrafted. That is they feel both organic and structured but, due to randomness, each is different enough to the other to provide something unique. Note that the level of variation in the output maps increases as the input map grows or if more input maps are used.
</p>
</body>
</html>