|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
07.06.2011, 17:07
|
#1
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
minecraft
1) я не пытаюсь сделать майнкрафт с элементами крайзиса
2) я вообще не пытаюсь сделать клон майнкрафта
3) я вобще не пытаюсь ничего сделать
просто интересно.
Итак. Собственно вопросы о некоторых приёмах в майнкрафте. Хотя эти приёмы есть во всех играх... но я раньше както не интересовался ими.
Вобщем вопросы:
1) Как происходит столкновения игрока с кубами? Перебираются все кубы в чанке* на котором находится игрок, и проверяется пересечение между игроком и каждым кубом?
2) Как выбирается куб (и его грань), над котором указатель мыши? Опять же, перебираюся все кубы и т.д ?
Размеры одного чанка* — 16 блоков шириной, 16 блоков длиной и 128 блоков глубиной [пруфлинк]. Тоесть 32768 кубов. И перебирать все эти кубы каждый(?) кадр помойму слишком долго.
*чанк - "кусочек" карты.
|
(Offline)
|
|
07.06.2011, 17:11
|
#2
|
Элита
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,157
Написано 502 полезных сообщений (для 1,012 пользователей)
|
Ответ: minecraft
наверно перебираются только кубы которые рядом,например 20*20*20,а сортированы они по пачкам тежи 20*20*20...
2) Как выбирается куб (и его грань), над котором указатель мыши? Опять же, перебираюся все кубы и т.д ?
|
пикают наверно,а потом по id находят в масиве где-нить
|
(Offline)
|
|
07.06.2011, 17:16
|
#3
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: minecraft
пикают наверно,а потом по id находят в масиве где-нить
|
да ты красавчег.
я и спрашиваю, полным перебором?
Все вопросы в силе.
|
(Offline)
|
|
07.06.2011, 18:56
|
#4
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: minecraft
1. Например физика, хотя в майнкрафте наверняка своя. Я вот тут ставил кубики для коллизий рядом с игроком (3х3 клетки, т.е. максимум 9 кубиков), по ним и прыгал.
2. Наверняка есть простой математический способ определить через какие кубики пространства проходит луч, потом по их координатам в мире проверить наличие кубика начиная от начала луча. Если кубик есть - мы его нашли. А грань можно определить исходя из координат предыдущего кубика, через который прошел луч.
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо pax за это полезное сообщение:
|
|
07.06.2011, 19:23
|
#5
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: minecraft
Хм, захотелось аж попробывать!
А если подключик к клону майнкрафта Bullet Physics не слишком жирно будет не будет зависаний?
|
(Offline)
|
|
07.06.2011, 19:38
|
#6
|
Дэвелопер
Регистрация: 10.09.2007
Сообщений: 1,442
Написано 793 полезных сообщений (для 1,460 пользователей)
|
Ответ: minecraft
Сообщение от Den
1) Как происходит столкновения игрока с кубами? Перебираются все кубы в чанке* на котором находится игрок, и проверяется пересечение между игроком и каждым кубом?
2) Как выбирается куб (и его грань), над котором указатель мыши? Опять же, перебираюся все кубы и т.д ?
|
лицорука.жпг
да у нас же регулярная сетка, делим каждый компонент вектора положения на размер грани куба нацело. получаем в каком кубе находимся. проверяем 26 соседних, можно даже не 26 а 7, т.к. знаем в какую сторону смещены относительно центра куба.
как пикать грани? думаю стоит погуглить алгоритм raycasting из wolfenstein3d.
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо ffinder за это полезное сообщение:
|
|
07.06.2011, 19:44
|
#7
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
|
Ответ: minecraft
Дык, есть чанк - он держит 3д массив с ссылками на каждый куб (хотя бы, наличие/отсутствие).
Далее, позиция объекта, по ней можно выбрать радиус ближайших элементов из массива чанка. Не нужно перебирать всё, идите с другой стороны, у вас уже есть инфа, какие нада перебирать, лишь те что рядом. Главное иметь к ним доступ из массива, где каждый индекс, имеет связь с координатами в мире, и есть возможность получать по координатам индекс и наоборот.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
07.06.2011, 19:52
|
#8
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: minecraft
Всё, тему можно закрывать. Спасибо ffinder'у!
|
(Offline)
|
|
07.06.2011, 21:58
|
#9
|
Терабайт исходников
Регистрация: 13.09.2008
Сообщений: 3,947
Написано 2,189 полезных сообщений (для 6,051 пользователей)
|
Ответ: minecraft
1) Как происходит столкновения игрока с кубами? Перебираются все кубы в чанке* на котором находится игрок, и проверяется пересечение между игроком и каждым кубом?
2) Как выбирается куб (и его грань), над котором указатель мыши? Опять же, перебираюся все кубы и т.д ?
|
да это же идеальный случай для octree.
коллизию считать вообще проще простого учитывая что всё состоит из неротированных кубов.
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо Mr_F_ за это полезное сообщение:
|
|
08.06.2011, 00:31
|
#10
|
Ференька
Регистрация: 26.01.2007
Адрес: улица Пушкина дом Колотушкина
Сообщений: 10,741
Написано 5,461 полезных сообщений (для 15,675 пользователей)
|
Ответ: minecraft
Уже Эф написал, что я хотел написать.
Почитай исходники моего недокрафта что ли, там как раз коллизия сделана (в более простом случае - в массиве)
__________________
Мои проекты:
Анальное Рабство
Зелёный Слоник
Дмитрий Маслов*
Различие**
Клюква**
* — в стадии разработки
** — в стадии проектирования
Для проектов в стадии проектирования приведены кодовые имена
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
08.06.2011, 00:37
|
#11
|
Дэвелопер
Регистрация: 10.09.2007
Сообщений: 1,442
Написано 793 полезных сообщений (для 1,460 пользователей)
|
Ответ: minecraft
октри для коллизии тут как собаке пятая нога, ящитаю.
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо ffinder за это полезное сообщение:
|
den (08.06.2011), pax (08.06.2011)
|
08.06.2011, 01:22
|
#12
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: minecraft
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо pax за это полезное сообщение:
|
|
12.06.2011, 19:36
|
#13
|
Знающий
Регистрация: 09.10.2009
Сообщений: 340
Написано 37 полезных сообщений (для 61 пользователей)
|
Ответ: minecraft
Народ у кого было сто комп вырубался при игре? Как полечить?
|
(Offline)
|
|
13.06.2011, 01:06
|
#14
|
ПроЭктировщик
Регистрация: 19.02.2011
Сообщений: 134
Написано 81 полезных сообщений (для 219 пользователей)
|
Ответ: minecraft
С того что упоминал Notch в твиттере и youtube, вся "система столкновений" Minecraft'а - банальный AABB (axis aligned bounding box).
То есть столкновения игрока с 3д массивом реализуются как три цикла for, проверяющие на наличие твердого блока в клетке. Диапазон задается как (x - sizeX) div blockSize .. (x + sizeX) div blockSize.
Поскольку мир весьма и весьма кубический, raycast можно так же упростить, делая проверку подобно рисованию линии в графических редакторах - смещение "указателя" делается постоянно, но проверки блока осуществляются лишь когда изменилась целая часть одной из составляющих.
К примеру, для угла ~44 градуса в двухмерном пространстве проверки будут делатся так:
____X
___XX
__XX_
_XX__
OX___
где "О" - точка в которой находится камера, X - проверяемая клетка карты.
Так же, если это вас интересует, для оптимизации рисования стороны блоков рисуются только для "граничных" блоков, а между блоками "внутри" рельефа не рисуются вовсе. Это неплохо видно на блоке-стекле.
JACUK: скорее всего просто заканчивается память изза постоянных утечек (см. порой нелинейные руки разработчика). Если играть в браузере, то в таком случае будет просто крах браузера (или контейнера плагинов) вместо всего компьютера.
Надеюсь, это помогает.
__________________
Мой сайт-блог. Игры, обновления, примеры для Haxe, JavaScript(+HTML5), GameMaker, Love2d...
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
13.06.2011, 01:54
|
#15
|
scientist.alien
Регистрация: 12.02.2007
Сообщений: 2,098
Написано 1,030 полезных сообщений (для 2,593 пользователей)
|
Ответ: minecraft
То есть столкновения игрока с 3д массивом реализуются как три цикла for, проверяющие на наличие твердого блока в клетке. Диапазон задается как (x - sizeX) div blockSize .. (x + sizeX) div blockSize.
|
Если так в майнкрафте (а судя по тормозам, это таки так) - нотч адский говнокодер. Набуя?! Тут уже говорили - дискретизируем координату, читаем соседние ячейки.. Регулярная сетка же, клинически простой случай.
__________________
Public service announcement: вы можете заблокировать отображение сообщений определённого пользователя, добавив его ник в список игнорируемых.
Tau lab. We LOVE you. We MADE you.
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 12:03.
|