# Best way to calculate city influence maps similar to civilisation?

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
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 visualisation (city at the brightest spot)

• In scenario 2, what's to stop the influence solver from going around (6,2), i.e. (5,2)->(5,3)->(6,3)->(7,3)->(7,2), and thus solve (7,2) as 6 influence instead? Commented Apr 27, 2015 at 0:37
• @congusbongus: nothing would (unless (5,3) etc had similar absorption). Commented Apr 27, 2015 at 6:52
• @Jon: not quite. Only city tiles emit influence, the rest just allow influence to propagate Commented Apr 27, 2015 at 6:53
• Having never played Civilisation, this question is quite unclear to me. How does this "influence" thing work?
– Anko
Commented Apr 27, 2015 at 13:26
• updated with some screens, hopefully clearer now Commented Apr 27, 2015 at 13:44

(A place to start that's easier than comments:)

1. Maintain a list of tiles that need calculating; the initial list contains only the city-tiles.
2. Each city-tile generates influence, X, and adds it to each of its' 8 nearest neighbors, also adding each neighbor to the list. (Does the city pass only 1/8 of its influence to each?) The city-tile then removes itself from the list.
3. While the list is not empty...
4. Tiles don't send or receive 0 influence; the tile received influence, so it must be "in".
5. The tile removes itself from the list and subtracts its' influence factor from the received amount.
6. If there is any remainder, the tile adds it to its' 3 nearest neighbor(s). (Does the tile share only 1/3 of its' influence with each?) The direction that tile's should emit is easily determined with the vector between the tile and the city.