Naive gravity algorithm

I've come up with an algorithm for naive gravity. Attached is an implementation of it in Lua, tested with the 5.1 and 5.2 command-line interpreters. I've put it into the public domain, so use it however you like. I've not encountered the algorithm yet, so it might be a new creation.

 

Wow that's a very clever way of doing it. Good job. I might end up using this in mine, I forget how I do it in the latest version.

 

Actually, I think the way mine works is it only checks modified (where the piece landed) lines then cuts the line out if it's cleared. So at most you have 4 loop cycles and all you need to do is remove an array element. I think I'm going to use an object for the stack soon, so I'll have to change the way I do it. I want to make a Tetris plus style game mode.

 

Nice algorithm but doesn't seem any different to anything everybody else would have programmed (not sure if this is a mega super efficient implementation or something?)

It seems reasonably efficient - only one copy of the playfield and only copies each line a maximum of once.

It could be further optimised if copyRow does nothing if rowSrc == rowDst. This is only true if lines == 0.

So you could change collapse copyRow to:

local function copyRow(playfield, rowSrc, rowDst)
....if rowSrc == rowDst then
........return
....end
....for x=1,10 do
........playfield[rowDst][x] = playfield[rowSrc][x]
....end
end

Alternatively, you could change Collapse lines:

local function collapseLines(playfield)
....local lines = 0
....for row=1,20 do
........if isLine(playfield, row) then
............lines = lines + 1
........if (lines != 0) then
............copyRow(playfield, row, row - lines)
........end
....end
....makeTopRowsEmpty(playfield, lines)

....return lines
end


It could also be optimized by only checking lines where the piece has landed and above.

 

Didn't check out the code, but I'm sort of confused how it makes sense to have an algorithm for naive gravity? Essentially what it means, from a programmer's point of view, is that there's no gravity at all.
In my Tetris implementation, the ONLY thing I do when a piece locks is copy the blocks in the current piece to the stack's grid data, and then spawn the next piece - once a piece is in the grid, there's nothing even remotely simulating gravity left.

 

AFAIK, naive gravity is often coded by copying all rows above a line down one row, then going up until another line is encountered and copying all rows down again, etc. I intentionally didn't apply the optimizations you suggested so the algorithm's structure would be easier to understand. And really, the only major advantage my algorithm has is it's easier to implement correctly; the slight efficiency gain is nice, but not significant on today's systems.

Possibly the most efficient method is, for stack blocks, to use a one-dimensional array in a C-like language with direct memory access, and using memcpy to copy multiple rows down at once.

 

As some of the memory will overlap during the copy, it is considered bad to use memcpy(), you should use memmove()

 

Aha! I never even thought of that as a "gravity" effect. I literally just see ever line above the cleared lines being copied X lines down. Unless you're doing this on insanely limited hardware, there's absolutely no reason to worry about how to optimize that stuff. If you want to optimize, focus on the stuff that's happening every single frame, or multiple times every frame.

 

I just broke it up into 2 steps, because I wanted to play an animation before removing the lines:

void CheckWellLines()
{
m_WellLines.clear();
for (int y = 0; y < GAMESIZE_Y; ++y)
{
int set = 0;
for (int x = 0; x < GAMESIZE_X; ++x)
{
if (GetWell(x,y))
{
set++;
}
}
if (set == GAMESIZE_X)
{
m_WellLines.push_back(y);
}
}
}

void ClearWellLines()
{
if( m_WellLines.size() == 0)
{
return;
}

int abovecleared = GAMESIZE_Y - 1;
for (int y = GAMESIZE_Y - 1; y >= 0 ; --y)
{
while(m_WellLines.size() > 0 && abovecleared == m_WellLines.back())
{
abovecleared--;
m_WellLines.pop_back();
}
if (abovecleared != y)
{
for (int x = 0; x < GAMESIZE_X; ++x)
{
SetWell( x, y,
(abovecleared > 0) ? GetWell(x, abovecleared) : false );
}
}
abovecleared--;
}
m_WellLines.clear();
}
It's C++, just ask if something is unclear.

So you have the index of the lines which are going to be cleared in m_WellLines and call ClearWellLines() only after the line clear delay.