Writing Mobile Code Essential Software Engineering for Building Mobile Applications [Electronic resources] نسخه متنی

How Many State Machines Should Be in Any Given Application?

Hopefully by now you have been convinced of the propriety of using state machines as a central part of your mobile application's design. As in any aspect of design, there are top-level guidelines and important implementation details. Designing the proper kinds of state machines is a bit of an art form that improves with experience. A state machine should be "an abstraction of one or more variables that can take only a set of finite values, each of which map to a useful discrete state." These variables should somehow correlate to different states that an application or class can be in. As in the code example above, it is useful to define an explicit enumeration that names and lists the valid set of states you want managed by a specific state machine.

Sometimes it is useful to have multiple state machines inside the same application. A state machine that manages cached data that was retrieved from a database may be used in addition to a separate state machine that manages graphical objects such as pens and brushes that are cached for use in common drawing. A third state machine may manage the running of tasks on background threads. Although all of these state machines could be combined into a single combined "über state machine," because there is little or no correlation in the states the separate machines manage the combined state machine would simply be the sum of all the permutations possible, and not of any added use. Similarly, it is possible to err at the other extreme and rather than build one useful central state machine you end up with dozens of little state machines each managing single application variables. The key here is correlation. It is appropriate and useful to use a state machine to manage a set of variables, objects, and resources if they somehow correlate to one another.

Below are some descriptions of useful state machines to use in your design.

The User Interface State Machine

User interfaces represent one of the most obvious areas where state machines are of great use. The behavior of controls sharing a form often correlate; some controls are shown and hidden at the same time; some controls are always hidden when other controls are visible; some controls are repositioned when other controls are shown, and so on. Each form you design should have a state machine associated with it that drives its visual behavior. If the form itself contains multiple subpages that users can flip through, such as tabbed dialogs or multistep wizards, it probably makes sense for each of these subpages to have a state machine of its own.

A form's user interface state is particularly important for mobile devices because screen real estate is a scarce commodity that needs to be properly managed. As the user navigates between different application states, user interface elements need to be shown and hidden or resized and moved around to make sure the appropriate information is available for the user in each state that the application can be in. Different parts of the application naturally vie for screen space, and if the logic to show, hide, or reposition controls is distributed in your application's logic a mess will result. There needs to be a central arbitrator for managing screen real estate and a state machine is great for this.

Figure 5.2 shows the user interface states for our Pocket PC vocabulary learning game. The top of the screen is devoted to the game's play field. The character moves around the play field and collects objects when the user answers vocabulary questions correctly. In the diagram are shown four states of the application along with arrows indicating the possible transitions between user interface states.

As you can see, each state has certain information that it wants to display to the user and certain input that it wants to allow in response. On a large desktop screen, this might not be a big challenge; given the limited real estate available on a mobile device, however, we need to be as efficient as possible in our use of it. A text box is used to display questions and answers and supplemental text is also painted directly to the playfield bitmap above it. Various buttons are displayed to the users, enabling them to make selections and move the application onto the next state. In this example, four distinct user interface states were required.

State machines also prove very useful in experimenting and refining the user interface. Various different positionings and sizings were able to be tested quickly by simply changing the layout code managed by the state machine. For instance, originally the text display area was located above the play field, but usage testing indicated that it would work better if positioned below, so it was moved and retested in various different configurations. Additionally, the size of the text box used to display general information to the user in different application states was experimented with to find an optimum configuration balancing utility and aesthetics. Although a state machine is not explicitly necessary to do this user interface reorganization it makes it much easier. Having all the code that controls the visibility, sizing, and positioning of controls in one place makes this kind of iterative design much quicker and more comprehensible than trying to manage layout changes that are scattered in many different places in an application's logic.

The Memory Model State Machine

Most applications keep some kind of significant state in memory. Word processors keep a model of the document being worked on in memory. Spreadsheets keep the tabular data of the spreadsheet they are working with in memory. Games keep state relating to the current play field the user is playing on. The language vocabulary teaching game previously described keeps part of a dictionary in memory.

Often the data kept in memory is a slice of a larger set of data. When working with databases, this slice is often called a "view" and represents the full or partial result of a specific query on the database. Because the user almost never needs to work with all the data at the same time, significant efficiencies can be achieved by only keeping in memory what the user currently needs. The user wants the experience of being able to work with all the data, but this does not mean all the data needs to be loaded in memory simultaneously.

