ホームに戻る
 迷路作成プログラム

LSIC-86(試食版)用の迷路作成プログラムです。
(Borland C++ Compiler5.5でもコンパイル、実行可能でした)
作るのは迷路データのみで他のプログラムからの利用を想定しています。
使い方はソースの上のほうにコメントしてあります。

アルゴリズムとしては、
まずスタート地点をランダムで決め、ランダム方向に道を掘り進めます。
最外壁や自分自身の道に突き当たり行き詰まった場合掘り進めるのをやめます。
次に、道以外の位置をランダムで決め、そこからランダム方向に次の道を掘り進めます。
この場合、掘り進めは現在の道より前の道のどこかに繋がるまで行います。
もし、現在の道と最外壁に突き当たって行き止まった場合は現在の道を消しやり直します。
やり直しを行うことで必ず道と道は繋がるといえます。
以降はこの操作を繰り返し道を作る場所が無くなったら終了とします。

/*
*   迷路作成プログラム
*
*   下図のような右手法で必ず解けるような迷路を作成します(■が壁、□は道)
*
*    □□□□□■□■□□□■□■□■□
*    ■■■■□■□■■■□■□■□■□
*    □□□■□□□■□□□□□□□□□
*    ■■□■■■□■□■■■□■■■■
*    □□□□□□□□□□□■□□□□□
*
*   利用できるのは次の1変数と2関数(その他は基本的に利用不可)
*   int *g_block;
*   int create_maze(int, int, int);
*   int break_maze(void);
*
*   g_blockにはcreate_maze関数によってメモリが確保され迷路データが入ります
*   データは左上から右端へ、右端から次の段の左端へ という順に入り右下で終わります
*   壁がある場合は数値が 0、 道の場合は 1 以上の数値となります
*
*   create_maze関数の引数は順に 横幅、縦幅、乱数生成用の整数値
*   横幅、縦幅は必ず奇数の値である必要があります
*   第3引数では数値によって異なった迷路を生成することができます
*   成功の場合g_blockに迷路データを入れ1を返し、失敗の場合0を返します
*
*   break_maze関数で迷路を破壊します g_blockに確保したメモリは解放されます
*   create_maze関数を呼んだ場合には必ずbreak_maze関数を呼んでください
*/


#include <stdio.h>
#include <stdlib.h>

#define ENABLE_UP    (1 << 3)
#define ENABLE_RIGHT (1 << 2)
#define ENABLE_DOWN  (1 << 1)
#define ENABLE_LEFT  (1)

/* 迷路の実体を確保するメモリの先頭 */
int *g_block = NULL;
/* 迷路の横、縦の幅 */
static int maze_width, maze_height;

/* 迷路領域のメモリを解放 */
void break_maze(void);
/* 進める方向のチェック(同じ番号の道、迷路外には行けない) 進める方向を1つ選んで返す */
int check_direction(int x, int y);
/* 迷路内の指定番号の道を 0 でクリア */
void clear_block(int num);
/* 奇数の縦、横幅幅を入れると block に迷路を返す param は乱数生成用 */
int create_maze(int width, int height, int param);
/* (x,y) の区画の値を得る */
int get_block(int x, int y);
/* 0 のblockから道作成のスタート地点をランダムに選択 ポインタ x, y のアドレスに選んだ地点を入れる */
int get_random_block(int *x, int *y);
/* 迷路をprintfで表示(デバグ用) */
void printf_maze(void);
/* (x,y) の区画に値 num をセット */
void set_block(int x, int y, int num);


void break_maze(void){
  free(g_block);
  g_block = NULL;
}

int check_direction(int x, int y){
  int direction;

  /* 進行可能な方向数のカウント */
  int count = 0;
  /* 進行可能方向を記録するフラグ */
  int direction_flag = 0;

  /* 上へのチェック */
  if(y >= 2){
    if(get_block(x, y - 2) - get_block(x, y) != 0){
      /* 上に進行可能 */
      count++;
      direction_flag |= ENABLE_UP;
    }
  }

  /* 右へのチェック */
  if(x < maze_width - 2){
    if(get_block(x + 2, y) - get_block(x, y) != 0){
      /* 右に進行可能 */
      count++;
      direction_flag |= ENABLE_RIGHT;
    }
  }

  /* 下へのチェック */
  if(y < maze_height - 2){
    if(get_block(x, y + 2) - get_block(x, y) != 0){
      /* 下に進行可能 */
      count++;
      direction_flag |= ENABLE_DOWN;
    }
  }

  /* 左へのチェック */
  if(x >= 2){
    if(get_block(x - 2, y) - get_block(x, y) != 0){
      /* 左に進行可能 */
      count++;
      direction_flag |= ENABLE_LEFT;
    }
  }

  /* 進める方向が無い場合 0 を返す */
  if(count == 0){
    return 0;
  }

  /* 進める方向から進む方向を選ぶ */
  direction = rand() % count;

  if(direction_flag & ENABLE_UP){
    if(direction == 0){
      return ENABLE_UP;
    }
    direction--;
  }

  if(direction_flag & ENABLE_RIGHT){
    if(direction == 0){
      return ENABLE_RIGHT;
    }
    direction--;
  }

  if(direction_flag & ENABLE_DOWN){
    if(direction == 0){
      return ENABLE_DOWN;
    }
    direction--;
  }

  if(direction_flag & ENABLE_LEFT){
    if(direction == 0){
      return ENABLE_LEFT;
    }
  }

  return -1;
}

