Разработка ZXOOM

[Lethargeek]

Еще немного - и получится нормальный рогалик

[Andrew771]

Да, вы оба меня убедили делать самогенерирующийся лабиринт. Я и сам изначально так хотел, только во второй версии. Теперь лучше сделаем в первой! Алгоритм Дейкстры есть, но я хочу только с одним правильным маршрутом, надо подумать, как сделать. Возможно, и из готовых кусков.
Динамическое изменение карты лучше не делать - сложновато и не реалистично.
Карту открывать по мере прохождения - думал над этим. Придется еще один бит заводить для каждой клетки (видима/не видима) - не хорошо. Я, кстати, изменил размеры лабиринта, увеличил даже немного, теперь 128х128 (8192 байт) вместо 150х100 (7500 байт) - так легче высчитывать адреса клеток. Второй параметр может быть и не 128, так что будем регулировать, если не хватит места под спрайты. 2048 байт под биты видимости отдавать жалко. Нужно что-то придумать еще.

---------- Post added at 12:14 ---------- Previous post was at 12:08 ----------

Алгоритм Дейкстры для готовых кусков лабиринта - только что стукнуло в голову

[NovaStorm]

>Нужно что-то придумать еще.
Придумать конечно можно, но при таких объёмах данных код обращения к элементу массива будет настолько большим, что перекроет выигрыш.
ЗЫ: Хотяяя =) Может можно не хранить карту, а генерировать её в реалтайме?

[Sinus]

Andrew771, а дейкстра чем поможет то? алгоритм дейкстры используется для поиска минимального пути в графе.
генерить лабиринт, а потом проверять на прохождаемость? медленно будет.

лучше делать так (пишу по памяти, так что где-то могут быть неточности; лучше найти в интернете подобный алгоритм):

1) есть поле размера W*H, W и H - чётные
2) рисуем границу
3) выбираем вход и выход - для этого убираем 2 граничных стенки (координаты либо [int(rand() * (w-1)) + 1, 0] либо [0, int(rand() * (р-1)) + 1] либо [..., h-1] либо [w-1, ...])

4) выбираем какую стенку надо добавить - горизонтальную либо вертикальную. например, горизонтальную. тогда y=int(rand() * (h-1) + 1) , size = int(rand() * ((w-2)/2) + 1) * 2
5) for x = 1 to w-2 step 2
6) if не_пусто(x, y) then next i (если дошли до конца, а всё занято, то надо выбрать другой y)
7) рисовать стенку от x,y до x+size,y. если в процессе рисования наткнулись на стенку, то надо стереть кубик до стенки. типа так (# - стенка которая уже есть, + - которую рисуем):

....#....
++++#....
....#....

превращается в:

....#....
+++.#.+++
....#....

8) goto 4

если держать список строк и столбцов, где ещё можно поставить стенку, то тогда в шаге 6 не надо будет выбирать новую случайную координату. вместо этого в шаге 4 y выбирается из списка (а значит там заведомо есть пустые места).

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

[Andrew771]

алгоритм дейкстры используется для поиска минимального пути в графе

Тьфу, я перепутал фамилии. Я имел в виду алгоритмы Прима и Краскала. Вот туть, из книжки по Delphi: http://www.piter-press.ru/attachment...853&at=exc&n=0 По моему, какой-то из них ты и описал. Читал когда-то про них теоретически. Только надо посмотреть теперь, они дают один вариант прохождения или нет...
Нужен именно один. Иначе игру пройти будет легко.

---------- Post added at 14:48 ---------- Previous post was at 14:44 ----------

Сейчас пока я занят рисованием перспективы, чтобы Jukov без дела не сидел. Тоже нетривиальная задача, искажения пока получаются на боковых кубах, слишком растянуты. Читаю теорию тут: http://shkola-izo.livejournal.com/#a...hkola_izo-7623

[Andrew771]

Нарисовал сетку перспективы, в соответствии со всеми правилами построения (см. приложенный файл). Теперь еще нужно вторую сетку с видом под углом 45 градусов.
Jukov, тебе в каком формате бросить и что нужно написать? Координаты всех пересечений, размеры и т.п. - что конкретно? Я в AutoCAD точно могу измерить.

[Advertiser]

[Jukov]

Сообщи размеры в пикселях всех фронтальных спрайтов (которые представляют из себя простые прямоугольники)

[Andrew771]

Прямоугольники вот:

длина-высота
150x112
66x50
38x29
27x20
21x15
17x13
14x11

плюс-минус 1 пиксель допускается.

Боковые трапеции нужны?

[Andrew771]

Хотяяя =) Может можно не хранить карту, а генерировать её в реалтайме?

Как я понимаю, мы говорим про мини-карту? Сама-то карта хранится уже.
Кстати, если генерить саму карту по ходу, то нужно хранить в точности то, где уже прошел игрок. Иначе при возвращении он не узнает, где был. В общем, всё равно приходится хранить основную карту.
Мини-карту, чтоб не хранить каждый ее бит в 2048 байтах, можно высчитывать на лету. Для этого, например, можно:
1. Запомнить все клетки, где был игрок. Точнее, даже не клетки, а, для экономии памяти, перемещения игрока от начальной позиции. По 2 бита на перемещение - 4 значения: вперед, назад, влево, вправо. Ессно, при возвращении в клетку, где уже был, создавать новое подмножество перемещений с запоминанием этой клетки. А еще - для большей экономии памяти - соседние посещенные клетки тоже сокращать. А уж по этим перемещениям высчитывать все окружающие клетки и их выводить на мини-карту. Теоретически, даже если игрок посетит все клетки лабиринта, всё равно получится меньше 2048 байт. Недостатки - слишком сложно для реализации и быстродействие будет хромать. Хотя, если мини-карту выводить только "по требованию", то пару-тройку секунд игрок может подождать.
2. Можно разбить лабиринт на условные квадраты, к примеру, 4х4 клетки. Тогда, если игрок посетил хотя бы одну клетку из квадрата, то весь квадрат виден на мини-карте. В памяти это займет, если по биту на квадрат, всего каких-то 128 байт! Недостаток есть небольшой - иногда будет видно частично то, что недоступно через стенку.

[Jukov]

Боковые трапеции нужны?

Попозже. Надо пока подумать как их вообще сделать