66% or better

Tetris code theory explained

[Graham] designed this PIC based Tetris game on a single board. The hardware is quite nice but we enjoyed his explanation of the graphics algorithm that he used. Having coded Tetris from the ground up ourselves we understand how difficult it is to explain how the program works. Tracking pieces already on the board as well as moving pieces, making sure that rotation won’t cause a collision with another piece or go out-of-bounds, and looking for completed lines all add up to one bid headache.

[Graham's] method for handling rotation involves choosing a point around which to rotate, measuring how this affects each pixel in the piece, and then checking those pixels for overlaps. It may take a couple of readings, but he’s done a brilliant job of making it understandable. There’s a demo after the break and the link at the top takes you to his treatise on Tetris.

Comments

  1. Johannes says:

    Pretty cool. Got those matrix boards laying around too, nifty idea!

  2. LifeSizeActionFigure says:

    I get a bid headache from eBay.

  3. cantido says:

    >Tracking pieces already on the board

    If you only have 1bit graphics that pretty simple isn’t it?.. Your graphics and your game state are the same thing. When you detect a collision with already settled blocks you get OR the falling blocks bits into your existing state..

    >making sure that rotation

    I wonder why he’s bother to rotate (graphically) pieces in code when it would easier just to have the pieces rotated in the program data… He says he’s used one method over the other for speed..

    >won’t cause a collision with another piece

    again, that isn’t hard.. somewhere in your struct for your pieces you have something that says how big it is, before you move a piece left/right or swap the piece out for a rotation you check that tetro_width + offset_x or go out-of-bounds, and looking for completed >lines all add up to one bid headache.

    so you have 16 entry long uint8 array.. you do some like this to check for complete lines.

    bool completelinedetector(){
    for (i = 0; i < 16; i++){
    if(checkarray[i] == 0xFF){
    return true;
    }
    }
    return false;
    }

    if you count the complete lines you can write a routine to animate out the completed lines too..

    "collision" detection is a case of comparing your incoming byte (a byte the represents the bottom of the current tetro shifted to it's current offset) with byte below the current y offset of the tetro in the check array… learning how shifts, boolean logic work in your language of choice is a must.

    I do like hackaday.. but you guys really over hype stuff sometimes.

  4. cantido says:

    Excuse the typos etc. :P

  5. Comrade says:

    @cantido
    Yes, someone codes differently than you and people think that’s neat therefore: HaD must “over hype things up.”
    /sarcasm

    The guy did it his own way, what are you complaining about? At least he bothered to do something, to reach out and learn; after all isn’t that what hacking is about? To learn, share, and grow…

  6. anonn says:

    @cantido.

    I thought it was a pretty cool breakdown and gave me a breif incite in another method of implementing tetris. even if you have the holy grail of tetris implementation.

  7. cantido says:

    @Comrade

    >The guy did it his own way,..

    I didn’t say the guy was doing it “wrong”. Read this line from the hack a day text;

    >>ourselves we understand how difficult
    >>it is to explain how the program works.

    No, it isn’t. If you’ve got more than a few bytes of memory to play with you don’t even need to do bit shifting… You can be very lazy and use your smallest native unit for each pixel! You have an 2 dimension array that has your game state and an array + x/y bounds descriptors for the pieces, the idea is to OR the pieces on to the game state array. You can do bounds checking by checking that the left edge of the piece isn’t out of the screen and left edge + piece width + current offset isn’t bigger than the screen when the user tries to move it left or right. Each time the piece moves down you compare the bottom of the piece array with what is “below” it in the state array, then you check the next line up,.. If there is a collision at any point the piece stops falling (I think the official rules include some grace time in which the player can adjust the piece). before the piece rotates you have to check the rotation will fit in the current state.. which is a just case of iterating over the state and piece arrays.
    When the piece has stopped falling you OR it into the state array. Then you check for complete lines.. which is (again!) just a case of iterating over the state array to find lines that are complete.

    There you go, I’ve just explained this terribly complex piece of computer science for you. Use it wisely.

    The data structures and logic are all very simple. Which is why there are lots and lots of tetris-like games out there on everything from desktop computers to hacked printer firmwares.

  8. BikeHelmet says:

    cantido:

    I agree. HackaDay’s summary makes Tetris sound impressive – but it really isn’t. I commend the guy for his efforts, but I have to be honest here – we’ve all done tetris!

    I think it was about a decade ago that I threw together Javascript Tetris. It took me close to 6 hours to create from scratch (much of that just learning the javascript) – this is with no former programming experience…

    Tetris isn’t that hard if you can think even slightly analytically…

    But then again, maybe my perspective is biased? Since then I’ve found everything including mario clones, 2D rendering engines, compiler frontends, and java servers to be challenging yet doable. I assumed HackaDay would be filled with more analytical engineer types than creative artists, but maybe I’m wrong? There are a lot of very creative hacks and gadgets posted to this site – many requiring extensive technical expertise – but that says nothing about the editors.

    So maybe his rotation algorithm really isn’t obvious to HaD’s editors? Maybe it is really impressive to them? :/

  9. anonn says:

    wall of text aside.

    I liked this.

  10. cantido says:

    @Comrade

    oh and here is how you do rotation,.. notice that you don’t actually need to do any complex maths;

    your struct looks something like this;

    0×00: length
    0×01: height
    0×02: piece data .. 0×00 for nothing, 0xff for a
    . block or something like that.
    . If you can manage shifts etc you can use
    . bits for this *wowza!*, if you are using
    . tilemaps i.e have more than 1 bit graphics
    . you would have a tile number here and check
    . for anything that isn’t 0×00 in your
    . checking routines.

    0×08: pointer to next rotation (length depends on how big your pointers are) The last rotation points back to the original form.

    When the piece is rotated you don’t need to do any rotation in ram.. you can find what you need using the pointer and because the last piece loops back to first you don’t need any logic to wrap around.

    You can use a table of pointers to the pieces and use a “random” offset to piece the starting piece + rotation (I think the official rules state that all pieces start at the initial form though.. so you would only put those into your table). On a micro you are likely to have lots of flash rom and very little data memory so use static data over generating stuff in ram where ever you can.

    Please feel free to use this highly sensitive data under the terms of the GPL documentation license.

  11. George Johnson says:

    Pretty nice bit of project. See? Things don’tt have to be sloppy.

  12. Roboguy says:

    The whole project emerged from neccessity for a good example in “how to manipulate LEDs and draw 2D graphics,” to help others learn.

    His solution may not have been the most elegant ever, and it’s certainly general in nature. But that was the point – to provide a relatively easy to understand method for 2D rotation that works on a wide scale.

    He did it well. It’s good that it was put on HaD, to maybe pique the interest of those new to embedded programming and/or 2D graphics.

    So, in summary: Criticizing the programming technique in an example for novices? Really?

  13. Roboguy says:

    As to the referenced article, I think it’s commendable to try to help those out who need it.

    I remember when I did Tetris (brand new to the language, to 2D graphics, and to programming in general). It was a great learning experience, but pretty tough. I think it’s great to walk people through the process and make it easier on them.

  14. M4CGYV3R says:

    I can’t thank and respect this dude enough for not using a frickin’ arduino. Neat project. I need to get some displays so I can try graphics on PIC.

  15. cantido says:

    @Roboguy

    So, in summary, if you actually read what people write.. you would notice that I didn’t criticise his code all that much. I criticised hack a day for saying this is “hard to describe”. Which it isn’t. It’s very simple.

    If I was going to criticise anything it might be the fact that he’s used a massive micro when he really didn’t need to. But that’s probably just using what’s at hand..

  16. donovan says:

    I’ve programmed tetris as well and I do not agree: it’s the most simple thing to write except maybe for snake!

  17. Graham says:

    HaD: Thanks a lot for posting the project, it made my day! Thanks too for the feedback guys.

    The intention of the project was to explore 2D graphic algorithms in aid for someone else (and for my own code tool-kit).

    For me, and plenty of other people out there – 2D graphics on a microcontroller is a pretty big leap forward.

    Understandably there are always going to be alternative approaches, some of which Cantido has politely suggested.

    @Cantido
    >I wonder why he’s bother to rotate (graphically) pieces in code when it would easier just to have the pieces rotated in the program data…

    At all stages of the project, an important feature for me was scalability. A number of different methods were trialled, and compared for performance. Rotating the objects with the 2D affine matrix method allows fast, scalable rotations (compared to many other techniques).

    The approach could easily be used in other retro games and much larger screens. There are a few ways to optimise the algorithm to suit larger screen areas (like GLCDs etc). More on that another time perhaps.

    You would be surprised as to how little information I could find online regarding PIC Microcontrollers and Tetris (let alone 2D graphics). Google appears to have taken my article straight to the top 3 for a few searches: “pic micro tetris”, “pic micro 2d graphics”.

    Perhaps the project is popular though usually finds itself the too ‘hard basket’ when working with the limitations of a microcontroller?

    In any case, I hope there are several handy code snippets and techniques that other readers can use.

  18. osgeld says:

    “I can’t thank and respect this dude enough for not using a frickin’ arduino. Neat project. I need to get some displays so I can try graphics on PIC.”

    be nice if you did anything cept flap that mouth of yours

  19. mihailiv says:

    Where do you get these matrix LED blocks? How are they called?

  20. osgeld says:

    search for 8×8 led matrix, I got some like those from ebay but they pop up at different suppliers also

  21. morgan says:

    bah, this is exactly what I was working on =( he got there first I guess :P

  22. mihailiv says:

    osgeld: I LOVE YOU

  23. You get the matrix displays from sure-electronics.

    They are $7.99 for 10 of them.

    If I may add, what is simple to one person certainly may not be simple to another. That is what is so great about the microcontroller community in that people are willing to post their code and tutorials as to how they achieved their end goal.

    I have been programming microcontrollers for a little under 3 years and like everyone I had to start from the ground up, It’s tutorials like Grahams that has got me to where I am today.

    So bring on the simple tutorials!

  24. richard says:

    @cantido

    Stop being a fucking elitist douchebag.

    The guy who made this game did something amazing – something that I certainly don’t have the knowledge to do.

    Who are you trying to prove anything to? To the internet? That you know more than someone else does?

    Get over yourself.

  25. max reiter says:

    Hi, is it possible to post the .hex file for this
    wonderful game? I’d like to build this with my
    pupils in school.
    Or is there a link somewhere with the hex?

    maxi

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s