CRTs and Numerical Integration

[herwin]

My basic point is that the 60 mile hex creates a poor model. We have to live with it, but if we're changing the scale, we might as well tune the game engine.

The issue is that a numerical integration algorithm (which is what a game engine is in the end) has to satisfy three things if it is to generate accurate outcomes: convergence, consistency, and stability. Convergence says that the solution generated by the algorithm has to approach an exact solution as the integration time step goes to zero. Consistency says that the local error of the method (that is, the difference between the exact solution and the results of the numerical integration at each time point) also has to go to zero as the step size decreases. Finally, stability says the algorithm has to be numerically stable--e.g., the system cannot be stiff, with multiple time scales. If it doesn't satisfy those conditions, it will generate flaky answers.

Euler's forward integration method (which is used by most game engines) is known to be flaky. If you use backwards integration, you'll get much better stability, but at the cost of not modelling threshold phenomena (aka breakpoints) well. You really need to use a compromise, like Crank-Nicholson. Using 1-day turns with 60 mile hexes means that you're working with rather stiff systems, and you're likely to get severe inaccuracy in your ground combat system.

We run into the same problems modelling neurones. Engineers tend to use very large compartments in their modelling, but people concerned with how the real brain works reduce the compartment size to the point where edge effects aren't dominating the results. For accuracy, we find that while you can get away with single compartments in in a few cells, for others, you have to use as many as 5000 compartments. We also find that using multiple integration time scales can help.

With 60 mile hexes, you need to model what's going on inside the hex in some detail to overcome those problems. The game produces really whacko results sometimes that totally blow the mind of anyone who actually knows something about what's being modelled.

Now, I'm open to questions.

[witpqs]

Thanks! [:)]

It was the meaning of 'local error' that I was first curious about. Now, could you describe a bit more the meaning of 'stiff'? Does that mean that results will tend to jump around (as with something mechanical being inflexible and difficult to make small movements with it)?

[herwin]

ORIGINAL: witpqs

Thanks! [:)]

It was the meaning of 'local error' that I was first curious about. Now, could you describe a bit more the meaning of 'stiff'? Does that mean that results will tend to jump around (as with something mechanical being inflexible and difficult to make small movements with it)?

See the section on Analysis of this webpage. I'll dig out my notes at school later.

[herwin]

ORIGINAL: witpqs

Thanks! [:)]

It was the meaning of 'local error' that I was first curious about. Now, could you describe a bit more the meaning of 'stiff'? Does that mean that results will tend to jump around (as with something mechanical being inflexible and difficult to make small movements with it)?

The best accessible discussion of the issues I've found is Mascagni and Sherman, 1998, "Numerical Methods for Neuronal Modeling," ch 14 in Koch and Segev, 1998, Methods in Neuronal Modeling, 2nd edition, MIT Press, and I'm following them here. Basically, when you model a land battle, you're concerned with the changes in a number of numerical variables describing the characteristics of a military force of some size. If you roll a die or use a random number generator, it's a stochastic model, but underlying it is a system of non-linear differential equations. One fundamental reason for error in doing that is the finite nature of numerical representations on computers. Numbers are truncated and quantised, resulting in errors in the modeling.

The three concepts numerical analysts use to address these issues are convergence, consistency, and stability. Convergence is first--the error between the game engine's solution and what would occur in reality is as small as we please. Small is defined here in terms of a numerical time step and a spacial mesh. Convergence is equivalent to showing that the game produces an average result that differs from what would happen in reality by a term that goes to zero as the time step and the mesh go to zero.

Consistency implies that the game engine models the real-world process leading to the outcome accurately. It doesn't just produce realistic results by magic. That is, the equations in the game engine applied to what happened in reality produce a approximation error you can make as small as you wish. Note that a method can be consistent and yet not convergent. Consistency implies that the exact solution satisfies the finite difference equations with a truncation error that goes to zero. Convergence, on the other hand, requires that the predictions of the game engine differ from reality by a small error at every point in time and space.

The third concept is stability. A game engine is stable if the solution to the finite-difference equations remains bounded as the time step and mesh go to zero. Some consistent methods are not stable and so do not converge, while some stable solutions exhibit small oscillations.

There is a theorem (the Lax equivalence theorem, Richtmyer and Morton 1967) that says a finite difference method for linear ODEs/PDEs is convergent if and only if it is both consistent and stable. That basically says your game engine should treat the hex size and time step of the battle as variable input parameters rather than as God-given. If you halve the time step and take two steps, you should get a better result than if you use the original time step, even if it's a stochastic model. Same for hex size and unit size, although you have to include the non-linear interactions--tanks don't just fight tanks; guns, guns; and infantry, infantry. I usually just try to get the detailed combined arms interactions right. I have some notebooks from my days doing studies of ground combat operations for NATO that examine those issues.

