Development environment



Chapter 13: Recursion

This chapter focuses on building an application involving a 2-dimensional grid, a simplified version of the minesweeper game installed on many computers. While studying this chapter, you will

• learn programming tricks for manipulating data organized in grids such as nested for-loops, arrays holding bounds, and calculating the cell from the coordinates

• appreciate the power of recursion, the situation in which a function calls itself

• observe again the process of staged development

• gain experience in Flash defining listener instances (movie clips set up to respond to specific events), using pushbutton components, and setting up frames for timing

Motivating Example

Minesweeper is a game of luck and logic. The grid of squares represents a minefield. Mines are distributed randomly in the cells. Initially, all cells appear as blank tiles. The player clicks on a cell. If the cell contains a mine, the game is over. If the cell does not contain a mine, the application computes the number of adjacent mines. If there are no adjacent mines, the application does the same calculation for all the adjacent cells, continuing this process whenever a cell is examined with no adjacent mines. A player can use displayed information on adjacent mines to make informed decisions on which cells to examine. It is possible for there to be a situation when the player has to guess, but over time the player using logic will do better than the player who only guesses. The game is timed.

The minesweeper present on many computers makes use of the right mouse button and a button combination in addition to the primary mouse button. The right button is used to mark a cell as having a flag. The game described here only uses the primary mouse button. The goal is to click on all the cells not containing mines. The player does nothing to the cells that he or she believes contain mines. When ready, the player clicks on a button labeled check. Figure 1 shows the opening screen.

[pic]

Figure 1. Opening screen for simplified minesweeper.

After clicking on the Start Game button, the grid appears and the clock starts as shown in Figure 2.

[pic]

Figure 2. Game started with 6 second elapsed.

The player plays by clicking on a cell. Figure 3 shows a game underway.

[pic]

Figure 3. Game underway: 3 cells examined, 9 seconds elapsed.

When the player believes that only cells containing mines remain unmarked, he or she clicks on the Check button. If all the cells have been examined except the ones containing mines, the player wins.

The player loses immediately if a cell containing a mine is clicked. The player also loses by clicking on the check button while there were still cells without mines that had not been clicked.

Figure 4 is a screen shot showing a game that ended when the player clicked on a mine in the second move of the game:

[pic]

Figure 4. Lost game.

The computer provides feedback to the player when there is a loss. The blanks represent where there were mines. The "M" is the cell which the player clicked to end the game. The question marks indicate cells that should have been examined. Notice that the 1, the result of the first move, is adjacent to one mine

TECHNICAL NOTE: The game described here differs in two more subtle ways from most commercial minesweeper implementations. It is possible to lose on the first move. The number of mines can vary.

The critical features required by this application include

• techniques for working with a 2-dimensional grid, including detecting the cell 'under' the mouse

• ways to implement the rules of the game, especially the one that calculates the number of adjacent mines to a given cell, and continues that process for all the cells adjacent to a cell without adjacent mines

Introduction to concepts

Many applications, including games, partition some or all of the screen area into a grid pattern. A virtual world representing a three dimensional reality also may be divided into a grid consisting of blocks. Games such as tic-tac-toe, chess, checkers, go, and minesweeper require programming dealing with the grid. Critical tasks for minesweeper and other applications include producing the display, determining the neighbors of a given cell, and calculating the particular cell pointed to by the mouse.

One of the ways to define abstractly the set of computable functions, that is, functions that can be calculated by a mechanical process, involves a procedure called recursion. Informally, a function that calls itself is a recursive function. Though it is necessary to be careful to avoid a circular definition and some programming languages do not support recursion, students who understand the use of recursion will have a powerful tool for programming.

A tactic for applications requiring attention to events such as mouse actions is to define so-called listener instances. This is somewhat antithetical to a pure object approach, but can be more efficient in terms of processing.

Description: grid tasks

A grid is a 2-dimensional structure consisting of some number of rows and some number of columns as shown in Figure 5.

[pic]

Figure 5. Grid.

A first task in many applications is to set up a grid. Your initial reaction may be great dismay since this seems to be such a tedious task. Instead, consider the following: this is the type of task for which computers were designed.

You need to know (or define variables that will hold)

• a starting position, say the upper left corner,

• the number of cells in a row,

• the number of cells in a column,

• the width of each cell, and

• the height of each cell.

The starting position could consist of a variable, firstcolumn, holding the horizontal coordinate of the first column and a variable, firstrow, holding the vertical position of the first row. The number of rows could be in hc and the number of columns could be in vc.

TIP: The trick here is to keep in mind that columns need to be positioned horizontally and rows need to be positioned vertically.

A nested for-loop construct produces the grid. The pseudo-code is

for (i=1; i1) {

return N * factorial(N-1);}

else {

return 1;}

}

