Digs - Персональная территория

Авторский проект Артема Глазкова
? 
        Версия для печати (цвет)  

Использование материалов
Заметка #34
11 сентября 2009

Локации



    Под локацией будем понимать некоторую зону, которая отделена от других зон стеной.

    В данном алгоритме локации будут строиться на основе лабиринта. Строим лабиринт без циклов по любому понравившемуся алгоритму (например, по алгоритму Краскала). Далее, для создания N локаций находим N-1 произвольную точку в проходе и устанавливаем туда стену. Таким образом, получаем N не связанных друг с другом лабиринтов. После этого нужно удалить все стены, которые окружены клетками одного и того же лабиринта.

    Теперь подробнее плюс реализация. Почти Copy-Paste с предыдущей заметки:

    Карта представляет собой двухмерный массив клеток. Каждая клетка либо проход (значение ноль), либо стена (значение единица). Чтобы между коридорами оставалось пространство, шаг прохода (а также стены) составляет две клетки. Следовательно, размеры карты должны быть нечетными. Размеры лабиринта заданы как количество шагов по осям: SizeX и SizeY. Реальные размеры лабиринта SizeX*2+1 на SizeY*2+1. На рисунках четные столбцы и строки (нумеруются с нуля) имеют толщину в два раза меньшую, чем нечетные.

    Переменная, хранящая карту:
  map : array[0..SizeY*2,0..SizeX*2] of byte;


    Локации
    Начинаем с того, что строим по какому-либо алгоритму лабиринт без циклов и занимающий все пространство карты. Стены на карте имеют код 1, проход 0. В начальный момент весь лабиринт объявляем единственной локацией. Заменяем все 0 на 2, при этом посчитав, из скольких клеток состоит локация. При построении локаций мы будет стараться сделать их приблизительно одинаковыми по площади. Для этого заведем массив, в котором эти площади будем хранить:

locSize: array[2..LocCount+1] of Integer;

    Массив нумеруем от 2 (код первой локации), чтобы проще к нему было обращаться. Заполнение первой локации:

  locSize[2] := 0;
  for y:=0 to SizeY*2 do
    for x:=0 to SizeX*2 do
      if map[y,x]=0 then
        begin
          map[y,x] := 2;
          inc(LocSize[2]);
        end

    Главный цикл по локациям. Внутри цикла сначала определим локацию, которую будем разбивать (у нее наибольшая площадь), а потом сделаем еще один цикл repeat...until false;, в котором будем искать подходящую точку для разбиения и в случае удачи прерывать его сами.

for i:=Low(LocSize)+1 to High(LocSize) do
  begin
    bigloc := 2;
    for j:=3 to i-1 do
      if locSize[j]>locSIze[bigloc] then bigloc := j;
    repeat
      ...
    until false;
  end;

    Находим точку, которая при удачном исходе проверки будет являться разбивающей. Такая точка должна быть в проходе, но с двух сторон ее должны окружать стены, а с двух проходы. Поэтому одна из координат точки должна быть четной, а другая нечетной. Также точка должна принадлежать локации, которую разбиваем:

x :=  Random(SizeX*2 -1)+1;
if x mod 2=0
  then y := Random(SizeY)*2+1
  else y := Random(SizeY-1)*2+2;
if map[y,x]=bigloc then
  begin
    ...
  end;

    Теперь нужно залить один из лабиринтов новым кодом, одновременно посчитав его площадь. Алгоритм заливки, как и алгоритм построения, здесь не привожу. Каждый выберет себе, какой ему удобнее. Если карта не большая, вполне приемлимо будет использовать обычный рекурсивный алгоритм.

    Если площадь новой локации нас устраивает (у меня не менее четверти изначальной локации), то оставляем как есть, не забыв запомнить площадь в locsize. Иначе, все нужно вернуть в исходное состояние и поискать другую точку.

map[y,x] := 1; //ставим стену
dy := x and 1; //находим смещение для определения, с какой
dx := y and 1; //стороны стены находятся локации
locSize[i] := 0; //В начальные момент площадь нулевая
...
//Здесь вызов заливки локации с новым кодом «I» начиная с точки y+dy,x+dx
//При этом заливка должна увеличивать locsize[i]
...
//Если новая локация больше четверти изначальной...
if (locSize[bigloc] div 4>LocSize[bigloc]-LocSize[i])or
  (locSize[bigloc] div 4>LocSize[i]) then
  begin
    map[y,x] := bigloc;//возвращаем место под стеной локации
    Swap(i,bigloc);//заменяем новые индексы «I» на старые «bigloc»
  end
