Best Tetris Data structure to use?

I was going to write a Tetris type game, and I figured I would begin by writing an actual Tetris game (to learn the ropes as it were). Anyway I know I could use arrays to strore the board or pit. But I figured that maybe linked lists would be a good alternative because I could easily remove a line from the list (providing each item in the list was a line on the board), and it would be easy to add new empty lines to the top of the pit/board.
How would I represent a line in each item in the list? I thought of using a binary representation. Is this a good idea. Can anyone help? I'd be grateful
I'd also like to know if there is a way you can directly reference an arbitray item in a list (like in an array), by number. e.g. list(10)., without having to cycle through the list. I thought of using an array of pointers to each item in the list, but I was wondering if there is a less-fudged way of doing it. Thank you very much :)

Rico

I'd probably just use an array of arrays that are references to your blocks.

It'd be a lot easier I reckon.

In my tetris game I had a TShape type and a TBlock type. The board (TBoard) was a regular 2d array, of TBlock.

A TBlock has an x and y, relative to position of the shape, not actual game coordinate. For example, 0, 0 is the central pivot of the shape, 0, 1 is to the right of the shape

Each tetris shape has only 4 blocks, so give a TShape an array of 4 TBlocks. I was first tempted to give each a 4x4 array as this would fit any shape, in order to store the shape, but an array of 4 is simplier, trust me.

A TShape so far has 4 TBlocks, and also needs an x and y for it on the board. This is where the central block is located. So if it's at 5, 6 on the board, then block of coordinate 0, 1 will be at 5, 7.

Your block will also need whether it's active, rotatable etc and other overhead.

What's the point of this 4 block array? It makes rotating VERY simple. Simply create a temperary 4 block array that is rotated, pick up the piece off the board, and try and place the temp array. If it works, set the actual array to the temp array. If it doesn't, replace the original array - it cannot rotate.

I found the rotating algorithm, and some other ideas, from this site:
http://www.codeproject.com/KB/game/tetriscontrol.aspx
which has since been deleted, so here is my code. (I was hoping to show you the idea but I have forgotten, you'll have to gleam it. But it is a very good algorithm)

Method rotate(factor:Int, grid:TGrid)
		'This method rotates the shape by 90 degrees factor times clockwise
		'about its pivot (point 0, 0)
		'For example factor=1 means 90 degree clockwise rotation
		'factor=-1 conterclockwise 90
		
		'Assert (Not game And Not inplay) Or game Else "Error rotate";
		
		'to avoid redundant rotations. yay the complicatedness
		factor = ((factor < 0) * 4 + factor) Mod 4;
		
		'if the piece cannot be rotated (square), or no rotation is requested(!) then return
		If Not rotatable Or factor = 0 Then Return;
		
		'create some new points to store the rotated piece
		Local newPoint:TPoint[] = New TPoint[pointnum];
		For Local i:Int = 0 Until pointnum
			newPoint[i] = New TPoint;
		Next
		
		'store the current points in a temp array
		Local tempPoint:TPoint[] = New TPoint[pointnum];
		For Local i:Int = 0 Until pointnum
			tempPoint[i] = point[i].clone();
		Next
		
		'rotate the piece by swapping X and Y and changing the appropriate sign
		For Local rotationCount:Int = 0 Until factor
			For Local i:Int = 0 Until pointnum
				newPoint[i].alive = tempPoint[i].alive;
				newPoint[i].x = -tempPoint[i].y;
				newPoint[i].y = tempPoint[i].x;
				tempPoint[i] = newPoint[i].clone();
			Next
		Next
		
		If Not inplay
			For Local i:Int = 0 Until pointnum
				point[i] = newPoint[i].clone();
			Next
		Else
			'remove the old piece from the game board
			pluckPiece(grid);
			
			'in case the piece cannot be rotated here, store the old points safely. then give the piece the new rotated points
			Local oldPoint:TPoint[] = New TPoint[pointnum];
			For Local i:Int = 0 Until pointnum
				oldPoint[i] = point[i].clone();
				point[i] = newPoint[i].clone();
			Next
			
			'attempts to place the rorated piece. returns false if cannot be rotated. in that case restore the old points and replace
			If Not placePiece(grid, originX, originY)
				For Local i:Int = 0 Until pointnum
					point[i] = oldPoint[i].clone();
				Next
				placePiece(grid, originX, originy);
			End If
		End If
	End Method

This is all well and good, but how does the piece inform the board where it is, for collision checking?

The TBlocks on the board aren't to hold their own blocks, but will references the TBlocks in the arrays inside TShape in order to know that they are there. When placing a piece, loop through the 4-block array and by using the absolute coordinate of the piece and the relative coordinate of each block, to set the TBlock cell in the board array to reference it. When removing the block, simply dereference the cell in the board. (This way is my own idea).

I think I've given you the general idea. If I've missed any points off or you need something explaining better, please ask.


About your question about using lists, the board is so small that it is acceptable to simply start at the top of the board and move everything downwards.

I'm not going to attempt to give you code here, last time I tried helping someone that way it went horribly wrong :lol: but how about this:

1. set up each individual square cell as an object instead of the whole shape. They're much easier to deal with.

2. do your collision by checking each cell instead of the whole object... its not an abnormal object this should make it easier.

3. get another object type set up where all it does is give itself a unique ID number, and type of brick (IE square, L shape, etc.)

4. when it is time for a new brick to fall, create a new ID type object, and it will then grab 4 cell type objects and arrange them in the correct pattern. Their xy location will be based on the ID type object, so they can be moved as a group with an ID.

They have a unique ID so you can communicate to that group of cells like for turning with ease. You are checking collision for each individual cell instead of the whole object so that is taken care of.

does that make sense?

Wow!, Thank you for all the help (I've been away for a few days - so couldn't reply sooner - sorry!). I just liked the idea of using lists for the board because i thought it would be easier to delete completed lines, but I can see now that this isn't necessary.
I'm still triyng to reach 200 lines on the original gameboy tetris - mono version (I can do 192). Some days though I am completely rubbish. There are some amazing players on YOuTube though, including someone who got over 600 lines!
Thank you again especially Czar and z80 for all your good help!

I'm curious though... do you think what I said will work? I know it didn't quite answer your question, but it sounds to me like a better way to go about it, though I doubt you'll undo everything you did to change it.

I'm not sure what your suggestions mean. Eg:

The best way to do collision checking for these kinds of games is to (without the user seeing of course) pick up the piece, see if it can fit in its new location: if it can, put it there, if it can't, replace it. Then you only need to write a simple place-checking function, other than go around the whole shape checking all cells to all directions.

I was thinking on too basic of a level I guess lol. its easier to see if an object has collided with a square than with a "T" for instance. That's all I was saying.