As with user interfaces, there are two ways to manage this data, either explicitly or implicitly. As noted earlier in this book, many desktop applications tend to take a very casual approach to managing the memory they are using. This results in a wasteful usage of resources that is somewhat compensated for by the large memory and memory paging files available on desktop computers. For mobile devices, it will result in unacceptably poor performance as unnecessary objects crowd out space needed by your application to run efficiently. Taking a more proactive and explicit approach to managing memory usage in mobile device applications is highly advisable.

When designing your mobile application's memory model, it is important to ask yourself the following questions:

How much data needs to be loaded at any given time for use by the user?

When and under what circumstances should loaded data be discarded? In answering this question, you should be aggressive. If data is not immediately useable by the user there should be a model for discarding it.

What is the right format for storing the data in memory? For small amounts of data, it may make sense to choose the most convenient format from a programmatic perspective. For larger amounts of data, such as for a large number of rows retrieved from a database, coming up with a memory and computationally optimized format for storing the data is imperative. There should also be a model that allows the most relevant pieces of data to be kept in memory and the rest flushed out.

Is there data that it makes sense to permanently cache in memory? There is no point in being overly aggressive in throwing out an object as soon as you are done with an immediate need for it if the application will need to reload or re-create it moments later. Memory is a resource to be wisely used neither wastefully nor in a miserly way. There is no gain in being memory wise and processor foolish.

If you are dealing with several different types of data or system resources, you may need a state machine for each. In the example above of a vocabulary learning game, there are several kinds of data and resources that must me managed in memory efficiently:

Vocabulary words
The dictionary we use for the game may contain thousands or tens of thousands of potential vocabulary words each with definitions and usage examples. We could try to load all these into memory at once, but this would almost certainly be wasteful. What we want is for the user of the application to have an experience that is comparable to having all the words loaded into memory at once while we intelligently swap words in and out as the game progresses. The software design challenge is to come up with a flexible state machine and supporting set of algorithms that provide this experience. Our memory management algorithms should provide that a fixed number of random words are loaded into memory and that these words are used for a while and then thrown out in favor of a new set of words. The design should also be scalable so that we can specify the number of words loaded into memory and tune this number as we learn more about the user's needs as well as the target device's available capacity to hold this data in memory. Because we are likely to hold a significant number of vocabulary words, their associated definitions, and other related information in memory, perhaps a hundred items at a time, it is also worth thinking about the most efficient way to store and access this data in memory.

Game board data
Because our game is a graphical, each level of the game board will have some resources and state associated with it. All bitmaps and objects holding state relating to pieces on the game board take up memory. It is likely we will want a state machine that keeps the data for one game board level in memory at any given time and discards the data as soon as it is no longer needed such as when the data for another level is loaded.

Globally cached graphics objects
Our graphical game is going to be doing a lot of common and repetitive drawing tasks. Rather than continually creating and discarding commonly used pens, brushes, and bitmaps, it may make sense to have a state model that allows these very commonly used resources to be kept in memory as long as repetitive drawing tasks need to occur. When the game's state switches to a mode where these resources are not required, they can be discarded.

The Background Processing State Machine

There will be portions of your mobile application that require potentially long-duration processing or network access; any processing operation that can potentially take more than 0.5 seconds to complete falls into the grouping of "long-duration activities." A few examples include the following:

Recursive or iterative computations that explore lots of options
Search algorithms, data-analysis algorithms, and games with artificial intelligence fall into this camp. A search of an optimum next chess move can explore many thousands of possible moves to varying degrees of depth. These operations can take a significant amount of time.

Large loads or saves of data
Loading several hundred pieces of information from an XML file or database can take a while.

Networked operations
Almost anything that happens over a network is susceptible to potential latency and communications problems.

For these kinds of operations, you will want to consider running them asynchronously to your application's user interface thread. For any asynchronous operation, a state machine allowing the user interface thread to communicate with the background thread and gain necessary information about the processing's progress is important. The user interface thread will want to be able to periodically query the state of the background operation and will want to give the user the option of aborting the operation. Conversely, the background processing thread will want the ability to update the user interface thread on its progress as well as get a notification if the foreground thread wants it to abort processing. A state-machine-driven processing model is an excellent way of meeting these objectives.

Following is an example that shows using a state machine to drive a potentially long-running background calculation. The calculation finds the next biggest prime number after a specified integer. The code can either be run synchronously for debugging purposes or asynchronously so that the user interface does not get blocked when the processing is occurring. Figure 5.3 shows the simple state machine that is used to allow the background processing thread to communicate its status. The state machine also allows the user interface thread to request that the background processing be terminated.

