Conquer & PageManager

Whilst I make the last changes to Synchron - I think the last thing remaining to implement is the mini-preview - I'm starting up a new project called Conquer, which is a fairly simple implementation of an RTS game. I've a few ideas around lines of communication, chains of command and other, real-world military concepts that tend to get glossed over in current RTSs but the truth is, I'm not really doing this to explore strategic game mechanics. Conquer is actually a vessel for me to test out a style of state management that I've called PageManager.

Let's say that we're simulating an object in 2D space: that object has a position (X & Y coordinates) and a velocity (change in X per second and change in Y per second) and we're updating the position of the object in real-time and then rendering it to the screen. The main thread of the simulation loops through two steps; first, it updates the position of the object by finding how far it has moved in this iteration, and second it renders the object in its new position. The distance the object has moved is the velocity of the object multiplied by the time span of this iteration; that is, the difference between the current time, and the time at which the last update took place. So if each update loop takes a second, then the position changes by velocity * 1; if each update takes half a second, then the position changes half as much per iteration, but there's twice as many iterations per second so the rate of change is constant. Ideally, we'd want at least 60 iterations per second to maintain a good frame rate.

So, that's the basics; the next step is to consider interacting values in the simulation. For example, let's say that our object is a spaceship; it has the properties of Position and Velocity (as before), but in this case it's propelling itself using an internal fuel source that steadily declines. As the fuel source is depleted, the power supplied is reduced and the velocity of our ship decreases - to simulate this, we'll include a property of Power, which has a Rate of Depletion.
In this example, the position is calculated as before, but velocity is now proportional to power and power decreases by "Rate of Depletion" amount per second. This means that there are several steps to the update and, more interestingly, the order in which they are determined has an effect on the result. If you update the position before you update the velocity, then your ship will always fly further on the same amount of fuel, because you'll use the earlier, faster velocity rather than the later, slower value. The same is true of updating velocity & power - if you update velocity before power, you get a better deal.

This gets a lot more complicated when you start simulating lots of objects interacting in various ways and becomes difficult to ensure that everything is evaluated in a specific order; this is especially true when you start working with multiple thread, where this situation is technically a race condition. So what's the solution?

A very neat and simple solution is to store every property on every object (at least, every property that changes over time) in pairs - a current value and a new value. During the update step, your code should always read the current value and write to the new value (e.g. NewPosition = CurrentVelocity * Time) - by doing this, you ensure that the current value remains constant and the calculations will come out the same no matter which order you evaluate them in. Once everything's done, you copy the new values into the current value variables (e.g. set CurrentPosition to the value of NewPosition) and repeat.

Now, I've not described anything new here, but we've reached the point at which I started thinking. The first thought that occurred to me is that copying all the values from New to Current is an expensive operation; instead, leave the values where they are, but use a boolean flag to indicate which variable is the current, and which is the new, then flip that flag for each iteration. For example, I have Position1 & Position2 properties on my object and I begin my update step with the flag set to false. This means that I update the variables numbered 2 from the variables numbered 1 (e.g. Position2 = Velocity1 * Time) - I also need to render from the properties marked 2, as these are the most up-to-date. In the next loop, the flag is set to true, so I update in the reverse direction (Position1 = Velocity2 * Time) and render from the opposite set of properties. This way, you get the advantage of separating the properties into a "current" and "new" pair, but without having to copy the values back and forth.

Expanding on this idea presents another possibility: splitting each property into several variables allows several threads (typically, an update thread and a render thread) to act on the same set of objects without interfering. So long as you ensure that the update thread never writes to the same copy of a property as the render thread is currently reading from, and that the update thread always reads from the newest copy, you can have both threads running at different rates - this is actually preferable, as the process of updating the simulated objects can vary drastically in length, whilst you want to keep the visual framerate fairly constant.

PageManager does this by dealing in pages & contexts. A page is simply a term for a copy of a property - for example, if there is a new and current copy, then there are two pages. A context provides two things: firstly, it provides a page number (similar to the boolean flag described above) that indicates which page the context is referring to and secondly, it locks the page for reading or writing.
There are two types of context: a Read Context, which locks a single page for reading (for use by render threads), and a Write Context, which locks one page for reading and one for writing (used by update threads). The PageManager is responsible for coordinating requests for and releases of contexts - when a Read Context is requested, the manager picks the newest available page (that is, the page that was updated last) and locks it. When a Write Context is requested, the manager locks a page for reading in the same way as for a Read Context, but also locks the oldest available page for writing. A page may be locked for reading multiple times, but a write lock is exclusive; neither read-locked or write-locked pages can be write-locked.

In this way, a render thread can request and hold a Read Context and take as long as it likes to render; meanwhile, the update thread requests and releases Write Contexts, reading from one page and writing new values to the other.

Hopefully that explains what the idea is about; next time, some code!