BASeTris, my Tetris Clone which has been genericized such that I was even able to add a “Dr.Mario” Game mode, has now been around for nearly 5 years.

I originally created it because I wanted to create a sort of “Tetris all-stars” concept, where all the various implementations I was familiar with- Game boy, NES, DS, SNES, etc. could effectively mingle together their visuals and sounds.

Last night for some reason I was dwelling on the idea of “Pentris”- that is, it’s Tetris, but instead of 4 blocks, there are 5. In BASeTris, the Tetris tetrominoes are separate class instances that define the block positions appropriately. And while I could do that for Pentris, I got the idea that realistically it should be entirely feasible to simply have the game generate every possible unique combination, given the number of blocks. Stemming from that, it should, therefore, be possible to not only have Pentris, but even, say, “Duodectris” and have the game handle everything from there.

The algorithm I ended up constructing works in two sections. First, it creates every single possible combination, and then it filters out duplicates.

The construction of all the possibilities effectively works by starting with a Duomino at 0,0 and 1,0. From there, using 1,0 as the “head” it effectively calls itself recursively to add blocks going Right, left, and Forward from that point, with the end-case of course being when the constructed Nomino has the number of needed blocks. The implementation for that was thus:

Note: NominoPoint is basically just “yet-another-point class” but doesn’t have much special capability)

This, of course, still did not yield (pun intended…) the correct set of Nominoes; this would yield each possible rotation as a separate Nomino, for example, and in fact it was quite possible for a different “path” to yield an identical nomino. For that reason, it is necessary to filter the pieces. So how, exactly, do we devise a way to remove duplicates? Well, if we “rebase” the coordinates so that they align in the same way, regardless of their generated position, we can create arrangements that match, if we can come up with a safe, unique “hash” for each, of course. We can then also rotate the nominoes 90 degrees, 180, and 270 degrees, and be able to detect if “rotated” versions of the candidate nomino are already in the resultset.

Which leads to the question of what to use for a “unique” value. At first, I tried to create a Hash for the set of points, by using the bijective algorithm on all the points sorted by x and y coordinate. This resulted in hash collisions, however, so some Nominoes that should have been present were not.

For debugging, I added some helper functions to create a string representation using Hash Marks. It occurred to me that that string representation would be perfectly sufficient for a unique hash. the same arrangement of blocks that were created a different way would still give that same text, and a string could be safely used as a HashSet key.

With this in hand, the FilterPieces function could now uh, filter pieces. The general idea is simple: we maintain a HashSet of all the previously returned pieces, and as we go through each piece, we basically check if it matches one in the HashSet. if it doesn’t, we will add the string representation of itself and the three rotations of that piece to the HashSet and yield it via the enumeration. Otherwise, it is filtered out as already having been returned.

With this in hand, I could see how many of these combinations specific block counts provided. Pentominoes, or Pentris, with 5 blocks, yields 12 possibilities. with 6 blocks, there were 32; 7 had 81, 8 had 219, and so on. With 13 blocks, that’s 29,663 possible … Tridecominoes (?).

Now, for actual gameplay, the idea is that with more blocks in each, you would, of course, have a larger playfield. Thankfully, the TetrisField class that implements the GameField of BASeTris has supported this more or less since the beginning, and simply defaults to the standard size.

One aspect which occurred to me that while some aspects of the Game do require knowing all possible Nominoes, It really isn’t necessary for all parts of GamePlay. For the “Choosers”, they need to know all Nominoes since they are responsible for how they randomize, but, one could make contingencies for an imagined “N-block” “Xtris” implementation.

The first thing to address is to allow for non-deterministic generation of the Nominoes. That is actually surprisingly easy- with the recursive algorithm it is effectively a matter of randomizing the order that the directions are chosen. It was at this time I refactored the routine and made it shorter, too:

Instead of the three almost identical blocks for each direction, they are now handled in a loop, and the order of that loop is determined via the ArrayOrder array; furthermore, if the Randomization is set, then the order of the array is randomized. This relatively straightforward change means effectively that while it will still go through every possibility, it will do so in an indeterministic order if the flag is passed.

By using an iterator method, this also allows for a rather interesting usage which simply wants one random piece:

For implementation, there are still issues. I quickly hacked the game such that the routine generating the next Nomino simply called the above. Results were a bit mixed.

Unfortunately, there are some architectural issues with this specific change. There’s good and bad indicators, here though. In particular, many things internally use the specific “Type” of the Nomino as a key into some dictionary or other cache; for example, the Images that are used for the Next Queue are actually indexed by the theme and the Nomino Type. Since all the “Pentominoes” here are actually just a Nomino, they share the same type, so all the Pentominoes share the image of the first one generated. The count of nominoes is of course not going to be useful here, since I didn’t change it. it is working properly in the sense that none of those Tetrominoes are used, though. Other than the presence of the Type being used as a Key for some aspects of the underlying handling, it actually handles the Pentominoes reasonably well; For example while it is just the one image, it did draw the Pentomino correctly, and it is handling them correctly within the game field, with some exceptions. A standard Tetris Field has 2 “hidden rows” which are basically used for generating the Tetrominoes off screen. All tetrominoes fit there. Pentominoes, however, do not; so what happens is some generated Pentominoes are generated and placed “off-screen” but they are now too high up and some blocks are actually outside the actual game field, including hidden rows. The game doesn’t handle this well. if the top row is outside, then it won’t let you move side to side until it falls one block. And it’s worse if a generated Nomino is two blocks above, because as soon as it falls one block, the game will detect that it cannot down (because the game considers the block that will still be outside the valid area invalid) and thus decides to “set” the block in place; and of course it’s at the very top which sets off the Game Over detection. Of course, the number of Hidden Rows is not hard-coded in my implementation, and nominoes could arguably be more intelligently spawned only as high as possible, instead of forcing them to be above the visible area.

In any case, My next task appears to be refactoring BASeTris such that the parts that use Nomino Class Types for HashSets and Dictionaries and such to instead use the string representation, which should address the “Next Queue” issue; From there I need to device a proper way for these extended “NTris” implementations to show for example the Nomino counts. My first thought is that the list of Nominoes would simply expand with each new unique one that is generated, and when there are too many to fit vertically it tries to create some sort of grid arrangement, with the Nomino image underneath and the count on top or something to that effect.

It’s a bit funny that I felt like doing this, and meanwhile the “Tetris 2” implementation is still largely unfinished and untested!