1
\$\begingroup\$

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
enter image description here
Influence mask
Influence mask
Influence visualisation (city at the brightest spot)
Influence visualisation

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – congusbongus Apr 27 '15 at 0:37
  • \$\begingroup\$ @congusbongus: nothing would (unless (5,3) etc had similar absorption). \$\endgroup\$ – Babis Apr 27 '15 at 6:52
  • \$\begingroup\$ @Jon: not quite. Only city tiles emit influence, the rest just allow influence to propagate \$\endgroup\$ – Babis Apr 27 '15 at 6:53
  • \$\begingroup\$ Having never played Civilisation, this question is quite unclear to me. How does this "influence" thing work? \$\endgroup\$ – Anko Apr 27 '15 at 13:26
  • \$\begingroup\$ updated with some screens, hopefully clearer now \$\endgroup\$ – Babis Apr 27 '15 at 13:44
1
\$\begingroup\$

(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
\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – Jon Apr 27 '15 at 7:32
  • \$\begingroup\$ it would be in. \$\endgroup\$ – Babis Apr 27 '15 at 13:34
  • \$\begingroup\$ @Babis, I updated the list; it's pretty much the same as what you created? \$\endgroup\$ – Jon Apr 27 '15 at 19:35
  • \$\begingroup\$ @Babis, I'm also curious to know if you are going to, ultimately, shove all of this into a compute shader? \$\endgroup\$ – Jon Apr 27 '15 at 19:36
  • \$\begingroup\$ 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. \$\endgroup\$ – Babis Apr 27 '15 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.