Myriarch Implementation Notes

Since I don’t know if or when I’ll do a proper PDF write-up on Myriarch, I thought I’d list a couple noteworthy implementation details. Feel free to ask if there’s anything in particular you’d like to know about.

Movement

The core simulation uses the QuadTree class of my Tektosyne library to locate units and their neighbors. During each time slice of 0.1 seconds, we loop through all units to obtain orders and execute them. Orders are either the division default orders (e.g. march north) or individual unit AI decisions when enemies are near. “Near” means within combat range during one time slice, given movement speed and weapon range, plus whatever extra range we can afford in terms of processing speed. (That’s going to be a problem for missile weapons!) Relatively isolated units look farther afield for enemies than units within a formation. Unit AI engages in combat if morale is good, and otherwise runs away.

Order execution consists of turning & marching into the desired direction until we’re either close enough to perform an attack, or a collision is detected. We always resolve collisions between two units only, picking the nearest one in our path and ignoring all others. Any collision terminates the current unit’s movement for the time slice, and changes future direction & speed for both colliding units. The current unit typically loses a bit of leftover movement capacity, but time slices are short enough relative to unit speeds that this is acceptable. The other unit will do its own collision processing later in the same time slice – possibly again colliding with the first unit, but using the newly adjusted impulses.

Compared to a textbook billiard ball simulation, we fudge our collision algorithm in several ways. First, we assume a minimum speed of 1 m/s for both units, even when they are stationary. This accounts for soldiers actively trying to move while blocked. Second, we accumulate “push mass” whenever two units collide while moving in the same direction. This increases the total force with which the front rank will eventually push against a unit going in the opposite direction. And lastly, we add a 10 cm random displacement to unit coordinates after a collision. This proved necessary to avoid two units permanently blocking each other, and also results in a more realistic “crowd simulation.”

Threading

This unit loop runs on a single background thread. The QuadTree class is not thread-safe and may change globally due to rebalancing after insertion or deletion, so breaking up the loop into multiple threads would be rather difficult. There’s also the question of available CPU resources. On my system, Myriarch keeps three out of four physical cores quite busy, with the fourth on standby for UI input.

Once the unit loop is finished with a time slice, the new simulation state is written to a snapshot which is then passed to a second background thread. This is a WPF Dispatcher thread based on the technique described by Dwayne Need and implemented by the Tektosyne class ConcurrentVisualHost – see “Concurrent Drawing” in the Tektosyne User’s Guide for details. We need this thread to keep the UI responsive while ten thousand unit geometries are being drawn.

Then there’s of course the main GUI thread itself; the WPF render thread; the CLR garbage collection thread; and lastly a separate thread for the modeless help window. That last one doesn’t really do anything, but is necessary to prevent the help window from locking up while the main GUI thread is busy with a modal dialog.

Event Storage

Myriarch records the entire simulation as a sequence of “events,” so as to allow exact replays. Most events store changed unit coordinates or other unit variables. The storage requirements for this task turned out to be rather enormous: on a 64-bit system, a full run of the Leuctra demo scenario fills up 4 GB or more! This originally resulted in out-of-memory exceptions because .NET collections are limited to 2 GB regardless of total RAM. To work around this limitation, I had to distribute events among multiple checkpoint collections.

Internal event storage uses the StructLayout(LayoutKind.Explicit) attribute which treats C# structs like C/C++ unions, allowing a variety of different primitive data types to be placed in the same physical sequence of bytes. Another low-level trick speeds up loading & saving events. Instead of writing individual event fields to XML, entire events are serialized to slices of Base64-encoded byte arrays. Declaring a byte array as another view on the C# “union” then allows direct copying between event data and serialization buffer.

Leave a Reply