Что можно нарисовать по клеточкам из майнкрафта: Рисунки по клеточкам «Майнкрафт» ☆ 39 рисунков

Minecraft: видеоигра, которая развивает клетки детского мозга

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

Стивен Шенкленд

30 марта 2016 г. 6:00 утра по тихоокеанскому времени

Стивен Шенкленд главный автор

Стивен Шенкленд работает репортером CNET с 1998 года и пишет о процессорах, цифровой фотографии, искусственном интеллекте, квантовых вычислениях, информатике, материаловедении, суперкомпьютеры, дроны, браузеры, 3D-печать, USB и новые вычислительные технологии в целом. Он питает слабость к группам стандартов и интерфейсам ввода/вывода. Его первая крупная сенсация была о радиоактивных кошачьих какашках.

Опытные процессоры, полупроводники, веб-браузеры, квантовые вычисления, искусственный интеллект, 3D-печать, дроны, информатика, физика, программирование, материаловедение, USB, UWB, Android, цифровая фотография, наука

См. полную биографию

7 мин чтения

Обеспокоены тем, что не можете оторвать свою дочь от Майнкрафта? Беспокоитесь о том, что ваш сын каждую минуту одержим ходами в суперпопулярной видеоигре?

Холод. Оказывается, Майнкрафт наращивает клетки мозга, а не растворяет их.

Minecraft — это не чертовы палаши и горящая резина. В нем нет сложных сюжетных линий или великолепно прорисованных изображений инопланетных солдат. Вместо этого он заполнен людьми, животными, деревьями и зданиями, которые выглядят так, как будто они построены из цифрового Лего. В каком-то смысле они были. Вселенная Minecraft состоит из блоков, представляющих такие материалы, как грязь, деревья, камень, руды и вода. Игроки добывают, а затем используют эти блоки для создания укрытий, инструментов и оружия, необходимых им для защиты от ночных атак монстров, называемых «мобами».

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

Попутно юные игроки в Minecraft изучают такие вещи, как компьютерное кодирование, инженерное дело, архитектуру, городское планирование и математику.

«Мне просто нравится аспект программирования. Он позволяет вам изменить саму игру», — говорит Эйден ЛаФранс, 10-летний мальчик из Ратона, штат Нью-Мексико, который играет в Minecraft с 6 лет. Последний проект Эйдена — решетка — оборонительные ворота, защищавшие средневековые замки, — которые автоматически поднимаются, когда персонаж проходит перед ними. Он подробно описывает свою работу на YouTube с объяснением того, как двухпоршневые удлинители и башня с горелкой заставляют ее работать.

«Я хотел бы стать программистом», — говорит Эйден. «Я вижу, что Minecraft помогает мне достичь этого».

Увеличить изображение

Заядлые фанаты Minecraft воссоздали Вестерос из «Игры престолов».

Maruku/WesterosCraft

Творческая искра

Minecraft предлагает два основных способа игры. В режиме выживания вы добываете сырье, такое как деревья и уголь, а затем создаете убежище и свет, чтобы противостоять ночному натиску мобов. Творческий режим, напротив, позволяет вам строить без ограничений, поэтому вы можете придумывать архитектурные прихоти, такие как летающие замки или интерактивные конструкции, такие как мины-ловушки для поимки плохих парней.

В Minecraft есть множество способов создать довольно сложные машины и сценарии. Одним из первых является «красный камень», материал, передающий электрические сигналы, которые активируют всевозможные действия типа «если это то, то то» — например, открытие двери, когда персонаж наступает на чувствительную к давлению пластину, или срабатывание поршня, чтобы толкнуть тыкву на конвейер, когда она станет достаточно большой. Наиболее впечатляюще то, что логические схемы, построенные из красного камня, могут образовывать работающий компьютер в мире Minecraft.

Дети приобретают более продвинутые компьютерные навыки с помощью «командных блоков» Minecraft — кода, который меняет правила игры. Это может быть что угодно, от изменения погоды до создания непобедимого летающего кальмара.

«Поскольку нет явной цели, нет непосредственного сюжета, нет структуры, у вас есть гибкость и свобода делать то, что вы хотите», — говорит Джефф Хейнс из Common Sense Media, которая оценивает программное обеспечение и игры на соответствие возрасту и ставит Minecraft на первое место. балл «обучения». «Это способствует развитию жизненных навыков, таких как творчество, любопытство, исследование и работа в команде».

