Рубрика «поиск пути в графе»

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

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

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

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

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

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

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

в 14:56, , рубрики: Алгоритмы, математика, матрица лапласиана, площадь четырехугольника, поиск пути в графе, потенциалы, ранжирование

А не замахнуться ли нам на Эдсгера нашего Дейкстру?

Путь лапласиана. Часть 2 - 1

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

В общем случае минимизируемая величина — это необязательно расстояние, — весами ребер графа могут быть стоимости, штрафы, убытки, времена, — любые величины, которые можно складывать. Задача является классической, наиболее простой алгоритм поиска кратчайшего пути дал Э. Дейкстра аж в 1959 году.
Читать полностью »

в 14:04, , рубрики: Алгоритмы, марковские сети, математика, матрица лапласиана, поиск пути в графе, потенциалы, ранжирование

… Молвит он: «Коль жив я буду, чудный остров навещу, у Гвидона погощу».

В поисках пути — царь Салтан осваивает лапласиан - 1

В царстве Салтана не без изьяна. Принят закон — не лезть за кордон, да тут князь Гвидон.
Опять прислал поклон, да приглашение на угощение,- надо принимать политическое решение.

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

Было однако одна проблема,- нужен был маршрут или схема. Поскольку никто (кроме Врангеля барона) не знал, как добраться до острова Гвидона. Корабельщики дали карту,- пришлось сесть за парту. Над картой склонился Салтан, — где тут остров Буян? Задача была как будто знакома — проложить путь к острову Гвидона. Но как найти дорогу, когда путей слишком много?

До ночи решал Салтан задачку, в итоге свалился в спячку. Снились ему матрицы и точки, да на болоте кочки. На кочку прыгнул Нео с острова Борнео.
— Если хочешь добраться ко сроку — плыви по максимальному потоку.
— Чего? — Салтан почти проснулся. Но Нео уже в зайца обернулся.
Читать полностью »

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