Nu har jag uppnått ett första delmål nämligen att få programmet att spela Tetris och uppföra sig på samma sätt som C++ versionen, dock än så länge utan grafiskt gränssnitt. När jag testar köra C++ versionen på min nya bärbara dator med Intel i7-processor lägger den 23.000 bitar per sekund medan Scala-versionen endast gör 2.000 bitar per sekund, alltså mindre än 10% av C++ versionens hastighet. Den ursprungliga Java-versionen (som skrevs före C++ versionen, alltså ej den halvfärdiga Java-version som finns med i detta projekt) kom upp till 20% av C++ versionen. Scala-versionen är dessutom endast hälften så snabb som Java-versionen trots att den kör på en tio år nyare 64-bitars JVM! Detta är lite av en besvikelse, men jag utgår ifrån att det finns utrymme för optimering.
Under Pieces/sec ser man att C++ versionen kör med en hastighet av 23.803 bitar per sekund (varierar lite under körning). Jag beklagar att jag inte kan släppa en körbar version då den innehåller en grafisk komponent som inte får distribueras fritt:
För att hantera att datorn kan spela själv har jag skapat klassen Game. Då jag ville säkerställa att Scala-versionen uppför sig exakt som C++ versionen skrev jag ett test som verifierar detta,
GameTest:
package net.sf.tetrisai.game
import org.junit.Test
import net.sf.tetrisai.settings.DefaultGameSettings
import net.sf.tetrisai.board.Board
import net.sf.tetrisai.boardevaluator.JoakimTengstrandBoardEvaluator
import net.sf.tetrisai.BaseTest
import net.sf.tetrisai.piece._
import collection.mutable.Buffer
import net.sf.tetrisai.piecegenerator.PredictablePieceGenerator
class GameTest extends BaseTest {
@Test def playFivePieces() {
val board = Board(10,15)
val boardEvaluator = new JoakimTengstrandBoardEvaluator(board.width, board.height)
val pieceGenerator = new PredictablePieceGenerator(List(new PieceO, new PieceL, new PieceI, new PieceZ, new PieceT))
val settings = new DefaultGameSettings
val game = new Game(board, boardEvaluator, pieceGenerator, settings)
game.play(5)
game.linesCleared should be (1)
board should be (Board(Buffer(
"#----------#",
"#----------#",
"#----------#",
"#----------#",
"#----------#",
"#----------#",
"#----------#",
"#----------#",
"#----------#",
"#----------#",
"#----------#",
"#----------#",
"#---------Z#",
"#--------ZZ#",
"#OO---TTTZL#",
"############")))
}
}
Den spelar fem bitar, för varje bit använder den sig av samma algoritm som i C++ för att hitta bästa alternativ att placera biten (jag kommer gå igenom algoritmen i detalj vid nästa blogginlägg). Därefter testas att korrekt antal rader rensats och att slutpositionen är den förväntade. Implementation av
Game:
package net.sf.tetrisai.game
import net.sf.tetrisai.settings.GameSettings
import net.sf.tetrisai.board.Board
import net.sf.tetrisai.boardevaluator.BoardEvaluator
import net.sf.tetrisai.piecegenerator.PieceGenerator
import net.sf.tetrisai.move.EvaluatedMoves
class Game(board: Board, boardEvaluator: BoardEvaluator, pieceGenerator: PieceGenerator, settings: GameSettings) {
var position = new Position(board, pieceGenerator.nextPiece, settings)
var linesCleared = 0
def play(maxMoves: Long) {
var moves: Long = 0
var evaluatedMoves = new EvaluatedMoves(position, board, boardEvaluator)
while (moves < maxMoves && !evaluatedMoves.isEmpty) {
val bestMove = evaluatedMoves reduceLeft { _ min _ }
position.movePiece(bestMove)
linesCleared += position.setPiece().linesCleared
moves += 1
position = new Position(board, pieceGenerator.nextPiece, settings)
evaluatedMoves = new EvaluatedMoves(position, board, boardEvaluator)
}
}
}
Det jag tror och hoppas är att jag hittat en tydlig uppdelning av ansvar för de klasser som är inblandade i att spela Tetris. Här följer en beskrivning av de klasser som används av Game, med respektive test angivet först:
För att hitta rätt värderingar av de olika alternativen att lägga en bit, behöver jag jämföra med C++ versionen:
EvaluatedMovesTest:
package net.sf.tetrisai.move
import org.junit.Test
import net.sf.tetrisai.BaseTest
import net.sf.tetrisai.boardevaluator.JoakimTengstrandBoardEvaluator
import net.sf.tetrisai.settings.DefaultGameSettings
import net.sf.tetrisai.game.Position
import net.sf.tetrisai.board.Board
import net.sf.tetrisai.piece.{PieceS}
class EvaluatedMovesTest extends BaseTest {
@Test def evaluatedMoves {
val board = Board()
val position = new Position(board, new PieceS, new DefaultGameSettings)
val boardEvaluator = new JoakimTengstrandBoardEvaluator(board.width, board.height)
val evaluatedMoves = new EvaluatedMoves(position, board, boardEvaluator)
val moves = for {
move <- evaluatedMoves.moves.sortBy{m => (m.equity)}
} yield roundThreeDecimals(move)
moves should be (List(
new MoveEquity(0,7, 18, 0.000),
new MoveEquity(1,0, 17, 0.660),
new MoveEquity(0,0, 18, 2.291),
new MoveEquity(0,5, 18, 3.040),
new MoveEquity(1,8, 17, 3.437),
new MoveEquity(0,2, 18, 3.468),
new MoveEquity(0,3, 18, 3.546),
new MoveEquity(0,1, 18, 3.854),
new MoveEquity(0,4, 18, 3.955),
new MoveEquity(0,6, 18, 4.727),
new MoveEquity(1,2, 17, 6.931),
new MoveEquity(1,6, 17, 7.017),
new MoveEquity(1,4, 17, 7.144),
new MoveEquity(1,5, 17, 7.902),
new MoveEquity(1,7, 17, 8.127),
new MoveEquity(1,3, 17, 8.925),
new MoveEquity(1,1, 17, 10.717)))
}
private def roundThreeDecimals(move: MoveEquity) = {
val equity = scala.math.round((move.equity - 12.43) * 1000) / 1000.0
new MoveEquity(move.rotation, move.x, move.y, equity)
}
}
EvaluatedMoves:
package net.sf.tetrisai.move
import net.sf.tetrisai.boardevaluator.BoardEvaluator
import net.sf.tetrisai.board.Board
import net.sf.tetrisai.game.Position
class EvaluatedMoves(position: Position, board: Board, boardEvaluator: BoardEvaluator) extends Traversable[MoveEquity] {
val moves: List[MoveEquity] = evaluateValidMoves
def foreach[U](f: MoveEquity => U) = {
val iterator = moves.iterator
while (iterator.hasNext) f(iterator.next)
}
/**
* Evaluates the equity of all valid moves for a given position.
*/
private def evaluateValidMoves: List[MoveEquity] = {
for {
move <- position.validMoves
} yield new MoveEquity(move.rotation,move.x, move.y, evaluate(move))
}
private def evaluate(move: Move) = {
position.movePiece(move)
val clearedLines = position.setPiece
val equity = boardEvaluator.evaluate(board)
position.undoSetPiece(clearedLines)
equity
}
}
En bra egenskap med denna klass är att den helt döljer den interna listan
moves och i stället erbjuder användaren av klassen möjlighet att stega elementen i listan genom att mixa in traitet Traversable och implementera metoden
foreach. Klassen
Game får då bl.a automatiskt tillgång till metoderna
isEmpty (rad 17) och
reduceLeft (rad 18) i
Game.
Metoderna
setPiece och
undoSetPiece (tidigare
clearPiece) har fått hantering av vilka rader som tagits bort. Detta för att kunna återställa positionen när man går igenom alla möjliga alternativ att lägga en bit,
PositionTest:
...
@Test def setPieceAndClearLine {
val board = Board(Buffer(
"#-----#",
"#-----#",
"#----x#",
"#x-xxx#",
"#######"))
val piece: Piece = new PieceT
val position = new Position(board, piece, settings)
position.movePiece(Move(0,0,2))
val clearedLines = position.setPiece()
clearedLines.linesCleared should be (1)
board should be (Board(Buffer(
"#-----#",
"#-----#",
"#-----#",
"#TTT-x#",
"#######")))
}
@Test def undoSetPieceRestoreClearedLine {
val board = Board(Buffer(
"#-----#",
"#-----#",
"#-----#",
"#TTT-O#",
"#######"))
val piece: Piece = new PieceT
val position = new Position(board, piece, settings)
position.movePiece(Move(0,0,2))
val clearedLines = new ClearedLines(List(new ClearedLine(3, BoardLine("#LTSSZ#"))))
position.undoSetPiece(clearedLines)
board should be (Board(Buffer(
"#-----#",
"#-----#",
"#----O#",
"#L-SSZ#",
"#######")))
}
Position:
package net.sf.tetrisai.game
import net.sf.tetrisai.board.Board
import net.sf.tetrisai.settings.GameSettings
import net.sf.tetrisai.piece.Piece
import net.sf.tetrisai.move.{ValidMoves, Move}
/**
* Responsible for moving and rotating current piece plus
* setting and clearing that piece on the board.
*/
class Position(board: Board, val piece: Piece, settings: GameSettings) {
val boardWidth = board.width
val boardHeight = board.height
var pieceMove = settings.pieceStartMove(board.width, piece)
private val rotationDirection = settings.rotationDirection
def setPiece(): ClearedLines = {
piece.shape(pieceMove.rotation).dots.foreach(dot => board.set(dot + pieceMove, piece.number))
board.clearLines(pieceMove.y, piece.height(pieceMove.rotation))
}
def undoSetPiece(clearedLines: ClearedLines) = {
board.undoClearedLines(clearedLines)
piece.shape(pieceMove.rotation).dots.foreach(dot => board.clear(dot + pieceMove))
}
def rotatePiece() = pieceMove = pieceMove.rotate(rotationDirection, piece.rotationModulus)
def movePiece(move: Move) = pieceMove = move
def validMoves = new ValidMoves(this).moves
def isValidMove: Boolean = isValidMove(pieceMove)
def isValidMove(move: Move): Boolean = {
try {
(piece.shape(move.rotation).dots.foldLeft(0) { (sum,dot) => sum + board.get(dot + move) }) == 0
} catch {
case e: IndexOutOfBoundsException => false
}
}
}
Metoden
clearLines i Board har jag skrivit om tidigare och kommer därför bara att nämna en detalj kring hanteringen att lägga till rader till ClearedLines,
Board:
package net.sf.tetrisai.board
import net.sf.tetrisai.Point
import scala.collection.mutable.Buffer
import net.sf.tetrisai.game.{ClearedLine, ClearedLines}
object Board {
def apply(width: Int = 10, height: Int = 20) = {
val boardLines = Buffer.fill(height) { BoardLine.emptyLine(width) }
new Board(width, height, boardLines)
}
def apply(lines: Buffer[String]) = {
val width = lines(0).length - 2
val height = lines.length - 1
require(lines(height) == bottomTextLine(width))
val boardLines = Buffer.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(
val width: Int,
val height: Int,
private val lines: Buffer[BoardLine]) {
require(height >= 4)
def get(dot: Point) = lines(dot.y).get(dot.x)
def set(dot: Point, number: Byte) = lines(dot.y).set(dot.x, number)
def clear(dot: Point) = lines(dot.y).clear(dot.x)
def emptyLine = BoardLine.emptyLine(width)
def completedLine = BoardLine.completedLine(width)
def bottomTextLine = Board.bottomTextLine(width)
def countDots = lines.foldLeft(0) { (sum,line) => sum + line.countDots }
def isFree(x: Int, y: Int) = {
try {
lines(y).get(x) == 0
} catch {
case e: IndexOutOfBoundsException => false
}
}
def undoClearedLines(clearedLines: ClearedLines): Board = {
clearedLines.lines.reverse.foreach(insertLine(_))
this
}
private def insertLine(clearedLine: ClearedLine) {
lines.remove(0)
lines.insert(clearedLine.y, clearedLine.boardLine)
}
/**
* Clears completed lines and returns which lines that was cleared.
* This method should be called after a piece has been dropped on the board.
* pieceY: the y position of the piece.
* pieceHeight: height of the piece.
*/
def clearLines(pieceY: Int, pieceHeight: Int): ClearedLines = {
var clearedLines = ClearedLines()
var y1 = pieceY + pieceHeight;
// Find first line to clear
do {
y1 -= 1
if (lines(y1).isComplete)
clearedLines += (y1, lines(y1).copy)
} while (clearedLines.linesCleared == 0 && y1 > pieceY)
// Clear lines
if (clearedLines.linesCleared > 0) {
var y2 = y1;
while (y1 >= 0) {
y2 -= 1
while (y2 >= pieceY && lines(y2).isComplete) {
clearedLines += (y2, lines(y2).copy)
y2 -= 1
}
if (y2 >= 0)
lines(y1) = lines(y2)
else
lines(y1) = emptyLine
y1 -= 1;
}
}
clearedLines;
}
override def equals(that: Any) = that match {
case other: Board => lines.toList == other.lines.toList
case _ => false
}
override def toString = lines.map { _.toString }.mkString("\n") + "\n" + bottomTextLine
}
Rad
78 och
88 lägger till en rad till listan
clearedLines. Det finns två fiffiga saker med hur detta är gjort. Det första är att jag använt mig av något som heter Tuples. Det är en konstruktion i Scala där man kan paketera ihop två eller fler värden genom att omringa dem med en parantes. Det andra är att jag implementerat operatorn + (plus) i
ClearedLines genom att just ta en Tupel som inargument:
package net.sf.tetrisai.game
import net.sf.tetrisai.board.BoardLine
object ClearedLines {
def apply() = new ClearedLines(List[ClearedLine]())
}
case class ClearedLine(val y: Int, val boardLine: BoardLine)
class ClearedLines(val lines: List[ClearedLine]) {
def +(y: Int, boardLine: BoardLine) = new ClearedLines(new ClearedLine(y, boardLine) :: lines)
val linesCleared = lines.size
override def equals(that: Any) = that match {
case other: ClearedLines => lines == other.lines
case _ => false
}
override def toString = lines.toString
}
Klassen innehåller en inner case klass
ClearedLine. Att jag valt att göra den som en case klass beror på att jag vill dra nytta av att case klasser automatiskt genererar bl.a metoden
equals som jag behöver då jag jämför instanser av
ClearedLine med varandra.
Det finns en sak till som kan vara värt att nämna. Scala (och Java) har ingen hantering av unsignade heltal. Slumptalsgeneratorn i C++ versionen använder sig just av detta, Random.h:
#ifndef __random__
#define __random__
class Random
{
private:
unsigned int seed;
public:
Random();
Random(unsigned int seed);
~Random();
void setSeed(int seed) { this->seed = seed; }
unsigned int getRandom();
int getRandomP();
};
#endif
Random.cpp:
#include "Random.h"
Random::Random()
{
this->seed = 0;
}
Random::Random(unsigned int seed)
{
this->seed = seed;
}
Random::~Random()
{
}
unsigned int Random::getRandom()
{
seed *= (unsigned int)(1664525);
seed += (unsigned int)(1013904223);
return seed;
}
int Random::getRandomP()
{
unsigned int seed = getRandom();
return seed % 7 + 1;
}
För att emulera detta beteende har jag i Scala behövt utföra operationerna med datatypen
Long och sedan maska av de 32 minst signifikanta bitarna:
package net.sf.tetrisai.piecegenerator
object DefaultPieceGenerator {
val BitMask = 0x00000000FFFFFFFFL
}
class DefaultPieceGenerator(var seed: Long = 0) extends PieceGenerator {
def nextPieceNumber = {
seed = (seed * 1664525) & DefaultPieceGenerator.BitMask
seed = (seed + 1013904223) & DefaultPieceGenerator.BitMask
modulus7 + 1
}
private def modulus7 = {
val div: Long = seed / 7;
(seed - div * 7).toInt
}
}
Scala (och Java) kan inte utföra modulus (%) operatorn på datatypen Long, utan vill ha en Integer. Jag skulle ha velat skriva
(seed.toInt % 7) + 1 på rad
13 men detta ger inte samma resultat som metoden
modulus7.
Det var allt denna gång!
