Performance for range of effect in city builder

Question

I am working on a city building game where all buildings are axis aligned rectangles. Currently I am using spatial hashing to detect if the insertion of a building intersects a building in the board.

Now I am implementing an effect system where every building placed has some effects that they can give to other buildings within a specific range. This happens during placement of a new building into the board.

Basically how it should work is, if I place a building within the range of another building in the board, the building in the board should receive the effects that the building I just placed has, and the building that I am placing should also receive the effects that the building in the board has. Basically like a handshake. This should happen with every building that is in the range of another building and will only take place and be calculated when a new building is inserted into the board.

Another thing to keep in mind is that if a building is already in the board and a new building is placed within its range, that new building should receive the effects of the building already in the board even if the other building does not have this building in its range. Thus this would be a one way transfer of effects and not a "handshake".

I currently have the exchange of effects working as it should, but its slow because I am checking every building range against every building. Thus the more buildings you place, the slower it gets.

I am looking for a way to make this faster whether it means changing from spatial hashing to some other spatial partitioning. I am currently reading Hierarchical Hash Grids but I don't know if this will benefit me at all.

Answer 1

Sounds like a use-case for influence maps.

1. For every kind of building effect you have, you create a two-dimensional array of integers with the size of your map. These are "influence maps" which represent the strength of each effect per map tile.
2. When you place a building emitting that effect, add 1 to every tile on the corresponding influence map which is within the area of effect range of the building. (If you don't want a building to benefit from its own effect, skip the tile(s) occupied by the building itself).
3. When you remove a building emitting an effect, subtract 1 from every tile within range.
4. When you want to check if a building is affected by a certain effect, check the corresponding influence map at its coordinate(s). It represents the number of overlapping buildings affecting it.

When the effect is a simple on/off thing, you can simply give the bonus when the value in that influence map is > 0. You might wonder why not use a bool array then. Well, when the player places 3 buildings nearby and then removes 2, you still want to know that there is 1 building left covering the tile. So you need to keep accurate count of how many buildings cover each tile, even if you don't care if it's more than one. But you can also use this for more complex mechanics. Like measuring cumulative effects of multiple buildings in range and model effects which become weaker with distance.

Performance-wise, this is pretty cheap. Sampling the influence map is a constant-time operation. And you only need to change it when a building is added or removed, in which case the performance cost depends on the area covered by the building that was added / removed.

For some more inspiration on what you can do with influence maps, check out this GDC talk: Spatial Knowledge Representation through Modular Scalable Influence Maps

Answer 2

Currently I am using spatial hashing to detect if the insertion of a building intersects a building in the board.

[...]

[I have the] effects working as it should, but its slow because I am checking every building range against every building. Thus the more buildings you place, the slower it gets.

The spatial hash organizes objects by how close they are to each other. You're already using it for collision-detection, so also use it to get a list of buildings within a maximum area of effect of the building you have just placed (or are about to place or whatever).