A system of ODEs is stiff if the solution contains a wide range of characteristic time scales. Neuronal models are typically stiff (with the stiffness increasing with the number of individual compartments), but so are combat models. The Euler method and similar explicit integration rules cannot handle stiff systems. On the other hand, implicit integration rules (the simplest being backward Euler) can't handle serious non-linearity. You have to compromise...

So a good game engine treats unit size, hex size and time step as variables. It treats combined arms interactions right and gives better results when the units are smaller, hexes are smaller, and time steps are shorter.

[witpqs]

When you talk about variable steps, in distance, in unit size, and in time, (at a high level) how could that be achieved?

I presume the fact that WITP has varying sized units is not what is meant. So, do you mean that the engine would have to 1) evaluate the prospective combat to take place within a hex, then 2) decide what scales (time, distance, unit size) to use for that particular combat resolution? If so, I guess one concern would be consistency from turn to turn. If in a given turn in a given hex combat was broken down into smaller scales (chunks of distance smaller than a hex, chunks of units smaller than the chunk 'all units present' for each side, perhaps chunks of time smaller than a day), that would in effect be like simulating (for example) which units would be where within the hex. The engine would then have to ensure some level of consistency from day to day, lest a division be represented as to the left of a 60-mile hex one day and to the right of it the next day. Breakdowns into chunks smaller than an individual unit would be automatically consistent from day to day, because effects of combat would be applied to the whole unit at the end of the turn.

I realize that for simulations more real-world detailed than WITP some of the statements I made above might not hold, but for a WITP-style simulation - is that the kind if thing you mean?

[herwin]

ORIGINAL: witpqs

When you talk about variable steps, in distance, in unit size, and in time, (at a high level) how could that be achieved?

I presume the fact that WITP has varying sized units is not what is meant. So, do you mean that the engine would have to 1) evaluate the prospective combat to take place within a hex, then 2) decide what scales (time, distance, unit size) to use for that particular combat resolution? If so, I guess one concern would be consistency from turn to turn. If in a given turn in a given hex combat was broken down into smaller scales (chunks of distance smaller than a hex, chunks of units smaller than the chunk 'all units present' for each side, perhaps chunks of time smaller than a day), that would in effect be like simulating (for example) which units would be where within the hex. The engine would then have to ensure some level of consistency from day to day, lest a division be represented as to the left of a 60-mile hex one day and to the right of it the next day. Breakdowns into chunks smaller than an individual unit would be automatically consistent from day to day, because effects of combat would be applied to the whole unit at the end of the turn.

I realize that for simulations more real-world detailed than WITP some of the statements I made above might not hold, but for a WITP-style simulation - is that the kind if thing you mean?

You should be able to adjust all three parameters, although you run into issues if they aren't compatible. The hex size is usually fixed for a given game, although the Gamer's OCS rules adjust it from game to game. For a division/brigade-scale game, the natural mesh is 5 mile hexes (with ZOCs) and 15 mile hexes (without), assuming only one side can occupy a hex. The natural time step is 1-4 days. WiTP has very short turns and very large hexes, so you'll need to model extended periods of in-hex combat.(Watch the paths!) That forces you to make assumptions about organisation for combat, deployment, and events happening within the hex. However, you have to do something of the sort to ensure consistency. Since everything can interact with everything within the hex, you also need to use an implicit algorithm, probably backward Euler, to ensure stability.

The difference between forward and backward Euler is where you get your derivatives (rates of change of position, losses, reinforcements, firepower, fortifications, etc.). In forward Euler, you use the derivatives based on the situation at the beginning of the turn; while for backward Euler, you use the derivatives at the end of the turn. You can also use derivatives from the middle of the turn, which is also stable. You can estimate the resulting error, and decide whether you need to split the turn into subturns to allow you to follow non-linearities. Look at Runge-Kutta integration with adaptive step-size for how to do it.

You probably don't want to split the hex into subhexes, although that's what you're really doing when you make assumptions about the in-hex situation. Breaking units into subunits may be necessary to cover the front. Of course, all this would be hidden in the game engine. The key point is that a turn in a hex is internally modelled as one or more realistic battles--that ensures consistency--and the rates of change are based on the middle or end of the individual battle--to get stability--and combining the two, you get convergence.

[witpqs]

Thanks, Harry. [:)]