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

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

Генерация лабиринтов, карт
» Случайные карты (прогрызаем)
» Случайные карты-2 (функции)
» Случайные карты-3 (строим)
» Алгоритм Краскала
» Локации
» Комнаты

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

Случайные карты-3 (строим)


 
    В отличие от подхода, использованного в первой статье, данный алгоритм не прогрызает проходы, а наоборот, строит стены в пустом пространстве.

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

  map : array[0..SizeY*2,0..SizeX*2] of byte;

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

    Движение во всех направлениях происходит одновременно. Т.е. создаем список точек, и разрешаем за один шаг сдвинуться из точки на несколько клеток во всех нужных направлениях, записывая каждую новую клетку (в том числе промежуточные) в список, который на следующем шаге считаем исходным.

    Лабиринт
    Очищаем все пространство, а клетки по периметру заполняем стенами. На правой и левой стене создаем вход и выход. Т.е. в произвольном месте (нечетная координата) ставится проход.

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

    Чтобы получить более ветвистые ходы, нужно создать случайным образом еще несколько точек внутри очищенной области, из которых будет начинаться построение. Таким образом, помимо тянущихся с разных сторон ветвей мы получим еще несколько ни с чем не связанных блоков стен.

    Блоки нужно связать, иначе получатся сплошные циклы. Для связи нужно установить в каждой начальной точке некоторое число (ID), которое будет разноситься на все построение. Чтобы состыковать два блока, нужно при очередной проверке на занятость проверить, чтобы ID текущее не совпадало с ID блока, с которым соединяемся. После соединения, нужно в одном из блоков его ID заменить на ID другого блока. Это будет гарантировать, что эти блоки соединятся только один раз.

    Но если соединить вообще все блоки, то проход исчезнет. Чтобы этого не произошло, будем соединять только блоки с одинаковой четностью. А так как, блоки с некоторой четностью могут быть зажаты с разных сторон блокам другой четности, то будут появляться циклы. Это не плохо. В принципе, если придерживаться правила заливать больший ID меньшим, то при отсутствии циклов (т.е. когда все блоки соединены), останутся только стены с ID равным 1 и 2. Следовательно, если остались блоки, из-за которых появились циклы, и циклы нежелательны, то оставшиеся блоки можно уже соединить с блоками с ID равным 1 или 2, без проверки четности.

    Итак, для верхних стен задаем ID=1, для нижних ID=2.

  p1y := 1 + 2*Random(SizeY); //Случайная координата входа
  p2y := 1 + 2*Random(SizeY); //Случайная координата выхода
  for x:=0 to SizeX*2 do
    begin
      map[0,x] := 1;       //верх ID=1
      map[SizeY*2,x] := 2; //низ ID=2
    end;
  for y:=1 to SizeY*2-1 do
    begin
      //над входом/выходом ID=1, под – ID=2
      if y<p1y then map[y,0] := 1 else
        if y=p1y then map[y,0] := 0
          else map[y,0] := 2;
      if y<p2y then map[y,SizeX*2] := 1 else
        if y=p2y then map[y,SizeX*2] := 0
          else map[y,SizeX*2] := 2;
    end;
  //остальную часть карты заполняем нулями
  for y:=1 to SizeY*2-1 do
    for x:=1 to SizeX*2-1 do map[y,x] := 0;

    Теперь процедура создания отростка из стены. Здесь stx, sty координата в стене, откуда будет выходить отросток. dx, dy – направление, в котором будет размещен отрезок.

procedure NewShoot(stx,sty,dx,dy : Integer);
begin
  if map[sty+dy*2,stx+dx*2]=0 then
    begin
      //создаем отросток с тем же кодом
      map[sty+dy,stx+dx] := map[sty,stx];
      map[sty+dy*2,stx+dx*2] := map[sty,stx];
      //заносим точку в список для последующего построения
      Points.Add(xPoint(stx+dx*2,sty+dy*2,dx,dy));
    end;
  end;

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

    После проверки возможности построения из данной текущей точки (P) в заданном направлении (dx, dy), а также вероятности построения, создаем цикл построения (idID текущего построения):

  //Полное смещение в нужном направлении
  ddx := dx * (Random(4)+1);
  ddy := dy * (Random(4)+1);
  for i:=1 to abs(ddx+ddy) do
    begin
      //если новое место не пусто, и не совпадает по четности
      //с текущим построением, заканчиваем цикл
      if (Map[P.y+dy*2,P.x+dx*2]<>0)and((Map[P.y+dy*2,P.x+dx*2]+id) mod 2=1) then exit;
      if (Map[P.y+dy*2,P.x+dx*2]=0)or(Map[P.y+dy*2,P.x+dx*2]<>id) then
        begin
          Map[P.y+dy,P.x+dx] := id;
          //если есть пересечение, то заменяем в построении один ID на другой
          if Map[P.y+dy*2,P.x+dx*2]<>0 then
            begin
              if id<Map[P.y+dy*2,P.x+dx*2]
                then FillWall(Map[P.y+dy*2,P.x+dx*2],id)
                else FillWall(id,Map[P.y+dy*2,P.x+dx*2]);
            end
          else
            //если место пусто, то просто строим стену
            begin
              Map[P.y+dy*2,P.x+dx*2] := id;
              inc(P.y,dy*2);
              inc(P.x,dx*2);
              //конечную точку - в новый список
              np.Add(xPoint(P.x,P.y,dx,dy));
            end;
        end;
    end;
end;

    Один шаг построения:

procedure Step;
var i : Integer;
begin
  //создаем новый список
  np := TxPointArray.Create;
  for i:=0 to Points.Count-1 do
    begin
      sub(Points[i],-1,0);
      sub(Points[i],1,0);
      sub(Points[i],0,1);
      sub(Points[i],0,-1);
    end;
  //замещаем текущий список на новый
  Points.Assign(np);
  np.Free;
end;

    Комнаты
    Комнаты будем делать простые: прямоугольная область, по периметру стены, на правой и левой стене по одному проходу. Такая комната напоминает начальное состояние лабиринта. Как и для лабиринта строим по всему периметру отростки, но здесь они будут торчать не внутрь, а наружу. Чтобы проход всегда через комнату был (чтобы стены его не замкнулись), верхней и нижней стене присваивается один и тот же ID. А чтобы стены комнат могли между собой соединяться, у всех комнат делаем ID одной и той же четности.

    Так как важно, чтобы стены комнат соединились между собой (чтобы проходы чаще шли через комнаты, а не в обход), нужно дать этому построение некоторую фору. В итоге все построение делаем в такой последовательности:
    1. Строим контур лабиринта и комнат;
    2. Делаем отростки от стен комнат;
    3. Совершаем несколько шагов построения (для нижнего рисунка было 2 шага);
    4. Строим отростки стен периметра и добавляем случайные точки в лабиринт, проверяя, чтобы последние не оказались в комнатах;
    5. Запускаем основной процесс построения, пока не иссякнет список точек.

    На этом все. Вот пример такого построения:



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