diff options
author | Franklin Wei <frankhwei536@gmail.com> | 2016-11-20 15:16:41 -0500 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2016-12-18 18:13:22 +0100 |
commit | 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 (patch) | |
tree | 8e7f2d6b0cbdb5d15c13457b2c3e1de69f598440 /apps/plugins/puzzles/laydomino.c | |
parent | 3ee79724f6fb033d50e26ef37b33d3f8cedf0c5b (diff) | |
download | rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.tar.gz rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.zip |
Port of Simon Tatham's Puzzle Collection
Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9
MIT Licensed. Some games still crash and others are unplayable due to
issues with controls. Still need a "real" polygon filling algorithm.
Currently builds one plugin per puzzle (about 40 in total, around 100K
each on ARM), but can easily be made to build a single monolithic
overlay (800K or so on ARM).
The following games are at least partially broken for various reasons,
and have been disabled on this commit:
Cube: failed assertion with "Icosahedron" setting
Keen: input issues
Mines: weird stuff happens on target
Palisade: input issues
Solo: input issues, occasional crash on target
Towers: input issues
Undead: input issues
Unequal: input and drawing issues (concave polys)
Untangle: input issues
Features left to do:
- In-game help system
- Figure out the weird bugs
Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368
Diffstat (limited to 'apps/plugins/puzzles/laydomino.c')
-rw-r--r-- | apps/plugins/puzzles/laydomino.c | 291 |
1 files changed, 291 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/laydomino.c b/apps/plugins/puzzles/laydomino.c new file mode 100644 index 0000000000..458027020b --- /dev/null +++ b/apps/plugins/puzzles/laydomino.c | |||
@@ -0,0 +1,291 @@ | |||
1 | /* | ||
2 | * laydomino.c: code for performing a domino (2x1 tile) layout of | ||
3 | * a given area of code. | ||
4 | */ | ||
5 | |||
6 | #include <stdio.h> | ||
7 | #include <stdlib.h> | ||
8 | #include "rbassert.h" | ||
9 | |||
10 | #include "puzzles.h" | ||
11 | |||
12 | /* | ||
13 | * This function returns an array size w x h representing a grid: | ||
14 | * each grid[i] = j, where j is the other end of a 2x1 domino. | ||
15 | * If w*h is odd, one square will remain referring to itself. | ||
16 | */ | ||
17 | |||
18 | int *domino_layout(int w, int h, random_state *rs) | ||
19 | { | ||
20 | int *grid, *grid2, *list; | ||
21 | int wh = w*h; | ||
22 | |||
23 | /* | ||
24 | * Allocate space in which to lay the grid out. | ||
25 | */ | ||
26 | grid = snewn(wh, int); | ||
27 | grid2 = snewn(wh, int); | ||
28 | list = snewn(2*wh, int); | ||
29 | |||
30 | domino_layout_prealloc(w, h, rs, grid, grid2, list); | ||
31 | |||
32 | sfree(grid2); | ||
33 | sfree(list); | ||
34 | |||
35 | return grid; | ||
36 | } | ||
37 | |||
38 | /* | ||
39 | * As for domino_layout, but with preallocated buffers. | ||
40 | * grid and grid2 should be size w*h, and list size 2*w*h. | ||
41 | */ | ||
42 | void domino_layout_prealloc(int w, int h, random_state *rs, | ||
43 | int *grid, int *grid2, int *list) | ||
44 | { | ||
45 | int i, j, k, m, wh = w*h, todo, done; | ||
46 | |||
47 | /* | ||
48 | * To begin with, set grid[i] = i for all i to indicate | ||
49 | * that all squares are currently singletons. Later we'll | ||
50 | * set grid[i] to be the index of the other end of the | ||
51 | * domino on i. | ||
52 | */ | ||
53 | for (i = 0; i < wh; i++) | ||
54 | grid[i] = i; | ||
55 | |||
56 | /* | ||
57 | * Now prepare a list of the possible domino locations. There | ||
58 | * are w*(h-1) possible vertical locations, and (w-1)*h | ||
59 | * horizontal ones, for a total of 2*wh - h - w. | ||
60 | * | ||
61 | * I'm going to denote the vertical domino placement with | ||
62 | * its top in square i as 2*i, and the horizontal one with | ||
63 | * its left half in square i as 2*i+1. | ||
64 | */ | ||
65 | k = 0; | ||
66 | for (j = 0; j < h-1; j++) | ||
67 | for (i = 0; i < w; i++) | ||
68 | list[k++] = 2 * (j*w+i); /* vertical positions */ | ||
69 | for (j = 0; j < h; j++) | ||
70 | for (i = 0; i < w-1; i++) | ||
71 | list[k++] = 2 * (j*w+i) + 1; /* horizontal positions */ | ||
72 | assert(k == 2*wh - h - w); | ||
73 | |||
74 | /* | ||
75 | * Shuffle the list. | ||
76 | */ | ||
77 | shuffle(list, k, sizeof(*list), rs); | ||
78 | |||
79 | /* | ||
80 | * Work down the shuffled list, placing a domino everywhere | ||
81 | * we can. | ||
82 | */ | ||
83 | for (i = 0; i < k; i++) { | ||
84 | int horiz, xy, xy2; | ||
85 | |||
86 | horiz = list[i] % 2; | ||
87 | xy = list[i] / 2; | ||
88 | xy2 = xy + (horiz ? 1 : w); | ||
89 | |||
90 | if (grid[xy] == xy && grid[xy2] == xy2) { | ||
91 | /* | ||
92 | * We can place this domino. Do so. | ||
93 | */ | ||
94 | grid[xy] = xy2; | ||
95 | grid[xy2] = xy; | ||
96 | } | ||
97 | } | ||
98 | |||
99 | #ifdef GENERATION_DIAGNOSTICS | ||
100 | printf("generated initial layout\n"); | ||
101 | #endif | ||
102 | |||
103 | /* | ||
104 | * Now we've placed as many dominoes as we can immediately | ||
105 | * manage. There will be squares remaining, but they'll be | ||
106 | * singletons. So loop round and deal with the singletons | ||
107 | * two by two. | ||
108 | */ | ||
109 | while (1) { | ||
110 | #ifdef GENERATION_DIAGNOSTICS | ||
111 | for (j = 0; j < h; j++) { | ||
112 | for (i = 0; i < w; i++) { | ||
113 | int xy = j*w+i; | ||
114 | int v = grid[xy]; | ||
115 | int c = (v == xy+1 ? '[' : v == xy-1 ? ']' : | ||
116 | v == xy+w ? 'n' : v == xy-w ? 'U' : '.'); | ||
117 | putchar(c); | ||
118 | } | ||
119 | putchar('\n'); | ||
120 | } | ||
121 | putchar('\n'); | ||
122 | #endif | ||
123 | |||
124 | /* | ||
125 | * Our strategy is: | ||
126 | * | ||
127 | * First find a singleton square. | ||
128 | * | ||
129 | * Then breadth-first search out from the starting | ||
130 | * square. From that square (and any others we reach on | ||
131 | * the way), examine all four neighbours of the square. | ||
132 | * If one is an end of a domino, we move to the _other_ | ||
133 | * end of that domino before looking at neighbours | ||
134 | * again. When we encounter another singleton on this | ||
135 | * search, stop. | ||
136 | * | ||
137 | * This will give us a path of adjacent squares such | ||
138 | * that all but the two ends are covered in dominoes. | ||
139 | * So we can now shuffle every domino on the path up by | ||
140 | * one. | ||
141 | * | ||
142 | * (Chessboard colours are mathematically important | ||
143 | * here: we always end up pairing each singleton with a | ||
144 | * singleton of the other colour. However, we never | ||
145 | * have to track this manually, since it's | ||
146 | * automatically taken care of by the fact that we | ||
147 | * always make an even number of orthogonal moves.) | ||
148 | */ | ||
149 | k = 0; | ||
150 | for (j = 0; j < wh; j++) { | ||
151 | if (grid[j] == j) { | ||
152 | k++; | ||
153 | i = j; /* start BFS here. */ | ||
154 | } | ||
155 | } | ||
156 | if (k == (wh % 2)) | ||
157 | break; /* if area is even, we have no more singletons; | ||
158 | if area is odd, we have one singleton. | ||
159 | either way, we're done. */ | ||
160 | |||
161 | #ifdef GENERATION_DIAGNOSTICS | ||
162 | printf("starting b.f.s. at singleton %d\n", i); | ||
163 | #endif | ||
164 | /* | ||
165 | * Set grid2 to -1 everywhere. It will hold our | ||
166 | * distance-from-start values, and also our | ||
167 | * backtracking data, during the b.f.s. | ||
168 | */ | ||
169 | for (j = 0; j < wh; j++) | ||
170 | grid2[j] = -1; | ||
171 | grid2[i] = 0; /* starting square has distance zero */ | ||
172 | |||
173 | /* | ||
174 | * Start our to-do list of squares. It'll live in | ||
175 | * `list'; since the b.f.s can cover every square at | ||
176 | * most once there is no need for it to be circular. | ||
177 | * We'll just have two counters tracking the end of the | ||
178 | * list and the squares we've already dealt with. | ||
179 | */ | ||
180 | done = 0; | ||
181 | todo = 1; | ||
182 | list[0] = i; | ||
183 | |||
184 | /* | ||
185 | * Now begin the b.f.s. loop. | ||
186 | */ | ||
187 | while (done < todo) { | ||
188 | int d[4], nd, x, y; | ||
189 | |||
190 | i = list[done++]; | ||
191 | |||
192 | #ifdef GENERATION_DIAGNOSTICS | ||
193 | printf("b.f.s. iteration from %d\n", i); | ||
194 | #endif | ||
195 | x = i % w; | ||
196 | y = i / w; | ||
197 | nd = 0; | ||
198 | if (x > 0) | ||
199 | d[nd++] = i - 1; | ||
200 | if (x+1 < w) | ||
201 | d[nd++] = i + 1; | ||
202 | if (y > 0) | ||
203 | d[nd++] = i - w; | ||
204 | if (y+1 < h) | ||
205 | d[nd++] = i + w; | ||
206 | /* | ||
207 | * To avoid directional bias, process the | ||
208 | * neighbours of this square in a random order. | ||
209 | */ | ||
210 | shuffle(d, nd, sizeof(*d), rs); | ||
211 | |||
212 | for (j = 0; j < nd; j++) { | ||
213 | k = d[j]; | ||
214 | if (grid[k] == k) { | ||
215 | #ifdef GENERATION_DIAGNOSTICS | ||
216 | printf("found neighbouring singleton %d\n", k); | ||
217 | #endif | ||
218 | grid2[k] = i; | ||
219 | break; /* found a target singleton! */ | ||
220 | } | ||
221 | |||
222 | /* | ||
223 | * We're moving through a domino here, so we | ||
224 | * have two entries in grid2 to fill with | ||
225 | * useful data. In grid[k] - the square | ||
226 | * adjacent to where we came from - I'm going | ||
227 | * to put the address _of_ the square we came | ||
228 | * from. In the other end of the domino - the | ||
229 | * square from which we will continue the | ||
230 | * search - I'm going to put the distance. | ||
231 | */ | ||
232 | m = grid[k]; | ||
233 | |||
234 | if (grid2[m] < 0 || grid2[m] > grid2[i]+1) { | ||
235 | #ifdef GENERATION_DIAGNOSTICS | ||
236 | printf("found neighbouring domino %d/%d\n", k, m); | ||
237 | #endif | ||
238 | grid2[m] = grid2[i]+1; | ||
239 | grid2[k] = i; | ||
240 | /* | ||
241 | * And since we've now visited a new | ||
242 | * domino, add m to the to-do list. | ||
243 | */ | ||
244 | assert(todo < wh); | ||
245 | list[todo++] = m; | ||
246 | } | ||
247 | } | ||
248 | |||
249 | if (j < nd) { | ||
250 | i = k; | ||
251 | #ifdef GENERATION_DIAGNOSTICS | ||
252 | printf("terminating b.f.s. loop, i = %d\n", i); | ||
253 | #endif | ||
254 | break; | ||
255 | } | ||
256 | |||
257 | i = -1; /* just in case the loop terminates */ | ||
258 | } | ||
259 | |||
260 | /* | ||
261 | * We expect this b.f.s. to have found us a target | ||
262 | * square. | ||
263 | */ | ||
264 | assert(i >= 0); | ||
265 | |||
266 | /* | ||
267 | * Now we can follow the trail back to our starting | ||
268 | * singleton, re-laying dominoes as we go. | ||
269 | */ | ||
270 | while (1) { | ||
271 | j = grid2[i]; | ||
272 | assert(j >= 0 && j < wh); | ||
273 | k = grid[j]; | ||
274 | |||
275 | grid[i] = j; | ||
276 | grid[j] = i; | ||
277 | #ifdef GENERATION_DIAGNOSTICS | ||
278 | printf("filling in domino %d/%d (next %d)\n", i, j, k); | ||
279 | #endif | ||
280 | if (j == k) | ||
281 | break; /* we've reached the other singleton */ | ||
282 | i = k; | ||
283 | } | ||
284 | #ifdef GENERATION_DIAGNOSTICS | ||
285 | printf("fixup path completed\n"); | ||
286 | #endif | ||
287 | } | ||
288 | } | ||
289 | |||
290 | /* vim: set shiftwidth=4 :set textwidth=80: */ | ||
291 | |||