Tallinna Tehnikaülikool

Infotehnoloogia teaduskond

Arvutitehnika instituut

Digitaaltehnika õppetool

Laboratoorne töö 3

Aruanne aines

Riist- ja tarkvara koosdisain

Töö sooritasid: Vadim Pesonen 020613

Maksim Gorev 020281

Juhendaja: Prof. Kalle Tammemäe

Tallinn 2009

A video game named Sokoban was designed for this laboratory work. Sokoban is translated from Japanese as a “warehouse keeper”. In the original game the warehouse keeper is moving boxes around the warehouse, but the game at hand is derived from KSokoban – a version of Sokoban for the K desktop environment in Linux.

The idea of the game is simple – all diamonds are to be placed on top of the green circles. Some simple rules apply:

  • Diamonds can only pushed and cannot be pulled
  • Only a single diamond can be pushed
  • All object are moved sequentially
  • Walls are solid and nothing can through them
  • In terms of movement, the green circles are equivalent to blank spaces

The target application should look similar to this (the layout may be different):

One can notice that the video consists of a very limited number of images, such as a diamond, a green circle, blank grey space, wall, etc. A screenshot was taken to separate these image, which would then be stored in memory for reference.

Below is the block diagram of the design:

In out implementation, the screen is divided into 10x10 rectangles to form a map with 100 locations. Each location will contain an image. Images are stored in image ROM and are displayed by the VGA engine. In order to select the right image for the right location, the VGA engine turns to the map RAM, where the images are represented by a code in the respective memory cell.

It is the responsibility of the processor to maintain the map and honour keyboard activity.

The hardware part

The VGA engine

The video standard that we employed is VESA 800x600 @ 72Hz. The reason behind the selection was the required horizontal clock frequency – in this case it is exactly 50 MHz, which is supplied by the board and hence need not be corrected. In addition, the 800x600 screen resolution is low enough to simplify implementation and high enough for acceptable image quality. As will be described further, our images are not of as good quality, as a monitor can display in this mode.

The actual displaying takes place only when the imaginary (in case of an LCD screen) cathode ray is in the display section of the screen. A counter that works from a 50MHz clock keeps track of this, and is used as an indicator of when to display and when not to. The display adapter is not aware of the data it is sending out. It is the responsibility of another module (see further below) to provide the VGA module with the correct values at the correct time. The following code illustrates the above said:

//horisontal counter

always @ (posedge clk)//50Mhz

begin

if (h_count == 1039)

h_count <= 0;

else

h_count <= h_count + 1;

end

//

//display

always @ (posedge clk)

begin

if ((h_count >= 0) & (h_count < 800))

begin

