Комментарии 8
Неплохо было бы сюда же зацепить тему воронова для регулярных сеток, со случайным смещением в узлах. Поскольку алгоритм воронова для нее получается тривиальным, а эффект интересным.
В реализации можно использовать стандартные контейнеры без придумывания структур. Просто список вершин (центры описанной окружности Vector2[], вершины треугольников Vector2[]) и индексы (список центров окружностей вокруг каждой вершины — полигоны Воронова или регионы int[][], список треугольников Долоне или ближайшие точки int[][]). Исходя из того что количество вершин треугольников равно количеству полигонов, при последовательной обработке, они уже будут между собой связанны без лишних ссылок. Это все хорошо представляется по аналогии с мешем. Единственное тут нет расстояния, но для сравнения расстояний можно быстро посчитать через скалярное произведение.
P.S. Имею на руках сборник статей о ДВ на английском и очень хочу его издать на русском, но оценить аудиторию читателей и, что важнее, покупателей, совсем не тривиальная задача. А без этого издательство не возьмётся. Отзовитесь те, для кого эта тема действительно очень интересна (до уровня покупки малотиражной->дорогой книги).
Выбирать место наибольшего скопления котиков по наименьшему треугольнику — неправильно. Представьте пустую поляну, где в одном краю 100 котиков на расстоянии, в среднем, 30 см между каждой парой, а в другом — в коробке 20*20 три котенка. Ваша мята достанется котятам.
Разумнее разделить поляну регулярной сеткой, например, гексагональной (тут триангуляция Делоне тоже пригодится), выбрав размер ребра сопоставимым с расстоянием, с которого котик чует мяту. Потом подсчитать количество котиков в каждой ячейке и уже из них выбирать максимум(ы). Это не гарантирует достижения теоретического максимума количества осчастливленных котиков, т.к. начальная точка для сетки выбирается произвольно, но даёт результат, достаточно хороший для большинства практических целей.
Реально это работает нормально только если расстояние между сторожевыми вышками будет примерно одинаковым.
Контрпример: если по пути прямого следования будет в 10 раз более плотное расположение вышек — Вороной также сегментирует эту площадь и A* проведет нас хоть и на одинаковом расстоянии между соседними вышками, но через наиболее плотное скопление, и в силу их плотности на этом маршруте мы пойдем в 10 раз ближе к вышкам, чем могли бы, пойдя немного в обход по разреженной области.
Вижу перевод.
А проще найти ближайшую аптечку нельзя?
В жизни всё веселей:
у разных пушек — разная мощность нанесения урона.
Местность — неоднородная
Мощность меняется с расстоянием до цели.
Тут даже о времени под огнём противника не упомянуто
Вобщем просто навели тень ДВ на плетень игр.
Как использовать диаграммы Вороного для управления ИИ