# 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
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 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? – congusbongus Apr 27 '15 at 0:37
• @congusbongus: nothing would (unless (5,3) etc had similar absorption). – Babis Apr 27 '15 at 6:52
• @Jon: not quite. Only city tiles emit influence, the rest just allow influence to propagate – Babis Apr 27 '15 at 6:53
• Having never played Civilisation, this question is quite unclear to me. How does this "influence" thing work? – Anko Apr 27 '15 at 13:26
• updated with some screens, hopefully clearer now – Babis Apr 27 '15 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.
7. Any neighbor that receives influence is added to the list.
8. Goto 3
• @Babis, if a tile receives influence but fully absorbs it and has none left to transmit, should it be considered in or out? Your wording makes me think #4 may belong after #5 and need the "remainder" conditional. – Jon Apr 27 '15 at 7:32
• it would be in. – Babis Apr 27 '15 at 13:34
• @Babis, I updated the list; it's pretty much the same as what you created? – Jon Apr 27 '15 at 19:35
• @Babis, I'm also curious to know if you are going to, ultimately, shove all of this into a compute shader? – Jon Apr 27 '15 at 19:36
• Similar but not the same. E.g. I didn't divide the influence by the neighbours, but I might try to do that to see how that differs! Probably not gonna shove it to a compute shader, as it's not that massively parallel anyway so I don't think it's worth the maintenance. – Babis Apr 27 '15 at 21:36