else //иначе все нормально...
  begin
    //у разбитой локации площадь теперь меньше
    LocSize[bigloc] := LocSize[bigloc] - LocSize[i];
    break; //заканчиваем цикл, переходим к следующему разбиению
  end;

    Здесь функция swap пробегает по всей карте и заменяет в клетках один код на другой.

    Осталось вычистить стенки внутри каждой локации:

for y:=1 to SizeY*2-1 do
  for x:=1 to SizeX*2-1 do
    if (((x+y) and $1)=1)and(map[y,x]=1) then
      begin
        dx := y and $1;
        dy := 1 - dx;
        if map[y+dy,x+dx]=map[y-dy,x-dx]
          then map[y,x] := map[y+dy,x+dx];
      end;

for y:=1 to SizeY-1 do
  for x:=1 to SizeX-1 do
    if (map[y*2-1,x*2]<>1)and(map[y*2-1,x*2]=map[y*2+1,x*2])
      then map[y*2,x*2] := map[y*2-1,x*2]
    else
      if (map[y*2,x*2-1]<>1)and(map[y*2,x*2-1]=map[y*2,x*2+1])
        then map[y*2,x*2] := map[y*2,x*2-1];


    Делаем проходы
    Код приводить не буду. Он достаточно прост, как и сама идея.

    Создаем квадратную матрицу, столбцам и строкам которой задаем индексы от 2 до LocCount+1. Каждый элемент матрицы это ссылка на список стен, которые разделяют локации с соответствующими кодами. При этом матрица будет симметричной, т.е. элемент [y,x] будет хранить ссылку на тот же список, что и [x,y]. Выбираем все стены, у которых одна координата четная, а вторая не четная. Смотрим, какие локации стена разделяет, и заносим в соответствующий список.

    Полученной матрицей можно воспользоваться как графом. Здесь два варианта, либо построить проходы от всех локаций ко всем возможным (смотреть на наличие списка), либо на основе графа запустить алгоритм формирования лабиринта. В любом случае, если между двумя локациями решили сделать проход, то надо выбрать соответствующий список и, выбрав в нем случайную стену, удалить ее.

    Хотя, если предполагается создавать не все связи, а лабиринт, то можно сделать проще. Нужно разрушить те стены, которые строились в самом начале алгоритма для разделения локаций.


    Мысли, пришедшие в процессе
    Введение различных комнат и прочих предопределенных объектов совершается просто. Достаточно разместить, пометить кодом уже готовой локации. Лабиринт в этом случае строится в оставшемся пространстве (каждый алгоритм надо модифицировать отдельно). Если в комнате возможны выходы только в определенном месте, то это просто надо учесть при проделывании проходов, когда собираются списки стен.

    С самими локациями тоже можно устроить разнообразие. Если игра – бродилка, то какую-либо локацию можно не вычищать от стен и там останется лабиринт. Можно еще пометить целую локацию как не используемую. Например, на карте отображать ее как озеро или горный непроходимый массив. Но перед этим нужно проверить проходимость остальных локаций (останется ли граф связный).

    Еще интересная мысль пробежаться в лабиринте из локаций рекурсивным способом. Допустим, на карте есть несколько объектов, к которым должен существовать путь от всех других объектов. Эти объекты разбросаны по разным локациям. Выбираем произвольную локацию, в которой, есть хотя бы один объект, и начинаем рекурсивно обходить весь лабиринт. В определенные моменты мы будем наталкиваться на тупики. В этот момент, если в тупике нет никакого объекта, мы ставим локации специальную метку и начинаем возвращаться из ветки, ставя такие же метки до тех пор, пока не наткнемся на локацию, в которой есть какой-либо объект. Если наткнулись на локацию с объектом (напомню: только при обратном ходе, выходе из рекурсии), то помечаем эту и дальнейшие локации меткой «путь к объекту». Если какая либо ветка, расставляющая «тупиковые» метки натыкается на метку «путь к объекту», то в дальнейшем обратном ходе она начинает проставлять именно ее. В результате такого прохождения каждая локация получает одну из двух меток. Те, которые пометили как «тупик», можно заполнять теми же озерами, горами, лесными массивами.


© 2005-16, Powered By Digs (Написать письмо, vk)