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

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

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

Использование материалов
Заметка #19
02 сентября 2006

Случайные карты-2 (функции)


    В моем детстве эпохе компьютеров предшествовала эпоха программируемых калькуляторов. МК-61, МК-52. Это были инженерные калькуляторы с обратной польской записью. Программируемыми они назывались потому, что у них была память, состоящая из 105 ячеек, в которые можно было помещать всевозможные программы расчетов. А там где можно написать программу, там же можно написать и игру.

Игр для калькуляторов писалось много, но из-за малого объема памяти все они (игры) были либо больше логические, либо примитивные. Одной из самых интересных (нам тогда так казалось) была игра "Пещера сокровищ" ("Пещера сюрпризов"). Карта (все то!) 7х4 клетки, по которой нужно было передвигаться и искать клад. Размер карты был маленький из-за малого объема памяти. И вот именно в то время у меня появилась мысль сделать игру с псевдослучайной картой.

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

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

    Сначала была написана функция, которая выдает псевдослучайные значения. А точнее она выдает true (проход) либо false (стена). Значение функции зависит только от координаты клетки карты. Придумать функцию достаточно просто, главное чтобы она создавала иллюзию хаотичности. У меня получилась такая:

function Q(x,y : Double) : boolean;
begin
  x := x + dx;
  y := y + dy;
  Result := Frac(100*abs(cos(cos(x)+Sqr(y)))) > 0.15;
end;

    Переменные dx и dy были введены для смещения карты относительно начала. Я написал изменение их управлением с клавиатуры, и поэтому, подобрав эти значения, можно было видеть наиболее подходящую картинку.

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

function Get(x, y: Integer): boolean;
begin
  Result := false;
  // если граница карты, то возвращаем стену
  // (размер карты SizeX*2+1 на SizeY*2+1)
  if (x=0)or(y=0)or(x=SizeX*2)or(y=SizeY*2) then exit;
  case (x mod 2)+(y mod 2)*2 of
    0 : Result := Q(x,y-1) and Q(x,y+1) and Q(x-1,y) and Q(x+1,y);
    1 : Result := Q(x,y) and Q(x,y-1) and Q(x,y+1);
    2 : Result := Q(x,y) and Q(x-1,y) and Q(x+1,y);
    3 : Result := Q(x,y);
  end;
end;


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