Проверьте, находится ли гекс в диапазоне гексагональной плитки с взвешенными гексами

Question

Задача

Допустим, у меня есть (бесконечный) шестиугольный лист.Начиная с 1 шестиугольника, я могу перемещаться во все соседние, за исключением некоторых «полых» шестиугольников.Некоторые шестиугольники имеют вес 1, другие имеют один из 2. С максимальным весом x, как получить все шестиугольники с совокупным весом из начального гекса ниже x?

Context

Я пытаюсь сделать мод для игры Civilization V. В ней мне нужно получить набор всех плиток, на которые юнит может перейти за 10 ходов, зная этот юнит.имеет 1 очко движения за ход, и что каждая плитка, кроме дорог, стоит 1 MP, чтобы пройти (дороги стоят 0,5).Горные и морские плитки недоступны.В двух словах, это расширенная версия области, отображаемой вокруг выбранных юнитов, показывающая все тайлы на расстоянии 1-витка от юнита.

Текущие тесты

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

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

Мне бы очень нужны были советы, как это сделать.

Спасибо, Méta

Answer 1

Здесь вам не нужен Дейкстра.
Достаточно простого алгоритма "волны".

Вам необходим массив dist для хранения числа (расстояния) для каждого шестиугольника на поле.
Вам также нужен еще один массив wave для хранения списка недавно обновленных шестиугольников.

Псевдокод:

variable x = 10 -- distance in MP
loop for each hexagon on the field
    dist[hexagon] = +infinity
end-loop
dist[unit_hexagon] = 0
wave = empty array
append unit_hexagon to array wave
loop while array wave is not empty
    create new empty array new_wave
    loop for each hexagon in array wave
        loop for each of 6 adjacent hexagons of hexagon
            if adjacent_hexagon is accessible (not a mountain)
                variable adj_dist = dist[hexagon] + price(adjacent_hexagon)
                -- where price = 0.5 for roads, 1 for other cells
                if (adj_dist < dist[adjacent_hexagon]) and (adj_dist < x) then
                    dist[adjacent_hexagon] = adj_dist
                    append adjacent_hexagon to array new_wave
                end-if
            end-if
        end-loop
    end-loop
    wave = empty array
    copy everything from array new_wave to array wave
end-loop
loop for each hexagon in the field
    if dist[hexagon] < +infinity then
        the hexagon is inside colored area around the unit
    end-if
end-loop

Answer 2

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

См. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm