Today's lesson: you can't implement back-buffer flipping with the DrawImage method in GDI. Well, you can, but it takes longer than the actual rendering, isn't multi-threadable and it still causes tearing. The original idea I'd had while implementing multi-monitor support in Synchron was to render everything to an off-screen buffer once and then copy it onto each screen using DrawImage, but a quick run through performance analysis put paid to that.
In the fullness of time I think I'll move to DirectX, but there's no rush.
Wednesday 28 January 2009
Wednesday 21 January 2009
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!
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!
Wednesday 14 January 2009
Synchron (continued)
I guess the important thing to know about Synchron is how to tell the time with it!Each unit of time (hours, minutes, seconds) is represented by a separate wave of differing amplitude, much like each hand on a (24hr) clock; the hours wave (the largest wave) is the hours in a single day, the minutes wave (the next largest) is the minutes in a single hour and so on. As time progresses, those waves move past a central line that marks the current time. The trough of the wave (left and right edges on the example image) is the crossover from one day/hour/minute to the next (for example, midnight), whilst the peak of the wave (the centre of the image) is half way through (e.g. midday). So whilst it's difficult to tell the exact time, you can get a reasonable estimate by looking at where each wave meets the centre line and where it is between the peak and the trough of the wave.
Synchron V1 (Beta)
To kick things off, I'll start with a simple project that I was inspired to do by "Geoyd", whose site I found whilst researching balanced ternary and the University of Moscow's research project into tri-state computing (Setun).
One of the items on his site is the Sinchron, a sine-wave "clock" that interprets a typical, circular clock (displaying the current offset of seconds, minutes or hours as an angle from the vertical) in a graph (in which the offset is the cosine of that angle). By marking a point on the resulting cosine wave (or moving the wave past a fixed line) you can show the current time.
Hmm, I'll put up a more detailed explanation tomorrow, but for now, here's the code implemented as a screensaver - I should also admit that I wrote this primarily because Geoyd's implementation is a Mac-only screensaver :-D.
One of the items on his site is the Sinchron, a sine-wave "clock" that interprets a typical, circular clock (displaying the current offset of seconds, minutes or hours as an angle from the vertical) in a graph (in which the offset is the cosine of that angle). By marking a point on the resulting cosine wave (or moving the wave past a fixed line) you can show the current time.
Hmm, I'll put up a more detailed explanation tomorrow, but for now, here's the code implemented as a screensaver - I should also admit that I wrote this primarily because Geoyd's implementation is a Mac-only screensaver :-D.
Welcome
Hey there,
As a brief introduction, I'd like to explain the name of this blog so that you get some idea of what it's going to be. As the name implies, it's about programming - specifically, programming oriented around ideas.
Typically, I'll have an idea and then experiment with an implementation, exploring the idea by building code around it; by doing so, I come to better understand the vague concept that I started with and will (with any luck) have built something that I can later reuse. As my understanding grows, the implementation changes, and so the code as a whole grows quite organically, often sprouting in directions completely unrecognisable from the initial root.
Sometimes the ideas aren't mine (in which case I'll give due credit) but the implementation piques my interest. In other cases, the idea is interesting but the implementation is impractical - hopefully here I'll inspire someone else to pick up where I left off.
In any case, often as not, trying to explain this haphazard sequence of thoughts and code-revisions is difficult. You start at the beginning and have to meander through all the following changes before you finally reach the current state of a project, by which point you've likely lost the listener (if not yourself) along the way. Trying to write a document or comments which explain what's going on is even worse, at least for me, because I can't write documents. Just can't. Write code, yes; write English, no. So instead, I'm going to make notes as I go, put them in this blog and add links to relevant code (which I'm currently storing on my CodePlex account) and we'll take this crazy journey together.
As a brief introduction, I'd like to explain the name of this blog so that you get some idea of what it's going to be. As the name implies, it's about programming - specifically, programming oriented around ideas.
Typically, I'll have an idea and then experiment with an implementation, exploring the idea by building code around it; by doing so, I come to better understand the vague concept that I started with and will (with any luck) have built something that I can later reuse. As my understanding grows, the implementation changes, and so the code as a whole grows quite organically, often sprouting in directions completely unrecognisable from the initial root.
Sometimes the ideas aren't mine (in which case I'll give due credit) but the implementation piques my interest. In other cases, the idea is interesting but the implementation is impractical - hopefully here I'll inspire someone else to pick up where I left off.
In any case, often as not, trying to explain this haphazard sequence of thoughts and code-revisions is difficult. You start at the beginning and have to meander through all the following changes before you finally reach the current state of a project, by which point you've likely lost the listener (if not yourself) along the way. Trying to write a document or comments which explain what's going on is even worse, at least for me, because I can't write documents. Just can't. Write code, yes; write English, no. So instead, I'm going to make notes as I go, put them in this blog and add links to relevant code (which I'm currently storing on my CodePlex account) and we'll take this crazy journey together.
Subscribe to:
Posts (Atom)