/TETRIS

Project of CSE3013 Computer Science and Engineering Laboratory/ 2018.05 / Sogang Univ.

Primary LanguageC

TETRIS

TERM

2018.05.06 ~ 2018.06.03

1. PLAY TETRIS

  • Block falls every seconds.

  • Rotate or Move block following input direction.

  • Get score according to the area the bottom of the falling block touch.

  • When the row of field fill, delete this row and get score.

2. RANKING SYSTEM

  • Build data structure by reading rank.txt file.

  • Sort data in nondecreasing order.

  • Print ranking of selected range.

  • Delete the ranking data according to input.

  • Print one's scores in nondecreasing order.

  • Before Finishing the program, store data structure in rank.txt file.

3. RECOMMENDED PLAY

  • Recommend position by using tree.

  • Automatic play mode that chooses position it expects to lead to the highest score.

IMPLEMENTATION

IDEA FOR RANKING SYSTEM

DATA STRUCTURE

"search" is defined constant.

Wine circle sign indicates the node that is stored in "Head"->link.

Unlike arrays, Linked-list has disadvantage of not being able to refer to intermediate node.

By using above data structure, I tried to solving this advantage.

ALGORITHM

  • Insertion / Deletion:

    • Find the approximate position by looking over "Head->link" list.

    • Start from one of "Head->link" list, find the exact position.

    • After insertion or deletion , adjust "Head->link" list.

  • Print ranking of selected range(x,y):

    • Find the approximate x position by looking over "Head->link" list.

    • Start from one of "Head->link" list, find the exact x position.

    • From x position, print node information as following the linked-list until arriving at y.

IDEA FOR AUTOMATIC PLAY

DATA STRUCTURE

lv: depth of node in tree.

max_h: maximum height of the blocks.

num array: store the number of blocks for each height.

h array: store the number of blocks for each col.

Example

Without storing entire field, I can expect how the block stacks up by looking over "h" array and whether or not any row can be full by looking over "num" array.

I tried to come up with node structure that uses memory efficiently.

ALGORITHM

  • Do deeper predictions only about the next situation that is judged to result in a high score.

  • In this process, I did not build tree. Instead, by recursive function call, I anticipate the dipper prediction.

  • I accept the potential if...

    • delete one or more lines

    • make blank less than or equal to that of the status of max score.

    • generate score that is higher than the previous max score

    • generate score that is equal to max score but create smaller number of blank spaces or lower max_h.