Поиск областей, которые можно исследовать
Материал из RLGClub :: Клуб любителей рогаликов
Данная статья была написана для 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.
