Поиск областей, которые можно исследовать

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

Данная статья была написана для RLNews Darren'а Hebden'а

Эта программа берет карту и делит её на области, которые полностью связаны, то есть не разделены пополам стенами, так что игрок не может нигде встать в области, начинающейся с произвольной точки. Я написал её, чтобы определять весь ли уровень подземелий достижим с лестниц, но вы можете найти для неё другое применение; например, можно использовать её результаты, чтобы обнаруживать где нужно добавить коридоры чтобы получить полностью связанный уровень. Без дальнейших хлопот, вот она.

 #include <stdio.h>

 /*
  * Эта программа делит набор 'сеток', которые могут быть как стеной, 
  * так и полом, на связанные области. Каждая сетка в области связана с 
  * каждым вторым квадратом в этой области вертикальной или горизонтальной 
  * (не диагональной) связью и не соединена с сетками в любой другой области.
  *
  * Мы поддерживаем карту, которая показывает, какая область содержится 
  * в каждой сетке. Чтобы избежать повторов по всей карте, каждый раз, 
  * когда мы обнаруживаем две области-кандидата на соединение, мы используем 
  * таблицу, в которой отображаются числа, использованные в сетке номеров 
  * фактических регионов. В конце вычисления мы перенумеруем сетку, 
  * использующую эту таблицу.
  */

 /* Поменяем её на 1, чтобы посмотреть, как она работает */
 #define debug 0

 #define MAP_WIDTH   12
 #define MAP_HEIGHT  12

 /*
  * На нашей карте 0 - стена, 1 - пол.
  *
  * Нам нужно обозначить границу стен, или мы можем получить странные ошибки.
  */
 char grid[MAP_HEIGHT][MAP_WIDTH] = {
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0},
 {0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0},
 {0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0},
 {0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0},
 {0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0},
 {0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0},
 {0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0},
 {0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0},
 {0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

 #define MAX_REGIONS 16
 #define NO_REGION   0   /* 0 is also a valid region */   

 int region_grid[MAP_HEIGHT][MAP_WIDTH];
 int region_map[MAX_REGIONS];
 int num_regions;

 /*
  * Чтобы уменьшить время на обработку, когда оказывается, что две области 
  * соединяются (а на самом деле, это одна и та же область), мы просто 
  * помечаем их как одинаковые без перенумеровывания сетки. В конце вычисления, 
  * или если мы испытываем недостаток номеров областей, мы используем эту 
  * функцию, чтобы скорректировать все сетки в подлинные номера областей. 
  * Это также уплотняет число область, чтобы впоследствии
  * использовались тем не менее все числа из области 0..num_regions-1.
  */
 void remap_regions(void)
 {
     int region_index[MAX_REGIONS];
     int region_index2[MAX_REGIONS];
     int new_regions;
     int x, y;
     int i; 

     new_regions = 0;

     /*
      * Проверьте полностью области и присвойте каждой новый номер из
      * не-перекартографированной области, чтобы закончить их уплотнение.   
      */
     for (i = 0; i < num_regions; i++)
     {
         /* Не совмещена ли эта область с другим? */
         if (region_map[i] == i)
         {
             /* Нет. Присвоить ей новый номер области. */
             if (debug)
             {
                 printf("Mapping region: #%i -> #%i\n", i,             
                        new_regions);
             }
             region_index[i] = new_regions++;
         }
         else
         {
             /* Она была перенумерована. Проверить на возможные ошибки. */
             if (region_map[region_map[i]] != region_map[i])
             {
                 /*
                  * Мы выявили ошибку: эта область была совмещена
                  * с областью, которая также была совмещена с ней.
                  * Выдать сообщение об ошибке и прервать выполнение.
                  */
                 fprintf(stderr, "Map %i->%i->%i\n", i, region_map[i],
                         region_map[region_map[i]]);
                 abort();
             }  

             /* Присвоить всем областям, лежащим в границах, 
                но не имеющим значений. */
             region_index[i] = NO_REGION;
         }
     }

     /*
      * Создание таблицы двунаправленных элементов, отмеченных
      * при прогоне карты и уплотнении.
      */
     for (i = 0; i < num_regions; i++)
         region_index2[i] = region_index[region_map[i]];  

     /* Перенумеруем сетки, используя рассчитанную нами таблицу */
     for (y = 0; y < MAP_HEIGHT; y++)
         for (x = 0; x < MAP_WIDTH; x++)
             region_grid[y][x] = region_index2[region_grid[y][x]];

     /* Создание новой ничего не делающей области в таблице карты. */
     for (i = 0; i < new_regions; i++)
         region_map[i] = i;

     /* Сохраним новое количество областей */
     num_regions = new_regions;
 }

 /*
  * Выберем две области-кандидата. Это просто подразумевает обновление
  * области таблицы прогона карты.
  */
 void join_regions(int r1, int r2)
 {
     int i;
     int r1_map, r2_map;  

     /* Здесь мы должны оперировать с изначальными областями. */
     r1_map = region_map[r1];
     r2_map = region_map[r2];

     if (debug)
     {
         printf("Joining regions #i) and #i)\n", r1, r1_map,
                r2, r2_map);
     } 

     /* Изменяем таблицу карты областей. */
     for (i = 0; i < num_regions; i++)
         if (region_map[i] == r2_map)
         {
             if (debug)
             {
                 printf("Mapping region #i) -> #%i\n", i,
                        region_map[i], r1_map);
             }
             region_map[i] = r1_map;
         }
  } 

 /*
  * Создаём новую область.
  */
 int new_region(void)
 {
     int i; 

     /* Если больше областей нет, уплотняем их. */
     if (num_regions >= MAX_REGIONS)
     {
         if (debug)
             printf("Remapping regions\n");
         remap_regions();
     }

     /* Если областей всё ещё нет, у нас проблемы. */
     if (num_regions >= MAX_REGIONS)
     {
         fprintf(stderr, "Too many regions\n");
         abort();
     }

     /* Размещаем (Allocate) новую область. */
     i = num_regions++;
     region_map[i] = i;

     if (debug)
         printf("New region: #%i\n", i);

     return i;
 }

 void find_regions(void)
 {
     int x, y;
     int i;

     if (debug)
         printf("Clearing region grid\n");

     /* Очищаем сетку области. */
     for (y = 0; y < MAP_HEIGHT; y++)
         for (x = 0; x < MAP_WIDTH; x++)
             region_grid[y][x] = NO_REGION; 

     /* Инициализируем таблицу карты на нулевой карте. */
     for (i = 0; i < MAX_REGIONS; i++)
         region_map[i] = i;

     /* Начинаем без областей. */
     num_regions = 0;

     /* Рассматриваем каждую ячейку сетки, за исключением границ 
      * (игнорируем их как и стены) 
      */
     for (y = 1; y < MAP_HEIGHT - 1; y++)
     {
         for (x = 1; x < MAP_WIDTH - 1; x++)
         {
             /* Сбрасываем ячейки стен. */
             if (!grid[y][x])
                 continue; 

             if (debug)
                 printf("(i) ", x, y);

             /* 
              * Рассматриваем возможные комбинации левых [и] верхних
              * ячеек.
              */
             if (!grid[y - 1][x])
             {
                 if (!grid[y][x - 1])
                 {
                     /* Слева или сверху нет пола */
                     region_grid[y][x] = new_region();
                 }
                 else
                 {
                     /* Пол есть слева, но отсутствует сверху */
                     if (debug)
                     {
                         printf("Copying over #%i\n", 
                                region_grid[y][x - 1]);
                     }
                     region_grid[y][x] = region_grid[y][x - 1];
                 }
             }
             else
             {
                 if (!grid[y][x - 1])
                 {
                     /* Пол есть сверху, но отсутствует слева */
                     if (debug)
                     {
                         printf("Copying down #%i\n", 
                                region_grid[y - 1][x]);
                     }
                     region_grid[y][x] = region_grid[y - 1][x];
                 }
                 else
                 {
                     /*
                      * Пол и слева и сверху - это ячейки одной
                      * области?
                      */
                     if (region_map[region_grid[y - 1][x]] !=
                         region_map[region_grid[y][x - 1]])
                     {
                         /* No, join them. */
                         join_regions(region_grid[y - 1][x],
                                      region_grid[y][x - 1]);
                     }

                     /* Они не из одной области, так что копируем их. */
                     if (debug)
                     {
                         printf("Copying down #%i\n", 
                                region_grid[y - 1][x]);
                     }
                     region_grid[y][x] = region_grid[y - 1][x];
                 }
             }
         }
     }

     /* Делаем окончательный прогон, чтобы уточнить region_grid[][]. */
     remap_regions();
 }

 /*
  * Распечатываем наши результаты.
  */
 void print_map(void)
 {
     int x, y;

     for (y = 1; y < MAP_HEIGHT - 1; y++)
     {
         for (x = 1; x < MAP_WIDTH - 1; x++)
         {
             if (grid[y][x])
             {
                 printf("%c", 'A' + region_grid[y][x]);
             }
             else
                 printf(" ");
         }
         printf("\n");
     }
 }

 int main(void)
 {
     find_regions();

     print_map();

     return 0;
 } 



Автор: Ross Morgan-Linial.
Источник: Finding Explorable Regions.
Перевел: Дмитрий О. Бужинский [Bu], 02.06.2005.