How should we be storing procedurally generated behavioural code?

Question

Me and a group of friends are developing a game and we've run into a road block. Before we describe that road block, here's a simplified explanation of our game:

The game will be able to take in a song in .wav format, and from that song procedurally generate a "level" whose elements and features vary depending on the properties of the song.

Seems simple enough on the surface (aside from the massively understated complexity of the procedural generation algorithms), but there's a problem. We want to be able to store the procedurally generated content in some portable format, but we also want to be able to execute it very quickly.

Here's the deal. The procedurally generated objects all have procedurally generated behaviours. They each have an update "method" that encapsulates this behaviour. The behaviour may be something like "if position is some position, do something" or "do this 10 times in a for loop", or something else (most likely only very simple code).

So I was thinking of using the bytecode pattern, and writing a very basic language in which we could encode the behaviour of each object. There's a problem with this though; there's a good chance it won't be fast enough.

On screen at once there will be thousands of these objects with procedurally generated behaviours. If the behaviours were coded in the native language (C# by the way), it would most likely be fast enough, but since we would be parsing and executing our own language bytecode in C# there would be a lot of added overhead that we think is enough to make our game unplayable.

Of course, we haven't tried implementing our own language to see if it actually would be fast enough, but we're kind of on a tight time constraint and don't want to take the risk of wasting time implementing something that won't work.

What should we do?

Answer 1

Get the simplest possible example that approaches your expected complexity, running. Code up say 5-6 considerably different behaviours, make entity count variable, and then test at different counts, optimise, and scale up from there. You cannot do game development without prototyping, it is the nature of this profession. You can reduce the complexity of your prototypes sometimes through forethought (which due to hidden complexities can only take you so far), but most typically during coding -- the front line is where you have your tactical epiphanies. ;)

One of the most exciting, definitive features of game dev against a background of traditional business programming, is the degree of flexibility we have in adapting engineering requirements to user experience; i.e. in cases of game logic it is not so often a black-and-white matter of "is this possible?" so much as "how do we reduce this enough to make it run acceptably in real time?".

Thousands is not unusual. If this were to become a problem, you could reduce the bounds within which these things operate, what I refer to as the "area of interest" around the player(s). You could also tie into a native code section e.g. by hooking up with a DLL written in C, once you are certain that your C# code has reached it's performance limits.

Consider factoring out your specialised behaviours as much as possible to make optimal use of the instruction cache... I'm sure this will be an ongoing process. Long functions that repeat code used in other behaviours means the instruction cache won't be optimally used. It can sometimes be to one's advantage to repeat code, but you probably needn't worry about this.

C# can actually get compiled to some pretty damned efficient code if you're careful with it, using things like tightly packed, cache-coherent struct-of-arrays etc., i.e. minimising the variety of data you are operating on at any one time, so data fits cache line widths. P.S. Unity or .Net / Mono?

FWIW, remember that your performance critical sections only make up a tiny proportion of your code; having said that, AI is almost certainly one of these in your case.

I am by no means convinced that you have no shot at making this work. Once you start optimising, you will often be astounded by the leaps and gains you make in increasing speed, and much of this early optimisation is data-driven, ensuring good cache performance. Optimisation on naive code is trivial; it's a rising curve, only getting much harder once you have already heavily optimised a given code section. That's the point at which an algorithmic paradigm shift is needed if still not fast enough.

At the end of the day though, you have to begin the project to begin to know if it's possible.