Детское пространство

Шведский разработчик Mojang выпустил Minecraft в 2009 году. С тех пор в игре зарегистрировались более 100 миллионов пользователей. На данный момент было продано более 70 миллионов копий для ПК с Windows и компьютеров Apple Mac, игровых консолей Xbox и PlayStation, а также мобильных устройств под управлением мобильных операционных систем Apple iOS и Google Android.

Microsoft была настолько впечатлена, что купила Mojang в 2014 году за 2,5 миллиарда долларов.

Сегодня преподаватели используют Minecraft для обучения всему: от естественных наук, технологий, инженерии и математики (STEM) до языка, истории и искусства. Но именно дети показали путь, превратив Minecraft в конструктивный инструмент, публикуя учебные пособия, делясь проектами и кодом и помогая друг другу в Интернете.

«Minecraft застал всех врасплох», — говорит Йохан Крюгер, родитель и программист, известный в мире Minecraft как Драгноз. Его уроки на YouTube смотрят более 129 000 подписчиков. «Прежде чем кто-либо узнал о его силе или о том, что он может быть образовательным, дети уже захватили мир и владели им».

Грамотные в Minecraft дети часто бегают вокруг родителей, желая не отставать. Это определенно верно для родителей Эйдена, Гаррета и Лиз ЛаФранс, которые включили игру в занятия Эйдена в домашней школе. «В итоге он научил нас большей части того, что мы знаем о Minecraft», — говорит его мама.

Для многих учителей это тоже не так просто, по словам Дейдры Кварнстром, главы отдела обучения Minecraft в Microsoft. «Это то, о чем каждый ребенок в классе знает больше, чем они сами». Куарнстрем возглавляет команду из пяти человек, которая консультирует преподавателей и деловых партнеров по использованию Minecraft в планах уроков и проектах.

«Мы очень рано поняли, что Minecraft используется способами, о которых мы и не думали, когда учителя начали приносить ее в класс», — говорит Ву Буй, главный операционный директор Mojang. «Со временем мы поняли, что это гораздо важнее, чем мы думали. Это то, что мы должны поддерживать».

Повышение квалификации

Minecraft может захватить молодые умы в впечатляюще раннем возрасте. Возьмите Натаниэля МакВитти, 7-летнего мальчика из Грин-Бей, штат Висконсин, чье понимание командных блоков помогает ему выучить язык программирования Python.

«Он смог понять, что строка кода на Python похожа на команду в Minecraft», — говорит его мама Лори МакВитти.

Minecraft позволяет Натаниэлю использовать этот навык программирования, чтобы развивать другую страсть: приключения научно-фантастического героя Доктора Кто. «Все его творения и приключения в последнее время сосредоточены на создании ТАРДИС и альтернативных измерениях», — говорит его мама.

Крису Райли, программисту из Ливермора, Калифорния, нравится, как блоки команд позволяют детям «учиться, делая, а не слушая». Райли планирует познакомить своих маленьких дочерей Мэйси и Аву с игрой, чтобы помочь им научиться пространственному восприятию, творчеству, планированию проектов, архитектуре, проектированию и программированию. (Вот это вы называете детской игрой.)

Самым сложным программированием в Minecraft является «моддинг», который изменяет базовый код самой игры. Созданный сотнями участников в течение трех лет, самым сложным модом на данный момент является, вероятно, WesterosCraft, масштабное воссоздание (сравнимое с 500 квадратных миль в реальном мире) вымышленного царства «Игры престолов».

«Моддинг позволяет вам манипулировать всем в игре — тем, как она выглядит, когда восходит и заходит солнце, едят ли вас зомби или дарят вам цветы», — говорит Линдси Хэндли, соавтор книги «Моддинг Minecraft для детей». и операционный директор ThoughtSTEM, внешкольной образовательной программы по информатике в Сан-Диего.

В Zaniac, общенациональной программе продленного дня, базирующейся в Солт-Лейк-Сити, дети модифицировали игровых персонажей, чтобы они выглядели как они в реальном мире. Они также разработали сырье, которое выращивают для изготовления буррито, — говорит Сидхарт Оберой, президент Zaniac и научный руководитель.

