What functional abstraction to use for multi-agent simulation?

Question

this is quite a broad question, touching a few different fields, so let me know if there's a way to narrow it down.

What I would like to know is your opinions on what abstraction to use for my use case.

My game is a grid-based trading game (it's more complicated than that, but for now think of a Patrician on a grid) and I want to do some heavy simulation in the settlements. Heavy here means that the decisional processes and actions of every individual is simulated. I already managed to do a stress test and I know I can handle about 1 milion individuals without any slow down for the game.

The game is written in Scala in a functional style. The problem is that I achieved those performances using a naive copy of immutable states. So for every entity and settlement I compute the next state, I aggregate it in a global state and in the next iteration, I replace the old state with the new one. The issue is with the garbage collector: if the state grows too much after a while it tries a full garbage collection to free up memory and considering that with this approach I may have two whole sized states (the old one and the just computed new state), this gargabe collection may happen at every step.

What I did to solve this was to break the global state in N parts, computing and replacing parts of the state in N iterations. This works because every settlement is assumed to be in isolation and so it won't conflict with the others. This is a strong assumption though and in such an early state of development I don't want to be bound to it.

So what I need is a way to structure this simulation, settlement by settlement but that allows the agents on the map to interact with the settlements. The abstraction must be functional and match the requirements for the memory issue.

An obvious answer may be to use actors but I fear that using frameworks like Akka, the overhead may be too great for a game.

Answer 1

Let's look just at the primary performance problem you mention, and ignore further wild assumptions.

GC issues can be eradicated by using an object pool and pre-allocating all possible objects you may need to use, at startup time (as the Marmalade framework does, for example). This way you reuse the same objects repeatedly, instead of freeing old and allocing new memory under the hood. That alone will give you the biggest performance boost you are likely to see for your application.

As an example of pre-allocation: Let's say I run an existing version of my app, warts and all, and determine I will never need more than a thousand towns maximum, and one million people maximum, across the entire world. I can now allocate the initial arrays of people and towns to these figures, and only use those portions of each array that I need at a given time. Any time one of them becomes defunct in the game, I clear its state, and pass its index (or instance at that index) into the object pool, thereby freeing it up for later reuse once a new person / town spawns.

As an alternative to pre-allocating all object instances at startup time, you could also start small but double the size of your array / collection every time you hit its size limit. This is a viable strategy for most applications, frameworks and platforms, as you will then rapidly get to a point where no further allocations are required and the application will run smoothly thereafter.

Also, GC is timed to happen at regular intervals; it will not happen every frame as you suspect. However, I imagine you could run out of available memory in the meantime while blocks that are to be flushed on the next sweep, remain in limbo. That all really depends on just how large your states are.

Why do we not always pre-allocate, then? Flexibility. Operating systems and desktop applications tend to handle multiple tasks and so allocate and free memory in small chunks, given that they don't know what demands the user is going to put on the system next. But for games where all your attention is focused on the game itself, until you shut it down, preallocation can work very well.

P.S. Once you've solved this problem, you can go back and look at other issues like data proximity for cache purposes and so on. But that will be a separate phase and perhaps even unnecessary.