-
Notifications
You must be signed in to change notification settings - Fork 0
/
diamond.html
152 lines (151 loc) · 9.99 KB
/
diamond.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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
<html><head><title>niplav</title>
<link href="./favicon.png" rel="shortcut icon" type="image/png"/>
<link href="main.css" rel="stylesheet" type="text/css"/>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type"/>
<!DOCTYPE HTML>
<style type="text/css">
code.has-jax {font: inherit; font-size: 100%; background: inherit; border: inherit;}
</style>
<script async="" src="./mathjax/latest.js?config=TeX-MML-AM_CHTML" type="text/javascript">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js"],
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
},
"HTML-CSS": { availableFonts: ["TeX"] }
});
</script>
<script>
document.addEventListener('DOMContentLoaded', function () {
// Change the title to the h1 header
var title = document.querySelector('h1')
if(title) {
var title_elem = document.querySelector('title')
title_elem.textContent=title.textContent + " – niplav"
}
});
</script>
</head><body><h2 id="home"><a href="./index.html">home</a></h2>
<p><em>author: niplav, created: 2020-11-20, modified: 2024-12-15, language: english, status: in progress, importance: 4, confidence: highly likely</em></p>
<blockquote>
<p><strong>The <a href="https://en.wikipedia.org/wiki/Diamond-square_algorithm">Diamond-Square
algorithm</a>
is a terrain-generation algorithm for two dimensions (producing a
three-dimensional terrain). I generalize the algorithm to any positive
number of dimensions, and analyze the resulting algorithm.</strong></p>
</blockquote><div class="toc"><div class="toc-title">Contents</div><ul><li><a href="#Description">Description</a><ul></ul></li><li><a href="#The_Long_Diamond__Long_Square_Spectrum">The Long Diamond ⇔ Long Square Spectrum</a><ul><li><a href="#Long_Diamond">Long Diamond</a><ul><li><a href="#Diamond">Diamond</a><ul></ul></li><li><a href="#Square">Square</a><ul></ul></li></ul></li></ul></li><li><a href="#Analysis">Analysis</a><ul></ul></li><li><a href="#Results">Results</a><ul><li><a href="#One_Dimension">One Dimension</a><ul></ul></li><li><a href="#Two_Dimensions">Two Dimensions</a><ul></ul></li><li><a href="#Three_Dimensions">Three Dimensions</a><ul></ul></li></ul></li></ul></div>
<h1 id="Generalizing_the_DiamondSquare_Algorithm_to_n_Dimensions"><a class="hanchor" href="#Generalizing_the_DiamondSquare_Algorithm_to_n_Dimensions">Generalizing the Diamond-Square Algorithm to n Dimensions</a></h1>
<blockquote>
<p>Libre de la metáfora y del mito<br/>
labra un arduo cristal: el infinito<br/>
mapa de Aquel que es todas Sus estrellas.</p>
</blockquote>
<p><em>— <a href="https://en.wikipedia.org/wiki/Jorge_Luis_Borges">Jorge Luis Borges</a>, <a href="https://thefunambulist.net/literature/litterature-spinoza-by-borges">“Spinoza”</a>, 1964</em></p>
<p>I learned of the diamond-square algorithm by reading through the archives
of <a href="https://nullprogram.com/">Chris Wellon's blog</a>, specifically his post
on <a href="https://nullprogram.com/blog/2007/11/20">noise fractals</a> and terrain
generation. The algorithm is a fairly simple and old one (dating back
to the 80s), but not being interested in graphics or game programming,
I shelved it as a curiosity.</p>
<p>However, a while later I needed a way to generate high-dimensional
landscapes for <a href="./toy_ai_takeoff_model.html">a simulation</a>, and
remembered the algorithm, I felt like I could contribute something here
by generalizing the algorithm to produce landscapes in an arbitrary number
of dimensions, and that this would be a fun challenge to sharpen my (then
fairly weak) Python and <a href="https://en.wikipedia.org/wiki/NumPy">numpy</a>
skills.</p>
<h2 id="Description"><a class="hanchor" href="#Description">Description</a></h2>
<p>The original (2-dimensional) diamond-square algorithm, in its simplest
form, starts with a <code>$2^n+1 \times 2^n+1$</code> grid of numbers.</p>
<p>It is easiest explained visually:</p>
<p><img alt="" src="./img/diamond/diamond_square.png"/></p>
<ol>
<li>Either a user or the algorithm itself assigns the four corners some values, which can be random.</li>
<li>In the <strong>diamond step</strong> after that, the value in the middle of the grid is determined as the average of the four values in the corners, plus a random value.</li>
<li>Next, the middle value every "face" of the grid is determined by the average of the three values in orthogonal directions plus a random value—the <strong>square step</strong>.</li>
<li>The grid is broken down into four sub-grids, and each sub-grid undergoes the <strong>diamond step</strong> and the <strong>square step</strong>. The only difference is in the square step: If a point on the grid lies at the face of two sub-grids, it receives the average of all four orthogonal points.</li>
<li>The algorithm terminates if each sub-grid is of size <code>$1 \times 1$</code>.</li>
</ol>
<p>For <code>$n$</code> dimensions, do that, just higher-dimensional.</p>
<hr/>
<p>We start by initializing an n-dimensional space with zeros, and the
corners with random values:</p>
<pre><code>def create_space(dim, size, minval, maxval, factor):
space=np.zeros([size]*dim)
corners=(size-1)*get_cornerspos(dim)
space[*(corners.T)]=np.random.randint(minval, maxval, size=len(corners))
</code></pre>
<p>Here, <code>get_cornerspos</code> is just the one-liner
<code>return np.array(list(itertools.product([0, 1], repeat=dim)))</code>.</p>
<p>We then intialize the variable <code>offsets</code>, and call the recursive
diamond-square algorithm:</p>
<pre><code> offsets=[np.array([0]*dim)]
return ndim_diamond_square_rec(space, dim, size, offsets, minval, maxval, factor)
</code></pre>
<p>Now there are two possible variants of the generalized diamond-square
algorithm: the Long Diamond variation and the Long Square variation.</p>
<h2 id="The_Long_Diamond__Long_Square_Spectrum"><a class="hanchor" href="#The_Long_Diamond__Long_Square_Spectrum">The Long Diamond ⇔ Long Square Spectrum</a></h2>
<p>Let's take a 3×3×3 cubical grid and think about how we can run the
diamond-square algorithm on it.</p>
<p><strong>One way</strong> of doing so would be to calculate the center of the cube as
the mean of all the corners, and then the center of each face as the mean
of its corners. The value for the midpoint of each edge is calculated
from the midpoints of the edges and the centers adjacent faces.</p>
<p><video controls="" src="./vid/diamond/long_diamond.mp4" type="video/mp4">
</video></p>
<p>I call this variant the <strong>Long Diamond</strong> variant. It performs <em>two</em>
diamond steps and only one square step along the three dimensions.</p>
<p>But there's <strong>another way</strong>: Calculate the center of the cube as the
mean of its corners, just as before. But now go directly to the edges
and calculate their midpoints as the mean of the endpoints of each edge.
Then, calculate the value of each face as the mean of the value in the
center of the cube <em>and</em> the centers of the adjacent edges.</p>
<p><video controls="" src="./vid/diamond/long_square.mp4" type="video/mp4">
</video></p>
<p>That is the <strong>Long Square</strong> variant: It performs one diamond step
(computing the value for the center) and two square steps (for edges
and for faces).</p>
<p>Consecutive diamond steps go from <em>higher</em> dimensions to <em>lower</em>
ones, consecutive square steps go from <em>lower</em> dimensions to <em>higher</em>
ones. There is one dimension where the values are "stitched together"—in
the long diamond case it's the first dimension (on edges), in the long
square step it's the second dimension (on faces). I guess one could
also leave out the diamond steps together and calculate the center of
the cube as the mean of the faces—zero diamond, very long square.</p>
<h3 id="Long_Diamond"><a class="hanchor" href="#Long_Diamond">Long Diamond</a></h3>
<p>The diamond step of the algorithm starts out with the base case: If the
space is only one element big, we return and do nothing (assuming the
value has been filled in):</p>
<pre><code>def ndim_diamond_square_rec(space, dim, size, offsets, minval, maxval, factor):
if size<=1:
return
</code></pre>
<p>We also have to update the size of any axis in the space (<em>not</em> the size
of the space itself), we are halving this every recursive call.</p>
<pre><code> nsize=size//2
</code></pre>
<p>Now we come to <code>offsets</code>. Remember above when after the first square
step, we moved into a diamond step on the smaller squares? <code>offsets</code>
describes where the "left lower corner" of those smaller squares is. We
initialized it with zeros, that way we start in a definite corner.</p>
<h4 id="Diamond"><a class="hanchor" href="#Diamond">Diamond</a></h4>
<h4 id="Square"><a class="hanchor" href="#Square">Square</a></h4>
<p>Code <a href="code/diamond/ndim_diamond_square.py">here</a>. I think this is probably
the 2nd-most beautiful code I've ever written, just after <a href="./99_problems_klong_solution.html#P25__Generate_a_random_permutation_of_the_elements_of_a_list">this absolute
smokeshow</a>.</p>
<h2 id="Analysis"><a class="hanchor" href="#Analysis">Analysis</a></h2>
<h2 id="Results"><a class="hanchor" href="#Results">Results</a></h2>
<h3 id="One_Dimension"><a class="hanchor" href="#One_Dimension">One Dimension</a></h3>
<p><img alt="Space generated by the algorithm in one dimension" src="./img/diamond/onedim.png" title="Space generated by the algorithm in one dimension"/></p>
<h3 id="Two_Dimensions"><a class="hanchor" href="#Two_Dimensions">Two Dimensions</a></h3>
<p><img alt="Space generated by the algorithm in two dimensions" src="./img/diamond/twodim.png" title="Space generated by the algorithm in two dimensions"/></p>
<h3 id="Three_Dimensions"><a class="hanchor" href="#Three_Dimensions">Three Dimensions</a></h3>
<!--TODO: slice plot perhaps-->
<p><img alt="Space generated by the algorithm in three dimensions" src="./img/diamond/threedim.png" title="Space generated by the algorithm in three dimensions"/></p>
</body></html>