1.4. 区画わけをしよう

区画わけをプログラムしていきます。

区画を追加する関数、rect_addを書きます。


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

GList *rect_list;

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

区画を分けていく関数、rect_splitを書きます。この関数は再帰的に呼び出されて、与えられた区画をさらに細かく分けていきます。今はコードにしてないところがあります。それは、再帰の終了条件と、分割は縦か横かの判断です。


enum {
  MINIMUM_RECT_SIZE = 4
};

void rect_split(struct _rect *rect_parent)
{
  struct _rect *rect_child;
  /*
   * 再帰の終了条件
   * if (...) return;
   */
  rect_child = rect_add(rect_parent->lx, rect_parent->ly,
			rect_parent->hx, rect_parent->hy);
  if (縦に分割するべき) {
    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_split(rect_parent);
    rect_split(rect_child);
    return;
  };
  if (横に分割するべき) {
    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_split(rect_parent);
    rect_split(rect_child);
    return;
  };
}

再帰で区画が分けられるかどうか、試してみましょう。再帰の終了条件は、区画が細かくなりすぎるときとします。分割の横か縦かは、とりあえず乱数で決めます。出力は、区画の枠が"#"となるようにします。さらに、出力を、関数map_printに任せるようにします。


#include <glib.h>

enum {
  MAP_W = 50,
  MAP_H = 40,
  MINIMUM_RECT_SIZE = 8
};

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

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

void map_print();
void rect_split(struct _rect *rect_parent);
struct _rect *rect_add(int lx, int ly, int hx, int hy);

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;
  rect_split(rect_add(0, 0, MAP_W - 1, MAP_H - 1));
  map_print();
  return 0;
}

void map_print()
{
  int i, j;
  GList *li;
  struct _rect *rect;
  for (li = g_list_first(rect_list); li != NULL; li = g_list_next(li)) {
    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 (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 rect_split(struct _rect *rect_parent)
{
  struct _rect *rect_child;
  if ((rect_parent->hy - rect_parent->ly <= MINIMUM_RECT_SIZE * 2) ||
      (rect_parent->hx - rect_parent->lx <= MINIMUM_RECT_SIZE * 2)) {
    return;
  };
  rect_child = rect_add(rect_parent->lx, rect_parent->ly,
			rect_parent->hx, rect_parent->hy);
  if (g_random_int_range(0, 2) == 0) {
    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_split(rect_parent);
    rect_split(rect_child);
    return;
  }  else {
    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_split(rect_parent);
    rect_split(rect_child);
    return;
  };
}

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

実行結果はこのようになります。

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

分割するごとにmap_printを呼び出すと、その様子を見ることができます。


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