XNA Game-Themed CS1 Examples (XGC1)

Release 2.0 (XNA V3.1)
2/8/2010

Topic: Topic.6.Arrays
Example: Ex_8.ProcessArray

Array Processing Patterns: Sum, Average, Min, and Max


References:

Goals:



1. Obtain the example code

Download and unzip the zip file and you will see an ExampleProgram folder. Open the ExampleProgram folder, the EXE folder contains the compiled program and you can double click on the .sln file to work with the source code.

When the game starts, you'll see a screen that looks similar to this:

In this tutorial, the program that you can run closely resembles the program that you ran in the previous tutorial.  What's different is the message at the top of the screen.  The program displays the sum of all the hit counts as "total", the average (which is the total, divided by the number of rectangles), the smallest hit count as "min", and the largest as "max"


2. Background


The major topic for this tutorial is the pattern for processing arrays.  Since we can only interact with arrays one element at a time, we will need a strategy that will allow us to accomplish tasks by only examining 1 element at a time.  The tasks that we'll examine in this tutorial include summing up all the numbers in the array, or averaging the numbers, or finding the min/max number.  Let's examine the overall pattern using the task of averaging the numbers in the array.

In order to calculate the average of the numbers in the array, we first need to first sum up all the elements in the array, and then divide that total by the number of elements in the array.  The we will break up the basic pattern into three phases:

  1. Pre-Loop Initialization
    When we start our algorithm, we haven't summed up any elements yet, so the running total should be initialized to zero (let's call this variable total).  Generally, just about anything we do to 'process' an array will require that we (at least) initialize some variables.

  2. The Loop
    In this stage, we'll process the array, step by step.  For our problem, this is where we'll sum up all the numbers in the array.  More detail on this, below.

  3. Post-Loop Processing
    Once we've got the sum of the elements, the only thing left to do is to divide that total by the number of elements, and then store the resulting average into a variable.

The second phase ("The Loop") is involved enough that we will examine it separately, here.  The key thing to understand is that since we can't deal with the entire array in a single statement, we'll have to approach the problem element-by-element.  It may help to mentally break the array down into a couple of regions: the region of the array wherein we've already done the work, the current array element that we're looking at, and the remaining elements in the array, where we'll need to do work in the future.  Here's a picture to help visualize that (using the first six elements of the array that keeps track of hits, in the above screenshot):

The green 'Already Done' region starts out being empty, since at the start of the loop, we haven't done any work.  The blue 'Current Element' region is just element #0 - in most (but not all) cases, it's easiest to count up from zero.  The tan 'Future Work' region consists of all of the elements we haven't looked at yet, which are elements 1 through 5.

How will we sum up all the elements in the array?  Simply put, we need to add the element we're currently looking at (number 11, stored in element #0), to the sum of all the elements that we've already looked at.  In other words, we need to add 11 to the total of the elements in the green region.  Since the variable total stores the sum of the elements in the green region, we just need to add 11 to that total (which starts out at zero).  Once we've done that, then we've processed element #0, and it becomes part of the green, 'Already Done' region of the array.  In the next iteration through the loop, the blue, 'Current Element' region moves up by one, like so:

In this iteration through the loop, we add the number in the current element (zero) to the total (11), and get 11, which extends the green region to now include the current element.


 At the start of the next iteration through the loop, we have:

In this iteration through the loop, we add the number in the current element (11) to the total (11), and get 22, which extends the green region to now include the current element. 

 At the start of the next iteration through the loop, we have:

As you can see, this process will repeat, until the 'Future Work' region is empty, and the entire array is covered by the green 'Already Done' region.  Once that's done, phase 2 ("The Loop") is done, and our program will have the sum of all the elements in the array, stored into the variable total.  After that, it will go on to phase 3, in which it will divide the sum by the number of elements, in order to get the average.

