Introduction

This is one of my midterm project design in EE113 Digital Integrated Circuit Design, 2048 Game Simulator Design Using Multisim

本文为EE113数字集成电路期中课程设计的报告。使用Multisim设计一个2048类似规则的游戏机。

The game rule is not strictly identical to original 2048 game in github.

2048 Game Simulator Design Using Multisim

Lyu Wentao ShanghaiTech University

2048 is a single-player sliding block puzzle game on mobile phones. With its simple and direct control design, 2048 became one of the most famous games. In this article, we will try to design a full-featured 2048 game simulator with a circuit using Multisim.

Introduction: Game Rule and Logical Design

In this section, we will review the basic game rule of 2048 and discuss the logical design of this game simulator.

Game Rule

The basic rule of 2048 game is simple. The playground is a 4x4 grid, every cell in which can be blank or filled with a number in {2, 4, 8, …, 2048}. There are four choices for users: Up, Down, Left and Right, just the four direction arrows in a keyboard. Every time the user push one of the four arrows, all cell will be the move towards the chosen direction, full the blank cell if possible, and merge into the sum if the neighborhood is the same number. Some new numbers might appear randomly in some blank cells and the main task is to produce the largest number 2048 .

Here is a sample of 2048 game rule:

image alt text

Logical Design

Based on the basic rule of 2048, we can easily understand the main task of the global game. Let’s do some reduction to divide the main task into three levels: global, column/row and cell level. The task of each level can be represented as the linear combination of the lower level tasks. In the following sub-sections, we will discuss the relationships between levels logically, and the detail of the circuit will be described in the Result and Conclusion section.

Here are some examples of three levels:

image alt text

Cell Level. Definition: Given a CURRECT cell and its four neighborhoods, as well as a command indicating the direction to move, move cells towards the center one and output two result, OUTPUT: new status of the center cell, OUTPUT2: new status of the next cell.

From the given input information, we can put them into a cross grid, and the center cell is the most important part we should care about. If the command is up direction, the neighbor cell under then center will be the next cell. The new status will only be related to these two cells. If the center cell is 0 (means here is a blank cell), then the OUTPUT should be equal to next cell, and OUTPUT2 should be 0; if the center cell is equal to the next cell, then OUTPUT should be center cell * 2 and OUTPUT2 should be 0; if the center cell is different from the next cell, the OUTPUT and OUTPUT2 remains equal to center cell and next cell.

We should notice which the next cell depends on which the direction command is. In short, the next cell is the neighbor cell with the reverse direction.

image alt text

Column/Row Level. Definition: Given a 1x4 or 4x1 matrix, and a command indicating the direction to move, move all cells by one step and output the result.

Take move up for example, in this case, the first cell on the top is the easiest one to transform into Cell Level process: transform this cell and its neighborhoods simply. After that, the following cells might be a little more complicated. For the second cell, we can’t input the original neighborhoods like the first one because the first process has already changed the first and second cells. Thus, we should connect the OUTPUT from the previous process into UP, and OUTPUT2 from the previous process into CURRENT, other inputs remain the original neighborhoods.

We should notice that above logic is correct only for up move command. We should process the different order and the input interface which connect to OUTPUT2 for different move direction. On the other hand, we didn’t know some neighborhoods information because in this level we only get the statuses of one column/row, but that’s ok to transform 0 into this unknown cell because they won’t be used and we can just ignore them.

image alt text

Global Level. Definition: Given a 4x4 matrix, and a command indicating the direction to move, move all cells by one step and output the result.

Take move up for example, in this case, each column is independent of others, and can be processed separately. So this level can be transformed into four different Column/Row Level processes. Each of them calculates one line (column or row, depends on the direction indicator command).
image alt text

Final Target. Definition: Given a 4x4 matrix, and a command indicating the direction to move, output the result.

In the most situation, this target can be simply transformed into one Global Level. But there exists one exception when more than 2 neighborhoods have the same number. Here is an example of this case.

image alt text

In this situation, each time using Global Level, all the cells move to the right one step. Because of there are four 2s in the second row, the *Global Level *should be processed four times.

Results

In this section, we will review the results and the full circuit design. Due to the Multisim cannot support too much circuit to be simulated, out circuit is unfinished yet. However, the most important parts of this project have already been finished, as well as their unit test circuit.

Overview

image alt text

Above sketch map shows all the high-level design of the whole project. All parts marked green are finished, and the red parts are not. In addition, to make sure all levels circuit is correct, two unit test circuits are also designed, one for cell level and another for Column/Row Level.

Interface

image alt text

Here is the circuit of the interface, we use 16 DCD_HEX_BLUE to display all the game UI. To make the circuit simply, one 4-bit number {1, 2, 3, …, 11} is used to represent the original {2, 4, 8, … , 2048}. All display bus is connected to the global level(CORE_PROCESSOR). Considering that there is no such click-button-like component, we use interactive and registers (BUTTON_CTL) to simulate the click button. Here is the circuit of BUTTON_CTL:

image alt text

In this circuit, the register can an OR gate make the OUTPUT be high only when INPUT changes. This approach will produce a high signal until the next CLK raise edge, lasted less than 1 click circle.

(Here is an unfinished part, this BUTTON_CTL circuit design should be changed but haven’t, we will discuss this in the Discussion section.)

Global Level

This circuit is global level. We use 16 REG_FILE_4x4 to keep the data saving in the flip flop. All the outputs of the registers are connected to display in INTERFACE. The input CMD is a 4-bit signal which expresses the 4 directions (UP: 0, RIGHT: 1, DOWN: 2, LEFT: 3). And the CMD_CVT is used to convert the CMD into 2 bit CONVERTED_CMD.