Командные блоки и модификации работают только в оригинальной версии Minecraft для ПК за 27 долларов — не в версиях для мобильных устройств, игровых консолей или Microsoft Windows 10. Но Mojang планирует добавить расширенные функции во все версии.

Именно это сочетание красного камня, командных блоков и моддинга делает открытую среду Minecraft такой мощной — позволяя игрокам формировать и изобретать практически все, что они могут придумать.

Но есть и обратная сторона: навязчивая игра.

Американская академия педиатрии в настоящее время рекомендует ограничить «экранное время» двумя часами в день; и Common Sense Media советует родителям не позволять Minecraft управлять детскими днями. Игра в Minecraft в течение 10 или 12 часов по выходным может повредить их способности взаимодействовать с людьми в реальном мире.

Что дальше?

Около 1350 детей приняли участие в программе Minecraft в Zaniac. Они измерили гравитационное ускорение, заставив своих персонажей спрыгнуть со здания, и воспроизвели свои схемы из красного камня в реальном мире. «При обучении на основе игр они на самом деле не осознают, что учатся», — говорит Оберой.

Тем не менее, некоторые считают, что Microsoft может сделать Minecraft еще более привлекательным. Роберт Гровер, со-генеральный директор компании PCS Edventures из Бойсе, штат Айдахо, хочет версию для виртуальной реальности. «Представьте себе студента, создающего виртуальную копию Великой пирамиды в Гизе, путешествующего по залам и знакомящегося с древним Египтом так, как не может описать ни один учебник», — говорит он.

Microsoft движется в этом направлении, показывая, как люди могут использовать свою гарнитуру дополненной реальности HoloLens для наложения блоков Minecraft на их реальное окружение.

Но Minecraft предлагает множество возможностей для исследования без модных очков дополненной реальности. Крюгер воссоздал картины для галереи Тейт в Лондоне, которые дети могут исследовать изнутри. Студенты Университета Халла создали MolCraft, в котором дети летают через гигантские версии молекул, таких как миоглобин, который доставляет кислород к мышцам.

Возможности обучения кажутся безграничными. Специальная версия игры, разработанная для классной комнаты, под названием MinecraftEdu, настолько популярна, что Microsoft купила ее в январе прошлого года.

«Каждый игрок в Minecraft изучает важные жизненные навыки, такие как удары по деревьям и хорошая защита Крипера», — шутит Оуэн Хилл, директор по творческим коммуникациям в Mojang. «Но при правильном использовании Minecraft может помочь людям во всем мире узнать гораздо больше».

Microsoft выпустит расширенную версию игры под названием Minecraft: Education Edition этим летом.

Несмотря на стремление Microsoft к образованию, Minecraft по-прежнему сосредоточен на развлечениях.

«Мы считаем Minecraft игрой, используемой в обучении, а не образовательной игрой», — говорит Куарнстром. «Студенты более вовлечены в уроки, когда они также весело проводят время».

Эта история опубликована в весеннем выпуске журнала CNET Magazine за 2016 год. Чтобы посмотреть другие журнальные истории, нажмите здесь.

Анализ движков, похожих на Minecraft — 0 FPS

…и, учитывая огромный успех Minecraft, я думаю, что они станут неотъемлемой частью игровых движков. Minecraft (и Infiniminer) живут в уникальном пространстве где-то между вокселями высокого разрешения и статическими сборными средами. Модификация мира Minecraft интуитивно понятна и элегантна; вы просто берете и размещаете блоки. Во многих отношениях это естественное 3D-обобщение старых игр, основанных на 2D-тайлах. Конечно, создание движка Minecraft гораздо сложнее, чем создание 2D-движка по ряду причин. Во-первых, это 3D, а во-вторых, обычно ожидается, что окружение должно быть гораздо более динамичным, с интерактивным освещением, физикой и так далее.

При создании воксельной игры важно заранее выбрать структуру данных для представления мира. Это решение больше, чем какое-либо другое, оказывает наибольшее влияние на общую производительность, гибкость и масштабность игры. В этом посте обсуждаются некоторые из возможных вариантов, которые можно сделать в этом направлении, и, надеюсь, будет дано лучшее объяснение того, какие технические соображения здесь задействованы. На самом деле, я утверждаю, что некоторые распространенные предположения о производительности движков типа Minecraft, вероятно, неверны. В частности, важность операций чтения/записи с произвольным доступом для модификаций часто переоценивается, а относительная стоимость итерации сильно недооценивается. В заключение этой статьи я представляю новую структуру данных, которая использует это наблюдение и в конечном итоге обеспечивает гораздо более быструю итерацию (для типичных карт в стиле Minecraft) за счет немного более медленного произвольного доступа.

