As the title says, imagine you want to generate the influence mask for a city, given that the map is a 2D grid rather than hex. An extra bit is that different points on the map might have different "influence absorpion" values. Some simple scenarios to make it less abstract:
Scenario 1:
City centered at (5,2) has 10 influence
All tiles have influence_absorption = 1
Tile at (6,2) has 9 influence, therefore within the influence of the city
Tile at (7,2) has 8 influence, therefore within the influence of the city
Tile at (14,2) has 1 influence, therefore within the influence of the city
Tile at (15,2) has 0 influence, therefore out of the influence of the city
Scenario 2:
City centered at (5,2) has 10 influence
All tiles have influence_absorption = 1, but tile at (6,2) has influence_absorption=4
Tile at (6,2) has 9 influence, therefore within the influence of the city
Tile at (7,2) has 5 influence, therefore within the influence of the city
Tile at (11,2) has 1 influence, therefore within the influence of the city
Tile at (12,2) has 0 influence, therefore out of the influence of the city
It's like using dijkstra on a 2D grid with single-source, multiple-destinations. Any pointers for good/fast algorithms are appreciated. Also, if this problem has a well-known name, that'd be appreciated as well.
I made the following algorithm (independently like Jon's, thanks btw, it's the intuitive solution I guess):
p0 = CITY_COORDS
Initialize all influences with 0
set CITY_INFLUENCE as the new influence at p0
list = [ p0 ]
while list not empty
p = get point in list with highest influence rating
pi = get influence at point
pa = get absorption at point
new_i = pi -pa
list_is_updated = false
for each valid neighbour nb
nbi = get neighbour's influence
if new_i > nbi
set new_i as the new influence at nb
add nb to list
list_is_updated = true
if list_is_updated
sort list // with selection sort, very fast
And I have the following results, which can also be helpful to understand what I'm after:
Influence absorption
Influence mask
Influence visualisation (city at the brightest spot)