Listing 5.4. Code for the Background Thread Prime Number Calculator

using System;
public class FindNextPrimeNumber
{
//States we can be in.
public enum ProcessingState
{
notYetStarted,
waitingToStartAsync,
lookingForPrime,
foundPrime,
requestAbort,
aborted
}
int m_startTickCount;
int m_endTickCount;
long m_startPoint;
long m_NextHighestPrime;
ProcessingState m_processingState;
//--------------------------------------------------
//A very simple state machine.
//--------------------------------------------------
public void setProcessingState(ProcessingState nextState)
{
//--------------------------------------------------
//Some very simple protective code to make sure
//we can't enter another state if we have either
//Successfully finished, or successfully aborted
//--------------------------------------------------
if   ((m_processingState == ProcessingState.aborted)
||  (m_processingState == ProcessingState.foundPrime))
{
return;
}
//Allow the state change
lock(this)
{
m_processingState = nextState;
}
}
public ProcessingState getProcessingState()
{
ProcessingState currentState;
//Thread saftey
lock(this)
{
currentState = m_processingState;
}
return currentState;
}
public int getTickCountDelta()
{
if (getProcessingState() == ProcessingState.lookingForPrime)
{
throw new Exception(
"Still looking for prime! No final time calculated");
}
return m_endTickCount - m_startTickCount;
}
//---------------------------------------------------
//Returns the prime
//---------------------------------------------------
public long getPrime()
{
if (getProcessingState() != ProcessingState.foundPrime)
{
throw new Exception("Prime number not calculated yet!");
}
return m_NextHighestPrime;
}
//Class constructor
public FindNextPrimeNumber(long startPoint)
{
setProcessingState(ProcessingState.notYetStarted);
m_startPoint = startPoint;
}
//------------------------------------------------------------
//Creates a new worker thread that will call
// "findNextHighestPrime()"
//------------------------------------------------------------
public void findNextHighestPrime_Async()
{
System.Threading.ThreadStart threadStart;
threadStart =
new System.Threading.ThreadStart(findNextHighestPrime);
System.Threading.Thread newThread;
newThread = new System.Threading.Thread(threadStart);
//Set our processing state to say that we are looking
setProcessingState(ProcessingState.waitingToStartAsync);
newThread.Start();
}
//------------------------------------------------------------
//This is the main worker function. This synchronously starts
//looking for the next prime number and does not exit until
//either:
// (a) The next prime is found
// (b) An external thread to this thread tells us to abort
//------------------------------------------------------------
public void findNextHighestPrime()
{
//If we've been told to abort, don't even start looking
if(getProcessingState() == ProcessingState.requestAbort)
{
goto finished_looking;
}
//Set our processing state to say that we are looking
setProcessingState(ProcessingState.lookingForPrime);
m_startTickCount = System.Environment.TickCount;
long currentItem;
//See if it's odd
if ((m_startPoint & 1) == 1)
{
//It's odd, start at the next odd number
currentItem = m_startPoint + 2;
}
else
{
//It's even, start at the next odd number
currentItem = m_startPoint + 1;
}
//Look for the prime item.
while(getProcessingState()  ==
ProcessingState.lookingForPrime)
{
//If we found the prime item, return it
if(isItemPrime(currentItem) == true)
{
m_NextHighestPrime =  currentItem;
//Update our state
setProcessingState(ProcessingState.foundPrime);
}
currentItem = currentItem  + 2;
}
finished_looking:
//Exit. At this point we have either been
//Told to abort the search by another thread, or
//we have found and recorded the next highest prime number
//Record the time
m_endTickCount = System.Environment.TickCount;
//If an abort was requested, note that we have aborted
//the process.
if (getProcessingState() == ProcessingState.requestAbort)
{
setProcessingState(ProcessingState.aborted);
}
} //End function
//Helper function that looks to see if a specific item
//is a prime number.
private bool isItemPrime(long potentialPrime)
{
//If it's even, it's not prime
if ((potentialPrime & 1) == 0)
{
return false;
}
//We want to look up until just past the square root
//of the item
long end_point_of_search;
end_point_of_search =
(long) System.Math.Sqrt(potentialPrime) + 1;
long current_test_item = 3;
while(current_test_item <= end_point_of_search )
{
//---------------------------------
//Check to make sure we have not been asked to abort!
//---------------------------------
if (getProcessingState() !=
ProcessingState.lookingForPrime)
{
return false;
}
//If the item is divisible without remainder,
//it is not prime
if(potentialPrime % current_test_item == 0)
{
return false;
}
//advance by two
current_test_item  = current_test_item  + 2;
}
//The item is prime
return true;
}
} //end class

