Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 14.11.2010, 15:57   #1
Taugeshtu
scientist.alien
 
Аватар для Taugeshtu
 
Регистрация: 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 за это полезное сообщение:
Harter (15.11.2010), St_AnGer (15.11.2010), tormoz (14.11.2010)
Старый 14.11.2010, 23:12   #2
ffinder
Дэвелопер
 
Аватар для ffinder
 
Регистрация: 10.09.2007
Сообщений: 1,442
Написано 793 полезных сообщений
(для 1,460 пользователей)
Ответ: Алгоритмы MineCraft-like игр

Сообщение от Taugeshtu Посмотреть сообщение
Насколько я понял, майнкрафт бьет пространство на кранчи 16х16х128, которые пишет в папки, названия которых - координаты кранча. Мне это кажется удобным с точки зрения генерируемого мира, но неудобным с точки зрения мира художественного (если я хочу сохранить на карте тут каньон, там - речку, а там гору с пляжем у подножья - нужно перебирать ключи генератора пока не выпадет что-то похожее на то, чего мне хочется, или копать вручную)
************
Ну а теперь мне интересно, что вы думаете об алгоритмах майнкрафта (не только записи карты мира) ?
я думаю, что это не связанные вещи.
я бы хранил карту чанками на диске, и одним массивом в памяти.
разные файлы могут быть удобны чтобы скидывать изменения мира на диск - не переписывать один огромный файл, а перезаписывать только изменившиеся маленькие.

что гораздо более интересно - это "механика" жидкостей и падающие породы.
всегда удивлялся висящим в воздухе срубленым деревьям в майнкрафте.
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Harter (15.11.2010)
Старый 15.11.2010, 01:24   #3
Taugeshtu
scientist.alien
 
Аватар для Taugeshtu
 
Регистрация: 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
ABTOMAT
Ференька
 
Аватар для ABTOMAT
 
Регистрация: 26.01.2007
Адрес: улица Пушкина дом Колотушкина
Сообщений: 10,741
Написано 5,461 полезных сообщений
(для 15,675 пользователей)
Ответ: Алгоритмы MineCraft-like игр

Ну вот песок, например, падает же
__________________
Мои проекты:
Анальное Рабство
Зелёный Слоник
Дмитрий Маслов*
Различие**
Клюква**

* — в стадии разработки
** — в стадии проектирования
Для проектов в стадии проектирования приведены кодовые имена

(Offline)
 
Ответить с цитированием
Старый 15.11.2010, 02:16   #5
Dr.Evil
Оператор ЭВМ
 
Регистрация: 20.11.2006
Сообщений: 38
Написано 8 полезных сообщений
(для 11 пользователей)
Ответ: Алгоритмы MineCraft-like игр

У каждого грунта 2 основных параметра это: угол внутреннего трения и коэффициент сцепления, "рыхлость" - это пористость грунта. У песка сцепление равно нулю, а угол =27-35 град. Грубо говоря это угол у основания призмы( кучи песка ), при большем угле происходит обрушение. Есть много разным способов расчета обрушения откоса. Сам думал на эту тему, но если не придумать упрощения, то много считать придется.
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо Dr.Evil за это полезное сообщение:
ABTOMAT (18.11.2010), ffinder (15.11.2010)
Старый 18.11.2010, 00:13   #6
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: Алгоритмы MineCraft-like игр

Собственно h1dd3n присылал ссылку на клон майнкрафта на Unity на форум и еще он мне давал почитать статью о его реализации:
http://www.m2h.nl/files/UserCustomiz...tualWorlds.pdf
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо pax за это полезное сообщение:
Dr.Evil (19.11.2010), ffinder (18.11.2010), Taugeshtu (18.11.2010)
Старый 09.01.2013, 01:12   #7
Trofer
AnyKey`щик
 
Регистрация: 09.01.2013
Сообщений: 1
Написано 0 полезных сообщений
(для 0 пользователей)
Ответ: Алгоритмы MineCraft-like игр

Зарегался только что бы сказать большое спасибо автору) Идеи очень классные, мы думали о чём то похожем и скорее всего сделаем что-то подобное скоро))
(Offline)
 
Ответить с цитированием
Старый 09.01.2013, 09:35   #8
AVL
Разработчик
 
Регистрация: 27.01.2011
Адрес: Афипский
Сообщений: 419
Написано 100 полезных сообщений
(для 182 пользователей)
Ответ: Алгоритмы MineCraft-like игр

Если я не ошибаюсь, в майне песок (и гравий, и наковальня) во время падения превращаются из блока в предмет.
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 01:10.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com