Please also keep in mind that the 'Three Phase' division, and the green/blue/tan way of thinking about this array processing pattern is something that's specific to this tutorial, and not something that will be commonly recognized anywhere in the computer industry.


3. Examining The Program:

Let's examine the C# source code that produces the behavior we see on-screen


FURTHER EXERCISES:

  1. Start from a blank starter project (1000.201, if you need it), and re-do the code from memory as much as possible.  On your first try, do what you can, and keep the above code open so that when you get stuck, you can quickly look up what you forgot (and that after you finish a line, so that you can compare your line to the 'correct' line).  On the next try, do the same thing, but try to use the finished code less.  Repeat this until you can type everything, without referring to the tutorial's code.
  2. Examining The AverageHits() Function
    For this exercise, you should use the same project that was explained in the above tutorial.
    Notice that the numbers stored in the m_BlockHits array are integers, and that TotalHits returns an integer.  Notice also that we are specifically declaring total to be a float, not an int.  Why was this done?  What would happen if you declare total to be an int, instead?
  3. Problem with MinHits if we assign min to be zero?
    For this exercise, you should use the same project that was explained in the above tutorial.
    Notice that in the function MinHits, we initialize the variable min to have the value of the first element of the array. 
    1. What problem(s) would arise if the variable min was assigned the value zero, instead?  It may help to list the values stored in an example array when explaining the danger of doing this.
    2. In your own words, in English, concisely explain why min is initialized with the value of the first element of the array, and not some other number, like zero.
  4. ComputeAllStats Function
    For this exercise, you should use the same project that was explained in the above tutorial.
    Instead of using each of the four, separate functions that each compute one thing, you will instead create a single function that does all four tasks using a single loop.  As you're doing this exercise, think about the advantages and disadvantages of writing the code this way.  Given a choice of a single ComputeAllStuats function, versus four separate functions, how do the two solutions compare in regards to how easy the code is to test, to debug, to maintain, and to use (as a programmer), as well as how efficient the algorithms are from the computer's point of view - is there work that's being duplicated in the ComputeAllStats solution?  In the solution with four separate functions?

    Your function should look like this, but filled in with working code:

    public void ComputeAllStats(ref float sum, ref float avg, ref float min, ref float max)

    {

    }

  5. Creating a SecondToMinHits function
    For this exercise, you should use the same project that was explained in the above tutorial.
    For this exercise, you should create a function named SecondToMinHits, which will find the second to smallest number in the array. 
    Here are some examples, to clarify
    1. If the array contains:
      Index 0 1 2 3 4
      Value 0 10 20 30 40


      Then the minimum element is: 0
      And the second to smallest number is: 10

    2. If the array contains:
      Index 0 1 2 3 4
      Value 90 12 20 30 9


      Then the minimum element is: 9
      And the second to smallest number is: 12

    3. If the array contains:
      Index 0 1 2 3 4
      Value 90 12 9 30 9


      Then the minimum element is: 9
      And the second to smallest number is: 9

  6. Extra Challenging: Reversing The Array
    For this exercise, you should use the same project that was explained in the above tutorial.
    Can you write a function that will take the m_BlockHits array, and reverse the order of the elements in the array? 
    For example, if the array starts out with the values
    Index 0 1 2 3 4
    Value 0 10 20 30 40


    then after calling the array-reversing function, the array should have the values:

    Index 0 1 2 3 4
    Value 40 30 20 10 0

    Keep in mind that this exercise is extra challenging, and may not be a good exercise to start with if you're looking at this topic for the first time.


Project home page: The Game-Themed Introductory Programming Project.
Kelvin Sung
Computing and Software Systems
University of Washington, Bothell
ksung@u.washington.edu
Michael Panitz
Business And Information Technology
Cascadia Community College
mpanitz@cascadia.eduu

Microsoft Logo This work is supported in part by a grant from Microsoft Research under the Computer Gaming Curriculum in Computer Science RFP, Award Number 15871 and 16531.
2/8/2010