1.6. 通路を作ろう

区画の間の分割線に注目してみてください。


[user@machine ~/dir]$ ./test
............#.....................................
............#.....................................
............#.....................................
............#.....................................
............#.....................................
............#.....................................
............#.................###############.....
..######....#.................###############.....
..######....#.................###############.....
..######....#.................###############.....
..######....#.................###############.....
..######....#.................###############.....
..######....#.................###############.....
..######....#.....................................
..######....#.....................................
..######....#.....................................
..######....######################################
..######....#........................#............
..######....#........................#....######..
..######....#........................#....######..
..######....#.####################...#....######..
..######....#.####################...#....######..
..######....#.####################...#....######..
..######....#.####################...#....######..
..######....#.####################...#....######..
..######....#........................#....######..
..######....#........................#....######..
..######....##########################....######..
..######....#........................#....######..
..######....#........................#....######..
............#........................#....######..
............#........................#....######..
............#........................#....######..
............#.........######.........#....######..
............#.........######.........#....######..
............#.........######.........#....######..
............#.........######.........#....######..
............#.........######.........#............
............#........................#............
............#........................#............

この分割線が、そのまま通路を作るときのガイドラインとして使えそうです。


..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..............................###############.....
..######....#################################.....
..######....#.................###############.....
..######....#.................###############.....
..######....#.................###############.....
..######....#.................###############.....
..######....#.................###############.....
..######....#............................#........
..######....#............................#........
..######....#............................#........
..######....#............#################.........
..######....#............#........................
..######....#............#................######..
..######....#............#................######..
..######....#.####################........######..
..######....#.########################....######..
..###########.####################...#....######..
..######......####################...#....######..
..######......####################...#....######..
..######....................#........#....######..
..######....................#........#....######..
..######................#####........#....######..
..######................#............#....######..
..######................#............#....######..
........................#............#....######..
........................#............#....######..
........................#............###########..
......................######..............######..
......................######..............######..
......................######..............######..
......................######..............######..
......................######......................
..................................................
..................................................

そこで、区画を分割するときに、分割線として追加するようにします。


enum {
  COUPLE_VERTICAL = 0,
  COUPLE_HORIZONAL = 1
};

struct _couple {
  int v_or_h;
  struct _rect *rect0, *rect1; 
};

struct _couple *couple_add(int v_or_h, struct _rect *rect0, struct _rect *rect1)
{
  struct _couple *couple;
  couple = my_new(struct _couple, 1);
  couple->v_or_h = v_or_h;
  couple->rect0 = rect0;
  couple->rect1 = rect1;
  couple_list = g_list_append(couple_list, couple);
  return(couple);
}

さらに、区画の”またぎ”が起きないように、区画の分割は、縦に1回と横に1回までしかできないようにします。


struct _rect {
  gboolean cant_split_vertical;
  gboolean cant_split_horizonal;
  int lx, ly, hx, hy;
  struct _room *room;
};

void rect_split(struct _rect *rect_parent)
{
  struct _rect *rect_child;
  if (rect_parent->hy - rect_parent->ly <= MINIMUM_RECT_SIZE * 2) {
    rect_parent->done_split_v = TRUE;
  };
  if (rect_parent->hx - rect_parent->lx <= MINIMUM_RECT_SIZE * 2) {
    rect_parent->done_split_h = TRUE;
  };
  if ((rect_parent->done_split_v) &&
      (rect_parent->done_split_h)) {
    return;
  };
  rect_child = rect_add(rect_parent->lx, rect_parent->ly,
			rect_parent->hx, rect_parent->hy);
  if (rect_parent->done_split_v == FALSE) {
    int split_coord_y;
    split_coord_y = g_random_int_range(rect_parent->ly + MINIMUM_RECT_SIZE, rect_parent->hy - MINIMUM_RECT_SIZE);
    rect_parent->hy = split_coord_y;
    rect_child->ly = split_coord_y;
    rect_parent->done_split_v = TRUE;
    rect_child->done_split_v = TRUE;
    couple_add(COUPLE_VERTICAL, rect_parent, rect_child);
    rect_split(rect_parent);
    rect_split(rect_child);
    return;
  };
  if (rect_parent->done_split_h == FALSE) {
    int split_coord_x;
    split_coord_x = g_random_int_range(rect_parent->lx + MINIMUM_RECT_SIZE, rect_parent->hx - MINIMUM_RECT_SIZE);
    rect_parent->hx = split_coord_x;
    rect_child->lx = split_coord_x;
    rect_parent->done_split_h = TRUE;
    rect_child->done_split_h = TRUE;
    couple_add(COUPLE_HORIZONAL, rect_parent, rect_child);
    rect_split(rect_parent);
    rect_split(rect_child);
    return;
  };
}