Но прежде чем забегать вперед, давайте рассмотрим некоторые подходы, которые в настоящее время используются для решения этой проблемы. Мы начнем с самого простого варианта — «плоского массива». В модели плоского массива вы просто храните все данные своего уровня в одном гигантском массиве:

Как показали нам Minecraft и Infiniminer, эта стратегия может быть жизнеспособной — при условии, что вы ограничиваете количество типов вокселей и делаете мир достаточно маленьким. . Хранение блоков в большом массиве имеет много преимуществ, таких как чтение и запись с произвольным доступом за постоянное время, но оно далеко от совершенства. Наиболее очевидным недостатком является то, что объем потребляемой памяти растет вместе с кубом линейной размерности, и в конечном итоге они имеют фиксированный размер. Эти свойства делают их подходящими для небольших миров-песочниц (например, в творческом режиме старой школы Minecraft), но не позволяют использовать их в бесконечном мире (например, в режиме выживания Minecraft).

Самое наивное решение предполагаемых недостатков плоских массивов (и я говорю это, потому что это почти всегда первое, что кто-либо предлагает) — попытаться поместить все воксели в октодерево. Октодерево — это дерево, которое рекурсивно делит пространство на октанты одинакового размера:

На первый взгляд, это звучит как хорошая идея. Карты Minecraft в основном представляют собой пустое пространство (или, по крайней мере, кусочно-постоянные области), поэтому удаление всех этих пустых вокселей должно немного упростить ситуацию. К сожалению, для тех, кто пробовал октодеревья, результаты обычно не столь впечатляющие: во многих ситуациях они оказываются на порядки медленнее, чем плоские массивы. Одним из часто цитируемых объяснений является то, что время доступа к соседним запросам в октодеревьях слишком медленное, что приводит к ненужным промахам кэша, а (пере)распределение узлов приводит к фрагментации памяти.

Однако, чтобы понять, почему октодеревья работают медленнее в играх Minecraft, нет необходимости прибегать к таким экзотическим объяснениям. Основная причина худшей производительности чисто алгоритмическая: каждый раз, когда касается произвольного вокселя, будь то итерация или выполнение произвольного доступа, необходимо пройти на всю высоту октодерева. Поскольку октодеревья не обязательно сбалансированы, это может быть столько же, сколько log (максимальный размер игрового мира)! Предполагая, что система координат, скажем, 32-битная, это приводит к дополнительным накладным расходам в виде 32 дополнительных несогласованных обращений к памяти на каждую операцию, касающуюся карты (в отличие от плоского массива, где все просто постоянное время).

Более успешный метод — и даже менее сложный — заключается в использовании подкачки или «виртуальной памяти» для увеличения размера плоского массива. Для этого нужно разбить плоский трехмерный массив на набор страниц или «фрагментов», а затем использовать хеш-таблицу для разреженного хранения только подмножества страниц, которые в данный момент требуются игре:

Страницы/фрагменты обычно назначаются так же, как и любая система виртуальной памяти: путем резервирования старших битов координаты для идентификатора фрагмента. Дополнительным преимуществом использования системы виртуальной памяти является возможность ленивой инициализации фрагментов, что отлично подходит для игр с процедурным контентом. Та же концепция также позволяет отображать фрагменты обратно на диск, когда они не нужны (то есть, когда поблизости нет игроков). Использование хэш-карты для хранения фрагментов позволяет поддерживать произвольный доступ с постоянным временем, одновременно используя преимущества разреженности, как в октодереве.

Похоже, нынешнее направление движков Minecraft начало сходиться к подходу «виртуализации». (И я основываю это утверждение на многочисленных сообщениях в блогах). Но действительно ли это лучшее решение? В конце концов, прежде чем мы прыгнем и попытаемся решить проблему, мы должны хотя бы попытаться количественно понять, что происходит; в противном случае мы могли бы с таким же успехом заниматься литературной критикой, а не информатикой. Итак, я задаю следующий основной вопрос:

На этот вопрос есть поверхностный ответ: «время доступа для чтения/записи»; ведь каждую операцию на карте Minecraft можно свести к простым воксельным запросам. Если вы принимаете это утверждение, то виртуализация оптимальна — конец истории. Однако по причинам, которые я вскоре объясню, это утверждение ложно. На самом деле, я надеюсь убедить вас, что на самом деле верно следующее:

Утверждение:  Главным узким местом в воксельных движках является итерация, а не произвольный доступ для чтения и записи!

Основная предпосылка основывается на том факте, что подавляющее большинство обращений к базе данных вокселов происходит в форме итераций по трехмерным диапазонам вокселей. Чтобы продемонстрировать это, давайте сначала рассмотрим некоторые высокоуровневые задачи, связанные с картой мира, с которыми должен работать воксельный движок:

• Размещение и удаление блоков
• Обнаружение столкновения
• Пикинг/трассировка лучей
• Обновления освещения
• Обновления физики
• Генерация сетки
• Сериализация диска
• Сериализация сети

Последние два элемента здесь можно считать необязательными, но я оставлю их для полноты картины (поскольку большинство воксельных игр требуют определенного уровня настойчивости, а многие стремятся хотя бы однажды стать многопользовательскими играми).

Мы будем классифицировать каждую задачу с точки зрения операций, необходимых для ее реализации в игровом цикле, таких как чтение/запись и произвольный доступ/итерация. Чтобы измерить стоимость, мы подсчитываем количество необработанных операций с вокселами (чтение-запись), которые происходят в течение некоторого произвольного интервала игрового процесса. Идея здесь в том, что мы ждем некоторую фиксированную единицу времени (t) и подсчитываем, сколько раз мы попали в воксели (то есть количество байтов, которые нам пришлось прочитать/записать). Если предположить, что мир намного больше кэша (что неизменно верно), эти операции с памятью фактически являются ограничивающим фактором в любых вычислениях, связанных с игровым миром.

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

 д. Это дает асимптотическую оценку стоимости каждой задачи в понятных единицах:

Задача	Операция	Стоимость (в воксельных операциях)
Размещение блоков 93 * (количество факелов) + (размер активного мира) * (изменение положения солнца)
Обновление физики	Итерация (RW)	(размер активного мира) * (количество кадров)
Генерация сетки	Итерация (R)	(размер блока) * (обновление блока)
Сериализация диска	Итерация (R)	(размер активного мира) * (сохранение событий)
Сетевой ввод-вывод	Итерация (R)	(размер активного мира) * (количество игроков) + (размер фрагмента) * (обновления фрагмента)

* При условии, что пикировка реализована с помощью ray-marching.

Отказ от ответственности:  Записи на этой диаграмме являются приблизительными, и я не утверждаю, что измерения для каждой задачи точны на 100 %. Если вы не согласны с чем-либо здесь, пожалуйста, оставьте комментарий.

Наша цель — точно определить, какие операции на этой диаграмме являются узким местом, и для этого нам нужен анализ измерений, чтобы преобразовать все наши единицы измерения в общий набор измерений. Несколько произвольно мы выбираем количество кадров и количество игроков, поэтому наших юнитов будет 9.0109 (воксельные операции * кадры * игроки) . Просматривая список каждого элемента, мы теперь пытаемся оценить некоторые правдоподобные границы для каждого измерения:

1. (количество кликов)  – это количество раз, которое пользователь щелкнул мышью в интервале. Поскольку пользователь может щелкнуть не более одного раза за кадр (и на практике, скорее всего, щелкнет гораздо меньше), это значение ограничено выше:
   • (количество кликов) < (количество кадров) * (количество игроков)
2. (количество мобов) — количество активных сущностей или подвижных объектов в игре. Если предположить, что они движутся не слишком быстро (т. е. максимальная скорость равна постоянному количеству блоков на кадр), то количество операций чтения из-за проверки на коллизии будет пропорционально количеству MOB и количеству кадров. . Мы предполагаем, что количество МОБов в мире пропорционально количеству игроков согласно некоторой константе ,
   • (количество МОВ) = * (количество игроков)