Listing 5.5 contains code that can be placed in a form to test the background processing algorithm above.

Listing 5.5. Test Code to Call the Background Thread Prime Number Calculator Above

//------------------------------------------------------------
//Code to process the click event of Button1 on the form
//
//Call the prime number function on this thread!
//(This will block the thread)
//------------------------------------------------------------
private void button1_Click(object sender, System.EventArgs e)
{
long testItem;
testItem = System.Convert.ToInt64("123456789012345");
FindNextPrimeNumber nextPrimeFinder;
nextPrimeFinder = new FindNextPrimeNumber(testItem);
nextPrimeFinder.findNextHighestPrime();
long nextHighestPrime;
nextHighestPrime = nextPrimeFinder.getPrime();
System.Windows.Forms.MessageBox.Show(
System.Convert.ToString(nextHighestPrime));
//How long did the calculation take?
int calculation_time;
calculation_time = nextPrimeFinder.getTickCountDelta();
System.Windows.Forms.MessageBox.Show(
System.Convert.ToString(calculation_time) + " ms");
}
//------------------------------------------------------------
//Code to process the click event of Button2 on the form
//
//Call the prime number function on another thread!
//(This will not
//block this thread)
//We will use a state machine to track the progress
//------------------------------------------------------------
private void button2_Click(object sender, System.EventArgs e)
{
long testItem;
testItem = System.Convert.ToInt64("123456789012345");
FindNextPrimeNumber nextPrimeFinder;
nextPrimeFinder = new FindNextPrimeNumber(testItem);
//------------------------------------
//Do the processing on another thread
//------------------------------------
nextPrimeFinder.findNextHighestPrime_Async();
//Go in a loop and wait until we either find the result
//or it is aborted
while((nextPrimeFinder.getProcessingState() !=
FindNextPrimeNumber.ProcessingState.foundPrime)
&&
(nextPrimeFinder.getProcessingState() !=
FindNextPrimeNumber.ProcessingState.aborted))
{
//TEST CODE ONLY:
//Show a message box, allow the user to dismiss it
//This will help pass the time!
System.Windows.Forms.MessageBox.Show("Still Looking...Hit OK");
//We could abort the search by calling:
//nextPrimeFinder.setProcessingState(
//  FindNextPrimeNumber.ProcessingState.requestAbort);
}
//If we aborted the search, exit gracefully
if (nextPrimeFinder.getProcessingState() ==
FindNextPrimeNumber.ProcessingState.aborted)
{
System.Windows.Forms.MessageBox.Show("Search was aborted!");
return;
}
long nextHighestPrime;
nextHighestPrime = nextPrimeFinder.getPrime();
System.Windows.Forms.MessageBox.Show(
System.Convert.ToString(nextHighestPrime));
//How long did the calculation take?
int calculation_time;
calculation_time = nextPrimeFinder.getTickCountDelta();
System.Windows.Forms.MessageBox.Show(
System.Convert.ToString(calculation_time) + " ms");
}

The sample number I passed in (123456789012345) took about 10 to 20 seconds to run on my Pocket PC emulator. Add or remove digits to your sample number to increase or decrease the processing time. (Longer numbers will typically take longer to run.)

Note

To keep the sample simple, I've purposefully put very few rules into the state transition function. In a real implementation, I would suggest putting more rules such as only allowing valid transitions and throwing exceptions in unexpected cases. Having strict rules on state transitions is very useful for ferreting out unexpected bugs due to code running on more than one thread. Things can get tricky and good rules, asserts, and exceptions will go a long way in helping you find subtle bugs that will cause you hours of frustration later.

State Machines Inside Games

State machines are extremely useful in action games where different game characters need to move around the screen and perform actions in different modes. Each character may have different modes of motionfor example: facingLeft, facingRight, runningLeft, runningRight, climbingLadder, and falling. Using a state machine for each game character with well-defined rules for what the characters behaviors can be in each state and which state transitions are allowable is a very useful way to build complex behavior into both computer-controlled and user-controlled characters.