これで、あとは通路の線を描くだけです。map_print()に以下を加えます。


  for (li = g_list_first(couple_list); li != NULL; li = g_list_next(li)) {
    couple = (struct _couple *)li->data;
    switch (couple->v_or_h) {
    case COUPLE_HORIZONAL:
      g_assert(couple->rect0->hx == couple->rect1->lx);
      c0x = couple->rect0->hx;
      c0y = g_random_int_range(couple->rect0->room->ly + 1, couple->rect0->room->hy);
      c1x = couple->rect1->lx;
      c1y = g_random_int_range(couple->rect1->room->ly + 1, couple->rect1->room->hy);
      line(c0x, c0y, c1x, c1y);
      line(couple->rect0->room->hx, c0y, c0x, c0y);
      line(couple->rect1->room->lx, c1y, c1x, c1y);
      break;
    case COUPLE_VERTICAL:
      g_assert(couple->rect0->hy == couple->rect1->ly);
      c0x = g_random_int_range(couple->rect0->room->lx + 1, couple->rect0->room->hx);
      c0y = couple->rect0->hy;
      c1x = g_random_int_range(couple->rect1->room->lx + 1, couple->rect1->room->hx);
      c1y = couple->rect1->ly;
      line(c0x, c0y, c1x, c1y);
      line(c0x, couple->rect0->room->hy, c0x, c0y);
      line(c1x, couple->rect1->room->ly, c1x, c1y);
      break;
    };
  };

コードを追っていきましょう。

*で示したところが、c0x, c0yの範囲です。


    case COUPLE_HORIZONAL:
      g_assert(couple->rect0->hx == couple->rect1->lx);
      c0x = couple->rect0->hx;
      c0y = g_random_int_range(couple->rect0->room->ly + 1, couple->rect0->room->hy);
............#.........................
............#.........................
............#.........................
............#.....###############.....
..######....#.....###############.....
..######....*.....###############.....
..######. ..*.....###############.....
..######....*.....###############.....
..######....*.....###############.....
..######....*.....###############.....
..######....*.........................
..######....*.........................
..######....*.........................
..######....*.........................
..######....*.........................
..######....#.........................
............#.........................
............#.........................

/で示したところが、c1x, c1yの範囲です。


      c1x = couple->rect1->lx;
      c1y = g_random_int_range(couple->rect1->room->ly + 1, couple->rect1->room->hy);
............#.........................
............#.........................
............#.........................
............#.....###############.....
..######..../.....###############.....
..######..../.....###############.....
..######. ../.....###############.....
..######..../.....###############.....
..######..../.....###############.....
..######....#.....###############.....
..######....#.........................
..######....#.........................
..######....#.........................
..######....#.........................
..######....#.........................
..######....#.........................
............#.........................
............#.........................

通路を結びます。


      1をline(c0x, c0y, c1x, c1y);
      2をline(couple->rect0->room->hx, c0y, c0x, c0y);
      3をline(couple->rect1->room->lx, c1y, c1x, c1y);
............#.........................
............#.........................
............#.........................
............#.....###############.....
..######....#.....###############.....
..######..../33333###############.....
..######. ..1.....###############.....
..######....1.....###############.....
..######....1.....###############.....
..######....1.....###############.....
..######....1.........................
..######....1.........................
..######2222*.........................
..######....#.........................
..######....#.........................
..######....#.........................
............#.........................
............#.........................

最終的にコードはこうなります。


#include <glib.h>

enum {
  MAP_W = 50,
  MAP_H = 40,
  MINIMUM_ROOM_SIZE = 4,
  MARGIN_BETWEEN_RECT_ROOM = 2,
  MINIMUM_RECT_SIZE = MINIMUM_ROOM_SIZE + (MARGIN_BETWEEN_RECT_ROOM * 2),
  COUPLE_VERTICAL = 0,
  COUPLE_HORIZONAL = 1
};

struct _rect {
  gboolean done_split_v;
  gboolean done_split_h;
  int lx, ly, hx, hy;
  struct _room *room;
};

struct _room {
  int lx, ly, hx, hy;
};

struct _couple {
  int v_or_h;
  struct _rect *rect0, *rect1; 
};

GList *rect_list;
GList *room_list;
GList *couple_list;
gboolean map[MAP_W][MAP_H];

void map_print();
void line(int x0, int y0, int x1, int y1);
void rect_split(struct _rect *rect_parent);
void room_make();
struct _rect *rect_add(int lx, int ly, int hx, int hy);
struct _room *room_add(int lx, int ly, int hx, int hy);
struct _couple *couple_add(int v_or_h, struct _rect *rect0, struct _rect *rect1);

