📄 maze.c
字号:
/******************************************************************************
* [ maze ] ...
*
* modified: [ 03-08-15 ] Ge van Geldorp <ge@gse.nl>
* ported to Reactos
* modified: [ 94-10-8 ] Ge van Geldorp <Ge.vanGeldorp@lr.tudelft.nl>
* ported to MS Windows
* modified: [ 3-7-93 ] Jamie Zawinski <jwz@lucid.com>
* added the XRoger logo, cleaned up resources, made
* grid size a parameter.
* modified: [ 3-3-93 ] Jim Randell <jmr@mddjmr.fc.hp.com>
* Added the colour stuff and integrated it with jwz's
* screenhack stuff. There's still some work that could
* be done on this, particularly allowing a resource to
* specify how big the squares are.
* modified: [ 10-4-88 ] Richard Hess ...!uunet!cimshop!rhess
* [ Revised primary execution loop within main()...
* [ Extended X event handler, check_events()...
* modified: [ 1-29-88 ] Dave Lemke lemke@sun.com
* [ Hacked for X11...
* [ Note the word "hacked" -- this is extremely ugly, but at
* [ least it does the job. NOT a good programming example
* [ for X.
* original: [ 6/21/85 ] Martin Weiss Sun Microsystems [ SunView ]
*
******************************************************************************
Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
All Rights Reserved
Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted,
provided that the above copyright notice appear in all copies and that
both that copyright notice and this permission notice appear in
supporting documentation, and that the names of Sun or MIT not be
used in advertising or publicity pertaining to distribution of the
software without specific prior written permission. Sun and M.I.T.
make no representations about the suitability of this software for
any purpose. It is provided "as is" without any express or implied warranty.
SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
OR PERFORMANCE OF THIS SOFTWARE.
*****************************************************************************/
#define STRICT
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h> /* required for all Windows applications */
#if !defined (APIENTRY) /* Windows NT defines APIENTRY, but 3.x doesn't */
#define APIENTRY far pascal
#endif
#if !defined(WIN32) /* Windows 3.x uses a FARPROC for dialogs */
#define DLGPROC FARPROC
#endif
static BOOL InitApplication(HINSTANCE hInstance);
static BOOL InitInstance(HINSTANCE hInstance, int nCmdShow);
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM uParam,
LPARAM lParam);
HINSTANCE hInst; /* current instance */
HWND hWnd; /* Main window handle.*/
HBRUSH hBrushDead;
HBRUSH hBrushLiving;
HDC hDC;
static BOOL waiting;
char szAppName[] = "Maze"; /* The name of this application */
char szTitle[] = "Maze"; /* The title bar text */
static int solve_delay, pre_solve_delay, post_solve_delay;
#define MAX_MAZE_SIZE_X ((unsigned long) 250)
#define MAX_MAZE_SIZE_Y ((unsigned long) 250)
#define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
#define WALL_TOP 0x8000
#define WALL_RIGHT 0x4000
#define WALL_BOTTOM 0x2000
#define WALL_LEFT 0x1000
#define DOOR_IN_TOP 0x800
#define DOOR_IN_RIGHT 0x400
#define DOOR_IN_BOTTOM 0x200
#define DOOR_IN_LEFT 0x100
#define DOOR_IN_ANY 0xF00
#define DOOR_OUT_TOP 0x80
#define DOOR_OUT_RIGHT 0x40
#define DOOR_OUT_BOTTOM 0x20
#define DOOR_OUT_LEFT 0x10
#define START_SQUARE 0x2
#define END_SQUARE 0x1
#define border_x (0)
#define border_y (0)
#define get_random(x) (rand() % (x))
static unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
static struct {
unsigned char x;
unsigned char y;
unsigned char dir;
unsigned char dummy;
} move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];
static int maze_size_x, maze_size_y;
static long sqnum, path_length;
static int cur_sq_x, cur_sq_y;
static int start_x, start_y, start_dir, end_x, end_y, end_dir;
static int grid_width, grid_height;
static int state = 1, pathi = 0;
static void
set_maze_sizes (width, height)
int width, height;
{
maze_size_x = width / grid_width;
maze_size_y = height / grid_height;
}
static void
initialize_maze() /* draw the surrounding wall and start/end squares */
{
register int i, j, wall;
/* initialize all squares */
for ( i=0; i<maze_size_x; i++) {
for ( j=0; j<maze_size_y; j++) {
maze[i][j] = 0;
}
}
/* top wall */
for ( i=0; i<maze_size_x; i++ ) {
maze[i][0] |= WALL_TOP;
}
/* right wall */
for ( j=0; j<maze_size_y; j++ ) {
maze[maze_size_x-1][j] |= WALL_RIGHT;
}
/* bottom wall */
for ( i=0; i<maze_size_x; i++ ) {
maze[i][maze_size_y-1] |= WALL_BOTTOM;
}
/* left wall */
for ( j=0; j<maze_size_y; j++ ) {
maze[0][j] |= WALL_LEFT;
}
/* set start square */
wall = get_random(4);
switch (wall) {
case 0:
i = get_random(maze_size_x);
j = 0;
break;
case 1:
i = maze_size_x - 1;
j = get_random(maze_size_y);
break;
case 2:
i = get_random(maze_size_x);
j = maze_size_y - 1;
break;
case 3:
i = 0;
j = get_random(maze_size_y);
break;
}
maze[i][j] |= START_SQUARE;
maze[i][j] |= ( DOOR_IN_TOP >> wall );
maze[i][j] &= ~( WALL_TOP >> wall );
cur_sq_x = i;
cur_sq_y = j;
start_x = i;
start_y = j;
start_dir = wall;
sqnum = 0;
/* set end square */
wall = (wall + 2)%4;
switch (wall) {
case 0:
i = get_random(maze_size_x);
j = 0;
break;
case 1:
i = maze_size_x - 1;
j = get_random(maze_size_y);
break;
case 2:
i = get_random(maze_size_x);
j = maze_size_y - 1;
break;
case 3:
i = 0;
j = get_random(maze_size_y);
break;
}
maze[i][j] |= END_SQUARE;
maze[i][j] |= ( DOOR_OUT_TOP >> wall );
maze[i][j] &= ~( WALL_TOP >> wall );
end_x = i;
end_y = j;
end_dir = wall;
}
static int choose_door ();
static long backup ();
static void draw_wall ();
static void draw_solid_square(int, int, int, HDC, HBRUSH);
static void enter_square(int, HDC, HBRUSH);
static void
create_maze() /* create a maze layout given the intiialized maze */
{
register int i, newdoor = 0;
HDC hDC;
hDC = GetDC(hWnd);
do {
move_list[sqnum].x = cur_sq_x;
move_list[sqnum].y = cur_sq_y;
move_list[sqnum].dir = newdoor;
while ( ( newdoor = choose_door(hDC) ) == -1 ) { /* pick a door */
if ( backup() == -1 ) { /* no more doors ... backup */
ReleaseDC(hWnd, hDC);
return; /* done ... return */
}
}
/* mark the out door */
maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
switch (newdoor) {
case 0: cur_sq_y--;
break;
case 1: cur_sq_x++;
break;
case 2: cur_sq_y++;
break;
case 3: cur_sq_x--;
break;
}
sqnum++;
/* mark the in door */
maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
/* if end square set path length and save path */
if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
path_length = sqnum;
for ( i=0; i<path_length; i++) {
save_path[i].x = move_list[i].x;
save_path[i].y = move_list[i].y;
save_path[i].dir = move_list[i].dir;
}
}
} while (1);
}
static int
choose_door(HDC hDC) /* pick a new path */
{
int candidates[3];
register int num_candidates;
num_candidates = 0;
/* top wall */
if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
goto rightwall;
if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
goto rightwall;
if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
goto rightwall;
if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
draw_wall(cur_sq_x, cur_sq_y, 0, hDC);
goto rightwall;
}
candidates[num_candidates++] = 0;
rightwall:
/* right wall */
if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
goto bottomwall;
if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
goto bottomwall;
if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
goto bottomwall;
if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
draw_wall(cur_sq_x, cur_sq_y, 1, hDC);
goto bottomwall;
}
candidates[num_candidates++] = 1;
bottomwall:
/* bottom wall */
if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
goto leftwall;
if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
goto leftwall;
if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
goto leftwall;
if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
draw_wall(cur_sq_x, cur_sq_y, 2, hDC);
goto leftwall;
}
candidates[num_candidates++] = 2;
leftwall:
/* left wall */
if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
goto donewall;
if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
goto donewall;
if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
goto donewall;
if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
draw_wall(cur_sq_x, cur_sq_y, 3, hDC);
goto donewall;
}
candidates[num_candidates++] = 3;
donewall:
if (num_candidates == 0)
return ( -1 );
if (num_candidates == 1)
return ( candidates[0] );
return ( candidates[ get_random(num_candidates) ] );
}
static long
backup() /* back up a move */
{
sqnum--;
if (0 <= sqnum) {
cur_sq_x = move_list[sqnum].x;
cur_sq_y = move_list[sqnum].y;
}
return ( sqnum );
}
int bw;
static void
draw_solid_square(i, j, dir, hDC, hBrush) /* draw a solid square in a square */
register int i, j, dir;
HDC hDC;
HBRUSH hBrush;
{
RECT rc;
switch (dir) {
case 0:
rc.left = border_x + bw + grid_width * i;
rc.right = rc.left + grid_width - (bw + bw);
rc.top = border_y - bw + grid_height * j;
rc.bottom = rc.top + grid_height;
break;
case 1:
rc.left = border_x + bw + grid_width * i;
rc.right = rc.left + grid_width;
rc.top = border_y + bw + grid_height * j;
rc.bottom = rc.top + grid_height - (bw + bw);
break;
case 2:
rc.left = border_x + bw + grid_width * i;
rc.right = rc.left + grid_width - (bw + bw);
rc.top = border_y + bw + grid_height * j;
rc.bottom = rc.top + grid_height;
break;
case 3:
rc.left = border_x - bw + grid_width * i;
rc.right = rc.left + grid_width;
rc.top = border_y + bw + grid_height * j;
rc.bottom = rc.top + grid_height - (bw + bw);
break;
}
(void) FillRect(hDC, &rc, hBrush);
}
static void
draw_maze_border(HWND hWnd, HDC hDC) /* draw the maze outline */
{
register int i, j;
HBRUSH hBrush;
for ( i=0; i<maze_size_x; i++) {
if ( maze[i][0] & WALL_TOP ) {
MoveToEx(hDC, border_x + grid_width * i, border_y, NULL);
(void) LineTo(hDC, border_x + grid_width * (i + 1) - 1, border_y);
}
if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
MoveToEx(hDC, border_x + grid_width * i,
border_y + grid_height * (maze_size_y) - 1, NULL);
(void) LineTo(hDC, border_x + grid_width * (i+1) - 1,
border_y + grid_height * (maze_size_y) - 1);
}
}
for ( j=0; j<maze_size_y; j++) {
if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
MoveToEx(hDC, border_x + grid_width * maze_size_x - 1,
border_y + grid_height * j, NULL);
(void) LineTo(hDC, border_x + grid_width * maze_size_x - 1,
border_y + grid_height * (j+1) - 1);
}
if ( maze[0][j] & WALL_LEFT ) {
MoveToEx(hDC, border_x, border_y + grid_height * j, NULL);
(void) LineTo(hDC, border_x, border_y + grid_height * (j+1) - 1);
}
}
hBrush = GetStockObject(BLACK_BRUSH);
draw_solid_square (start_x, start_y, start_dir, hDC, hBrush);
draw_solid_square (end_x, end_y, end_dir, hDC, hBrush);
}
static void
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -