1 registered members (AndrewAMD),
718
guests, and 4
spiders. |
Key:
Admin,
Global Mod,
Mod
|
|
|
Re: Maze generation algorithm
[Re: 3run]
#430584
09/29/13 09:59
09/29/13 09:59
|
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
|
I mean after maze generation.
wait_for ( maze_depth_first );
int start_x = 0;
int start_y = 0;
int x = 1;
for ( ; x<MAZEX; x+=2 )
{
int y = 1;
for ( ; y<MAZEY; y+=2 )
{
if ( array_cell(maze,x,y) > array_cell(maze,start_x,start_y) )
{
start_x = x;
start_y = y;
}
}
}
array_cell(maze,start_x,start_y) = START;
array_draw ( maze, MAZEX, MAZEY, panMaze->bmap );
|
|
|
Re: Maze generation algorithm
[Re: 3run]
#430585
09/29/13 10:01
09/29/13 10:01
|
Joined: Jun 2009
Posts: 2,210 Bavaria, Germany
Kartoffel
Expert
|
Expert
Joined: Jun 2009
Posts: 2,210
Bavaria, Germany
|
@3run: if I have to guess: on every maze-step the depth value gets increased by 1. which means that the position with the maximum depth has the highest distance to the generation start-point.
POTATO-MAN saves the day! - Random
|
|
|
Re: Maze generation algorithm
[Re: Kartoffel]
#430586
09/29/13 10:25
09/29/13 10:25
|
Joined: May 2009
Posts: 5,370 Caucasus
3run
OP
Senior Expert
|
OP
Senior Expert
Joined: May 2009
Posts: 5,370
Caucasus
|
txesmi@ thank you very much man, I've got a fully functional simple maze-game Kartoffel@ I've got the theory, but I'm always messed up on practice.. :< Link: Download Screen: Thank you man!
|
|
|
Re: Maze generation algorithm
[Re: Kartoffel]
#430588
09/29/13 11:06
09/29/13 11:06
|
Joined: May 2009
Posts: 5,370 Caucasus
3run
OP
Senior Expert
|
OP
Senior Expert
Joined: May 2009
Posts: 5,370
Caucasus
|
I've got trapped :< Edit: just noticed, that you've edited your post btw, nice graphics man!
Last edited by 3run; 09/29/13 11:06. Reason: ***
|
|
|
Re: Maze generation algorithm
[Re: 3run]
#430612
09/29/13 19:47
09/29/13 19:47
|
Joined: Nov 2006
Posts: 497 Ohio
xbox
Senior Member
|
Senior Member
Joined: Nov 2006
Posts: 497
Ohio
|
|
|
|
Re: Maze generation algorithm
[Re: xbox]
#430614
09/29/13 20:59
09/29/13 20:59
|
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
|
Hi, I modified the algorithm to get halls in the path. It does not fill all the square and the code is pretty messy but here it goes
#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 START -1
#define UNVISITED 0
#define WALL 1
#define END 2
#define OPEN 3
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;
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 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 );
}
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 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 ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
continue;
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;
}
void main ()
{
// video_mode = 8;
video_set ( 512, 512, 32, 2 );
random_seed ( 0 );
fps_max = 30;
wait(3);
panMaze = pan_create ( "flags=SHOW;", 1 );
panMaze->bmap = bmap_createblack ( 512, 512, 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 + 1;
while ( !key_esc )
{
if ( key_space )
keySpace = 1;
else if ( keySpace ) //|| ( total_ticks > clock ) )
{
clock = total_ticks + 1;
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 );
}
|
|
|
Re: Maze generation algorithm
[Re: txesmi]
#430619
09/29/13 23:01
09/29/13 23:01
|
Joined: May 2009
Posts: 5,370 Caucasus
3run
OP
Senior Expert
|
OP
Senior Expert
Joined: May 2009
Posts: 5,370
Caucasus
|
txesmi@ man, this could be used to create some kind of a Wolfenstein3D game, but with random levels I'll give it a try tomorrow, the screen looks promising, I wish I could write such stuff myself Thank you very much! Best greets
|
|
|
|