1 registered members (AndrewAMD),
1,306
guests, and 3
spiders. |
Key:
Admin,
Global Mod,
Mod
|
|
|
Re: Maze generation algorithm
[Re: 3run]
#430645
09/30/13 12:50
09/30/13 12:50
|
Joined: Jun 2007
Posts: 1,337 Hiporope and its pain
txesmi
Serious User
|
Serious User
Joined: Jun 2007
Posts: 1,337
Hiporope and its pain
|
glad to help I went a bit deeper with this: Halls, doors and treasures are indentified.
#include <acknex.h>
#include <default.c>
#define PRAGMA_POINTER
//#define WATCH_GENERATION
PANEL *panMaze;
int make_odd ( int i )
{
return i - ( i % 2 ) + 1;
}
#define array_cell(array,x,y) *(*(array+x)+y)
var **array_create ( int size_x, int size_y )
{
var **array = (var**)sys_malloc ( sizeof(var*) * size_x );
var **c = array;
var **cl = c + size_x;
for ( ; c<cl; c++ )
*c = (var*)sys_malloc ( sizeof(var) * size_y );
return array;
}
void array_remove ( var **array, int size_x )
{
var **c = array;
var **cl = c + size_x;
for ( ; c<cl; c++ )
{
var *r = *c;
sys_free ( r );
}
sys_free ( array );
}
#define UNVISITED 0
#define WALL 1
#define START 2
#define END 3
#define HALL 4
#define HALL2 5
#define DOOR 6
#define BONUS 7
#define OPEN 100
void array_draw ( var **maze, int size_x, int size_y, BMAP *bmp )
{
var cell_x = bmap_width ( bmp ) / size_x;
var cell_y = bmap_height ( bmp ) / size_y;
draw_textmode ( "Arial", 0, cell_y, 100 );
bmap_rendertarget ( bmp, 0, 0 );
draw_quad ( NULL, vector(0,0,0), NULL, vector(bmap_width(bmp),bmap_height(bmp),0), NULL, vector(1,1,1), 100, 0 );
int c = 0;
for ( ; c<size_x; c+=1 )
{
int r = 0;
for ( ; r<size_y; r+=1 )
{
switch ( array_cell(maze,c,r) )
{
case UNVISITED:
case WALL:
break;
case END: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 ); break;
case HALL: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, vector(240,240,240), 100, 0 ); break;
case HALL2: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 ); break;
case OPEN: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 ); break;
case START: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 ); break;
case DOOR: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );
draw_text ( "d", (size_x/8)+c*cell_x, r*cell_y, nullvector ); break;
case BONUS: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );
draw_text ( "t", (size_x/8)+c*cell_x, r*cell_y, nullvector ); break;
default: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 ); break;
}
}
}
bmap_rendertarget ( NULL, 0, 0 );
}
void array_draw_update ( var **maze, int size_x, int size_y, int pos_x, int pos_y, BMAP *bmp )
{
var cell_x = bmap_width ( bmp ) / size_x;
var cell_y = bmap_height ( bmp ) / size_y;
bmap_rendertarget ( bmp, 0, 1 );
int c = pos_x - 1;
for ( ; c<pos_x+2; c+=1 )
{
int r = pos_y - 1;
for ( ; r<pos_y+2; r+=1 )
{
switch ( array_cell(maze,c,r) )
{
case UNVISITED:
case WALL:
break;
case END: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 ); break;
case HALL:
case OPEN: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 ); break;
case START: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 ); break;
default: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 ); break;
}
}
}
bmap_rendertarget ( NULL, 0, 0 );
}
var no[4][2] =
{
-1, 0,
0, -1,
1, 0,
0, 1
};
var ns[8][2] =
{
-1, 0,
-1, -1,
0, -1,
1, -1,
1, 0,
1, 1,
0, 1,
-1, 1
};
int maze_step_calls = 0;
void maze_hall ( var **array, int size_x, int size_y, int x, int y, int cells_to_end )
{
if ( array_cell(array,x,y) == END )
return;
int noi = integer ( random(4) );
int roll_side = sign ( random(1)-0.5 );
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = x + no[noi][0] * 2;
int ny = y + no[noi][1] * 2;
int noi2 = cycle ( noi + roll_side, 0, 4 );
int nx2 = x + no[noi2][0] * 2;
int ny2 = y + no[noi2][1] * 2;
int nx3 = x + ( no[noi][0] * 2 ) + ( no[noi2][0] * 2 );
int ny3 = y + ( no[noi][1] * 2 ) + ( no[noi2][1] * 2 );
if ( ( nx3 < 0 ) || ( nx3 >= size_x ) || ( ny3 < 0 ) || ( ny3 >= size_y ) )
{
noi = cycle ( noi + roll_side, 0, 4 );
continue;
}
if ( ( array_cell(array,nx,ny) > UNVISITED ) || ( array_cell(array,nx2,ny2) > UNVISITED ) || ( array_cell(array,nx3,ny3) > UNVISITED ) )
{
noi = cycle ( noi + roll_side, 0, 4 );
continue;
}
int nx4 = x + ( no[noi][0] * 3 ) + ( no[noi2][0] * 3 );
int ny4 = y + ( no[noi][1] * 3 ) + ( no[noi2][1] * 3 );
int step_x = sign ( nx3 - x );
int step_y = sign ( ny3 - y );
int pos_x = x;
for ( ; pos_x!=nx4; pos_x+=step_x )
{
int pos_y = y;
for ( ; pos_y!=ny4; pos_y+=step_y )
{
if ( array_cell(array,pos_x,pos_y) < END )
{
array_cell(array,pos_x,pos_y) = cells_to_end;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx5 = pos_x+no[i][0]*2;
int ny5 = pos_y+no[i][1]*2;
if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
continue;
if ( abs ( array_cell(array,nx5,ny5) - cells_to_end ) < 3 )
{
nx5 = pos_x+no[i][0];
ny5 = pos_y+no[i][1];
array_cell(array,nx5,ny5) = cells_to_end;
}
}
}
#ifdef WATCH_GENERATION
array_draw_update ( array, size_x, size_y, pos_x, pos_y, panMaze->bmap );
#endif
}
}
#ifdef WATCH_GENERATION
wait(1);
#endif
int hall = integer ( random(6) );
switch ( hall )
{
case 0: maze_hall ( array, size_x, size_y, nx, ny, cells_to_end ); break;
case 1: maze_hall ( array, size_x, size_y, nx2, ny2, cells_to_end ); break;
case 2: maze_hall ( array, size_x, size_y, nx3, ny3, cells_to_end ); break;
}
break;
}
}
void maze_step ( var **array, int size_x, int size_y, int *x, int *y, int *cells_to_end )
{
int noi = integer ( random(4) );
int roll_side = sign ( random(1)-0.5 );
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = *x + no[noi][0] * 2;
int ny = *y + no[noi][1] * 2;
if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
{
noi = cycle ( noi + roll_side, 0, 4 );
continue;
}
if ( array_cell(array,nx,ny) > UNVISITED )
{
noi = cycle ( noi + roll_side, 0, 4 );
continue;
}
int nx2 = *x + no[noi][0];
int ny2 = *y + no[noi][1];
array_cell(array,nx2,ny2) = OPEN;
array_cell(array,nx,ny) = OPEN;
*x = nx;
*y = ny;
*cells_to_end += 2;
int ii = 0;
for ( ; ii<4; ii+=1 )
{
int nx5 = nx+no[ii][0]*2;
int ny5 = ny+no[ii][1]*2;
if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
continue;
if ( abs ( array_cell(array,nx5,ny5) - *cells_to_end ) < 3 )
{
int nx6 = nx+no[ii][0];
int ny6 = ny+no[ii][1];
array_cell(array,nx6,ny6) = *cells_to_end;
}
}
#ifdef WATCH_GENERATION
array_draw_update ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, panMaze->bmap );
wait(1);
#endif
int hall = integer ( random(1.2) );
if ( hall == 0 )
{
maze_step_calls += 1;
maze_hall ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, *cells_to_end );
}
maze_step_calls += 1;
maze_step ( array, size_x, size_y, x, y, cells_to_end );
break;
}
if ( i == 4 )
{
if ( array_cell(array,*x,*y) != END )
{
array_cell(array,*x,*y) = *cells_to_end;
*cells_to_end -= 1;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = *x + no[i][0];
int ny = *y + no[i][1];
if ( array_cell(array,nx,ny) != OPEN )
continue;
array_cell(array,nx,ny) = *cells_to_end;
*cells_to_end -= 1;
*x += no[i][0] * 2;
*y += no[i][1] * 2;
#ifdef WATCH_GENERATION
array_draw_update ( array, size_x, size_y, *x-no[i][0] * 2, *y-no[i][1] * 2, panMaze->bmap );
wait(1);
#endif
maze_step_calls += 1;
maze_step ( array, size_x, size_y, x, y, cells_to_end );
break;
}
}
}
}
void maze_depth_first ( var **array, int size_x, int size_y, int end_x, int end_y )
{
array_draw ( array, size_x, size_y, panMaze->bmap );
var **c = array;
var **cl = c + size_x;
for ( ; c<cl; c+=2 )
{
var *r = *c;
var *rl = r + size_y;
for ( ; r<rl; r++ )
{
*r = WALL;
}
}
var **c = array + 1;
var **cl = c + size_x - 1;
for ( ; c<cl; c+=2 )
{
var *r = *c;
var *rl = r + size_y;
for ( ; r<rl; r+=2 )
{
*r = WALL;
}
}
int *x = sys_malloc ( sizeof(int) );
int *y = sys_malloc ( sizeof(int) );
int *cells_to_end = sys_malloc ( sizeof(int) );
*x = end_x;
*y = end_y;
*cells_to_end = OPEN;
array_cell(array,*x,*y) = END;
maze_step_calls += 1;
maze_step ( array, size_x, size_y, x, y, cells_to_end );
#ifdef WATCH_GENERATION
while ( proc_status ( maze_step ) > 0 )
wait(1);
#endif
sys_free ( x );
sys_free ( y );
sys_free ( cells_to_end );
// Clean up
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
int n = 0;
int cell_depth = 0;
int i = 0;
for ( ; i<8; i+=1 )
{
int nx = pos_x + ns[i][0];
int ny = pos_y + ns[i][1];
if ( array_cell(array,nx,ny) > WALL )
{
n += 1;
cell_depth += array_cell(array,nx,ny);
}
}
if ( n == 8 )
array_cell(array,pos_x,pos_y) = cell_depth / 8;
}
}
// Look for start point
int start_x = 0;
int start_y = 0;
int pos_x = 1;
for ( ; pos_x<size_x; pos_x+=2 )
{
int pos_y = 1;
for ( ; pos_y<size_y; pos_y+=2 )
{
if ( array_cell(array,pos_x,pos_y) > array_cell(array,start_x,start_y) )
{
start_x = pos_x;
start_y = pos_y;
}
}
}
array_cell(array,start_x,start_y) = START;
// Isolate halls
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int n = 0;
int i = 0;
for ( ; i<8; i+=1 )
{
int nx = pos_x + ns[i][0];
int ny = pos_y + ns[i][1];
if ( ( array_cell(array,nx,ny) > WALL ) || ( array_cell(array,pos_x,pos_y) == START ) || ( array_cell(array,pos_x,pos_y) == END ) )
n += 1;
}
if ( n == 8 )
array_cell(array,pos_x,pos_y) = HALL;
}
}
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int i = 0;
for ( ; i<8; i+=1 )
{
int nx = pos_x + ns[i][0];
int ny = pos_y + ns[i][1];
if ( array_cell(array,nx,ny) != HALL )
continue;
array_cell(array,pos_x,pos_y) = HALL2;
break;
}
}
}
// Look for doors
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = pos_x + no[i][0];
int ny = pos_y + no[i][1];
if ( array_cell(array,nx,ny) != HALL2 )
continue;
array_cell(array,pos_x,pos_y) = DOOR;
break;
}
}
}
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int n = 0;
int cheapest_x = 0;
int cheapest_y = 0;
var weight = 100000;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = pos_x + no[i][0];
int ny = pos_y + no[i][1];
if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
continue;
if ( ( array_cell(array,nx,ny) >= OPEN ) || ( array_cell(array,nx,ny) == BONUS ) )
{
n += 1;
if ( array_cell(array,nx,ny) < weight )
{
cheapest_x = nx;
cheapest_y = ny;
weight = array_cell(array,nx,ny);
}
}
}
if ( n >= 3 )
array_cell(array,cheapest_x,cheapest_y) = DOOR;
}
}
// Look for bonus
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int n = 0;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = pos_x + no[i][0];
int ny = pos_y + no[i][1];
if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
continue;
if ( ( array_cell(array,nx,ny) >= OPEN ) || ( array_cell(array,nx,ny) == DOOR ) || ( array_cell(array,nx,ny) == BONUS ) || ( array_cell(array,nx,ny) == END ) || ( array_cell(array,nx,ny) == START ) )
n += 1;
}
if ( n == 1 )
array_cell(array,pos_x,pos_y) = BONUS;
}
}
}
void main ()
{
// video_mode = 8;
video_set ( 700, 700, 32, 2 );
random_seed ( 0 );
fps_max = 30;
wait(3);
panMaze = pan_create ( "flags=SHOW;", 1 );
panMaze->bmap = bmap_createblack ( 700, 700, 24 );
int maze_x = integer ( make_odd ( bmap_width(panMaze->bmap) / 15 ) );
int maze_y = integer ( make_odd ( bmap_height(panMaze->bmap) / 15 ) );
var **maze = array_create ( maze_x, maze_y );
maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
#ifdef WATCH_GENERATION
wait_for ( maze_depth_first );
#endif
array_draw ( maze, maze_x, maze_y, panMaze->bmap );
var keySpace = 0;
var clock = total_ticks + 8;
while ( !key_esc )
{
if ( key_space )
keySpace = 1;
else if ( keySpace ) //|| ( total_ticks > clock ) )
{
clock = total_ticks + 8;
keySpace = 0;
array_remove ( maze, maze_x );
maze = array_create ( maze_x, maze_y );
maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
#ifdef WATCH_GENERATION
wait_for ( maze_depth_first );
#endif
array_draw ( maze, maze_x, maze_y, panMaze->bmap );
}
wait(1);
}
bmap_remove ( panMaze->bmap );
pan_remove ( panMaze );
array_remove ( maze, maze_x );
sys_exit ( NULL );
}
Salud!
|
|
|
Re: Maze generation algorithm
[Re: txesmi]
#430647
09/30/13 14:08
09/30/13 14:08
|
Joined: Jun 2009
Posts: 2,210 Bavaria, Germany
Kartoffel
Expert
|
Expert
Joined: Jun 2009
Posts: 2,210
Bavaria, Germany
|
wow, great ( I'll implement it into my 1st person maze for practise )
POTATO-MAN saves the day! - Random
|
|
|
Re: Maze generation algorithm
[Re: Kartoffel]
#430650
09/30/13 15:08
09/30/13 15:08
|
Joined: May 2009
Posts: 5,370 Caucasus
3run
OP
Senior Expert
|
OP
Senior Expert
Joined: May 2009
Posts: 5,370
Caucasus
|
txesmi@ damn! it's so freaking awesome dude! I'll create fps shooter with it (or horror), as I've said before! Is there a way to identify a closed door with a key, which is available for it? So the key will be placed out of the closed room. Greets
|
|
|
Re: Maze generation algorithm
[Re: 3run]
#430658
09/30/13 16:05
09/30/13 16:05
|
Joined: Jun 2007
Posts: 1,337 Hiporope and its pain
txesmi
Serious User
|
Serious User
Joined: Jun 2007
Posts: 1,337
Hiporope and its pain
|
@3run I can imagine how to order the doors and treasures from start to end, so there is a chance for that gameplay. For now I placed light points
#include <acknex.h>
#include <default.c>
#define PRAGMA_POINTER
//#define WATCH_GENERATION
PANEL *panMaze;
int make_odd ( int i )
{
return i - ( i % 2 ) + 1;
}
#define array_cell(array,x,y) *(*(array+x)+y)
var **array_create ( int size_x, int size_y )
{
var **array = (var**)sys_malloc ( sizeof(var*) * size_x );
var **c = array;
var **cl = c + size_x;
for ( ; c<cl; c++ )
*c = (var*)sys_malloc ( sizeof(var) * size_y );
return array;
}
void array_remove ( var **array, int size_x )
{
var **c = array;
var **cl = c + size_x;
for ( ; c<cl; c++ )
{
var *r = *c;
sys_free ( r );
}
sys_free ( array );
}
#define UNVISITED 0
#define WALL 1
#define START 2
#define END 3
#define HALLCENTER 4
#define HALLBORDER 5
#define DOOR 6
#define BONUS 7
#define LIGHTWALL 8
#define LIGHTHALL 9
#define LIGHTCORRIDOR 10
#define OPEN 100
void array_draw ( var **maze, int size_x, int size_y, BMAP *bmp )
{
var cell_x = bmap_width ( bmp ) / size_x;
var cell_y = bmap_height ( bmp ) / size_y;
draw_textmode ( "Arial", 0, cell_y, 100 );
bmap_rendertarget ( bmp, 0, 0 );
draw_quad ( NULL, vector(0,0,0), NULL, vector(bmap_width(bmp),bmap_height(bmp),0), NULL, vector(1,1,1), 100, 0 );
int c = 0;
for ( ; c<size_x; c+=1 )
{
int r = 0;
for ( ; r<size_y; r+=1 )
{
switch ( array_cell(maze,c,r) )
{
case UNVISITED:
case WALL:
break;
case END: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 ); break;
case HALLCENTER: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, vector(240,240,240), 100, 0 ); break;
case HALLBORDER: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 ); break;
case OPEN: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_BLUE, 100, 0 ); break;
case START: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 ); break;
case DOOR: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );
draw_text ( "D", (size_x/8)+c*cell_x, r*cell_y, nullvector ); break;
case BONUS: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );
draw_text ( "T", (size_x/8)+c*cell_x, r*cell_y, nullvector ); break;
case LIGHTWALL: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );
draw_text ( "L", (size_x/8)+c*cell_x, r*cell_y, nullvector ); break;
case LIGHTHALL: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, vector(240,240,240), 100, 0 );
draw_text ( "L", (size_x/8)+c*cell_x, r*cell_y, nullvector ); break;
case LIGHTCORRIDOR: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );
draw_text ( "L", (size_x/8)+c*cell_x, r*cell_y, nullvector ); break;
default: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 ); break;
}
}
}
bmap_rendertarget ( NULL, 0, 0 );
}
void array_draw_update ( var **maze, int size_x, int size_y, int pos_x, int pos_y, BMAP *bmp )
{
var cell_x = bmap_width ( bmp ) / size_x;
var cell_y = bmap_height ( bmp ) / size_y;
bmap_rendertarget ( bmp, 0, 1 );
int c = pos_x - 1;
for ( ; c<pos_x+2; c+=1 )
{
int r = pos_y - 1;
for ( ; r<pos_y+2; r+=1 )
{
switch ( array_cell(maze,c,r) )
{
case UNVISITED:
case WALL:
break;
case END: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 ); break;
case HALLCENTER:
case OPEN: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 ); break;
case START: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 ); break;
default: draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 ); break;
}
}
}
bmap_rendertarget ( NULL, 0, 0 );
}
var no[4][2] =
{
-1, 0,
0, -1,
1, 0,
0, 1
};
var ns[8][2] =
{
-1, 0,
-1, -1,
0, -1,
1, -1,
1, 0,
1, 1,
0, 1,
-1, 1
};
int maze_step_calls = 0;
void maze_hall ( var **array, int size_x, int size_y, int x, int y, int cells_to_end )
{
if ( array_cell(array,x,y) == END )
return;
int noi = integer ( random(4) );
int roll_side = sign ( random(1)-0.5 );
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = x + no[noi][0] * 2;
int ny = y + no[noi][1] * 2;
int noi2 = cycle ( noi + roll_side, 0, 4 );
int nx2 = x + no[noi2][0] * 2;
int ny2 = y + no[noi2][1] * 2;
int nx3 = x + ( no[noi][0] * 2 ) + ( no[noi2][0] * 2 );
int ny3 = y + ( no[noi][1] * 2 ) + ( no[noi2][1] * 2 );
if ( ( nx3 < 0 ) || ( nx3 >= size_x ) || ( ny3 < 0 ) || ( ny3 >= size_y ) )
{
noi = cycle ( noi + roll_side, 0, 4 );
continue;
}
if ( ( array_cell(array,nx,ny) > UNVISITED ) || ( array_cell(array,nx2,ny2) > UNVISITED ) || ( array_cell(array,nx3,ny3) > UNVISITED ) )
{
noi = cycle ( noi + roll_side, 0, 4 );
continue;
}
int nx4 = x + ( no[noi][0] * 3 ) + ( no[noi2][0] * 3 );
int ny4 = y + ( no[noi][1] * 3 ) + ( no[noi2][1] * 3 );
int step_x = sign ( nx3 - x );
int step_y = sign ( ny3 - y );
int pos_x = x;
for ( ; pos_x!=nx4; pos_x+=step_x )
{
int pos_y = y;
for ( ; pos_y!=ny4; pos_y+=step_y )
{
if ( array_cell(array,pos_x,pos_y) < END )
{
array_cell(array,pos_x,pos_y) = cells_to_end;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx5 = pos_x+no[i][0]*2;
int ny5 = pos_y+no[i][1]*2;
if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
continue;
if ( abs ( array_cell(array,nx5,ny5) - cells_to_end ) < 3 )
{
nx5 = pos_x+no[i][0];
ny5 = pos_y+no[i][1];
array_cell(array,nx5,ny5) = cells_to_end;
}
}
}
#ifdef WATCH_GENERATION
array_draw_update ( array, size_x, size_y, pos_x, pos_y, panMaze->bmap );
#endif
}
}
#ifdef WATCH_GENERATION
wait(1);
#endif
int hall = integer ( random(6) );
switch ( hall )
{
case 0: maze_hall ( array, size_x, size_y, nx, ny, cells_to_end ); break;
case 1: maze_hall ( array, size_x, size_y, nx2, ny2, cells_to_end ); break;
case 2: maze_hall ( array, size_x, size_y, nx3, ny3, cells_to_end ); break;
}
break;
}
}
void maze_step ( var **array, int size_x, int size_y, int *x, int *y, int *cells_to_end )
{
int noi = integer ( random(4) );
int roll_side = sign ( random(1)-0.5 );
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = *x + no[noi][0] * 2;
int ny = *y + no[noi][1] * 2;
if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
{
noi = cycle ( noi + roll_side, 0, 4 );
continue;
}
if ( array_cell(array,nx,ny) > UNVISITED )
{
noi = cycle ( noi + roll_side, 0, 4 );
continue;
}
int nx2 = *x + no[noi][0];
int ny2 = *y + no[noi][1];
array_cell(array,nx2,ny2) = OPEN;
array_cell(array,nx,ny) = OPEN;
*x = nx;
*y = ny;
*cells_to_end += 2;
int ii = 0;
for ( ; ii<4; ii+=1 )
{
int nx5 = nx+no[ii][0]*2;
int ny5 = ny+no[ii][1]*2;
if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
continue;
if ( abs ( array_cell(array,nx5,ny5) - *cells_to_end ) < 3 )
{
int nx6 = nx+no[ii][0];
int ny6 = ny+no[ii][1];
array_cell(array,nx6,ny6) = *cells_to_end;
}
}
#ifdef WATCH_GENERATION
array_draw_update ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, panMaze->bmap );
wait(1);
#endif
int hall = integer ( random(1.2) );
if ( hall == 0 )
{
maze_step_calls += 1;
maze_hall ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, *cells_to_end );
}
maze_step_calls += 1;
maze_step ( array, size_x, size_y, x, y, cells_to_end );
break;
}
if ( i == 4 )
{
if ( array_cell(array,*x,*y) != END )
{
array_cell(array,*x,*y) = *cells_to_end;
*cells_to_end -= 1;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = *x + no[i][0];
int ny = *y + no[i][1];
if ( array_cell(array,nx,ny) != OPEN )
continue;
array_cell(array,nx,ny) = *cells_to_end;
*cells_to_end -= 1;
*x += no[i][0] * 2;
*y += no[i][1] * 2;
#ifdef WATCH_GENERATION
array_draw_update ( array, size_x, size_y, *x-no[i][0] * 2, *y-no[i][1] * 2, panMaze->bmap );
wait(1);
#endif
maze_step_calls += 1;
maze_step ( array, size_x, size_y, x, y, cells_to_end );
break;
}
}
}
}
void maze_depth_first ( var **array, int size_x, int size_y, int end_x, int end_y )
{
array_draw ( array, size_x, size_y, panMaze->bmap );
var **c = array;
var **cl = c + size_x;
for ( ; c<cl; c+=2 )
{
var *r = *c;
var *rl = r + size_y;
for ( ; r<rl; r++ )
{
*r = WALL;
}
}
var **c = array + 1;
var **cl = c + size_x - 1;
for ( ; c<cl; c+=2 )
{
var *r = *c;
var *rl = r + size_y;
for ( ; r<rl; r+=2 )
{
*r = WALL;
}
}
int *x = sys_malloc ( sizeof(int) );
int *y = sys_malloc ( sizeof(int) );
int *cells_to_end = sys_malloc ( sizeof(int) );
*x = end_x;
*y = end_y;
*cells_to_end = OPEN;
array_cell(array,*x,*y) = END;
maze_step_calls += 1;
maze_step ( array, size_x, size_y, x, y, cells_to_end );
#ifdef WATCH_GENERATION
while ( proc_status ( maze_step ) > 0 )
wait(1);
#endif
sys_free ( x );
sys_free ( y );
sys_free ( cells_to_end );
// Clean up
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
int n = 0;
int cell_depth = 0;
int i = 0;
for ( ; i<8; i+=1 )
{
int nx = pos_x + ns[i][0];
int ny = pos_y + ns[i][1];
if ( array_cell(array,nx,ny) > WALL )
{
n += 1;
cell_depth += array_cell(array,nx,ny);
}
}
if ( n == 8 )
array_cell(array,pos_x,pos_y) = cell_depth / 8;
}
}
// Look for start point
int start_x = 0;
int start_y = 0;
int pos_x = 1;
for ( ; pos_x<size_x; pos_x+=2 )
{
int pos_y = 1;
for ( ; pos_y<size_y; pos_y+=2 )
{
if ( array_cell(array,pos_x,pos_y) > array_cell(array,start_x,start_y) )
{
start_x = pos_x;
start_y = pos_y;
}
}
}
array_cell(array,start_x,start_y) = START;
// Isolate halls
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int n = 0;
int i = 0;
for ( ; i<8; i+=1 )
{
int nx = pos_x + ns[i][0];
int ny = pos_y + ns[i][1];
if ( array_cell(array,nx,ny) > WALL )
n += 1;
}
if ( n == 8 )
array_cell(array,pos_x,pos_y) = HALLCENTER;
}
}
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int i = 0;
for ( ; i<8; i+=1 )
{
int nx = pos_x + ns[i][0];
int ny = pos_y + ns[i][1];
if ( array_cell(array,nx,ny) != HALLCENTER )
continue;
array_cell(array,pos_x,pos_y) = HALLBORDER;
break;
}
}
}
// Look for doors
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = pos_x + no[i][0];
int ny = pos_y + no[i][1];
if ( array_cell(array,nx,ny) != HALLBORDER )
continue;
array_cell(array,pos_x,pos_y) = DOOR;
break;
}
}
}
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int n = 0;
int cheapest_x = 0;
int cheapest_y = 0;
var weight = 100000;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = pos_x + no[i][0];
int ny = pos_y + no[i][1];
if ( ( array_cell(array,nx,ny) >= OPEN ) || ( array_cell(array,nx,ny) == BONUS ) )
{
n += 1;
if ( array_cell(array,nx,ny) < weight )
{
cheapest_x = nx;
cheapest_y = ny;
weight = array_cell(array,nx,ny);
}
}
}
if ( n >= 3 )
array_cell(array,cheapest_x,cheapest_y) = DOOR;
}
}
// Look for bonus
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int n = 0;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = pos_x + no[i][0];
int ny = pos_y + no[i][1];
if ( ( array_cell(array,nx,ny) >= OPEN ) || ( array_cell(array,nx,ny) == DOOR ) || ( array_cell(array,nx,ny) == BONUS ) || ( array_cell(array,nx,ny) == END ) || ( array_cell(array,nx,ny) == START ) )
n += 1;
}
if ( n == 1 )
array_cell(array,pos_x,pos_y) = BONUS;
}
}
// Hall lights
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=1 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=1 )
{
if ( array_cell(array,pos_x,pos_y) != HALLCENTER )
continue;
int n = 0;
int i = 0;
for ( ; i<8; i+=1 )
{
int nx = pos_x + ns[i][0];
int ny = pos_y + ns[i][1];
if ( ( array_cell(array,nx,ny) == HALLCENTER ) || ( array_cell(array,nx,ny) == LIGHTWALL ) )
n += 1;
}
if ( n < 2 )
{
int ni = integer ( random(4) );
int roll_side = sign ( random(1)-0.5 );
int nx = pos_x + no[ni][0];
int ny = pos_y + no[ni][1];
while ( array_cell(array,nx,ny) != HALLBORDER )
{
ni = cycle ( ni+1, 0, 4 );
nx = pos_x + no[ni][0];
ny = pos_y + no[ni][1];
}
int i = 1;
for ( ; i<8; i+=2 )
{
int nx2 = nx + ns[i][0];
int ny2 = ny + ns[i][1];
if ( array_cell(array,nx2,ny2) == LIGHTWALL )
break;
}
if ( i == 9 )
{
int i = 0;
for ( ; i<4; i+=1 )
{
int nx2 = nx + ns[i][0] * 2;
int ny2 = ny + ns[i][1] * 2;
if ( ( nx2 < 0 ) || ( nx2 >= size_x ) || ( ny2 < 0 ) || ( ny2 >= size_y ) )
continue;
if ( array_cell(array,nx2,ny2) == LIGHTWALL )
break;
}
if ( i == 4 )
array_cell(array,nx,ny) = LIGHTWALL;
}
}
if ( n == 8 )
array_cell(array,pos_x,pos_y) = LIGHTHALL;
}
}
// Corridor lights
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=2 )
{
int pos_y = 2;
for ( ; pos_y<size_y-1; pos_y+=2 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = pos_x + no[i][0] * 2;
int ny = pos_y + no[i][1] * 2;
if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
continue;
int nx2 = pos_x + no[i][0];
int ny2 = pos_y + no[i][1];
if ( ( array_cell(array,nx,ny) == LIGHTCORRIDOR ) && ( array_cell(array,nx2,ny2) > OPEN ) )
break;
}
if ( i == 4 )
{
i = 1;
for ( ; i<8; i+=2 )
{
int nx = pos_x + ns[i][0];
int ny = pos_y + ns[i][1];
if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
continue;
if ( array_cell(array,nx,ny) == LIGHTCORRIDOR )
break;
}
if ( i == 9 )
array_cell(array,pos_x,pos_y) = LIGHTCORRIDOR;
}
}
}
int pos_x = 2;
for ( ; pos_x<size_x-1; pos_x+=2 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=2 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = pos_x + no[i][0] * 2;
int ny = pos_y + no[i][1] * 2;
if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
continue;
int nx2 = pos_x + no[i][0];
int ny2 = pos_y + no[i][1];
if ( ( array_cell(array,nx,ny) == LIGHTCORRIDOR ) && ( array_cell(array,nx2,ny2) > OPEN ) )
break;
}
if ( i == 4 )
{
i = 1;
for ( ; i<8; i+=2 )
{
int nx = pos_x + ns[i][0];
int ny = pos_y + ns[i][1];
if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
continue;
if ( array_cell(array,nx,ny) == LIGHTCORRIDOR )
break;
}
if ( i == 9 )
array_cell(array,pos_x,pos_y) = LIGHTCORRIDOR;
}
}
}
int pos_x = 1;
for ( ; pos_x<size_x-1; pos_x+=2 )
{
int pos_y = 1;
for ( ; pos_y<size_y-1; pos_y+=2 )
{
if ( array_cell(array,pos_x,pos_y) < OPEN )
continue;
int n = 0;
int i = 0;
for ( ; i<4; i+=1 )
{
int nx = pos_x + no[i][0];
int ny = pos_y + no[i][1];
if ( array_cell(array,nx,ny) == DOOR )
n += 1;
if ( ( array_cell(array,nx,ny) == LIGHTCORRIDOR ) || ( array_cell(array,nx,ny) == BONUS ) || ( array_cell(array,nx,ny) > OPEN ) )
n -= 1;
}
if ( n == 2 )
array_cell(array,pos_x,pos_y) = LIGHTCORRIDOR;
}
}
}
void main ()
{
// video_mode = 8;
video_set ( 700, 700, 32, 2 );
random_seed ( 0 );
fps_max = 30;
wait(3);
panMaze = pan_create ( "flags=SHOW;", 1 );
panMaze->bmap = bmap_createblack ( 700, 700, 24 );
int maze_x = integer ( make_odd ( bmap_width(panMaze->bmap) / 15 ) );
int maze_y = integer ( make_odd ( bmap_height(panMaze->bmap) / 15 ) );
var **maze = array_create ( maze_x, maze_y );
maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
#ifdef WATCH_GENERATION
wait_for ( maze_depth_first );
#endif
array_draw ( maze, maze_x, maze_y, panMaze->bmap );
var keySpace = 0;
var clock = total_ticks + 8;
while ( !key_esc )
{
if ( key_space )
keySpace = 1;
else if ( keySpace ) //|| ( total_ticks > clock ) )
{
clock = total_ticks + 8;
keySpace = 0;
array_remove ( maze, maze_x );
maze = array_create ( maze_x, maze_y );
maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
#ifdef WATCH_GENERATION
wait_for ( maze_depth_first );
#endif
array_draw ( maze, maze_x, maze_y, panMaze->bmap );
}
wait(1);
}
bmap_remove ( panMaze->bmap );
pan_remove ( panMaze );
array_remove ( maze, maze_x );
sys_exit ( NULL );
}
Salud!
|
|
|
Re: Maze generation algorithm
[Re: xbox]
#430959
10/06/13 21:49
10/06/13 21:49
|
Joined: Jun 2007
Posts: 1,337 Hiporope and its pain
txesmi
Serious User
|
Serious User
Joined: Jun 2007
Posts: 1,337
Hiporope and its pain
|
Let's start with the first code. The briefly called variables are: c -> column cl -> column last r -> row rl -> row last no -> neighbor offset noi -> neighbor offset index nx -> neighbor x coordinate ny -> neighbor y coordinate Once you have the maze constructed, you have to check the cells that has just one neighbor navigable. If you look at the cell style defines you will realize that all the navigable cells are bigger than WALL. Note that only odd cells (starting with 0) can be deadends. So...
int pos_x = 1;
for ( pos_x=1; pos_x<size_x; pos_x +=2 ) // go trough every odd columns
{
int pos_y = 1;
for ( pos_y=1; pos_y<size_y; pos_y+=2 ) // go trough every odd row on each column
{
if ( array_cell(maze,pos_x,pos_y) > WALL ) // is the current cell a navigable cell?
{
int nc = 0; // neighbor count
int noi = 0;
for ( noi=0; noi<4; noi+=1 ) // go trough every couple of members of neighbor offset array
{
int nx = pos_x + no[noi][0]; // calculate the neighbor coords
int ny = pos_y + no[noi][1];
if ( array_cell(maze,nx,ny) > WALL ) // is the current neighbor a navigable cell?
{
nc += 1; // increase the neighbor count by one
}
}
if ( nc == 1 ) // has the current cell just a single neighbor?
{
array_cell(maze,pos_x,pos_y) = DEADEND; // it is a deadend
}
}
}
}
Salud!
|
|
|
|