# What functional abstraction to use for multi-agent simulation?

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.

• How long did/does it take for the GC to collect/free all that memory of the previous state? – user77245 Jan 7 '18 at 7:07
• If I recall correctly it was around one full second every major step. Anyway in the end I solved the problem moving the whole structure to Akka and removed any freeze. The overhead is tough though. – Chobeat Jan 8 '18 at 8:27

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.

• Thanks for the explanation. Being my first game I never heard of this pattern. The point is that I wanted to avoid (or hide) mutable state as much as possible and stay on the functional side. Do you have any example of object pooling done in a functional way? Does it even make sense? – Chobeat Mar 5 '17 at 19:15
• @Chobeat Understood. I don't have examples of object pooling for FP but the principles should be much the same: Allocate and reuse vs Allocate and free ad nauseam. Of course, as you say, it requires mutable state to achieve usable object pools. Re avoiding that, I can only suggest you look at this and that, and other posts on FP in games. – Engineer Mar 5 '17 at 19:31
• Perhaps someone else can provide a better answer. Or perhaps seek an FP platform where GC is less of a problem than in Scala. Or perhaps don't do FP right now, and learn in a more games-compatible paradigm? – Engineer Mar 5 '17 at 19:36
• For sure that would be the easiest and most performant solution, no doubt. But this is a for fun project with no time constraint, so taking the hard path is not a problem. I know my solution is far from ergonomic to game development but it's mainly to practice, improve and experiment. – Chobeat Mar 5 '17 at 19:45
• Under those circumstances, your current solution - a "staged" state - seems better than anything else you're likely to come across. That's just my relatively humble opinion, and the way I'd likely tackle it as well. You need to remain true to FP's dictated paradigms, and that's the best way to do exactly that without shifting platforms or coming up with complicated or hybrid methods of achieving immutable state. Short of the platform undergoing major changes (unlikely given Scala), it seems your best bet. – Engineer Mar 5 '17 at 19:51