[Chapter 11] 11.2 Game of Concentration

11.2 Game of Concentration

Up to this point, we have discussed reasonably useful applications. So it is time now to look at some pure entertainment: the game of Concentration (also called Memory). The game consists of an arbitrary number of tiles, where each tile exactly matches one other tile. The value (or picture) "under" each tile is hidden from the user. Figure 11.1 shows what the initial screen looks like.

Figure 11.1: First game screen

[Graphic: Figure 11-1]

When the user selects a tile, the value is displayed. The user can select two tiles at a time. If they match, the values behind the tiles remain displayed. The object of the game is to find all matching tiles in as few looks as possible. Figure 11.2 shows a successful match.

Figure 11.2: Game screen with successful match

[Graphic: Figure 11-2]

The new technique introduced by this example is how to store the entire state of the board in the HTML code sent to the browser. Each click by the user sends the state of the tiles back to the server so that a correct new board can be generated. This is how you access the program for the first time:

http://some.machine/cgi-bin/concentration.pl

This program displays a board, where each tile links back to this program with a query string like this:

http://some.machine/cgi-bin/concentration.pl?
%258%c8%7d0%834%578%4b0%a8c%dac%ce4%bb8%1450%2bc%ea6%960%6a4%708%1%0

The query string actually contains all of the board information (encrypted so that you can't cheat!) as well as the user selections. This is yet another way to store information when multiple sessions are involved, if you don't want to use temporary files and magic cookies. It is not a general solution for all applications, because the length of the query string can be truncated by the browser or the server--see Chapter 4, Forms and CGI. But in this case, the size of the data is small, so it is perfect.

When a certain tile is selected, the program receives a query like the one above. It processes the query, checks to see if the two user selections match, and then creates a new series of query strings for each tile. The process is repeated until the game is finished.

Now for the code:

#!/usr/local/bin/perl
@BOARD = ();

The BOARD array is used to store the board information--the values "under" each tile. A typical array might look like this:

1 4 5 8 7 2 1 6 7 4 6 3 2 8 3 5

In this game, the board contains 16 tiles, each containing a number from 1 to 8. For example, the user has to choose location numbers 2 and 10 to find a match for the value 4.

$display = "";

This variable will hold the needed HTML to produce a board layout. The program creates the layout simply by appending information to this string. If the user's browser does not support graphics, this string is output as is. However, if a graphic browser is being used, the program performs some string substitution and inserts <IMG> tags.

We will look at the graphic aspects in more detail after we run through the logic of the game.

$spaces = " " x 5;
$images_dir = "/icons";

The $spaces variable is used to add extra spaces to the output between each tile. And $images_dir points to the directory where the images (representing the values behind the tiles) are stored.

$query_string = $ENV{'QUERY_STRING'};
if ($query_string) {

If a query string is passed to this program (which happens every time the user clicks on a tile), this block of code is executed.

    ($new_URL_query, $user_selections) = &undecode_query_string (*BOARD);

The undecode_query_string subroutine decodes the query string (and also decrypts it), fills the BOARD array with the board information--based on the information stored in query string--and returns all the information needed by the program to interpret the state of the board. The two strings returned are $new_URL_query, containing the values of the 16 markers, and $user_selections, containing the positions of the tiles that the user selected. This is what $new_URL_query looks like:

%1%4%5%8%7%2%1%6%7%4%6%3%2%8%3%5

in other words, 16 values separated by percent signs. The position of each value represents the position of the tile on the board. The value shown is the actual value under the tile. For example, the second tile contains the value 4.

The format of $user_selections is:

1%0

It contains two values because the user turns up two tiles in succession, trying to find two that match. The 1%0 in this case indicates that the user has clicked on tile number 1 for his or her first selection. The 0 (which doesn't correspond to any position on the board) indicates that only one tile has been turned up. Next time, if the user selects another tile--say tile number 7--the user selection string will look like this:

1%7

From the board data in $new_URL_query above, you can see that tiles number 1 and 7 both contain the value 1, which signifies a match. In this case, the program changes the query string for each tile to reflect a match by adding a "+" sign:

%1+%4%5%8%7%2%1+%6%7%4%6%3%2%8%3%5

These tiles will no longer have links (the user cannot "open" the tile as the value is known), but rather, the values will be displayed.

    &draw_current_board (*BOARD, $new_URL_query, $user_selections);

The draw_current_board routine uses the information stored in the BOARD array, as well as the query information and user selections, to draw an updated board.

} else {
    &create_game (*BOARD);
    $new_URL_query = &build_decoded_query (*BOARD);
    &draw_clear_board ($new_URL_query);
}

If no query string is passed to this program, the create_game subroutine is called to fill the BOARD array with new board information. The values for each tile are randomly selected, so a person can play over and over again as long as boredom does not set in. The build_decoded_query subroutine uses the information in BOARD to create a encrypted query string. Finally, draw_clear_board uses the information to draw the board. Actually, the board is not yet drawn, but rather the HTML needed to draw the board is stored in the $display variable.

&display_board ();
exit(0);

The display_board subroutine checks the user's browser type (either text or graphic), performs the appropriate substitutions, and sends the information to the browser for display.

The create_game subroutine fills up the specified array with a random board layout.

sub create_game
{
    local (*game_board) = @_;
    local ($loop, @number, $random);
    srand (time | $$);

A good seed for the random number generator is set by using the combination of the current time and the process PID.

    for ($loop=1; $loop <= 16; $loop++) {
        $game_board[$loop] = 0;
    }
    for ($loop=1; $loop <= 8; $loop++) {
        $number[$loop] = 0;
    }

The game_board and number arrays are initialized. Remember, $game_board is just a reference to the array that is passed to this subroutine. Throughout the different subroutines in this program, we will use $game_board to store the values behind the 16 tiles. Note that the loop begins at 1, because tiles are numbered from 1 to 16. We never load anything into $game_board[0]. In fact, we use the number 0 in other parts of the program to indicate when the user has not yet selected a tile.

The $number array keeps track of the values that are already placed in the game_board array. This is so that a value appears "behind" only two tiles.

    for ($loop=1; $loop <= 16; $loop++) {
        do {
            $random = int (rand(8)) + 1;
        } until ($number[$random] < 2);
        $game_board[$loop] = $random;
        $number[$random]++;
    }
}

First, a random value from 1 to 8 is selected. If the value is already stored in the $number array twice, another random value is chosen. On the other hand, if the value is valid, it is stored in the $game_board array. This whole process is repeated 16 times, until the board is completely filled.

The build_decoded_query subroutine uses the array we just created to construct a decoded query string.

sub build_decoded_query
{
    local (*game_board) = @_;
    local ($URL_query, $loop, @temp_board);
    for ($loop=1; $loop <= 16; $loop++) {
        ($temp_board[$loop] = $game_board[$loop]) =~
            s/(\w+)/sprintf ("%lx", $1 * (($loop * 50) + 100))/e;
    }

The loop builds up a string of 16 values, one at a time. These values come from the BOARD array, which the calling program passes to this subroutine.

The $temp_board array takes on the value of a successive element of the board array each time through the loop. A series of arithmetic operations are performed on the value, and then it is converted to a hexadecimal number. This is an arbitrary encryption scheme. Just about any encryption technique can be used, as long as you can reverse the process when you get the string back, and so that the user will not be able to see the board information by looking at a query string.

Of course, if you use the exact algorithm I'm showing here, someone who's read this book can play your game and figure out what the values are. Maybe no one would go to such trouble to cheat on a game that three-year-olds play, but you should be sure to make up a different encryption algorithm if you're using this subroutine in a serious CGI application.

Note the e at the end of the regular expression, which instructs Perl to execute the second part of the substitute operator (the sprintf statement). In fact, we have been using this type of construct throughout the book; see all the parse_form_data subroutines.

    $URL_query = join ("%", @temp_board);
    return ($URL_query);
}

The temp_board array is joined to create a string containing the query string. Notice how the loop starts with the index of 1, which means that the query will start with a leading "%". There is no specific reason for doing this; you could omit it if you want.

We'll use this short subroutine later in this section:

sub build
{
    local (@string) = @_;
    $display = join ("", $display, @string);
}

This subroutine concatenates the string(s) passed to it with the $display variable. Note that $display is a global variable.

The draw_clear_board subroutine draws the board when the program is invoked for the first time.

sub draw_clear_board
{
    local ($URL_query) = @_;
    local ($URL, $inner, $outer, $index, $anchor);
    $URL = join ("", $ENV{'SCRIPT_NAME'}, "?", $URL_query);

The input to this subroutine is the BOARD array, the elements of which get joined into a string and placed after a question mark. So the $URL variable contains a string that looks like this:

/cgi-bin/concentration.pl?
%258%c8%7d0%834%578%4b0%a8c%dac%ce4%bb8%1450%2bc%ea6%960%6a4%708

To continue with the subroutine:

    for ($outer=1; $outer <= 4; $outer++) {
        for ($inner=1; $inner <= 4; $inner++) {
            $index = (4 * ($outer - 1)) + $inner;
            $anchor = join("%", "", $index, "0");

The loop iterates 16 times to add information about the tile number for each tile. For example, it will add the string "%1%0" to the query string for tile number 1, "%2%0" for tile 2, and so on. Later, when the board is displayed and the user clicks a tile, the program can look at the string to figure out which tile was clicked.

You might be wondering why we did not just use a for loop to iterate 16 times. The reason is that we want to display four tiles on one line (see the graphic output above or the text output below).

            &build(qq|<A HREF="$URL$anchor">**</A>|, $spaces);
        }
        &build ("\n\n");
    }
}

For text browsers, the string "**" represents each tile. Figure 11.3 shows how the output will appear on a text browser.

Figure 11.3: Text browser output

[Graphic: Figure 11-3]

You've probably been wondering how we're going to untangle the marvelous encrypted garbage that we've stored in the HTML code for each tile. The next subroutine we will look at decodes the query information when a tile is selected.

sub undecode_query_string
{
    local (*game_board) = @_;
    local ($user_choices, $loop, $original_query, $URL_query);
    $ENV{'QUERY_STRING'} =~ /^((%\w+\+{0,1}){16})%(.*)$/;
    ($original_query, $user_choices) = ($1, $3);

The regular expression takes the first 16 strings in the format of %xx (possibly followed by "+" to indicate a match), stores them in $original_query, and places the rest of the query (the user selections) in the variable $user_choices.

The regular expression is shown below. Basically, (%\w+\+{0,1}) matches strings like %258 or %258+ (where the plus sign indicates that the tile has been successfully matched). So the larger expression ((%\w+\+{0,1}){16}) matches the whole 16 tiles. This larger expression becomes $1 because it is enclosed in the first set of parentheses.

[Graphic: Figure from the text]

Notice the second set of parentheses? They're the parentheses in (%\w+\+{0,1}). This becomes $2, but we don't care about that. We used the parentheses simply to group an expression so we could repeat it 16 times.

After the 16 tiles comes a percent sign, which we specify explicitly, and then the (.*) that matches everything else. (We didn't really need the $ to match the end of the line, because .* always matches everything that's left.) The (.*) becomes $3, and we save it as the user selections.

So now, $original_query will contain the encrypted values in the tiles, looking something like this:

%258%c8%7d0%834%578%4b0%a8c%dac%ce4%bb8%1450%2bc%ea6%960%6a4%708

while $user_choices contains the user selections, like this:

1%7

We can now operate on the string of tile values.

    @game_board = split (/%/, $original_query);

The $original_query variable is split on the "%" delimiter to create a 16-element array consisting of the board positions.

    for ($loop=1; $loop <= 16; $loop++) {
        $game_board[$loop] =~ s|(\w+)|hex ($1) / (($loop * 50) + 100)|e;
    }

A regular expression similar to the one used to encode the query string is used to decode it. The hex command translates a number from hexadecimal to a format that can be used in arithmetic calculations.

    $URL_query = join ("%", @game_board);
    return ($URL_query, $user_choices);
}

Finally, the decoded query string and the string consisting of the user choices are returned.

Here is the most complicated part of the program--the draw_current_board subroutine that checks for tiles that match, and then updates the board to reflect this. For each tile, the subroutine has to decide whether to turn it up (display the hidden value) or down (in which case it has a link so the user can click on it and continue the game). When a link is added, it must contain the state of the entire 16 tiles, plus information on which tile if any is currently selected.

sub draw_current_board
{
    local (*game_board, $URL_query, $user_choices) = @_;
    local ($one, $two, $count, $script, $URL, $outer, $inner, $index, $anchor);
    ($one, $two) = split (/%/, $user_choices);

The user choice string (i.e.,"1%2") is split on the "%" delimiter and each choice is stored in a separate variable.

    $count = 0;

The $count variable is initialized to zero. It is used to keep track of the total number of matched tiles on the board. If that is equal to 16, the user has won the game.

    if ( int ($game_board[$one]) == int ($game_board[$two]) ) {
        $game_board[$one] = join ("", $game_board[$one], "+");
        $game_board[$two] = join ("", $game_board[$two], "+");
    }

If the two user choices match the values stored in the board array, a "+" is added to each position in the array. Remember, before the user selects a tile, the query string will look like this (for tile number 1):

http://some.machine/cgi-bin/concentration.pl?
%258%c8%7d0%834%578%4b0%a8c%dac%ce4%bb8%1450%2bc%ea6%960%6a4%708%1%0

And for tile number 2, it will have the following format:

http://some.machine/cgi-bin/concentration.pl?
%258%c8%7d0%834%578%4b0%a8c%dac%ce4%bb8%1450%2bc%ea6%960%6a4%708%2%0

Notice how the next-to-last number indicates the tile number. After the user selects a second tile (say tile number 4), the query string for tile number 1 will look like this:

http://some.machine/cgi-bin/concentration.pl?
%258%c8%7d0%834%578%4b0%a8c%dac%ce4%bb8%1450%2bc%ea6%960%6a4%708%1%4

If the values stored under tiles 1 and 4 match, the program will append a "+" to indicate a match, so that there is no hypertext link created for these tiles.

    $URL_query = &build_decoded_query (*game_board);

A query based on the current board configuration is created by calling the build_decoded_query subroutine, just as we did when the game started.

    $script = $ENV{'SCRIPT_NAME'};
    $URL = join ("", $script, "?", $URL_query);
    for ($outer=1; $outer <= 4; $outer++) {
        for ($inner=1; $inner <= 4; $inner++) {
            $index = (4 * ($outer - 1)) + $inner;

The two loops iterate through the board array four elements at a time.

            if ($game_board[$index] =~ /\+/) {
                $game_board[$index] =~ s/\+//;
                &build (sprintf ("%02d", $game_board[$index]), 
                                           $spaces);
                $count++;

If the value in the board contains a "+", the count is incremented, and the actual value behind the tile is displayed. No hypertext link is attached to the tile, because the user is not supposed to select the tile again.

            } elsif ( ($index == $one) || ($index == $two) ) {
                &build (sprintf ("%02d", $game_board[$index]), 
                                          $spaces);

The value of a tile is displayed if the loop index equals the tile that is selected by the user. Remember, if the two tiles that are selected by the user do not match, they are "closed."

            } else {
                if ($one && $two) {
                    $anchor = join("%", "", $index, "0");
                } else {
                    $anchor = join("%", "", $one, $index);
                }

You have to take a minute to think about when this else clause executes. The current tile has not been turned up because of a successful match (that happened during the if block) nor is it currently selected (that happened during the elsif block). So we know that the tile is turned down, and that we want to attach a hypertext link so that the user can select it.

The only question is what to put in the user selections. If both $one and $two are set, we know that the user selected two tiles and that we are starting over. Therefore, we want to display "1%0" for tile number 1, "2%0" for tile number 2, and so on. That happens in the if block. If one tile has been chosen, we want to record that tile and the current tile. For instance, if the user selects tile 1, we want tile 7 to contain "1%7" as the user selections. This happens in the else block.

                &build(qq|<A HREF="$URL$anchor">**</A>|, $spaces);
            }
        }
        &build ("\n\n");
    }

A hypertext link is generated for all of the other tiles that are turned down.

    if ($count == 16) {
        &build ("<HR>You Win!\nIf you want to play again, ");
        &build (qq|click <A HREF="$script">here</A><BR>|);
    }
}

Finally, if the count is 16, which means that the user has matched all 8 pairs, a victory message is displayed.

The last subroutine we will discuss manipulates the $display variable to show images if a graphic browser is being used.

sub display_board
{
    local ($client_browser, $nongraphic_browsers);
    $client_browser = $ENV{'HTTP_USER_AGENT'};
    $nongraphic_browsers = 'Lynx|CERN-LineMode';
    print "Content-type: text/html", "\n\n";
    if ($client_browser =~ /$nongraphic_browsers/) {
            print "Welcome to the game of Concentration!", "\n";
        } else {
        print qq|<IMG SRC="$images_dir/concentration.gif">|;
        $display =~ s|\*\*</A>|<IMG SRC="$images_dir/question.gif"></A> |g;
        $display =~ s|(\d+)\s|<IMG SRC="$images_dir/$1.gif">   |g;

The string "**" is replaced with the "question.gif" image, and each number found (indicating either a match or a selection) is substituted with an appropriate "gif" image ("01.gif" for the value 01, and so on).

        $display =~ s|\n\n|\n\n\n|g;
        $display =~ s|You Win!|<IMG SRC="$images_dir/win.gif">|g;
    } 
    print "<HR>", "<PRE>", "\n";
    print $display, "\n";
    print "</PRE>", "<HR>", "\n";
}

The variable $display is sent to the browser for output. The <PRE> tags allow the formatting to remain intact. In other words, spaces and newline are preserved.


Animated Clock		Introduction to Imagemaps

CGI Programming on the World Wide Web

11.2 Game of Concentration

Figure 11.1: First game screen

Figure 11.2: Game screen with successful match

Figure 11.3: Text browser output