There are alternative ways to program the factorial function. For example,

function factorial(N) {

If (N>1) { ans = N;

for (i=N-1;i>1;i--) {

ans = ans * i;

}

return ans;}

else {

return 1;}

}

This is called the iterative approach. The loop could be written to start at 1 and work up. One difference between the two is that the underlying programming system does more of the work in the recursive approach.

END OF TECHNICAL NOTE

The critical question to ask for any recursive definition is: does it stop or is it circular? You do not want the function to never end because 'it' keeps on calling itself.

Each situation requires its own reasoning. The reasoning for the case of factorial is that the definition provides a way of computing the answer for N in terms of a smaller number, N-1. When the number gets small enough, namely when it reaches 1, the definition is not recursive but given directly. Here is how the definition works for Factorial(4)

Factorial(4) = 4 * Factorial(3), by rule 2

Factorial(3) = 3* Factorial(2), by rule 2

Factorial(2) = 2* Factorial(1), by rule 2

Factorial(1) = 1, by definition, by rule 1

Factorial(2) = 2* 1 = 2

Factorial(3) = 3*2 = 6

Factorial(4) = 4*6 = 24

Moving from defining functions abstractly to writing programs generates new questions for recursion. Some programming languages simply do not support recursion. This is because the language must keep track of each of the invocations of a function separately. In the factorial example, there are 4 invocations of the function active at one time. The information the programming language has to manage for each call includes the parameters and the local variables as well as the calling point to which a value must be returned along with the flow of control. The burden of handling these calls may mean that recursion, even if it is possible, may not be the best way to handle a problem. However, in some cases, it is a good way. Recursion can be a way of dividing up the work, making many small jobs out of a big job.

EXAMPLE: The minesweeper application includes the task of counting the number of adjacent mines. The rules of the game indicate that this process is to continue for each adjacent cell if it turns out that the original cell did not have any neighboring mines. This makes this task a candidate for recursion.

Description: listener instances

In the simplified minesweeper application, described in more detail in the next section, when the player clicks the mouse button when it is on a cell, the program responds by determining if a mine is in the cell and, if not, examines the surrounding cells for mines. With object oriented programming in mind, you may decide to set up each cell to 'listen' for a mouse click, determine if the mouse cursor is on the cell, and then proceed with the appropriate action. Since each cell probably is created as a duplicate of a seed cell, you only need to do the coding once. However, during run-time, the code would be executed for each cell to check on the mouse. An alternative approach is to create a listener instance. This object would 'listen' for the mouse action, do the calculation described earlier to determine which cell holds (is under) the cursor, and proceed with the appropriate action. The checking on the mouse is just done one time.

Situations in which listener instances are a good approach are not limited to Flash and ActionScript.

Description: defining steps of implementation

Partitioning the aspects of an application into parts is not an easy or automatic process. The bouncing ball application described in Chapter 10 could be considered a preliminary version for the cannonball application in Chapter 11. The cannonball application itself was divided into getting the ball moving in the parabolic arc, adding the conditions for stopping and enhancing the effects of the target being hit. General rules for games also apply to other applications and include the following:

Start by implementing the static aspects of the game, namely the board.

Try as best you can to not have to play the game while implementing it. This can mean

make hidden elements visible

postpone the probabilistic aspects of the application

postpone timed aspects of the application or manipulate the time periods to reduce time pressure

Making hidden elements visible can allow you to use stochastic (random) calculations but not over-burden the debugging process.

NOTE: To avoid confusion with the Stage of Flash, the term step is used for the different stages of implementation.

EXAMPLE: The minesweeper application is a good candidate for staged implementation. Since minesweeper is itself a challenging game, you will see how the implementation described below does follow the suggestions just given to proceed slowly and to avoid having to play the game while building it.

Reading Checks

1. What is a 2-dimensional grid?

2. What other games have boards that are 2-dimensional grids?

3. Describe recursion in your own words.

4. What is Factorial(2)? What is Factorial(6)?

5. Is Factorial defined for numbers that are not integers?

Application

Review of previous examples

Previous applications in Flash made use of button symbols. You, the programmer, created your own button as a new symbol, brought an instance of the button onto the Stage and then associated event handling code for the on(release) event for the button instance. The Flash product has added pushbutton components to the software, a way to ease the implementation of common tasks. You still would implement your own buttons in an application such as rock-paper-scissors as described in Chapter 6, but components may be appropriate in many situations.

Previous chapters featured staged implementation of the examples or implementation of one version of a game and then enhancing it with additional features. This is always a good practice.

Plan of attack for one-button minesweeper

The implementation will be divided into 6 steps:

Step 1: construct a grid and decide on the position of mines. The decision will be done using a pseudo-random calculation, but the cells with mines will be made visible.