void clear_block(int num){
  int i, j;

  for(i = 0; i < maze_height; i++){
    for(j = 0; j < maze_width; j++){
      if(get_block(j,i) == num){
        set_block(j, i, 0);
      }
    }
  }
}

int create_maze(int width, int height, int param){
  int end_flag = 0;   /* ループ終了用のフラグ */
  int now_point_x, now_point_y;   /* 処理の現在地点 */

  /* 乱数系の初期化 */
  srand(param);

  maze_width = width;
  maze_height = height;

  if(g_block == NULL){
    g_block = (int *)calloc(width * height, sizeof(int));
  }

  if(g_block == NULL){
    return 0;
  }

  while(!end_flag){
    static int index = 0;   /* 道番号 1 から増えていく */

    if(get_random_block(&now_point_x, &now_point_y)){
      index++;
      set_block(now_point_x, now_point_y, index);
    }
    else{
      break;
    }

    /* 進行位置を探し移動 */
    for(;;){
      /* 進行可能な方向から1つ進行方向を得る */
      int direction = check_direction(now_point_x, now_point_y);

      if(direction == 0){
        /* 進行方向が無い */
        if(index != 1){
          clear_block(index);
        }
        break;
      }
      else if(direction == ENABLE_UP){
        set_block(now_point_x, now_point_y - 1, index);
        if(get_block(now_point_x, now_point_y - 2) != 0){
          break;
        }
        set_block(now_point_x, now_point_y - 2, index);
        now_point_y -= 2;
      }
      else if(direction == ENABLE_RIGHT){
        set_block(now_point_x + 1, now_point_y, index);
        if(get_block(now_point_x + 2, now_point_y) != 0){
          break;
        }
        set_block(now_point_x + 2, now_point_y, index);
        now_point_x += 2;
      }
      else if(direction == ENABLE_DOWN){
        set_block(now_point_x, now_point_y + 1, index);
        if(get_block(now_point_x, now_point_y + 2) != 0){
          break;
        }
        set_block(now_point_x, now_point_y + 2, index);
        now_point_y +=  2;
      }
      else if(direction == ENABLE_LEFT){
        set_block(now_point_x - 1, now_point_y, index);
        if(get_block(now_point_x - 2, now_point_y) != 0){
          break;
        }
        set_block(now_point_x - 2, now_point_y, index);
        now_point_x -= 2;
      }
    }
  }

  return 1;
}

int get_block(int x, int y){
  return g_block[maze_width * y + x];
}

int get_random_block(int *x, int *y){
  int i, j;
  int free_block_count = 0;
  int selected_block;
  int count = 0;

  for(i = 0; i < maze_height; i += 2){
    for(j = 0; j < maze_width; j += 2){
      if(get_block(j,i) == 0){
        free_block_count++;
      }
    }
  }

  if(free_block_count != 0){
      selected_block = rand() % free_block_count + 1;
  }
  else{
    return 0;
  }

  for(i = 0; i < maze_height; i += 2){
    for(j = 0; j < maze_width; j += 2){
      if(get_block(j, i) == 0){
        count++;
      }
      if(count == selected_block){
        *x = j;
        *y = i;
        i = maze_height;
        j = maze_width;
      }
    }
  }

  return 1;
}

void printf_maze(void){
  int i, j;

  for(i = 0; i < maze_height; i++){
    for(j = 0; j < maze_width; j++){
      if(get_block(j, i) == 0){
        printf("■");
      }
      else{
        printf("□");
      }
    }
    printf("\n");
  }
}

void set_block(int x, int y, int num){
  g_block[maze_width * y + x] = num;
}

int main(){
  create_maze(39, 21, 1);
  printf_maze();
  break_maze();
  return 0;
}

inserted by FC2 system