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

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

Использование материалов
Заметка #33
22 августа 2009

Алгоритм Краскала



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

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

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

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

    Второй массив:
  map2: array[0..SizeY*2,0..SizeX*2] of Integer;

    Элемент, описывающий стену:
TxPoint = record
  x,y,dx,dy : Integer;
end;

   x и y координаты стенки, dx и dy – единичное смещение, для нахождения координат локаций, разделенных стеной. Координаты локаций, соответственно, [y+dy,x+dx] и [y-dy,x-dx]. Вообще, dx и dy можно было и не хранить, а находить локации исходя из четности x и y, но я сделал именно так, для наглядности кода.

   Объявляем список (у меня массив) стен и заполняем:

var
  Walls: array[0..(SizeX-1)*SizeY+SizeX*(SizeY-1)-1] of TxPoint;
begin
  for y:=0 to SizeY-1 do
    for x:=0 to SizeX-2 do
      Walls[y*(SizeX-1)+x] := xPoint(x*2+2,y*2+1,1,0);
  for x:=0 to SizeX-1 do
    for y:=0 to SizeY-2 do
      Walls[(SizeX-1)*SizeY + x*(SizeY-1)+y] := xPoint(x*2+1,y*2+2,0,1);

    Функция xPoint(x,y,dx,dy: Integer), по подобию функции Point, возвращает запись, заполненную переданными значениями.

    Перемешиваем: меняем каждый элемент списка со случайным:

for x:=0 to High(Walls) do
  begin
    y := Random(High(Walls)+1);
    tmp := Walls[x];
    Walls[x] := Walls[y];
    Walls[y] := tmp;
  end;

    Заполняем карту. В первом массиве все заполняем стенами кроме локаций (нечетные x и y). Во втором проставляем номера локациям.

for y:=0 to SizeY*2 do
  for x:=0 to SizeX*2 do
    map[y,x] := 1-(x*y) mod 2;

for y:=0 to SizeY-1 do
  for x:=0 to SizeX-1 do
    map2[y*2+1,x*2+1] := y*SizeX+x+1;

    А теперь сам цикл:

for i:=0 to High(Walls) do
  with Walls[i] do
    if map2[y+dy,x+dx]<>map2[y-dy,x-dx] then
      begin
        map[y,x] := 0;
        Fill(map2[y+dy,x+dx],map2[y-dy,x-dx]);
      end;

    Функция Fill пробегает по всей карте и заменяет один номер на другой. Если хочется, чтобы она работала чуть быстрее, то можно завести массив прямоугольников (размер SizeX*SizeY), описывающих локации (крайние координаты локации). Тогда замену номеров можно будет делать не по всей карте, а только в нужном прямоугольнике. При объединении локаций производить суммирование прямоугольников. При этом для быстроты надо менять номера в локации, у которой прямоугольник имеет меньшую площадь.

    С построением комнат все достаточно просто. К примеру, для прямоугольной комнаты нужно вычистить в ней все стенки и сделать всю комнату одной локацией: один и тот же номер во всех клетках.


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