Step 2: detect which cell is clicked on by the player, determine if it is a mine, and, if not, call the expand function to determine the count of neighboring mines. Use the trace function to indicate if it is a mine.

Step 3: the expand function determines if it is necessary to call itself. Use the trace function to signal this information.

Step 4: the expand function does call itself recursively.

Step 5: add the start game and check buttons, add check function, and add timing.

Step 6: remove the code that makes the mines visible.

NOTE: What follows is a quick overview of the features of the complete game. The next section will describe the implementation in greater detail.

The calling/called table for functions for this application when complete is the following

|Function |Called/Invoked by |Calls |

|layout |Start Game button click handler | |

|expand |on clipevent (mouseDown) of listener |expand, getbounds |

| |instance | |

| |expand | |

|getbounds |expand | |

|check |Check button click handler | |

The table makes the application seem fairly simple. Its power lies in the use of recursion and in the use of Flash components.

Step1 makes use of an instance of one new movie clip symbol. The instance is called cellseed and it is duplicated to construct the grid. See Figure 7.

[pic]

Figure 7. Step 1 showing cellseed off-Stage.

The grid will consists of duplicate instances of cellseed. The names of the instances will incorporate the row and column of the cell, making it easy to reference cells, once the row and column is calculated.

The later steps will make use of what is called a listener instance. This is a completely empty movie clip whose sole purpose is to react to events. Figure 8 shows the ActionScript associated with the listener instance.

[pic]

Figure 8. The event code for the listener instance.

If the primary button of the mouse is pressed down when the cursor controlled by the mouse is anywhere, this code is invoked. The code calculates the cell using the _root._xmouse and _root._ymouse and then invokes the expand function using the cell as the parameter.

The last step will include 2 pushbutton components, each set up to invoke a designated function.

TIP: Flash components include pushbuttons, radio buttons, and dropdown lists. They are a quick way to implement standard devices for user interaction.

The Flash pushbutton component is for standard buttons.

TIP: You would not use the pushbutton component for applications such as rock-paper-scissors, when you want to button to be a distinctive shape.

The event handling and the label for the button are set using the Property panel. Figure 9 shows the Step 5 development environment. The button labeled Start Button is selected. The programmer (the author) used the Property panel to enter the label and to indicate that clicking the button should invoke the layout function.

Notice that this step has a longer time-line. The coding in the last frame updates the dynamic text field on screen.

[pic]

Figure 9. Step 5 development, with property panel showing handler for Start button.

The code in this application follows the practice followed so far in this text. Function definitions and global variables are in the first frame, actions layer. The functions in the complete application include

layout

expand

getbounds

check

Step 1 just has the layout function. The expand and getbounds are added in the second step and expand is enhanced in subsequent step. The check function is added in the last step. In the last step, you will remove or make a comment out of the statement that displays where the mines are.

Use of concepts in implementation

Step 1

Name the first layer actions and add a new layer, naming it board.

Create a movie clip symbol to be the seed for all the cells. The graphical content of this movie clip is a Dynamic text field. Use the Properties panel as shown in Figure 10 to set the W for width and H for height to 20.0 pixels. Be sure and give the Dynamic Text field a Var name: show.

[pic]

Figure 10. Cell movie clip symbol.

This symbol also has frame action code, namely a variable that will indicate if this is or is not a mine, and variables to hold the row and the col[umn] of this cell, as shown in Figure 11.

[pic]

Figure 11. Actions panel for cell movie clip symbol.

Bring an instance to the Stage, off-stage, board layer, and name it cellseed.

NOTE: The author apologizes for the language: "to the Stage, off-stage". An alternative could be "to the Stage, in the wings" but that may be relying too heavily on the metaphor.

The code in the actions layer, first and only frame [so far] consists of global variables, the definition of the layout function and free-standing code to invoke the layout function.

|var hc = 8; |horizontal count = number of columns |

|var vc = 8; |vertical count = number of rows |

|var nl = 0; |used when duplicating movie instances |

|var firstrow = 100; |position of first row |

|var firstcol = 100; |position of first column |

|var unit = 20; |size of cell |

|var odds = 10/64; |probability of any one cell holding a mine |

The layout function is essentially 2 nested for-loops. The cells are created using the cellseed instance. Flash requires that each created movie clip reside in its own layer, so the nl variable is used to keep track of the instances created. The row and column of the created instance is saved to be used in later steps. The decision to put a mine in a cell is done by invoking Math.random() and comparing the results to odds. Note that the fact that a cell holds a mine is displayed to the programmer/debugger by putting a "B" in the dynamic text field in each cell. This will facilitate testing.

TIP: Displaying the hidden element is a better approach than dropping the random factor and forcing the mines to be in specific places. The statement making the display can be removed or commented out when the program is complete.

|function layout () { |function header |

| for (i=1; i ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download