CODEWITHSUNDEEP
algorithmlua
MetaZenithian
MetaZenithian

Reputation: 65

Check if hex is in range of hexagonal tiling with weighted hexes

Problem

Let's say I have an (infinite) hexagonal tiling. Starting from 1 hexagon, I can move to every adjacent ones except for some "hollow" hexagons. Some hexagons have a weight of 1, others have one of 2. With a maximum weight of x, how to get all hexagons that have a cumulative weight from the starting hex below x ?

Context

I'm trying to make a mod for the game Civilization V. In it, I need to get the set of all the tiles a unit can go to within 10 turns, knowing this unit has 1 movement point per turn, and that every tiles except roads cost 1 MP to go to (roads cost 0.5). Mountain and maritime tiles are unaccessible. In a nutshell, it is an extended version of the area displayed around selected units, showing all the tiles within a 1-turn distance of a unit.

Current tests

As of now, I have tried 2 solutions, but none of them seems to be very efficient. Most of my tries fails at knowing which tiles to check (either beacause they have not been already checked, or because they have not been checked for the shirtest path) and which one not to, and ends up checking every tile within range multiple times and rejecting several tiles that are seemingly within range but have been checked from a longer path than necessary thus thiking they are too far.

I would really need some advices in how to do this.

Thank you, Méta

Upvotes: 0

Views: 199

Answers (2)

Egor Skriptunoff
Egor Skriptunoff

Reputation: 23767

You don't need Dijkstra here.
Simple "wave" algorithm is enough.

You need an array dist for storing a number (distance) for each hexagon on the field.
You also need another array wave for storing list of hexagons recently refreshed.

Pseudocode: 

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

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59303

You should use Dijkstra's algorithm to find the shortest paths to nearby tiles. Since Dijkstra's algorithm finds the shortest paths in order of increasing length, you can just stop when you find a shortest path longer than x.

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

Upvotes: 1

Related Questions