|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
14.11.2010, 15:57
|
#1
|
scientist.alien
Регистрация: 12.02.2007
Сообщений: 2,098
Написано 1,030 полезных сообщений (для 2,593 пользователей)
|
Алгоритмы MineCraft-like игр
Warning! Алгоритмическая база топикстартера очень маленькая, так что просьба приводить ссылки на описание предлагаемых/обсуждаемых алгоритмов. Да, я до сих пор не выучил Octree. Заранее спасибо.
Знаю, в эту ветку форума мало кто заглядывает, но тем не менее. Заинтересовала меня алгоритмическая подоплека майнкрафта и возможные альтернативы. Самый любопытный вопрос - хаки для уменьшения размера карты, хранимой на диске.
Насколько я понял, майнкрафт бьет пространство на кранчи 16х16х128, которые пишет в папки, названия которых - координаты кранча. Мне это кажется удобным с точки зрения генерируемого мира, но неудобным с точки зрения мира художественного (если я хочу сохранить на карте тут каньон, там - речку, а там гору с пляжем у подножья - нужно перебирать ключи генератора пока не выпадет что-то похожее на то, чего мне хочется, или копать вручную)
Какая идея пришла в голову мне во время бесед с Данилом и PAX'ом:
во-первых, хранить не байт информации для одного кубика, а бит. Просто флаг существования в данной точке пространства материи.
во-вторых, модифицировать формат кранча. не просто развернутый в последовательность бит массив, а развернутый по-плоскостно (т.е. вертикальная координата меняется после того, как записали все клетки в этой горизонтальной плоскости) массив, содержащий запись вида:
12 9 4
где 12 - число следующих за предыдущей отметкой других знаков. Началом всегда считается 0, т.е. запись выше равна:
000000000000 111111111 0000
(но в файле использовать 15-ричную систему, 16-й символ (код "1111") - конец числа, указывающего длинну последовательности)
Почему я предлагаю такой формат записи:
очень маловероятно, что игрок захочет сделать "решето" (а если прикрутить потом физику обвалов - у него это и вовсе не получится), поэтому внутренний механизм сжатия, основанный на гипотезе больших монотонных пространств (заполненных/пустых) предположительно даст больше выигрыша, чем какой-нибудь алгоритм со словарем...
Идем дальше. А как узнать, какого типа этот конкретный кубик?
Тут я предлагаю использовать хитрую штуку по имени "геологические карты": текстуры 1024х1024. В R-канале - толщина слоя от конца предыдущего слоя до начала следующего (или от дна мира, если предыдущего слоя нет; или до поверхности, если следующего слоя нет), в G-канале - по 4 бита на тип породы и тип примеси, в B- и A-каналы можно засунуть дополнительную информацию. Почему именно текстуры? Просто проще редактировать. На 1 тексель приходится площадь либо 1 (0.5?) кранча, либо 10х10 кубиков - тут надо посмотреть, как удобнее будет. Детализировать (определять, какой конкретно кубик какого конкретно материала) предлагаю процедурными алгоритмами (каким-нибудь 100%-повторяемым нойзом)
В итоге 10-20 текстурами мы опишем ландшафт 10х10 километров, созданный дизайнером а не машиной.
Лирическое отступление: если задуматься, то такой подход наиболее реалистичен, что ли. Вы задаете форму мира и примерно намечаете его содержание - а машина перемешивает различные породы, давая игроку ощущения одновременно и машинного многообразия, и ручной работы.
Спавнеры и прочие особенности я думаю имеет смысл записывать в форме отдельного блока данных с указанием координат и типа элемента.
Ну и наконец, куда записывать произведения игрока:
Тут можно писать кранчи "в лоб" как это сделано в майнкрафте - байтовые массивы. Возможно - кубические кранчи (не знаю, насколько абсурдна эта фраза, не знаю точного определения слова "кранч") произвольного размера в произвольных координатах - с целью уменьшения опять же занимаемого на диске места... Но скорее всего игра с произвольной разбивкой не стоит свеч, и "в лоб" решить задачу будет проще.
Последнее. Как это всё собрать в единую картинку мира:
(геологические данные + интерполяция нойзом) * битовую запись существования материи + запись уникальных объектов (спавнеров) + запись скрафченного игроком.
Разумеется, всё это - в рамках зоны видимости.
Ну а теперь мне интересно, что вы думаете об алгоритмах майнкрафта (не только записи карты мира) ?
__________________
Public service announcement: вы можете заблокировать отображение сообщений определённого пользователя, добавив его ник в список игнорируемых.
Tau lab. We LOVE you. We MADE you.
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо Taugeshtu за это полезное сообщение:
|
|
14.11.2010, 23:12
|
#2
|
Дэвелопер
Регистрация: 10.09.2007
Сообщений: 1,442
Написано 793 полезных сообщений (для 1,460 пользователей)
|
Ответ: Алгоритмы MineCraft-like игр
Сообщение от Taugeshtu
Насколько я понял, майнкрафт бьет пространство на кранчи 16х16х128, которые пишет в папки, названия которых - координаты кранча. Мне это кажется удобным с точки зрения генерируемого мира, но неудобным с точки зрения мира художественного (если я хочу сохранить на карте тут каньон, там - речку, а там гору с пляжем у подножья - нужно перебирать ключи генератора пока не выпадет что-то похожее на то, чего мне хочется, или копать вручную)
************
Ну а теперь мне интересно, что вы думаете об алгоритмах майнкрафта (не только записи карты мира) ?
|
я думаю, что это не связанные вещи.
я бы хранил карту чанками на диске, и одним массивом в памяти.
разные файлы могут быть удобны чтобы скидывать изменения мира на диск - не переписывать один огромный файл, а перезаписывать только изменившиеся маленькие.
что гораздо более интересно - это "механика" жидкостей и падающие породы.
всегда удивлялся висящим в воздухе срубленым деревьям в майнкрафте.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
15.11.2010, 01:24
|
#3
|
scientist.alien
Регистрация: 12.02.2007
Сообщений: 2,098
Написано 1,030 полезных сообщений (для 2,593 пользователей)
|
Ответ: Алгоритмы MineCraft-like игр
Как раз по случаю вчера наткнулся на соседнем ресурсе на тему о водопадах.. Один умелец высчитывал сумму высоты террайна + высоты столба жидкости на нем, если в любом из соседних тайлов эта сумма была меньше - перетекаем туда.
А падающие породы это вполне реализуемо. Нужно определить коэффициент "рыхлости" породы, и если он не превышен какой-либо загогулиной - ронять кусок породы, висящий в воздухе, до контакта с поверхностью. А если он упал на какой-нибудь шпиль - тут начнутся проверки на "рыхлость" породы
__________________
Public service announcement: вы можете заблокировать отображение сообщений определённого пользователя, добавив его ник в список игнорируемых.
Tau lab. We LOVE you. We MADE you.
|
(Offline)
|
|
15.11.2010, 02:02
|
#4
|
Ференька
Регистрация: 26.01.2007
Адрес: улица Пушкина дом Колотушкина
Сообщений: 10,742
Написано 5,461 полезных сообщений (для 15,675 пользователей)
|
Ответ: Алгоритмы MineCraft-like игр
Ну вот песок, например, падает же
__________________
Мои проекты:
Анальное Рабство
Зелёный Слоник
Дмитрий Маслов*
Различие**
Клюква**
* — в стадии разработки
** — в стадии проектирования
Для проектов в стадии проектирования приведены кодовые имена
|
(Offline)
|
|
15.11.2010, 02:16
|
#5
|
Оператор ЭВМ
Регистрация: 20.11.2006
Сообщений: 38
Написано 8 полезных сообщений (для 11 пользователей)
|
Ответ: Алгоритмы MineCraft-like игр
У каждого грунта 2 основных параметра это: угол внутреннего трения и коэффициент сцепления, "рыхлость" - это пористость грунта. У песка сцепление равно нулю, а угол =27-35 град. Грубо говоря это угол у основания призмы( кучи песка ), при большем угле происходит обрушение. Есть много разным способов расчета обрушения откоса. Сам думал на эту тему, но если не придумать упрощения, то много считать придется.
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо Dr.Evil за это полезное сообщение:
|
|
18.11.2010, 00:13
|
#6
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Алгоритмы MineCraft-like игр
Собственно h1dd3n присылал ссылку на клон майнкрафта на Unity на форум и еще он мне давал почитать статью о его реализации:
http://www.m2h.nl/files/UserCustomiz...tualWorlds.pdf
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо pax за это полезное сообщение:
|
|
09.01.2013, 01:12
|
#7
|
AnyKey`щик
Регистрация: 09.01.2013
Сообщений: 1
Написано 0 полезных сообщений (для 0 пользователей)
|
Ответ: Алгоритмы MineCraft-like игр
Зарегался только что бы сказать большое спасибо автору) Идеи очень классные, мы думали о чём то похожем и скорее всего сделаем что-то подобное скоро))
|
(Offline)
|
|
09.01.2013, 09:35
|
#8
|
Разработчик
Регистрация: 27.01.2011
Адрес: Афипский
Сообщений: 419
Написано 100 полезных сообщений (для 182 пользователей)
|
Ответ: Алгоритмы MineCraft-like игр
Если я не ошибаюсь, в майне песок (и гравий, и наковальня) во время падения превращаются из блока в предмет.
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 15:08.
|