"So I need to use algorithms that can account for these changes when calculating their geographical properties. The last thing I want to do is recalculate the values for those properties from scratch every single time an action occurs, as this would slow down the game noticeably." - Am I right in understanding that you are not going to introduce any other ways to optimize these processes yet? I am a person far from the code and it is difficult for me to judge, but it seems to me - correct if I am wrong - it would be possible to carry out the work of this code at the time of the player's call by making a cooldown of diplomatic actions, and the AI could directly interact with the factions in the tribe, so that do not overload the simulation. I could misunderstand the meaning of the sentence, since I translate everything through Google's auto-translator. Sorry for the inconvenience.
Hello Werdin!
So, the values that I need to calculate can be calculated on demand when the player performs the action. The game is currently designed to stop simulating until all decisions are resolved. So I could use a naïve algorithm to calculate those values. What the player would experience is one second pause (approximately) while the game calculates the values before presenting the player with a choice. This doesn't seem like big deal, but this precludes me from ever using that same algorithm in situations that do not involve pausing the game.
What I want (and I already have a solution in mind. I just haven't written the code yet) is an algorithm that updates those values on-the-fly while minimizing the recalculations. This way, the values will be already calculated before the player performs the action and there will be no delays in presenting the player with a choice. If this works, then I will be able to use that same algorithm in situations that do not require the simulation to pause.
Like I said, I already have a solution in mind. It's not perfect and will require a bit of work. But it's a decent solution that solves the bigger problem: What I need is something that gives me the bounds of a polity (in map squares) without going through every cell. That is, without doing 'n' checks (where n is the number of cells in the polity). If my solution works, I will be able to do it by performing roughly sq(n) checks (where 'sq' is the square root). Also, this is an operation that I will only need to do very occasionally. 90% of the time, I will only need to perform one check when I need to update the bounds of the polity.