-
Notifications
You must be signed in to change notification settings - Fork 0
/
life.cc
286 lines (256 loc) · 12 KB
/
life.cc
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
#include "life.h"
#include <cstdlib>
#include <iostream>
namespace conway {
LiveLife::LiveLife()
: live_points_(new std::vector<const Point>()),
weights_(new std::unordered_map<const Point, int>()) {
// Picked via experimentation.
weights_->max_load_factor(0.33);
}
LiveLife::~LiveLife() {}
void LiveLife::AddLivePoint(const Point& p) {
live_points_->push_back(p);
}
// Iterates over all the live points and applies influence to the 3x3 block surrounding it.
// Influence is stored in a hashtable which means we require 9 hashtable lookups per live point.
// Afterwards, we iterate over the hashtable and replace the live_points_ vector with those points.
// The main benefit of this algorithm over a matrix based algorithm is that memory usage scales
// with number of points and not size of the board.
void LiveLife::DoStep() {
// For each live point, add 1 influence to the surrounding 8 cells.
for (auto p : *live_points_) {
weights_->emplace(Point(p.x - 1, p.y - 1), 0).first->second++;
weights_->emplace(Point(p.x - 1, p.y - 0), 0).first->second++;
weights_->emplace(Point(p.x - 1, p.y + 1), 0).first->second++;
weights_->emplace(Point(p.x - 0, p.y - 1), 0).first->second++;
// Add 1+10 to signal this cell was alive so we don't need to look it up later.
weights_->emplace(Point(p.x - 0, p.y - 0), 0).first->second += 11;
weights_->emplace(Point(p.x - 0, p.y + 1), 0).first->second++;
weights_->emplace(Point(p.x + 1, p.y - 1), 0).first->second++;
weights_->emplace(Point(p.x + 1, p.y - 0), 0).first->second++;
weights_->emplace(Point(p.x + 1, p.y + 1), 0).first->second++;
}
live_points_->clear();
for (auto it = weights_->begin(); it != weights_->end();) {
// Basic generational garbage collection --
// if the weight is still zero on this generation, erase it.
// Helps reduce memory allocations because most points need
// to be rechecked from generation to generation.
if (it->second == 0) {
it = weights_->erase(it);
continue;
}
if (it->second == 3 || it->second == 13 || it->second == 14) {
live_points_->push_back(it->first);
}
it->second = 0;
it++;
}
}
std::vector<const Point> LiveLife::LivePoints() {
return *live_points_;
}
const BlockLife::BlockArray BlockLife::EMPTY_BLOCK = BlockArray{{0}};
BlockLife::BlockLife()
: blocks_(new std::unordered_map<const Point, BlockArray>()),
new_blocks_(new std::unordered_map<const Point, BlockArray>()) {
}
BlockLife::~BlockLife() {}
Point BlockLife::toBlockIndex(const Point& p) {
return Point(p.x & BLOCK_MASK, p.y & BLOCK_MASK);
}
Point BlockLife::toBlockCoordinates(const Point& p) {
return Point(p.x & (~BLOCK_MASK), p.y & (~BLOCK_MASK));
}
void BlockLife::AddLivePoint(const Point& p) {
BlockArray& block = blocks_->emplace(toBlockIndex(p), EMPTY_BLOCK).first->second;
Point blockCoord = toBlockCoordinates(p);
block[blockCoord.y * BLOCK_DIM + blockCoord.x] = 1;
}
void BlockLife::DoStep() {
for (const auto& p : *blocks_) {
DoStepForBlock(p.first, p.second);
}
// Iterate over new_blocks_ converting weights into live and dead points.
// Remove any blocks that do not have any live points so we don't have bother checking them next generation.
for (auto it = new_blocks_->begin(); it != new_blocks_->end();) {
bool block_has_points = false;
for (int i = 0; i < it->second.size(); i++) {
it->second[i] = it->second[i] == 3 || it->second[i] == 13 || it->second[i] == 14;
block_has_points |= it->second[i];
}
if (!block_has_points) {
it = new_blocks_->erase(it);
} else {
++it;
}
}
new_blocks_.swap(blocks_);
new_blocks_->clear();
}
// Apply influence to each block of 9 cells around any live cell.
// Uses a 32x32 (1024 byte) block of memory which eliminates the need for hashtable
// lookups for the inner 30x30 square and reduces the number of hashtable lookups
// for the outer region to just one per neighboring region.
// Like LiveLife, this supports much larger boards than the simple matrix based approach,
// but it trades additional memory use and unrolled loops for speed in computing the next generation.
void BlockLife::DoStepForBlock(const Point& block_index, const BlockArray& block) {
BlockArray *b1,*b2,*b3;
BlockArray *b4,*b5,*b6;
BlockArray *b7,*b8,*b9;
// Determine the blocks we need.
if (block[(BLOCK_DIM - 1) * BLOCK_DIM + 0] == 1) { b1 = &(new_blocks_->emplace(Point(block_index.x - BLOCK_DIM, block_index.y + BLOCK_DIM), EMPTY_BLOCK).first->second); }
if (block[(BLOCK_DIM - 1) * BLOCK_DIM + (BLOCK_DIM - 1)] == 1) { b3 = &(new_blocks_->emplace(Point(block_index.x + BLOCK_DIM, block_index.y + BLOCK_DIM), EMPTY_BLOCK).first->second); }
if (block[0 * BLOCK_DIM + 0] == 1) { b7 = &(new_blocks_->emplace(Point(block_index.x - BLOCK_DIM, block_index.y - BLOCK_DIM), EMPTY_BLOCK).first->second); }
if (block[0 * BLOCK_DIM + (BLOCK_DIM - 1)] == 1) { b9 = &(new_blocks_->emplace(Point(block_index.x + BLOCK_DIM, block_index.y - BLOCK_DIM), EMPTY_BLOCK).first->second); }
bool needs_b2 = false;
bool needs_b4 = false;
bool needs_b6 = false;
bool needs_b8 = false;
for (int i = 0; i < BLOCK_DIM; i++) {
needs_b2 |= block[(BLOCK_DIM - 1) * BLOCK_DIM + i] == 1;
needs_b4 |= block[i * BLOCK_DIM + 0] == 1;
needs_b6 |= block[i * BLOCK_DIM + (BLOCK_DIM - 1)] == 1;
needs_b8 |= block[0 * BLOCK_DIM + i] == 1;
}
if (needs_b2) { b2 = &(new_blocks_->emplace(Point(block_index.x - 0, block_index.y + BLOCK_DIM), EMPTY_BLOCK).first->second); }
if (needs_b4) { b4 = &(new_blocks_->emplace(Point(block_index.x - BLOCK_DIM, block_index.y - 0), EMPTY_BLOCK).first->second); }
if (needs_b6) { b6 = &(new_blocks_->emplace(Point(block_index.x + BLOCK_DIM, block_index.y - 0), EMPTY_BLOCK).first->second); }
if (needs_b8) { b8 = &(new_blocks_->emplace(Point(block_index.x - 0, block_index.y - BLOCK_DIM), EMPTY_BLOCK).first->second); }
b5 = &(new_blocks_->emplace(Point(block_index.x, block_index.y), EMPTY_BLOCK).first->second);
// Inner block.
for (int y = 1; y < BLOCK_DIM - 1; y++) {
for (int x = 1; x < BLOCK_DIM - 1; x++) {
if (block[y * BLOCK_DIM + x] == 1) {
(*b5)[(y - 1) * BLOCK_DIM + (x - 1)] += 1;
(*b5)[(y - 1) * BLOCK_DIM + (x - 0)] += 1;
(*b5)[(y - 1) * BLOCK_DIM + (x + 1)] += 1;
(*b5)[(y - 0) * BLOCK_DIM + (x - 1)] += 1;
(*b5)[(y - 0) * BLOCK_DIM + (x - 0)] += 11; // Same +10 trick as above.
(*b5)[(y - 0) * BLOCK_DIM + (x + 1)] += 1;
(*b5)[(y + 1) * BLOCK_DIM + (x - 1)] += 1;
(*b5)[(y + 1) * BLOCK_DIM + (x - 0)] += 1;
(*b5)[(y + 1) * BLOCK_DIM + (x + 1)] += 1;
}
}
}
// Top Left Corner
if (block[(BLOCK_DIM - 1) * BLOCK_DIM + 0] == 1) {
(*b1)[0 * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b2)[0 * BLOCK_DIM + 0] += 1;
(*b2)[0 * BLOCK_DIM + 1] += 1;
(*b4)[(BLOCK_DIM - 1) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b5)[(BLOCK_DIM - 1) * BLOCK_DIM + 0] += 11;
(*b5)[(BLOCK_DIM - 1) * BLOCK_DIM + 1] += 1;
(*b4)[(BLOCK_DIM - 2) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b5)[(BLOCK_DIM - 2) * BLOCK_DIM + 0] += 1;
(*b5)[(BLOCK_DIM - 2) * BLOCK_DIM + 1] += 1;
}
// Top Right Corner
if (block[(BLOCK_DIM - 1) * BLOCK_DIM + (BLOCK_DIM - 1)]) {
(*b2)[0 * BLOCK_DIM + (BLOCK_DIM - 2)] += 1;
(*b2)[0 * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b3)[0 * BLOCK_DIM + 0] += 1;
(*b5)[(BLOCK_DIM - 1) * BLOCK_DIM + (BLOCK_DIM - 2)] += 1;
(*b5)[(BLOCK_DIM - 1) * BLOCK_DIM + (BLOCK_DIM - 1)] += 11;
(*b6)[(BLOCK_DIM - 1) * BLOCK_DIM + 0] += 1;
(*b5)[(BLOCK_DIM - 2) * BLOCK_DIM + (BLOCK_DIM - 2)] += 1;
(*b5)[(BLOCK_DIM - 2) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b6)[(BLOCK_DIM - 2) * BLOCK_DIM + 0] += 1;
}
// Lower Left Corner
if (block[0 * BLOCK_DIM + 0]) {
(*b4)[1 * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b5)[1 * BLOCK_DIM + 0] += 1;
(*b5)[1 * BLOCK_DIM + 1] += 1;
(*b4)[0 * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b5)[0 * BLOCK_DIM + 0] += 11;
(*b5)[0 * BLOCK_DIM + 1] += 1;
(*b7)[(BLOCK_DIM - 1) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b8)[(BLOCK_DIM - 1) * BLOCK_DIM + 0] += 1;
(*b8)[(BLOCK_DIM - 1) * BLOCK_DIM + 1] += 1;
}
// Lower Right Corner
if (block[0 * BLOCK_DIM + (BLOCK_DIM - 1)]) {
(*b5)[1 * BLOCK_DIM + (BLOCK_DIM - 2)] += 1;
(*b5)[1 * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b6)[1 * BLOCK_DIM + 0] += 1;
(*b5)[0 * BLOCK_DIM + (BLOCK_DIM - 2)] += 1;
(*b5)[0 * BLOCK_DIM + (BLOCK_DIM - 1)] += 11;
(*b6)[0 * BLOCK_DIM + 0] += 1;
(*b8)[(BLOCK_DIM - 1) * BLOCK_DIM + (BLOCK_DIM - 2)] += 1;
(*b8)[(BLOCK_DIM - 1) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b9)[(BLOCK_DIM - 1) * BLOCK_DIM + 0] += 1;
}
// Top row
for (int i = 1; i < BLOCK_DIM - 1; i++) {
if (block[(BLOCK_DIM - 1) * BLOCK_DIM + i] == 1) {
(*b2)[0 * BLOCK_DIM + (i - 1)] += 1;
(*b2)[0 * BLOCK_DIM + (i - 0)] += 1;
(*b2)[0 * BLOCK_DIM + (i + 1)] += 1;
(*b5)[(BLOCK_DIM - 1) * BLOCK_DIM + (i - 1)] += 1;
(*b5)[(BLOCK_DIM - 1) * BLOCK_DIM + (i - 0)] += 11;
(*b5)[(BLOCK_DIM - 1) * BLOCK_DIM + (i + 1)] += 1;
(*b5)[(BLOCK_DIM - 2) * BLOCK_DIM + (i - 1)] += 1;
(*b5)[(BLOCK_DIM - 2) * BLOCK_DIM + (i - 0)] += 1;
(*b5)[(BLOCK_DIM - 2) * BLOCK_DIM + (i + 1)] += 1;
}
}
// Bottom row
for (int i = 1; i < BLOCK_DIM - 1; i++) {
if (block[0 * BLOCK_DIM + i] == 1) {
(*b5)[1 * BLOCK_DIM + (i - 1)] += 1;
(*b5)[1 * BLOCK_DIM + (i - 0)] += 1;
(*b5)[1 * BLOCK_DIM + (i + 1)] += 1;
(*b5)[0 * BLOCK_DIM + (i - 1)] += 1;
(*b5)[0 * BLOCK_DIM + (i - 0)] += 11;
(*b5)[0 * BLOCK_DIM + (i + 1)] += 1;
(*b8)[(BLOCK_DIM - 1) * BLOCK_DIM + (i - 1)] += 1;
(*b8)[(BLOCK_DIM - 1) * BLOCK_DIM + (i - 0)] += 1;
(*b8)[(BLOCK_DIM - 1) * BLOCK_DIM + (i + 1)] += 1;
}
}
// Left column
for (int i = 1; i < BLOCK_DIM - 1; i++) {
if (block[i * BLOCK_DIM + 0] == 1) {
(*b4)[(i - 1) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b5)[(i - 1) * BLOCK_DIM + 0] += 1;
(*b5)[(i - 1) * BLOCK_DIM + 1] += 1;
(*b4)[(i - 0) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b5)[(i - 0) * BLOCK_DIM + 0] += 11;
(*b5)[(i - 0) * BLOCK_DIM + 1] += 1;
(*b4)[(i + 1) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b5)[(i + 1) * BLOCK_DIM + 0] += 1;
(*b5)[(i + 1) * BLOCK_DIM + 1] += 1;
}
}
// Right column
for (int i = 1; i < BLOCK_DIM - 1; i++) {
if (block[i * BLOCK_DIM + (BLOCK_DIM - 1)] == 1) {
(*b5)[(i - 1) * BLOCK_DIM + (BLOCK_DIM - 2)] += 1;
(*b5)[(i - 1) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b6)[(i - 1) * BLOCK_DIM + 0] += 1;
(*b5)[(i - 0) * BLOCK_DIM + (BLOCK_DIM - 2)] += 1;
(*b5)[(i - 0) * BLOCK_DIM + (BLOCK_DIM - 1)] += 11;
(*b6)[(i - 0) * BLOCK_DIM + 0] += 1;
(*b5)[(i + 1) * BLOCK_DIM + (BLOCK_DIM - 2)] += 1;
(*b5)[(i + 1) * BLOCK_DIM + (BLOCK_DIM - 1)] += 1;
(*b6)[(i + 1) * BLOCK_DIM + 0] += 1;
}
}
}
std::vector<const Point> BlockLife::LivePoints() {
std::vector<const Point> live_points;
for (auto pair : *blocks_) {
for (int y = 0; y < BLOCK_DIM; y++) {
for (int x = 0; x < BLOCK_DIM; x++) {
if (pair.second[y * BLOCK_DIM + x] == 1) {
live_points.emplace_back(pair.first.x + x, pair.first.y + y);
}
}
}
}
return live_points;
}
} // namespace conway