Best Tetris Data structure to use?

BlitzMax Forums/BlitzMax Beginners Area/Best Tetris Data structure to use?

Rico(Posted 2008) [#1]
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


Perturbatio(Posted 2008) [#2]
I'd probably just use an array of arrays that are references to your blocks.

It'd be a lot easier I reckon.


Czar Flavius(Posted 2008) [#3]
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)



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.


z80jim(Posted 2008) [#4]
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?


Rico(Posted 2008) [#5]
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!


z80jim(Posted 2008) [#6]
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.


Czar Flavius(Posted 2008) [#7]
I'm not sure what your suggestions mean. Eg:

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


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.


z80jim(Posted 2008) [#8]
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.