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

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

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

Использование материалов
Заметка #13
10 сентября 2005

Случайные карты (прогрызаем)


    Собственно, все началось с одной игрухи на Спектруме (кажется, она называлась Fred). Там бегал мужичок по лабиринту и пытался найти выход. Интересным для меня (с детства помешанном на программировании) был факт, что лабиринты были всегда разные. Эта мысль как-то запала в мою голову и, в итоге, со временем родилась идея, что лабиринты не хранились в сжатом виде и поэтому их было много, а делались случайным образом. Когда пришла мысль, была написана одна из первых игрушек, в которой был встроен генератор карт.

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

    Мне известны два метода прогрызания. Рекурсивный и прогрызание в ширину. Есть четыре направления, по которым делаем проходы. Вообще, насколько мне помнится, характер лабиринта разный в зависимости от выбранного метода. Рекурсия делает какие-то более запутанные ходы. Прогрызание в ширину у меня строит достаточно простые ходы (можно посмотреть по рисунку), но его можно использовать как просто карту, а не лабиринт. В случае с рекурсией нужно последовательность направлений выбирать случайно. Так же случайно определять делать проход, или на этом остановиться. В случае прогрызания в ширину можно случайно последовательность направлений не выбирать, так как проходы идут как бы параллельно.

    Приведу кусок кода только для “ширинного” метода. Субпроцедуре дается на вход направление. С некоторой вероятностью она решает, будем ли делать проход в этом направлении или нет. Если делаем, то определяет, насколько длинный проход. Затем происходит как бы прогрызание прохода до тех пор, пока он не достигнет нужной длины, либо пока не появится на пути другой проход. В последнем случае нужно остановиться до этого прохода, чтобы не было пересечений. Как и для поиска в ширину здесь нужно вести массив координат от которых будет происходить прогрызание. Поэтому в данной процедуре после того, как сделали проход, кладем в массив новых координат координату конца нового прохода.

    Основная процедура вызывает субпроцедуру четыре раза (по разу на направление) для каждой точки из массива координат. В итоге получили такое:

procedure Process;
var np : TPointArray;
    ii : Integer;
  procedure sub(P : TPoint;dx,dy : Integer);
  var ddx,ddy,i : Integer;
  begin
    if Random(6)>4 then exit;
    ddx := dx * (Random(3)+1);
    ddy := dy * (Random(3)+1);
    if (P.x+ddx*2<1) or (P.x+ddx*2>SizeX*2) or
       (P.y+ddy*2<1) or (P.y+ddy*2>SizeY*2) then exit;
    for i:=1 to abs(ddx+ddy) do
      begin
        if Map[P.y+dy*2,P.x+dx*2]<>1 then
          if i<>1 then break else exit;
        Map[P.y+dy,P.x+dx] := 0;
        Map[P.y+dy*2,P.x+dx*2] := 0;
        inc(P.y,dy*2);
        inc(P.x,dx*2);
      end;
    np.Add(Point(P.x,P.y));
  end;
begin
  for ii:=0 to Points.Count-1 do
    Map[Points[ii].x,Points[ii].y] := 0;
  while Points.Count<>0 do
    begin
      np := TPointArray.Create;
      for ii:=0 to Points.Count-1 do
        begin
          sub(Points[ii],-1,0);
          sub(Points[ii],1,0);
          sub(Points[ii],0,1);
          sub(Points[ii],0,-1);
        end;
      Points.Assign(np);
      np.Free;
    end;
end;

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

    Разнообразие первое
    На самом деле просто лабиринт для игр не интересен. Уж больно он скучен и однообразен: одинаковые стены, одинаковые проходы. К тому же в обычном лабиринте нет циклов. Это значит, что из одной точки в другую можно попасть всего по одному пути. В таком случае начинает работать правило правой стены: если все время идти вдоль правой стены, обязательно рано или поздно придешь к выходу.

    Делаем циклы. Находим все такие стены, чтобы две соседние клетки по противоположным направлениям (например, справа и слева) были стеной, а две другие (соответственно, сверху и внизу) проходом. Причем расстояние между двумя последними (по проходам) лежали в заданном интервале. Допустим не менее 20 и не более 40 клеток. Выбираем из списка найденных схем несколько в зависимости от размеров лабиринта и делаем в них проход.

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

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

    Вот тут появляется нюанс. Когда закончили удалять стену, в последней точке для стены нужно выставить атрибут “монолитная”, т.е. стена, которую нельзя удалить. Иначе мы рискуем таким процессом удалить вообще все стены на карте. Почему так произойдет, думайте сами :)

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

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

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

    А вообще, все что написал, это баловство, так как для написания серьезных игр используется более серьезные алгоритмы генерации. Будем считать это тренировкой для ума :)


    Где-то видел хорошую фразу: пьяный червяк роет проходы. Это про лабиринты.


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