3. (расстояние выбора)  это максимальный диапазон, на котором игрок может выбрать блок, и мы будем считать, что это всего лишь небольшая константа.
4. Опять же, (радиус факела) — это небольшое число. В Minecraft это теоретически может достигать 16, но пока мы просто оставим его как крошечную константу.
5. (количество факелов) — количество факелов, поставленных/удаленных за интервал. Размещение факела, как правило, является нерегулярным событием, поэтому мы оцениваем, что игрок будет размещать факел довольно редко, со скоростью, определяемой некоторой константой ,
   • (количество факелов) = (количество игроков) * (количество кадров) *
6. (изменение положения солнца) — количество раз, когда солнце меняется. Это происходит регулярно каждые несколько кадров, поэтому мы оцениваем, что
   • (изменение положения солнца) = (количество кадров) *
7. (размер активного мира) — размер мира. Это в основном пропорционально количеству чанков, видимых каждым игроком. Предполагая мир в стиле Minecraft с ограничением по высоте, это будет квадратично изменяться в зависимости от видимого радиуса или кубически для мира с неограниченным значением z.
   • (размер активного мира) = (количество игроков) * (размер фрагмента) *
8. (обновления чанка)  возникают при каждом изменении чанка. Предполагая, что это случайно, но пропорционально размеру активного мира, мы получаем
   • (обновления фрагмента) = (размер активного фрагмента) / (размер фрагмента) *
9. (сохранение событий)   происходят через равные промежутки времени и сохраняют карту на диск. Опять же, поскольку они регулярны, мы можем просто ограничить их константой, умноженной на количество кадров.
   • (сохранение событий) = (количество кадров) *

Подставив все это, мы получим следующее выражение для общего количества операций вокселей произвольного доступа:

(операции случайного вокселя) = C * (количество игроков) * (счетчик кадров)

И для последовательных или итерационных воксельных операций мы получаем:

(последовательные воксельные операции) = C * (количество игроков) * (количество кадров) *   (размер фрагмента) *

Как правило, последнее количество намного больше, в раз (размер блока) * или в раз (размер блока) *

, если у вас неограниченный рост. Итак, если вы считаете, что эти оценки разумны, то вы должны быть уверены, что итерация на сегодняшний день доминирует над производительностью игры в стиле Minecraft. На самом деле эта оценка объясняет несколько других вещей, например, почему видимый радиус является таким важным фактором производительности в Minecraft. Линейное увеличение радиуса прорисовки снижает производительность квадратично!

Главный вывод, который можно сделать из приведенной выше оценки, заключается в том, что мы действительно должны сосредоточить наши усилия по оптимизации на итерации. Если мы сможем значительно снизить эту стоимость, то можем ожидать значительных улучшений в производительности игры. Но тогда возникает вопрос: возможно ли это вообще? Чтобы показать, что, по крайней мере, в принципе это так, мы используем простое наблюдение: в любой ситуации, когда мы итерируем, нам нужно рассматривать только локальные окрестности вокруг каждой ячейки. Например, если вы вычисляете обновление физики (в minecraft), вы учитываете только ячейки в вашем районе Мура. Более того, эти обновления являются детерминированными: если у вас есть два вокселя с одинаковым окружением Мура, то результат применения физического обновления к каждой ячейке будет одинаковым. В результате, если мы можем перебирать ячейки в группах, имеющих одинаковое соседство, то мы можем применить одно и то же обновление ко всем ячейкам в этой группе одновременно!

Это основная идея нашей стратегии ускорения итераций. Сейчас мы постараемся объяснить этот принцип более подробно. Пусть будет набором типов блоков, и пусть будет картой, представляющей наш мир (т.е. присвоение типов блоков целочисленным координатам на регулярной сетке). Радиус — окрестность Мура является элементом множества . Окрестность Мура координаты определяется картой, такой что0003

Тогда тот факт, что мы можем группировать ячейки, соответствует наблюдению, что: сложность итерации на существенную величину.

На самом деле, эта же идея применима и к сетке:  Если у вас есть последовательность смежных кубов, имеющих одинаковую окрестность 3x3x3, вы можете соединить их грани вместе, чтобы создать меньшую сетку. Например, вместо создания сетки для каждого куба по одному:

Мы можем объединить ячейки с одним и тем же соседством Мура вместе:

Таким образом, если мы можем перебирать ячейки в пакетах, мы должны ожидать, что не только наш физический цикл станет быстрее, но мы также должны ожидать, что сетка качество тоже должно улучшиться!