int main(int argc, char *argv[])
{
  int i, j;
  for (j = 0; j < MAP_H; j++) {
    for (i = 0; i < MAP_W; i++) {
      map[i][j] = FALSE;
    };
  };
  rect_list = NULL;
  room_list = NULL;
  rect_split(rect_add(0, 0, MAP_W - 1, MAP_H - 1));
  room_make();
  map_print();
  return 0;
}

void map_print()
{
  int i, j;
  GList *li;
  struct _rect *rect;
  struct _room *room;
  struct _couple *couple;
  int c0x, c0y, c1x, c1y;
  for (li = g_list_first(rect_list); li != NULL; li = g_list_next(li)) {
    break;
    rect = (struct _rect *)li->data;
    for (i = rect->lx, j = rect->ly; i <= rect->hx; i++) map[i][j] = TRUE;
    for (i = rect->lx, j = rect->hy; i <= rect->hx; i++) map[i][j] = TRUE;
    for (i = rect->lx, j = rect->ly; j <= rect->hy; j++) map[i][j] = TRUE;
    for (i = rect->hx, j = rect->ly; j <= rect->hy; j++) map[i][j] = TRUE;
  };
  for (li = g_list_first(room_list); li != NULL; li = g_list_next(li)) {
    room = (struct _room *)li->data;
    for (i = room->lx; i <= room->hx; i++) {
      for (j = room->ly; j <= room->hy; j++) {
      	map[i][j] = TRUE;
      };
    };
  };
  for (li = g_list_first(couple_list); li != NULL; li = g_list_next(li)) {
    couple = (struct _couple *)li->data;
    switch (couple->v_or_h) {
    case COUPLE_HORIZONAL:
      g_assert(couple->rect0->hx == couple->rect1->lx);
      c0x = couple->rect0->hx;
      c0y = g_random_int_range(couple->rect0->room->ly + 1, couple->rect0->room->hy);
      c1x = couple->rect1->lx;
      c1y = g_random_int_range(couple->rect1->room->ly + 1, couple->rect1->room->hy);
      line(c0x, c0y, c1x, c1y);
      line(couple->rect0->room->hx, c0y, c0x, c0y);
      line(couple->rect1->room->lx, c1y, c1x, c1y);
      break;
    case COUPLE_VERTICAL:
      g_assert(couple->rect0->hy == couple->rect1->ly);
      c0x = g_random_int_range(couple->rect0->room->lx + 1, couple->rect0->room->hx);
      c0y = couple->rect0->hy;
      c1x = g_random_int_range(couple->rect1->room->lx + 1, couple->rect1->room->hx);
      c1y = couple->rect1->ly;
      line(c0x, c0y, c1x, c1y);
      line(c0x, couple->rect0->room->hy, c0x, c0y);
      line(c1x, couple->rect1->room->ly, c1x, c1y);
      break;
    };
  };
  for (j = 0; j < MAP_H; j++) { 
    for (i = 0; i < MAP_W; i++) {
      if (map[i][j]) g_print("#"); else g_print(".");
    }; 
    g_print("\n"); 
  }; 
} 

void line(int x0, int y0, int x1, int y1)
{
  int min_x, max_x, min_y, max_y, i, j;
  min_x = MIN(x0, x1);
  max_x = MAX(x0, x1);
  min_y = MIN(y0, y1);
  max_y = MAX(y0, y1);
  g_assert((min_x >= 0) && (max_x < MAP_W) && (min_y >= 0) && (max_y < MAP_H));
  if ((x0 <= x1) && (y0 >= y1)) {
    for (i = min_x; i <= max_x; i++) map[i][max_y] = TRUE;
    for (j = min_y; j <= max_y; j++) map[max_x][j] = TRUE;
    return;
  };
  if ((x0 > x1) && (y0 > y1)) {
    for (i = min_x; i <= max_x; i++) map[i][min_y] = TRUE;
    for (j = min_y; j <= max_y; j++) map[max_x][j] = TRUE;
    return;
  };
  if ((x0 > x1) && (y0 <= y1)) {
    for (i = min_x; i <= max_x; i++) map[i][min_y] = TRUE;
    for (j = min_y; j <= max_y; j++) map[min_x][j] = TRUE;
    return;
  };
  if ((x0 <= x1) && (y0 < y1)) {
    for (i = min_x; i <= max_x; i++) map[i][max_y] = TRUE;
    for (j = min_y; j <= max_y; j++) map[min_x][j] = TRUE;
    return;
  };
}

