Алгоритм створення лабіринту: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 384:
==Приклад коду мовою С==
Нижче наведен приклад алгоритму пошуку в глибину для створення лабіринту мовою С.
<source lang="
//Код написан
#include <stdio.h>
Рядок 394:
typedef struct
{
int x, y; //Позиція вузла -
void *parent; //Покажчик на батьківський вузол
char c; //Символ для відображення
Рядок 434:
Node *link( Node *n )
{
//Connects node to random neighbor (if possible) and returns
//address of next node that should be visited
int x, y;
char dir;
Node *dest;
//Nothing can be done if null pointer is given - return
if ( n == NULL ) return NULL;
//While there are directions still unexplored
while ( n->dirs )
{
//Randomly pick one direction
dir = ( 1 << ( rand( ) % 4 ) );
//If it has already been explored - try again
if ( ~n->dirs & dir ) continue;
//Mark direction as explored
n->dirs &= ~dir;
//Depending on chosen direction
switch ( dir )
{
//Check if it's possible to go right
case 1:
if ( n->x + 2 < width )
Рядок 468 ⟶ 469:
break;
//Check if it's possible to go down
case 2:
if ( n->y + 2 < height )
Рядок 478 ⟶ 479:
break;
//Check if it's possible to go left
case 4:
if ( n->x - 2 >= 0 )
Рядок 488 ⟶ 489:
break;
//Check if it's possible to go up
case 8:
if ( n->y - 2 >= 0 )
Рядок 499 ⟶ 500:
}
//Get destination node into pointer (makes things a tiny bit faster)
dest = nodes + x + y * width;
//Make sure that destination node is not a wall
if ( dest->c == ' ' )
{
//If destination is a linked node already - abort
if ( dest->parent != NULL ) continue;
//Otherwise, adopt node
dest->parent = n;
//Remove wall between nodes
nodes[n->x + ( x - n->x ) / 2 + ( n->y + ( y - n->y ) / 2 ) * width].c = ' ';
//Return address of the child node
return dest;
}
}
//If nothing more can be done here - return parent's address
return n->parent;
}
Рядок 527 ⟶ 528:
int i, j;
//Outputs maze to terminal - nothing special
for ( i = 0; i < height; i++ )
{
Рядок 542 ⟶ 543:
Node *start, *last;
//Check argument count
if ( argc < 3 )
{
Рядок 549 ⟶ 550:
}
//Read maze dimensions from command line arguments
if ( sscanf( argv[1], "%d", &width ) + sscanf( argv[2], "%d", &height ) < 2 )
{
Рядок 556 ⟶ 557:
}
//Allow only odd dimensions
if ( !( width % 2 ) || !( height % 2 ) )
{
Рядок 563 ⟶ 564:
}
//Do not allow negative dimensions
if ( width <= 0 || height <= 0 )
{
Рядок 570 ⟶ 571:
}
//Seed random generator
srand( time( NULL ) );
//Initialize maze
if ( init( ) )
{
Рядок 580 ⟶ 581:
}
//Setup start node
start = nodes + 1 + width;
start->parent = start;
last = start;
//Connect nodes until start node is reached and can't be left
while ( ( last = link( last ) ) != start );
draw( );
|