diff options
Diffstat (limited to 'apps/plugins/maze.c')
-rw-r--r-- | apps/plugins/maze.c | 437 |
1 files changed, 437 insertions, 0 deletions
diff --git a/apps/plugins/maze.c b/apps/plugins/maze.c new file mode 100644 index 0000000000..e558ea1799 --- /dev/null +++ b/apps/plugins/maze.c | |||
@@ -0,0 +1,437 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2007 Matthias Wientapper | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | |||
20 | |||
21 | /* This is the implementation of a maze generation algorithm. | ||
22 | * The generated mazes are "perfect", i.e. there is one and only | ||
23 | * one path from any point in the maze to any other point. | ||
24 | * | ||
25 | * | ||
26 | * The implemented algorithm is called "Depth-First search", the | ||
27 | * solving is done by a dead-end filler routine. | ||
28 | * | ||
29 | */ | ||
30 | |||
31 | #include "plugin.h" | ||
32 | #include "pluginlib_actions.h" | ||
33 | |||
34 | PLUGIN_HEADER | ||
35 | |||
36 | #define MAZE_NEW PLA_START | ||
37 | #define MAZE_QUIT PLA_QUIT | ||
38 | #define MAZE_SOLVE PLA_FIRE | ||
39 | |||
40 | #define MAZE_RIGHT PLA_RIGHT | ||
41 | #define MAZE_LEFT PLA_LEFT | ||
42 | #define MAZE_UP PLA_UP | ||
43 | #define MAZE_DOWN PLA_DOWN | ||
44 | #define MAZE_RRIGHT PLA_RIGHT_REPEAT | ||
45 | #define MAZE_RLEFT PLA_LEFT_REPEAT | ||
46 | #define MAZE_RUP PLA_UP_REPEAT | ||
47 | #define MAZE_RDOWN PLA_DOWN_REPEAT | ||
48 | |||
49 | |||
50 | /* propertie bits of the cell */ | ||
51 | #define WALL_N 0x00000001 | ||
52 | #define WALL_E 0x00000002 | ||
53 | #define WALL_S 0x00000004 | ||
54 | #define WALL_W 0x00000008 | ||
55 | #define WALL_ALL 0x0000000F | ||
56 | |||
57 | #define BORDER_N 0x00000010 | ||
58 | #define BORDER_E 0x00000020 | ||
59 | #define BORDER_S 0x00000040 | ||
60 | #define BORDER_W 0x00000080 | ||
61 | #define PATH 0x00000100 | ||
62 | |||
63 | static struct plugin_api* rb; | ||
64 | const struct button_mapping *plugin_contexts[] | ||
65 | = {generic_directions, generic_actions}; | ||
66 | |||
67 | #if ( LCD_WIDTH == 112 ) | ||
68 | #define MAZE_WIDTH 16 | ||
69 | #define MAZE_HEIGHT 12 | ||
70 | #else | ||
71 | #define MAZE_WIDTH 32 | ||
72 | #define MAZE_HEIGHT 24 | ||
73 | #endif | ||
74 | |||
75 | unsigned short maze[MAZE_WIDTH][MAZE_HEIGHT]; | ||
76 | unsigned short solved_maze[MAZE_WIDTH][MAZE_HEIGHT]; | ||
77 | |||
78 | int stack[MAZE_WIDTH*MAZE_HEIGHT]; | ||
79 | int solved = false; | ||
80 | char buf[30]; | ||
81 | |||
82 | int sy = 0; | ||
83 | int sx = 0; | ||
84 | |||
85 | |||
86 | void init_maze(void){ | ||
87 | int x, y; | ||
88 | |||
89 | rb->memset(maze, 0, sizeof(maze)); | ||
90 | sx = 0; | ||
91 | sy = 0; | ||
92 | |||
93 | for(y=0; y<MAZE_HEIGHT; y++){ | ||
94 | for(x=0; x<MAZE_WIDTH; x++){ | ||
95 | |||
96 | /* all walls are up */ | ||
97 | maze[x][y] |= WALL_ALL | PATH; | ||
98 | |||
99 | /* setup borders */ | ||
100 | if(x == 0) | ||
101 | maze[x][y]|= BORDER_W; | ||
102 | if(y == 0) | ||
103 | maze[x][y]|= BORDER_N; | ||
104 | if(x == MAZE_WIDTH-1) | ||
105 | maze[x][y]|= BORDER_E; | ||
106 | if(y == MAZE_HEIGHT-1) | ||
107 | maze[x][y]|= BORDER_S; | ||
108 | } | ||
109 | } | ||
110 | } | ||
111 | |||
112 | void show_maze(void){ | ||
113 | int x, y; | ||
114 | int wx, wy; | ||
115 | unsigned short cell; | ||
116 | |||
117 | wx = (int) LCD_WIDTH / MAZE_WIDTH; | ||
118 | wy = (int) LCD_HEIGHT / MAZE_HEIGHT; | ||
119 | |||
120 | rb->lcd_clear_display(); | ||
121 | |||
122 | for(y=0; y<MAZE_HEIGHT; y++){ | ||
123 | for(x=0; x<MAZE_WIDTH; x++){ | ||
124 | |||
125 | cell = maze[x][y]; | ||
126 | |||
127 | /* draw walls */ | ||
128 | if(cell & WALL_N) | ||
129 | rb->lcd_drawline(x*wx, y*wy, x*wx+wx, y*wy); | ||
130 | if(cell & WALL_E) | ||
131 | rb->lcd_drawline(x*wx+wx, y*wy, x*wx+wx, y*wy+wy); | ||
132 | if(cell & WALL_S) | ||
133 | rb->lcd_drawline(x*wx, y*wy+wy, x*wx+wx, y*wy+wy); | ||
134 | if(cell & WALL_W) | ||
135 | rb->lcd_drawline(x*wx, y*wy, x*wx, y*wy+wy); | ||
136 | |||
137 | if(cell & BORDER_N) | ||
138 | rb->lcd_drawline(x*wx, y*wy, x*wx+wx, y*wy); | ||
139 | if(cell & BORDER_E) | ||
140 | rb->lcd_drawline(x*wx+wx, y*wy, x*wx+wx, y*wy+wy); | ||
141 | if(cell & BORDER_S) | ||
142 | rb->lcd_drawline(x*wx, y*wy+wy, x*wx+wx, y*wy+wy); | ||
143 | if(cell & BORDER_W) | ||
144 | rb->lcd_drawline(x*wx, y*wy, x*wx, y*wy+wy); | ||
145 | |||
146 | if(solved){ | ||
147 | if(cell & PATH){ | ||
148 | #if LCD_DEPTH >= 16 | ||
149 | rb->lcd_set_foreground( LCD_RGBPACK( 127, 127, 127 )); | ||
150 | #elif LCD_DEPTH == 2 | ||
151 | rb->lcd_set_foreground(1); | ||
152 | #endif | ||
153 | rb->lcd_fillrect(x*wx+2, y*wy+2, wx-3, wy-3); | ||
154 | #if LCD_DEPTH >= 16 | ||
155 | rb->lcd_set_foreground( LCD_RGBPACK( 0, 0, 0)); | ||
156 | #elif LCD_DEPTH == 2 | ||
157 | rb->lcd_set_foreground(0); | ||
158 | #endif | ||
159 | } | ||
160 | } | ||
161 | } | ||
162 | } | ||
163 | |||
164 | /* mark start and end */ | ||
165 | rb->lcd_drawline(0, 0, wx, wy); | ||
166 | rb->lcd_drawline(0, wy, wx, 0); | ||
167 | rb->lcd_drawline((MAZE_WIDTH-1)*wx,(MAZE_HEIGHT-1)*wy, | ||
168 | (MAZE_WIDTH-1)*wx+wx, (MAZE_HEIGHT-1)*wy+wy); | ||
169 | rb->lcd_drawline((MAZE_WIDTH-1)*wx,(MAZE_HEIGHT-1)*wy+wy, | ||
170 | (MAZE_WIDTH-1)*wx+wx, (MAZE_HEIGHT-1)*wy); | ||
171 | |||
172 | |||
173 | /* draw current position */ | ||
174 | rb->lcd_fillrect(sx*wx+2, sy*wy+2, wx-3, wy-3); | ||
175 | |||
176 | rb->lcd_update(); | ||
177 | } | ||
178 | |||
179 | |||
180 | int random_neighbour_cell_with_walls(int *px, int *py, int *pnx, int *pny){ | ||
181 | |||
182 | int ncount = 0; | ||
183 | int neighbours[4]; | ||
184 | int found_cell; | ||
185 | |||
186 | |||
187 | /* look for neighbour cells with walls */ | ||
188 | |||
189 | /* north */ | ||
190 | if(!(maze[*px][*py] & BORDER_N)){ | ||
191 | if((maze[*px][*py-1] & WALL_ALL) == WALL_ALL){ | ||
192 | /* save found cell coordinates */ | ||
193 | neighbours[ncount]=(*px<<8)|((*py)-1); | ||
194 | ncount++; | ||
195 | } | ||
196 | } | ||
197 | |||
198 | /* west */ | ||
199 | if(!(maze[*px][*py] & BORDER_W)){ | ||
200 | if((maze[*px-1][*py] & WALL_ALL) == WALL_ALL){ | ||
201 | /* save found cell coordinates */ | ||
202 | neighbours[ncount]=((*px-1)<<8)|(*py); | ||
203 | ncount++; | ||
204 | } | ||
205 | } | ||
206 | |||
207 | /* east */ | ||
208 | if(!(maze[*px][*py] & BORDER_E)){ | ||
209 | if((maze[*px+1][*py] & WALL_ALL) == WALL_ALL){ | ||
210 | /* save found cell coordinates */ | ||
211 | neighbours[ncount]=((*px+1)<<8)|(*py); | ||
212 | ncount++; | ||
213 | } | ||
214 | } | ||
215 | |||
216 | /* south */ | ||
217 | if(!(maze[*px][*py] & BORDER_S)){ | ||
218 | if((maze[*px][*py+1] & WALL_ALL) == WALL_ALL){ | ||
219 | /* save found cell coordinates */ | ||
220 | neighbours[ncount]=(*px<<8)|((*py)+1); | ||
221 | ncount++; | ||
222 | } | ||
223 | } | ||
224 | |||
225 | /* randomly select neighbour cell with walls */ | ||
226 | if(ncount!=0){ | ||
227 | found_cell = neighbours[rb->rand()%ncount]; | ||
228 | *pny = found_cell &0x000000ff; | ||
229 | *pnx = (unsigned int) found_cell >> 8; | ||
230 | } | ||
231 | return ncount; | ||
232 | } | ||
233 | |||
234 | void remove_walls(int *px, int *py, int *pnx, int *pny){ | ||
235 | |||
236 | /* where is our neighbour? */ | ||
237 | |||
238 | /* north or south */ | ||
239 | if(*px==*pnx){ | ||
240 | if(*py<*pny){ | ||
241 | /*south*/ | ||
242 | maze[*px][*py] &= ~WALL_S; | ||
243 | maze[*pnx][*pny] &= ~WALL_N; | ||
244 | } else { | ||
245 | /*north*/ | ||
246 | maze[*px][*py] &= ~WALL_N; | ||
247 | maze[*pnx][*pny] &= ~WALL_S; | ||
248 | } | ||
249 | } else { | ||
250 | /* east or west */ | ||
251 | if(*py==*pny){ | ||
252 | if(*px<*pnx){ | ||
253 | /* east */ | ||
254 | maze[*px][*py] &= ~WALL_E; | ||
255 | maze[*pnx][*pny] &= ~WALL_W; | ||
256 | |||
257 | } else { | ||
258 | /*west*/ | ||
259 | maze[*px][*py] &= ~WALL_W; | ||
260 | maze[*pnx][*pny] &= ~WALL_E; | ||
261 | } | ||
262 | } | ||
263 | } | ||
264 | } | ||
265 | |||
266 | |||
267 | void generate_maze(void){ | ||
268 | int stp = 0; | ||
269 | int total_cells = MAZE_WIDTH * MAZE_HEIGHT; | ||
270 | int visited_cells; | ||
271 | int neighbour_cell; | ||
272 | int x, y; | ||
273 | int nx = 0; | ||
274 | int ny = 0; | ||
275 | int *px, *py, *pnx, *pny; | ||
276 | |||
277 | px = &x; | ||
278 | py = &y; | ||
279 | pnx = &nx; | ||
280 | pny = &ny; | ||
281 | |||
282 | x = rb->rand()%MAZE_WIDTH; | ||
283 | y = rb->rand()%MAZE_HEIGHT; | ||
284 | |||
285 | visited_cells = 1; | ||
286 | while (visited_cells < total_cells){ | ||
287 | neighbour_cell = random_neighbour_cell_with_walls(px, py, pnx, pny); | ||
288 | if(neighbour_cell == 0){ | ||
289 | |||
290 | /* pop from stack */ | ||
291 | stp--; | ||
292 | *py = stack[stp]; | ||
293 | *py &= 0xff; | ||
294 | *px = (stack[stp])>>8; | ||
295 | } else { | ||
296 | remove_walls(px, py, pnx, pny); | ||
297 | |||
298 | /* save position on the stack */ | ||
299 | stack[stp] = ((*px<<8)|*py); | ||
300 | stp++; | ||
301 | /* current cell = neighbour cell */ | ||
302 | x=nx; | ||
303 | y=ny; | ||
304 | |||
305 | visited_cells++; | ||
306 | } | ||
307 | } | ||
308 | } | ||
309 | |||
310 | |||
311 | void solve_maze(void){ | ||
312 | int x, y; | ||
313 | unsigned short cell; | ||
314 | unsigned short w; | ||
315 | int dead_ends = 1; | ||
316 | |||
317 | /* dead end filler*/ | ||
318 | |||
319 | /* copy maze for solving */ | ||
320 | rb->memcpy(solved_maze, maze, (MAZE_HEIGHT*MAZE_WIDTH*sizeof(maze[0][0]))); | ||
321 | |||
322 | |||
323 | /* remove some borders and walls on start and end point */ | ||
324 | solved_maze[0][0] &= ~(WALL_N|BORDER_N); | ||
325 | solved_maze[MAZE_WIDTH-1][MAZE_HEIGHT-1] &= ~(WALL_S|BORDER_S); | ||
326 | |||
327 | while(dead_ends){ | ||
328 | dead_ends = 0; | ||
329 | /* scan for dead ends */ | ||
330 | for(y=0; y<MAZE_HEIGHT; y++){ | ||
331 | rb->yield(); | ||
332 | for(x=0; x<MAZE_WIDTH; x++){ | ||
333 | cell = solved_maze[x][y]; | ||
334 | w = ~cell & 0x000f; | ||
335 | if(w == WALL_N || | ||
336 | w == WALL_E || | ||
337 | w == WALL_S || | ||
338 | w == WALL_W){ | ||
339 | /* found dead end, clear path bit and fill it up */ | ||
340 | maze[x][y] &= ~PATH; | ||
341 | solved_maze[x][y] |= WALL_ALL; | ||
342 | /* don't forget the neighbours */ | ||
343 | if(!(cell & BORDER_N)) | ||
344 | solved_maze[x][y-1]|=WALL_S; | ||
345 | if(!(cell & BORDER_E)) | ||
346 | solved_maze[x+1][y]|=WALL_W; | ||
347 | if(!(cell & BORDER_S)) | ||
348 | solved_maze[x][y+1]|=WALL_N; | ||
349 | if(!(cell & BORDER_W)) | ||
350 | solved_maze[x-1][y]|=WALL_E; | ||
351 | dead_ends++; | ||
352 | } | ||
353 | } | ||
354 | } | ||
355 | } | ||
356 | } | ||
357 | |||
358 | /**********************************/ | ||
359 | /* this is the plugin entry point */ | ||
360 | /**********************************/ | ||
361 | enum plugin_status plugin_start(struct plugin_api* api, void* parameter) | ||
362 | { | ||
363 | int button = 0; | ||
364 | int quit = 0; | ||
365 | |||
366 | (void)parameter; | ||
367 | rb = api; | ||
368 | |||
369 | rb->backlight_set_timeout(1); | ||
370 | #if LCD_DEPTH > 1 | ||
371 | rb->lcd_set_backdrop(NULL); | ||
372 | rb->lcd_set_background(LCD_DEFAULT_BG); | ||
373 | #endif | ||
374 | |||
375 | init_maze(); | ||
376 | generate_maze(); | ||
377 | show_maze(); | ||
378 | |||
379 | while(!quit) { | ||
380 | button = pluginlib_getaction(rb, TIMEOUT_BLOCK, plugin_contexts, 2); | ||
381 | switch(button) { | ||
382 | case MAZE_NEW: | ||
383 | solved = false; | ||
384 | init_maze(); | ||
385 | generate_maze(); | ||
386 | show_maze(); | ||
387 | break; | ||
388 | case MAZE_SOLVE: | ||
389 | solved = ~solved; | ||
390 | solve_maze(); | ||
391 | show_maze(); | ||
392 | break; | ||
393 | case MAZE_RIGHT: | ||
394 | case MAZE_RRIGHT: | ||
395 | if( !(maze[sx][sy] & WALL_E) && !(maze[sx][sy] & BORDER_E)){ | ||
396 | sx++; | ||
397 | show_maze(); | ||
398 | } | ||
399 | break; | ||
400 | case MAZE_LEFT: | ||
401 | case MAZE_RLEFT: | ||
402 | if( !(maze[sx][sy] & WALL_W) && !(maze[sx][sy] & BORDER_W)){ | ||
403 | sx--; | ||
404 | show_maze(); | ||
405 | } | ||
406 | break; | ||
407 | case MAZE_UP: | ||
408 | case MAZE_RUP: | ||
409 | if( !(maze[sx][sy] & WALL_N) && !(maze[sx][sy] & BORDER_N)){ | ||
410 | sy--; | ||
411 | show_maze(); | ||
412 | } | ||
413 | break; | ||
414 | case MAZE_DOWN: | ||
415 | case MAZE_RDOWN: | ||
416 | if( !(maze[sx][sy] & WALL_S) && !(maze[sx][sy] & BORDER_S)){ | ||
417 | sy++; | ||
418 | show_maze(); | ||
419 | } | ||
420 | break; | ||
421 | |||
422 | case MAZE_QUIT: | ||
423 | /* quit plugin */ | ||
424 | quit=true; | ||
425 | return PLUGIN_OK; | ||
426 | break; | ||
427 | default: | ||
428 | if (rb->default_event_handler(button) == SYS_USB_CONNECTED) { | ||
429 | return PLUGIN_USB_CONNECTED; | ||
430 | } | ||
431 | break; | ||
432 | } | ||
433 | rb->yield(); | ||
434 | } | ||
435 | rb->backlight_set_timeout(rb->global_settings->backlight_timeout); | ||
436 | return PLUGIN_OK; | ||
437 | } | ||