Bugbox Single-Threaded
Download the BugboxSingleThreaded
EXE (35KB) in compressed ZIP format.
Download the BugboxSingleThreaded
project files (30KB) in compressed ZIP format. This first design is going to be a standard, non-componentised, Windows application. The logical analysis has been done and it is time to make something real and tangible from it. You may recall the 'observe bugs' use cases; the one which used the 'calculate motion of a bug' use case. These are rather abstract ideas at present so now we have to bridge the gap between the idea and the solution by asking questions and making design decisions. Specifically: how are the Bugs observed; how quickly do they move; how does a Bug store its state, i.e. the values of its properties; how does a Bug know when its way forward is obstructed; how does the Box manage its Bugs; and how does each Bug know which Box it is in?
WinZip® brings the convenience of Windows to the use of Zip files and other compression formats. If you don't have "the most celebrated shareware app in the history of computing" already, use the above link to download it.
Observation may be accomplished in more than one way: perhaps a continuous textual readout of the Bugs' location and bearing, perhaps a graphical simulation showing the same information. I have chosen the latter.
What do we mean by quickly? There are two factors to the apparent speed of motion of an animated graphic: the distance travelled per move; and the time interval between calculating consecutive moves. The distance travelled must be constant and must be small enough to make the motion smooth - a few pixels, no more. So how long between calculating moves? In reality, time and motion are continuous; creatures do not generally move a small, discrete amount and then pause for a spell before moving again as they will in this simulation. Discrete time systems look smoother when their sample frequency is high. So our simulation will have to perform motion calculation as often as the number of Bugs and the hardware will allow.
Tight, CPU-bound loops are a sign of ill-breeding in Windows society, and intuition suggests that if I design the motion calculation and rendering loop in this way then, regardless of the number of Bugs present, the CPU usage will max out and hardly give any other application a look-in. I'll come back to whether such intuition is correct in the conclusion. In addition to the above problem, a tight loop will mean that the first Bug added will race around at full tilt and then, as subsequent Bugs are added, the entire company will slow down in concert. Altogether not very realistic. As a solution I have chosen to trigger motion calculation and rendering on a Windows timer.
As for the remaining questions: in this first sample, the state of a Bug is held within data members of the CBug class. A Bug calculates the rectangle it would occupy if allowed to take its next move and then queries the Box to determine if this rectangle is vacant of a boundary and, if the flag is set, of another Bug. The Box is the best class to determine the vacancy or otherwise of a region of its area, given that it owns its boundaries as well as all the Bugs. The Box manages its Bugs inside an STL vector and, on being prompted by the timer, it delegates the work like this:
void CBox::OnTimer()
{
for_each(m_pvecBugs.begin(), m_pvecBugs.end(), mem_fun(&CBug::OnTimer));
}
A Bug is provided with a constant Box pointer in its constructor through
which it makes its queries about vacant regions. Please feel free to download
the executable and/or Visual
C++ project files for further
study. In this first solution, a single thread is performing all of the following: calculate all the Bugs' new positions, check for obstructions, render the Bugs to the screen, handle any user interaction. Every 20 milliseconds a timer causes the thread to move and render all the Bugs. The application runs fairly smoothly with only a few Bugs present, but add more than a handful and performance begins to suffer even before the CPU usage begins register in NT's Task Manager. The fact is that not even a tight moving-and-rendering loop would have maxed-out the CPU because most of the time the processor and its single thread are idle waiting for graphics i/o. If you have the patience to add one or two hundred Bugs you'll still find the CPU usage negligible but, when the application is minimised, CPU usage leaps up to around 50% because it is freed from waiting for BitBlts.
What this application needs is the ability to have more than one task on hand at once; something that people and microprocessors do all the time. No single microprocessor can actually do two things at the same time and neither, if they're honest, can people. But what we can do is have the sense to, for example, chop some onions whilst waiting for the kettle to boil for the pasta. And that's the principle behind multi-threading. In an effort to employ the time of the processor to better effect, the next solution (Bugbox Multi-Threaded) will allocate a separate thread of execution to each Bug. Then, a Bug stalled on i/o can be switched-out by the processor and another switched-in in the hope that it might have some work more worthy of the processor's attention.