blue = {(pixel_data[7:6]),1'b0};

green = (pixel_data[5:3]);

red = (pixel_data[2:0]);

end

else

begin

blue = 3'b000;

green = 3'b000;

red = 3'b000;

end

end

//

The counter clears at value 1040, which is the sum of the display section (800), the horizontal front porch (56), back porch (64) and horizontal synchronization signal (120).

There is a also a vertical counter that recognizes the 600th vertical line. The counter clears at value 666, which includes the vertical resolution, plus the front porch, back porch and vertical synchronization signals – 37, 23 and 6 respectively.

//vertical counter

always @ (negedge hs)

begin

if (v_count == 665)

v_count <= 1'b0;

else

v_count <= v_count + 1;

end

//

The horizontal synchronization signal is clocking the vertical counter, and since the synchronization signals are active low, the vertical counter is sensitive to the negative front.

Calculating pixel addresses

The next section describes how the image ROM is organized and also the module, which generates the address of pixel data that should be displayed next.

The image above illustrates the map with 100 locations. Since the whole screen is 800x600, each location is therefore 80x60 pixels. Each pixel requires (in our case) 1 byte of colour information. To keep image ROM small, the images are not 80x60, but rather 20x15 pixels, and so have to be resized to 80x60 before displaying.

The image ROM is therefore organized in the following way:

  • the address is 13-bits wide
  • the 4 MSBs select an image within ROM, up to 16 images can be addressed
  • the remaining 9 bits select the pixel within an image, 512 pixels in each image can be addressed, but only 300 (20x15) are used. This produced certain gaps “between” the images in the ROM
  • the total ROM size is 16 Kbytes

This module keeps track of where the imaginary cathode ray is at the moment by listening the horizontal and vertical counters from the VGA module.

The VGA engine needs to select the proper pixel data from the image ROM. To do so, one must first select the proper image, i.e. first the map RAM has to be referenced for the image code, and only then one can read the image ROM.

Because the position of the “cathode ray” changes independently of everything else and it does not wait, the correct pixel address has to be calculated in advance, so that the data would be fetched in time. Let us not forget, that image has to be resized as well.

All this is implemented in the following way:

The pixel address is comprised of the address in map and the relative address (pixel address) within the image.

assign addr = {map_data_reg,rel_addr};

The map address is registered, because it does not change for whole 80 horizontal pixels. The following code explains how the value is calculated:

always @ (h_count,v_count)

begin

if (v_count < 60)

begin

case (h_count)

77:map_addr = 1;

157:map_addr = 2;

237:map_addr = 3;

317:map_addr = 4;

397:map_addr = 5;

477:map_addr = 6;

557:map_addr = 7;

637:map_addr = 8;

717:map_addr = 9;

797:map_addr = 10;

default:map_addr = 0;

endcase

end

else if (v_count < 120)

…

…

This is the calculation for the first row of images – images 0 to 9, and the next image, i.e. image 10 (the address has to calculated in advance, as explained above). As one can see, the v_count value is compared with the location’s vertical size, but h_count is reduced by 3 pixels. The 3 clock cycle delay is required to first fetch the image code from map RAM and then to fetch the correct pixel data from image ROM.

As soon as h_count reaches the listed values, map_addr is registered.

always @ (posedge clk)

begin

if ((h_count == 77) || (h_count == 157) || …

map_data_reg <= map_data;

end

//

As mentioned above, one must also keep track of the position within every image. In addition, images have to be resized from 20x15 to 80x60, that is by a factor of 4. Two counters are used to do all that – h_pos and v_pos. One way to resize the image is to repeat the pixel address several times, in this case 4 times – both horizontally and vertically. This can be done by delaying the h_pos and v_pos counters’ clock signals:

always @ (h_count)

begin

if ((h_count[1:0] == 2'b01) &(h_count >= 0) & (h_count < 800))

h_pos_clk = 1'b1;

else

h_pos_clk = 1'b0;

end

//

This generated clock signal only works in the visible horizontal range (from 0 to 800), and only once in 4 main clock cycles, as denoted by the (h_count[1:0] == 2'b01) condition.

The clock for the v_pos is organized in a similar way, except for that the v_counter clock is the negative front of the horizontal synchronization signal (negedge hs).

Now, knowing the position within an image, the relative address can be easily calculated:

//relative address calculation

always @ (v_pos,h_pos)

begin

case (v_pos)

0:rel_addr = 0+ h_pos;

1:rel_addr = 20+ h_pos;

2:rel_addr = 40+ h_pos;

3:rel_addr = 60+ h_pos;

4:rel_addr = 80+ h_pos;

5:rel_addr = 100+ h_pos;

6:rel_addr = 120+ h_pos;

7:rel_addr = 140+ h_pos;

8:rel_addr = 160+ h_pos;

9:rel_addr = 180+ h_pos;

10:rel_addr = 200+ h_pos;

11: rel_addr = 220+ h_pos;

12:rel_addr = 240+ h_pos;

13:rel_addr = 260+ h_pos;

14:rel_addr = 280+ h_pos;

default:

rel_addr = 0;

endcase

end

//

The next section briefly describes the design on the block level.

The inputs of our design are the primary 50MHz clock, the keyboard clock and keyboard data signals. The outputs are the 3x3 colours, the horizontal and vertical synchronization signals.

The top-level module combines the VGA engine module, the pixel address calculation module, the processor, the program ROM, map RAM and image ROM.

On-chip block ram is exclusively used for all memories. In order to achieve a 1-cycle access time, the memories are clocked with an inverted (compared to the rest of the hardware) clock signal. The whole system runs at 50MHz.

The software part

Software development task

We have decided to make one of the famous game named SOKOBAN. The task of this game is to put all the rubins on to special places marked by green circles.The rules are following:

  • The man can only push rubins.
  • Rubin can not be moved if there is another rubin or wall before it.
  • The man cannot go through rubin or wall
  • The man can stand on the green circe.
  • The rubin can stand on the green circle.

To implement the game the playground was presented as a square 10x10 blocks wich can be represented as 7 different pictures:

  1. The Man
  2. The wall
  3. The rubin
  4. The green circle
  5. The Man on green circle
  6. The Rubin on green circle.
  7. The Background(the floor).

The matrix is implemented in block Ram and pictures are encoded with 7 binary numbers. Software part presents keyboard controller and game management: picture codes „movements“ in block ram, element positions storage and management, as well as game constraints implementation.

Hardware part is to read picture code from blockRam and generate images on the screen.

Keyboard controller

In order to play the game – the keyboard is used. There are 6 buttons wich can be used during this game. Their functions are the following:

  • left arrow – move man left
  • right arrow – move man right
  • up arrow – move man up
  • down arrow – move man down
  • backspace – undo the last step
  • Escape – restart the game



Keyboard is using two lines to send data. These are DATA line and CLOCK line. It doesn't require initialization, so it is only needed to read from DATA line on appropriate CLOCK signal. The clock signal was connected to PicoBlaze'i interrupt input with invertor. So that every time the clock line contains „0“ value, interrupt is generated. It gives software a possibility to read every bit of the button code bitstream and decode the message from the keyboard.

Keyboard button code is represented by 8 bit binary value. In case of extended keys the value of the code is 16 bit and the highest 8 bit contains extended button code E0. When key pressed keyboard sends one time the code of the button. In case of extended button it sends code with E0 before button code. When key is depressed the keyboard sends button code again, but this time it puts code F0 before the button code. So if extended key was depressed the 24 bit bitstream will be sent from the keyborad: F0 E0 XX(button code) .

The keys used in game have the following codes:

  • UP - E0 75
  • DOWN – E0 72
  • LEFT – E0 6B
  • RIGHT – E0 74
  • ESC – 76
  • BACKSPACE – 66

The workflow of keyboard controller is shown on the Figure 1. Bits are read sequentially until byte is read. Program understands it from the bitcounter value. Byte value is decoded and depend on the value of this byte the E0 or F0 status are set or cleared in the status register, the specific button function is called or the code is rejected and other bits of the message are rejected as well.

In other words, the program read the first byte of the message.

  • If it is E0 it sets the corresponding flag and reads the second byte. If E0 and second byte represent the code wich is neede byte the game, procidure to inform the game of this code is started.
  • If the first byte is not E0, but the code of Esc or Backspace, the inform procedure is started as well.
  • If the first byte is F0, then second byte is rejected, and if the second byte was E0, then the third byte of the message is read by the program, but is rejected.
  • If none of above then message is rejected.

The procedure wich informs game of the key pressed simply writes the specific code from 0 to 5 into register, where game reads from during main loop.

The game

The main algorithm of the game is displayed on figure 2.

At the very beginning of the game the program copy map from upper block RAM (addresses 100 – 199) to lower blockRam(addresses 0 to 99). This is needed to give a possibility to a program to reset the map in the future and doesn't store it somewhere else.

When map is copied man position and circle positiona are searched through the map and saved inside the processor. Man coordinate saved into specific register and circle coordinates are saved into internal RAM of PicoBlaze processor. Circle coordinates are needed for program to detect the „end of game“ condition, when all rubins are on circles. After that program goes to main loop where it reades keyboard code register until it is not zero.

When interrupt occurs and keyboard controller writes a code into coderegister and exits ISR , the main program reads the code and writes zero into keyboard register instead. If this code was direction code it calculates sequantially 3 coordinates next to man coordinate, depending on the direction. Program reads current picture codes on this coordinates from external memory. After that it stores all of them in internal memory. This is done to provide the ability to undo last step of the game later.When this is done them man is „moved“ or not, dependidng what is located in the coordinates next to the man. When movements are done, all circle coordinates are read from the internal memory and after that external memory checked for “rubin on circle“ block on this coordinates to detect the „end of game condition“. If condition is not detected program goes to the main loop. If condition is detected – all circle coordinates have block type „rubin on cirle“ the program flashes rubins on circles 3 times and restarts the game, jumping to the very beginning.

Figure 2. Game algorithm

When esc code is detected the program jumps to the very beginning of the code and starts from scratch rewriting game map from upper blockRam addresses.

To write the program pBlazIDE36 software were used to enter code, test and compile a code into VHDL instruction ROM.

Conclusions

The work turned out to be quite challenging in terms of realization. Many decisions have had to be make, which include, but are not limited to:

  • Deciding on the hardware/software partition
  • Storing images in ROM – sizes, formats, etc.
  • Making the game map easily modifiable
  • Designing the game logic
  • Getting further acquainted with the PicoBlaze processor and its debugging techniques
  • Designing a custom video adapter

The achieved result proves that the system was designed correctly and its performance is very stable. The hardware/software partition also proved to be very successful and convenient for this design.