На данный момент у нас теперь есть довольно хорошее интуитивное представление о том, что мы можем выполнять итерацию быстрее, поэтому очевидным следующим шагом является выяснение того, как именно это работает. Вот одна стратегия, которую я использовал в простой игре Minecraft на основе javascript (которую вы можете получить здесь). Идея вытекает из простого наблюдения, что миры в стиле Minecraft можно легко кодировать по длине. При кодировании длин серий сначала 3D-массив, описывающий фрагмент, сводится к одномерной строке. Затем подстроки повторяющихся символов или «серии» группируются вместе. Например, строка:

     aaaaabbbbacaa 

Стало бы:

      5a4b1a1c2a 

Это уменьшение размера примерно на 25%. Вы можете представить себе замену символов в строке типами вокселей, а затем их сжатие таким образом. Теперь применение кодирования длин серий к чанкам ни в коем случае не является новой идеей. На самом деле, это даже разумно сделать в качестве шага предварительной обработки перед g-zip-архивированием фрагментов и их отправкой по сети/буферизацией на диск. Тот факт, что кодирование длин серий действительно сжимает фрагменты, работает в наших интересах: мы можем использовать этот факт для итерации по набору вокселей в единицах прогонов, а не в пикселях, и его также можно легко расширить для обхода окрестностей Мура.

Звучит отлично для итераций, но как насчет чтения и записи с произвольным доступом? В конце концов, нам все еще нужно как-то обрабатывать обнаружение столкновений, размещение блоков и трассировку лучей. Если бы мы были тупыми, просто доступ к случайному блоку из фрагмента, закодированного по длине прогона, мог бы занять линейное время. Очевидно, что мы не должны быть довольны такой производительностью, и действительно есть простое решение. Ключевое наблюдение состоит в том, что кодирование строки по длинам серий формально эквивалентно представлению в виде дерева интервалов.

Интервальное дерево — это просто обычное бинарное дерево, где ключ каждого узла — это начало прогона, а значение — координата прогона. Нахождение наибольшей нижней границы координаты эквивалентно нахождению интервала, содержащего узел. Сделать вставку немного сложнее, но ненамного. Это включает в себя работу с несколькими особыми случаями вручную, но в этом нет ничего невозможного, не потратив немного времени и блокнота бумаги. Если мы реализуем эту структуру данных, используя какой-либо тип самобалансирующегося двоичного дерева (например, красно-черное дерево или расширенное дерево), то мы можем выполнять случайное чтение и запись за логарифмическое время на количество прогонов . Лучше всего то, что мы также бесплатно получаем улучшенную генерацию сетки и сжатие в памяти!

На практике вам может понадобиться совместить эту идею с виртуализацией. По сути, вы должны хранить каждый фрагмент в виде дерева интервалов, а затем представлять весь мир в виде хэш-карты. Причиной этого может быть более плавная интеграция подкачки и генерации фрагментов. Фактически, это метод, который я использовал в последних двух играх типа Minecraft, которые я написал, и вы можете найти пример кода, иллюстрирующий эту структуру данных, прямо здесь.

Хорошо, теперь, когда мы рассмотрели детали, давайте разберем наши варианты по структуре данных и временной сложности:

. 16 блоков 32 различных типов. Чтобы оценить производительность, мы измеряем, сколько времени в среднем занимает случайное чтение, и сколько времени требуется для последовательной итерации (для радиусов Мура, равных 0 и 1). Результаты теста следующие:

Структура данных	Время произвольного доступа	Время итерации	Размер	Примечания
Плоский массив
Виртуализированный массив				— количество занятых (виртуальных) чанков
Октри				— высота октодерева

Структура данных	Ср. случайное чтение	Ср. последовательное чтение (радиус Мура = 0)	Ср. последовательное чтение (радиус Мура = 1)
Плоский массив	0,224 мкс/чтение	0,178 мкс/чтение	0,060 мкс/чтение
Виртуальный массив	0,278 мкс/чтение	0,210 мкс/чтение	0,107 мкс/чтение
Октри	2,05 мкс/чтение	0,981 мкс/чтение	0,933 мкс/чтение
Интервальное дерево + хеширование	0,571 мкс/чтение	0,003 мкс/чтение	0,006 мкс/чтение

В каждом столбце жирным шрифтом выделен лучший результат.