c/app/maze.c · 7181 字节 · 下载原文
/* maze.c —— 迷宫(随机生成 + 走到出口)
* maze.c -- maze (randomly generated; walk to the exit)
*
* 玩法:每局**现生成**一张新迷宫(深度优先挖洞,一定连通、一定有路);
* Rules: every round **generates** a fresh maze (depth-first carving, always connected, always solvable);
* 方向键 / 点屏幕四边移动,走到右下角出口就算通关,按 ESC 换一张。
* arrow keys / tapping a screen edge move the player; reaching the bottom-right exit wins; ESC gives a
* new maze.
*
* 生成用的是**显式栈**(数组 + 栈顶下标),不是递归 —— 这一层的栈空间是 VM 给的固定额度,
* Generation uses an **explicit stack** (an array plus a top index), not recursion -- the stack on this
* layer is a fixed budget granted by the VM,
* 递归在这种规模上容易把栈吃掉(而且真出事的症状是"跑到一半没了",很不好查)。
* and recursion at this size can eat it (and when it does go wrong the symptom is "it just vanished
* halfway", which is hard to trace).
*
* 迷宫的表示:`(2N+1) × (2M+1)` 的格子图,1 = 墙、0 = 通路 —— 画的时候一格一个方块。
* Representation: a `(2N+1) x (2M+1)` cell map, 1 = wall, 0 = passage -- drawn as one square per cell.
*/
#include <vml_ui.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX_FRAMES 12000
#define MW 21 /* 地图宽(奇数) */
#define MH 21
#define STACK_MAX 512
#define C_BG 0xFF101018
#define C_WALL 0xFF2A2A36
#define C_PATH 0xFF1A1A24
#define C_PLAYER 0xFF51E86E
#define C_GOAL 0xFFE06C50
#define C_TEXT 0xFFE8E8F0
#define C_DIM 0xFF9AA0B0
static int SW, SH, g_lang, g_frames;
static int cell, ox, oy;
static int map[MW][MH];
static int px, py, won, steps;
static unsigned int seed = 20261123;
static int rnd(int n)
{
seed = seed * 1103515245u + 12345u;
return (int)((seed >> 16) % (unsigned int)n);
}
static void relayout(void)
{
int side;
SW = ui_scr_get_w();
SH = ui_scr_get_h();
if (SW <= 0) SW = 360;
if (SH <= 0) SH = 620;
{
int top;
int bottom;
top = (SH < 420 || SW < 360) ? 64 : 110;
bottom = (SH < 420 || SW < 360) ? 40 : 60;
side = SW - 16;
if (side > SH - top - bottom) side = SH - top - bottom;
if (side < 60) side = 60;
cell = side / MW;
if (cell < 3) cell = 3;
ox = (SW - MW * cell) / 2;
oy = top + (SH - top - bottom - MH * cell) / 2;
if (oy < top) oy = top;
}
}
/* 深度优先挖洞:从 (1,1) 出发,每次跳两格挖通中间那格 */
static void generate(void)
{
int sx[STACK_MAX], sy[STACK_MAX], top = 0;
int x, y, done = 0;
for (x = 0; x < MW; x++)
for (y = 0; y < MH; y++) map[x][y] = 1;
x = 1; y = 1;
map[x][y] = 0;
sx[top] = x; sy[top] = y; top++;
while (top > 0 && !done) {
int cx = sx[top - 1], cy = sy[top - 1];
int dirs[4], n = 0, k, i;
/* 找出四个方向里"还全是墙"的那些(那种才没挖过) */
if (cx + 2 < MW - 1 && map[cx + 2][cy] == 1) dirs[n++] = 0;
if (cx - 2 > 0 && map[cx - 2][cy] == 1) dirs[n++] = 1;
if (cy + 2 < MH - 1 && map[cx][cy + 2] == 1) dirs[n++] = 2;
if (cy - 2 > 0 && map[cx][cy - 2] == 1) dirs[n++] = 3;
if (n == 0) { top--; continue; } /* 死路:回退 */
k = dirs[rnd(n)];
if (k == 0) { map[cx + 1][cy] = 0; cx = cx + 2; }
else if (k == 1) { map[cx - 1][cy] = 0; cx = cx - 2; }
else if (k == 2) { map[cx][cy + 1] = 0; cy = cy + 2; }
else { map[cx][cy - 1] = 0; cy = cy - 2; }
map[cx][cy] = 0;
if (top < STACK_MAX) { sx[top] = cx; sy[top] = cy; top++; }
}
/* 右下角出口强制打通(保证一定到得了) */
for (i = 0; i < 3; i++) {
if (MW - 2 - i >= 0) map[MW - 2 - i][MH - 2] = 0;
if (MH - 2 - i >= 0) map[MW - 2][MH - 2 - i] = 0;
}
}
static void new_game(void)
{
generate();
px = 1;
py = 1;
won = 0;
steps = 0;
}
static void draw(void)
{
int x, y;
char buf[12];
ui_2d_clear(C_BG);
for (x = 0; x < MW; x++) {
for (y = 0; y < MH; y++) {
ui_2d_rect(ox + x * cell, oy + y * cell, cell, cell,
map[x][y] ? C_WALL : C_PATH, 1, 0, 0);
}
}
ui_2d_rect(ox + (MW - 2) * cell + 1, oy + (MH - 2) * cell + 1, cell - 2, cell - 2, C_GOAL, 1, 0, 2);
ui_2d_rect(ox + px * cell + 1, oy + py * cell + 1, cell - 2, cell - 2, C_PLAYER, 1, 0, cell / 2);
itoa(steps, buf);
ui_2d_text(10, 24, buf, C_TEXT, 15, VML_ANCHOR_LEFT);
ui_2d_text(10, 46, g_lang == 0 ? "步数" : "steps", C_DIM, 10, VML_ANCHOR_LEFT);
if (won)
ui_2d_text(SW / 2, oy + MH * cell + 28, g_lang == 0 ? "走出来了!ESC 换一张" : "Out! ESC for a new maze",
C_TEXT, 15, VML_ANCHOR_CENTER);
else
ui_2d_text(SW / 2, oy + MH * cell + 28, g_lang == 0 ? "方向键 / 点屏幕四边,走到红格"
: "Arrows / tap a screen edge; reach the red cell",
C_DIM, 11, VML_ANCHOR_CENTER);
ui_2d_present();
}
static void move(int dx, int dy)
{
int nx = px + dx, ny = py + dy;
if (won) return;
if (nx < 0 || ny < 0 || nx >= MW || ny >= MH) return;
if (map[nx][ny]) return; /* 墙 */
px = nx;
py = ny;
steps = steps + 1;
if (px == MW - 2 && py == MH - 2) won = 1;
}
/* 点屏幕四边:离哪边最近就往那边走 */
static void tap(int x, int y)
{
int dl = x, dr = SW - x, dt = y, db = SH - y;
if (dl <= dr && dl <= dt && dl <= db) move(-1, 0);
else if (dr <= dt && dr <= db) move(1, 0);
else if (dt <= db) move(0, -1);
else move(0, 1);
}
int main(void)
{
int msg[4];
int tid;
int done = 0;
char buf[12];
g_lang = ui_scr_get_language();
relayout();
ui_win_open_ex("maze.c", 0, 0, VML_WIN_ROTATABLE, VML_WIN_NO_GAMEPAD);
relayout();
new_game();
draw();
tid = ui_timer_set(120, 1);
while (!done && ui_win_is_closed() == 0) {
int t = ui_msg_wait(msg, 0);
if (t == VML_MSG_NONE) continue;
if (t == VML_MSG_TOUCHDOWN || t == VML_MSG_MOUSEDOWN) { tap(msg[1], msg[2]); draw(); continue; }
if (t == VML_MSG_KEYDOWN) {
if (msg[1] == VML_KEY_ESCAPE) { new_game(); draw(); continue; }
if (msg[1] == VML_KEY_LEFT) move(-1, 0);
if (msg[1] == VML_KEY_RIGHT) move(1, 0);
if (msg[1] == VML_KEY_UP) move(0, -1);
if (msg[1] == VML_KEY_DOWN) move(0, 1);
draw();
continue;
}
if (t == VML_MSG_TIMER) {
g_frames = g_frames + 1;
if (g_frames >= MAX_FRAMES) done = 1;
continue;
}
if (t == VML_MSG_WINDOWRESIZE) { relayout(); draw(); continue; }
if (t == VML_MSG_WINDOWCLOSE) break;
}
ui_timer_kill(tid);
ui_win_close();
itoa(steps, buf);
printf("maze: steps=%s won=%d done\n", buf, won);
return 0;
}