Генерация лабиринтов

[TomCaT]

спорол чепуху. Ранее выложенные Maziacs и в самом деле вроде не работают. А т.к. в этой теме были люди, не слышавшие об этом шедевре-малютке, сюда кладу правильный аттач. (Тот SN плохо с дискеты писал лучше б сразу сказал Disc error).

(вложение MAZIACS.ZIP перемещено на VIRT, 12.6 Кбайт, 13 просмотров на 19 IX 2006)

[Знахарь]

О! правильно - есть такие люди и они благодарствуют !

[Andrew771]

у мой алгоритм, SMT... Или по полочкам ?

Попробуем вспомнить:

Генерится сперва матрица типа

111111111
101010101...
111111111...
101010101
111111111
(вместо 1 - 255)

Потом берется
рнд вход
если справа от входа нет 0 то опять рнд вход

То же для выхода, но в конце, после генерации.

находимся в 0 справа от входа.
рнд верх вниз лево право

Короче... Там есть 3 маркера
0
255 абсолют не проходимо
254

Кажется, вот его человеческое описание с примером на ActionScript: http://coderlife.ru/progr/generaciya-labirinta.html

А чтобы сделать лабиринт с комнатами, за элемент лабиринта надо брать не одну клетку, а квадрат из клеток. Вот здесь уже думал: http://zx.pk.ru/showpost.php?p=361787&postcount=87
Там указан алгоритм Прима или Краскала, но это не обязательно, можно любой другой.

---------- Post added at 15:02 ---------- Previous post was at 14:57 ----------

Описания алгоритмов Прима и Краскала с исходниками на Delphi: http://www.piter-press.ru/attachment...853&at=exc&n=0

---------- Post added at 16:20 ---------- Previous post was at 15:02 ----------

А вот еще такую статью нашел в ZX Review: http://zxpress.ru/article.php?id=1782
Там приведены несколько алгоритмов на Бейсике и один на ассемблере!

[jerri]

тебе нужен этот генератор в виде сорцов?

[Andrew771]

тебе нужен этот генератор в виде сорцов?

да. Мне этот алгоритм больше всего нравится по простоте и быстродействию.

[jerri]

ну как домой доберусь теперь - на работе нету

Добавил
будут вопросы - задавай

Прога сия написана Знахарем
моё в ней только кой какие косметические изменения

[Andrew771]

ОК, спасибо тебе заранее!

[Andrew771]

Прога сия написана Знахарем
моё в ней только кой какие косметические изменения

Попробовал компильнуть - не хватает двух процедур.

Написал свой генератор на этом же принципе для PC, в котором можно побаловаться параметрами генерации, см.файл. Найду оптимальные и сконвертану в ассемблер.

[bsivko]

Каждый уважающий себя геймдевелопер должен написать свой генератор лабиринтов (;
С большой ностальгией просматривал топик.

От себя хочу сказать. Генерация лабиринтов - достаточно простая задача, если усвоить основные принципы. Но после этого не нужно останавливаться. Лабиринты вида Прима-Краскала - это только начало.

Любая генерация происходит для конкретной задачи. Например посмотрим на лабиринты, прошедшие в Google AI Challenge. Их условия:

Maps are limited to 2 to 10 players
Maps must be symmetric
Hills must be between 20 and 150 steps away from other enemy hills (friendly hills can be closer)
Hills may not be within close range, euclidean distance no less than 6
Must be a path through all hills traversable by a 3x3 block
Maps must not contain islands
Maps are limited to at most 200 in each direction
Maps are limited in area to 900 to 5000 area per player, with a total area limit of 25,000.

Один из них: http://ants.aichallenge.org/map.php?...aze_p04_47.map

Он очень непохож на Прима-Краскала. В основном из-за 3х3 блоков, но не только.

Это пример того, что лабиринты бывают очень разные, и делаются они под конкретный геймплей.

И, чтобы не останавливаться, могу предложить следующие лабиринты (для воображения, а не для реализации):
1. Бесконечный лабиринт. Т.е. такой, прохождение которого для игрока требует времени, намного превышающего время его жизни. (геймплей же не обязательно требует бесконечного времени)
2. Динамический лабиринт. Лабиринт меняется в процессе игры, и делает это так, что его свойства сохраняются (например один и только один путь
из любой точки А в точку B).
3. Карта звезд ELITE. Это лабиринт. Лабиринт, в котором из одной звезды (узел графа) в другой можно попасть только тогда, когда расстояние <= 7.0 ly

[goblinish]

Каждый уважающий себя геймдевелопер должен написать свой генератор лабиринтов (;

не геймдевелопер, но...
нашел в архивах интро на 256 байт для ЦЦ, алгоритм из SWAG'a