Considering that the 4 directions can be divided into 2 group which take action vertically or horizontally, we put two groups of Column/Row Level, one group is used to calculate 4 rows. And another for 4 columns. All output put is selected by MUX according to CMD (only bit 0, because of the mirror of 2 directions). After that, we should check if the new state should be written to registers. If all 4 bits of CMD are 0, registers shouldn’t be written anything, definitely.

(All Blue part is not finished yet)

image alt text

image alt text

CMD_CVT

Column/Row Level

image alt text

This circuit is TRANS_H, one of the two Column/Row Level circuits. In this circuit, what we care is only row operations. There are two possible operations in a row: RIGHT and LEFT, so two groups of CELL LEVEL(CU) are used. The top four CU are for RIGHT operation, and we can see the outputs of the right CU is connected to the inputs of its left CU.

In order to select these two conditions using single-MUX, we design a new MUX which can select 2x4x4 bit. The circuit is shown below:

image alt text

The CMD of this TRANS_H will only be 1(RIGHT) or 3(LEFT), so CMD bit 1 is used to select the MUX.

Cell Level

Cell level is the final part of this project. It is used to calculate the state update. The CMD might be one of the four possible directions so 4 TO sub-circuits is used. After that, we use the MUX to select these four outputs according to CMD.

image alt text

TO sub-circuit is a black-box to calculate with center cell and next cell. It is CMD independent so its design is universal. In TO block, there are some small circuit called EqualZero, Equal, Plus, which is used to check if the center cell is zero, if the center cell is equal to next cell and plus one to the center cell. Another small sub-circuit is OUTPUT and OUTPUT2, which can connect the output according to check results.

image alt text

TO

image alt text

EqualZero

image alt text

Equal

image alt text

Plus

image alt text

OUTPUT

image alt text

OUTPUT2

Cell Level Unit Test

In order to make sure that cell level circuit works correctly as what we expected, a unit test circuit is used. Here are some test simulation states:

image alt text

Hex LED display shown in green area are current cell and its neighborhoods. Direction command is in the blue area, (0, 1, 2, 3 representing up, right, down and left). Output is connected in the yellow area, the OUTPUT is the left one, and the OUTPUT2 is the second one.

image alt text

Move down with center cell is blank (next cell move to the center)

image alt text

Move down with center cell is equal to the next cell (next cell will be merged into center cell)

image alt text

Move down with center cell is not equal to the next cell (all cells keep unchanged)

Column/Row Level Unit Test

Similarly, there is another unit test circuit design for Column/Row Level circuit to check if the circuit work correctly as what we expected. Here are some test simulation states:

image alt text

Green area shows the input of one column. The order from the left is from the top to bottom. Direction command is in the blue area, (0, 1, 2, 3 representing up, right, down and left). Output is connected in the yellow area, with the same order as the green one.

image alt text

Move down with [3 7 6 0] (all number will be move down one step)

image alt text

Move down with [7 7 6 4] (the two 7 should be merged)

image alt text

Move down with [7 6 6 4] (two 6 are merged, but the 7 shouldn’t, because that this will move only one step)

Discussion, Perspective and Conclusion

In this section, we will discuss the whole project, the challenges and the solutions, the shortcomings and the possible future work to improve it.

Advanced Approach of BUTTON_CTL

As we expected, up to now, our circuit can run at least in one column or row with one step. It’s simple to popularize these circuit into 4x4 matrix grids by calculating parallel. However, there is a hidden issue that if we just simply connect all TRANS_V and TRANS_H in Global Level, only one step will be processed, which is unacceptable. One possible advanced approach is to change the logic in BUTTON_CTL. The BUTTON_CTL will produce one high signal during at most one clock cycle, but if we connect 3 register end to end, the high signal will last at least 3 clock circle. So actually, we force to process the move for 3 times, which is enough in the 4x4 grid.

But there comes another challenge. What if I change the button too quickly to change the state twice? The BUTTON_CTL might produce a signal with high lasted less than 3 clock cycles, which is definitely wrong. Besides, two different operations might be processed in the same time, that is also unacceptable.

But perhaps there can be another solution. Let’s change the clock cycle of all BUTTON_CTL into 3 times. This problem can be solved. No move confliction can be produced.

Another Perspective to Change the Cell Level Design

After this project design, I think deeply into the level design. I noticed that there must be two cells that won’t be used in Cell Level design, which usually means a useless design. Actually, it is.

Another better Cell Level design can only input the center cell and its previous and next cells, the Cell Level circuit will handle two different cases rather four. Because that if we can make sure all cells are in one line in the Column/Row Level, it is useless to take care of other never existed cells. What’s more, this change of Cell Level design will also change the Column/Row Level design, TRANS_V and TRANS_H might be able to merge into one universal TRANS block, because there is no difference between rows and columns.

Other Possible Future Work

  • Add random reset circuit, using a random number circuit to get a new game experience.

  • Add new cell number after every move operation.

Add restriction of the register (up to 11: 2^11=2048)

Conclusion

In this article, we designed the basic 2048 game simulator logic and make sure that it will work at least under the row/column level. But unfortunately, Multisim cannot support these large circuits and work very slow (To open the file cost 18 minutes, run the simulator cost 10 minutes, and add another TRANS_V cost more than 2 hours to process in my i7 computer).

However, the unfinished area is not so important, there are some basic connection between Column/Row Level blocks and registers. All of our main logical processor circuit are designed and work correctly as expected. This fact proves that out logical design and circuit design are both acceptable. Perhaps once we get a better computer or simulation platform, this 2048 game simulator can be finally produced.

I will continue to focus on any possible way to finish and improve this circuit design.