Implementera clearLines()

C++ versionen TetrisAnalyzer var ganska hårt prestandaoptimerad. Då jag är mån om att även Scala-versionen ska ha bra prestanda kommer jag att behålla en del av dessa prestandaoptimeringar. Vissa av optimeringarna kommer jag att avvakta med och införa vid ett senare tillfälle. Metoden clearLines i klassen Board såg i C++ versionen ut så här:

int Board::clearLines(int ymin, int pieceHeight)
{
 int y1;
 int y2;
 int clearedLines = 0;

 y1 = ymin + pieceHeight;

 while (--y1 >= ymin)
 {
  if (countLine(y1) == width)
  {
   clearedLines++;
   break;
  }
 }
   
 if (clearedLines == 0)
  return 0;   // No rows to clear

 y2 = y1;

 while (y1 >= 0)
 {
  while (--y2 >= ymin)
   if (countLine(y2) == width)
    clearedLines++;
   else
    break;
    
  if (y2 >= 0)
   copyLine(y2, y1);
  else
   clearLine(y1);

  y1--;
 }
 
 return clearedLines;
}

void Board::copyLine(int from_y, int to_y)
{
 char *board1 = board + from_y * width;
 char *board2 = board + to_y * width;

 for (int x=0; x<width; x++)
  board2[x] = board1[x];
}

void Board::clearLine(int y)
{
 char *line = board + y*width;
 
 for (int x=0; x<width; x++)
  line[x] = 0;
}

int Board::countLine(int y)
{
 int cnt = 0;
 char *line = board + y*width;
 
 for (int x=0; x<width; x++)
  if (line[x] != 0)
   cnt++;
   
 return cnt;
}

En sak man kan notera är att jag för tio år sedan valde att deklarera variabler i början av metoder (rad 3-5) och inte vid dess första användning! En annan detalj är att då vi infört klassen BoardLine slipper vi hantering av enskilda rader i klassen Board (metoderna copyLine, clearLine och countLine).

Metoden clearLines är något lång och lätt kryptisk men har fördelen att den har bra prestanda. Väljer därför kopiera den i stort sett rakt av, så här ser nu våran Board ut:

package net.sf.tetrisai

object Board {
  def apply(lines: Array[String]) = {
    val width = lines(0).length - 2
    val height = lines.length - 1

    require(lines(height) == bottomTextLine(width))

    val boardLines: Array[BoardLine] = Array.tabulate(height) (
      ((y) => (BoardLine(lines(y))))
    )
    new Board(width, height, boardLines)
  }

  def bottomTextLine(width: Int) = "#" * (width + 2)
}

/**
 * Represents the game board.
 * Standard size is 10x20 (width x height).
 */
class Board(width: Int, height: Int, lines: Array[BoardLine]) {
  require(height >= 4)

  def emptyLine() = BoardLine.emptyLine(width)
  def bottomTextLine() = Board.bottomTextLine(width)
  def asText() = lines.map { _.asText }.mkString("\n") + "\n" + bottomTextLine

  /**
   * Clears completed lines and returns number of cleared lines.
   * This method should be called after a piece has been dropped on the board.
   *   minY: the y position of the piece.
   *   height: height of the piece.
   */
  def clearLines(minY: Int, height: Int): Int = {
    var clearedLines = 0;
    var y1 = minY + height;

    do {
      y1 -= 1
      if (lines(y1).isComplete)
        clearedLines += 1
    } while (clearedLines == 0 && y1 > minY)

    if (clearedLines > 0) {
      var y2 = y1;

      while (y1 >= 0) {
        y2 -= 1
        while (y2 >= minY && lines(y2).isComplete) {
          clearedLines += 1
          y2 -= 1
        }
        if (y2 >= 0)
          lines(y1) = lines(y2)
        else
          lines(y1) = emptyLine

        y1 -= 1;
      }
    }
    clearedLines;
  }
}

Här har metoderna emptyLine och clearLines tillkommit. I C++ versionen används break på rad 14 och 29. Scala har inte stöd för break och jag blev då tvungen att skriva om koden lite som på köpet blev något mer läsbar.

I objektet BoardLine har metoden emptyLine tillkommit som använder sig av metoden fill som fyller en array med i detta fallet värdet 0:

def emptyLine(width: Int) = new BoardLine(Array.fill(width){ 0 })

I klassen BoardLine har metoden isComplete tillkommit:

def isComplete() = line.sum == line.length

Testet ser ut så här:

@Test def clearLines() {
    val board = Board(Array(
      "#----------#",
      "#----x-----#",
      "#xxxxxxxxxx#",
      "#xxxxxxxxxx#",
      "#-x--x----x#",
      "#xxxxxxxxxx#",
      "############"))

    board.clearLines(2, 4) should be (3)

    board.asText should be (Array(
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#----x-----#",
      "#-x--x----x#",
      "############").mkString("\n"))
  }

Jag ville egentligen implementera metoden equals på klassen Board för att slippa köra asText och mkString men hade problem att komma åt attributet lines på inkommande argument i equals och väljer därför denna lösning tills vidare.