Рубрика «Диаграммы Вороного»

в 10:35, , рубрики: гёмбёц, геология, геометрия, Диаграммы Вороного, математика, Научно-популярное, физика

Упражнения в чистой математике привели к созданию масштабной теории об устройстве мира

Учёные раскрыли универсальную геометрию геологии, и оказалось, что мир состоит из кубов - 1

Где-то в середине лета 2016 года венгерский математик Габор Домокош взошёл на крыльцо дома Дугласа Джерольмака, геофизика из Филадельфии. С собой у Домокоша были дорожные чемоданы, сильная простуда и жгучая тайна.

Чуть позже двое мужчин гуляли по гравийной дорожке на площадке за домом, где жена Джерольмака держала тележку для продажи тако. Под их ногами хрустел измельчённый известняк. Домокош указал под ноги.

«Сколько граней у каждого из этих камушков?» – спросил он. Затем он ухмыльнулся. «Что, если я скажу вам, что их количество обычно равно шести?» А затем он задал ещё более общий вопрос, который, как он надеялся, надолго поселится в мозге его коллеги. Что, если мир состоит из кубов?
Читать полностью »

в 11:17, , рубрики: алгоритм Форчуна, Алгоритмы, Диаграммы Вороного, Дизайн игр, искусственный интеллект, искусственный интеллект в играх, поиск пути в графе, разработка игр, триангуляция Делоне
image

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

Пространственные отношения

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

Такие отношения постоянно используются в видеоиграх и могут предоставлять очень полезную информацию ИИ, а также самому игроку.

У Вороного есть ответ

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

в 13:33, , рубрики: Алгоритмы, генерация карт, Диаграммы Вороного, Дизайн игр, процедурная генерация, разработка игр, релаксация, тайловые карты
Генерируем тайловые уровни и прячем квадраты от игрока - 1

Генерация уровней в Unexplored 2

Мы очень гордимся генератором уровней игры Unexplored 2, это программа, отвечающая всем современным требованиям. В посте я расскажу о том, как создаются уровни игры.

Нам не пришлось заново изобретать велосипед. В Unexplored 1 мы уже создали техники, которые сильно повлияли на успех первой игры. Unexplored 2 просто продолжила начатое. Фундамент нашей технологии состоит из двух частей: мы применяем многоэтапную генерацию, которая почти имитирует процесс, очень похожий на работу живого дизайнера уровней. Поверх него мы используем технику под названием "циклическая генерация подземелий", которая гораздо лучше справляется с генерацией естественно выглядящих уровней, чем большинство стандартных приложений генеративного создания контента. В этом посте я расскажу о первом аспекте. Адаптация циклической генерации подземелий к Unexplored 2 будет темой будущего поста.

Имитация «человеческого» дизайна уровней

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

в 5:37, , рубрики: c++, Алгоритмы, Диаграммы Вороного, Программирование, разделяй и властвуй, метки:
image

Недавно, на хабрахабре была опубликована статья, целиком и полностью посвященная диаграммам Вороного. В статье автор подробно описывает алгоритм Форчуна, применяемый для построения Диаграммы Вороного за O(n*log(n)). Стоит отметить, что описание этого алгоритма ни раз появлялось в рунете, в то время как о других алгоритмах (с той же асимптотикой) рассказано ровным счетом ничего. Данная статья исправляет это недоразумение, а также является отличным дополнением к уже опубликованному ранее материалу.

Ниже я расскажу о алгоритме 'разделяй и властвуй' построения диаграммы Вороного за O(n*log(n)), а также, основываясь на своем практическом опыте, о по-настоящему крутых штуках, в которых это применимо. Вообще, алгоритмы типа 'разделяй и властвуй' являются своего рода классикой программирования (думаю, про сортировку данным методом слышал каждый программист), хорошо параллелятся и легко читаются (если, конечно, знать основную идею алгоритма).
Читать полностью »

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js