void rect_split(struct _rect *rect_parent)
{
  struct _rect *rect_child;
  if (rect_parent->hy - rect_parent->ly <= MINIMUM_RECT_SIZE * 2) {
    rect_parent->done_split_v = TRUE;
  };
  if (rect_parent->hx - rect_parent->lx <= MINIMUM_RECT_SIZE * 2) {
    rect_parent->done_split_h = TRUE;
  };
  if ((rect_parent->done_split_v) &&
      (rect_parent->done_split_h)) {
    return;
  };
  rect_child = rect_add(rect_parent->lx, rect_parent->ly,
			rect_parent->hx, rect_parent->hy);
  if (rect_parent->done_split_v == FALSE) {
    int split_coord_y;
    split_coord_y = g_random_int_range(rect_parent->ly + MINIMUM_RECT_SIZE, rect_parent->hy - MINIMUM_RECT_SIZE);
    rect_parent->hy = split_coord_y;
    rect_child->ly = split_coord_y;
    rect_parent->done_split_v = TRUE;
    rect_child->done_split_v = TRUE;
    couple_add(COUPLE_VERTICAL, rect_parent, rect_child);
    rect_split(rect_parent);
    rect_split(rect_child);
    return;
  };
  if (rect_parent->done_split_h == FALSE) {
    int split_coord_x;
    split_coord_x = g_random_int_range(rect_parent->lx + MINIMUM_RECT_SIZE, rect_parent->hx - MINIMUM_RECT_SIZE);
    rect_parent->hx = split_coord_x;
    rect_child->lx = split_coord_x;
    rect_parent->done_split_h = TRUE;
    rect_child->done_split_h = TRUE;
    couple_add(COUPLE_HORIZONAL, rect_parent, rect_child);
    rect_split(rect_parent);
    rect_split(rect_child);
    return;
  };
}

void room_make()
{
  GList *li;
  struct _rect *rect;
  int x, y, w, h;
  for (li = g_list_first(rect_list); li != NULL; li = g_list_next(li)) {
    rect = (struct _rect *)li->data;
    w = g_random_int_range(MINIMUM_ROOM_SIZE, rect->hx - rect->lx - (MARGIN_BETWEEN_RECT_ROOM * 2) + 1);
    h = g_random_int_range(MINIMUM_ROOM_SIZE, rect->hy - rect->ly - (MARGIN_BETWEEN_RECT_ROOM * 2) + 1);
    x = g_random_int_range(rect->lx + MARGIN_BETWEEN_RECT_ROOM, rect->hx - MARGIN_BETWEEN_RECT_ROOM - w + 1);
    y = g_random_int_range(rect->ly + MARGIN_BETWEEN_RECT_ROOM, rect->hy - MARGIN_BETWEEN_RECT_ROOM - h + 1);
    rect->room = room_add(x, y, x + w, y + h);
  };
}

struct _rect *rect_add(int lx, int ly, int hx, int hy)
{
  struct _rect *rect;
  rect = g_new(struct _rect, 1);
  rect->done_split_v = FALSE;
  rect->done_split_h = FALSE;
  rect->lx = lx;
  rect->ly = ly;
  rect->hx = hx;
  rect->hy = hy;
  rect_list = g_list_append(rect_list, rect);
  return(rect);
}

struct _room *room_add(int lx, int ly, int hx, int hy)
{
  struct _room *room;
  room = g_new(struct _room, 1);
  room->lx = lx;
  room->ly = ly;
  room->hx = hx;
  room->hy = hy;
  room_list = g_list_append(room_list, room);
  return(room);
}

struct _couple *couple_add(int v_or_h, struct _rect *rect0, struct _rect *rect1)
{
  struct _couple *couple;
  couple = g_new(struct _couple, 1);
  couple->v_or_h = v_or_h;
  couple->rect0 = rect0;
  couple->rect1 = rect1;
  couple_list = g_list_append(couple_list, couple);
  return(couple);
}
[user@machine ~/dir]$ ./test
..................................................
..................................................
......................................#########...
.........#############................#########...
.........#############................#########...
.........#############................#########...
.........#############............#############...
.........##########################...#########...
.........#############............................
.........#############............................
.........#############............................
..........#.......................................
..........#.......................................
.........##.......................................
.........#........................................
.........#........................................
....#######.......................................
....#######.......................................
....#######....###############################....
....#######.##################################....
....#######.#..###############################....
....#######.#..###############################....
....#########..###############################....
....#######....###############################....
....#######....###############################....
....#######....###############################....
....#######.............#.........................
....#######.............######....................
....#######..................#....................
....#######.........##############....##########..
....#######.........##############.#############..
....#######.........##############.#..##########..
....#######.........##############.#..##########..
....#######.........##############.#..##########..
....#######.........################..##########..
....................##############....##########..
....................##############....##########..
..................................................
..................................................
..................................................