Terminal-based Tetris - Part 1: Procedural polyomino generation

Page content

Donate

This is the first part of a series of tutorials on creating a terminal-based Tetris clone with Go.

Code for this tutorial is available on GitLab.

go get gitlab.com/tslocum/terminal-tetris-tutorial/part-1 # Download and install
~/go/bin/part-1 # Run

For a complete implementation of a Tetris clone in Go, see netris.

Disclaimer

Tetris is a registered trademark of the Tetris Holding, LLC.

Rocket Nine Labs is in no way affiliated with Tetris Holding, LLC.

Minos

Game pieces are called “minos” because they are polyominos. This tutorial series will focus on the seven one-sided terominos, where each piece has four blocks.

         XX      X      X         X      XX     XX
XXXX     XX     XXX     XXX     XXX     XX       XX

 I       O       T       J       L       S       Z

The number of blocks a mino has is also known as its rank.

Mino data model

Tetris is played on an X-Y grid, so we will store minos as slices of points.

<!          !>   
<!          !>
<! 1,7      !>
<!          !>
<!   3,5    !>
<!          !>
<!          !>
<!     5,2  !>
<!          !>
<!  2,0     !>
<!==========!>
  \/\/\/\/\/

Example coordinate positions in 10x10 playfield

// Point is an X,Y coordinate.
type Point struct {
	X, Y int
}

func (p Point) Rotate90() Point  { return Point{p.Y, -p.X} }
func (p Point) Rotate180() Point { return Point{-p.X, -p.Y} }
func (p Point) Rotate270() Point { return Point{-p.Y, p.X} }
func (p Point) Reflect() Point   { return Point{-p.X, p.Y} }

// Mino is a set of Points.
type Mino []Point

var exampleMino = Mino{{0, 0}, {1, 0}, {2, 0}, {1, 1}} // T piece

Generating minos

Instead of hard-coding each piece into our game, let’s procedurally generate them. This allows us to play with any size of mino.

Sorting and comparing minos

To compare minos efficiently while generating, we will define a String method which sorts a mino’s coordinates before printing them.

This will allow us to identify duplicate minos by comparing their string values.

func (m Mino) Len() int      { return len(m) }
func (m Mino) Swap(i, j int) { m[i], m[j] = m[j], m[i] }
func (m Mino) Less(i, j int) bool {
	return m[i].Y < m[j].Y || (m[i].Y == m[j].Y && m[i].X < m[j].X)
}

func (m Mino) String() string {
	sort.Sort(m)

	var b strings.Builder
	b.Grow(5*len(m) + (len(m) - 1))

	for i := range m {
		if i > 0 {
			b.WriteRune(',')
		}

		b.WriteRune('(')
		b.WriteString(strconv.Itoa(m[i].X))
		b.WriteRune(',')
		b.WriteString(strconv.Itoa(m[i].Y))
		b.WriteRune(')')
	}

	return b.String()
}

// Render returns a visual representation of a Mino.
func (m Mino) Render() string {
	var (
		w, h = m.Size()
		c    = Point{0, h - 1}
		b    strings.Builder
	)
	for y := h - 1; y >= 0; y-- {
		c.X = 0
		c.Y = y

		for x := 0; x < w; x++ {
			if !m.HasPoint(Point{x, y}) {
				continue
			}

			for i := x - c.X; i > 0; i-- {
				b.WriteRune(' ')
			}

			b.WriteRune('X')
			c.X = x + 1
		}

		b.WriteRune('\n')
	}

	return b.String()
}

Origin returns a translated mino located at 0,0 and with positive coordinates only.

A mino with the coordinates (-3, -1), (-2, -1), (-1, -1), (-2, 0) would be translated to (0, 0), (1, 0), (2, 0), (1, 1):

    |                       |
    |                       |X
--X-|-----      ->      ----XXX---  
 XXX|                       |
    |                       |

Translating a mino to (0,0)

// minCoords returns the lowest coordinate of a Mino.
func (m Mino) minCoords() (int, int) {
	minx := m[0].X
	miny := m[0].Y

	for _, p := range m[1:] {
		if p.X < minx {
			minx = p.X
		}
		if p.Y < miny {
			miny = p.Y
		}
	}

	return minx, miny
}

// Origin returns a translated Mino located at 0,0 and with positive coordinates only.
func (m Mino) Origin() Mino {
	minx, miny := m.minCoords()

	newMino := make(Mino, len(m))
	for i, p := range m {
		newMino[i].X = p.X - minx
		newMino[i].Y = p.Y - miny
	}

	return newMino
}

Another transformation is applied not only to help identify duplicate minos, but also to retrieve their initial rotation, as pieces should spawn flat-side down.

XXX              X
  X      ->      XXX

Flattening a mino

Flatten calculates the flattest side of a mino and returns a flattened mino.

// Size returns the dimensions of a Mino.
func (m Mino) Size() (int, int) {
	var x, y int
	for _, p := range m {
		if p.X > x {
			x = p.X
		}
		if p.Y > y {
			y = p.Y
		}
	}

	return x + 1, y + 1
}

// Flatten calculates the flattest side of a Mino and returns a flattened Mino.
func (m Mino) Flatten() Mino {
	var (
		w, h  = m.Size()
		sides [4]int // Left Top Right Bottom
	)
	for i := 0; i < len(m); i++ {
		if m[i].Y == 0 {
			sides[3]++
		} else if m[i].Y == (h - 1) {
			sides[1]++
		}

		if m[i].X == 0 {
			sides[0]++
		} else if m[i].X == (w - 1) {
			sides[2]++
		}
	}

	var (
		largestSide   = 3
		largestLength = sides[3]
	)
	for i, s := range sides[:2] {
		if s > largestLength {
			largestSide = i
			largestLength = s
		}
	}

	var rotateFunc func(Point) Point
	switch largestSide {
	case 0: // Left
		rotateFunc = Point.Rotate270
	case 1: // Top
		rotateFunc = Point.Rotate180
	case 2: // Right
		rotateFunc = Point.Rotate90
	default: // Bottom
		return m
	}

	newMino := make(Mino, len(m))
	for i := 0; i < len(m); i++ {
		newMino[i] = rotateFunc(m[i])
	}

	return newMino
}

Variations returns the three other rotations of a mino.

 X             X                 X
XXX    ->      XX      XXX      XX
               X        X        X

Variations of a mino

// Variations returns the three other rotations of a Mino.
func (m Mino) Variations() []Mino {
	v := make([]Mino, 3)
	for i := 0; i < 3; i++ {
		v[i] = make(Mino, len(m))
	}

	for j := 0; j < len(m); j++ {
		v[0][j] = m[j].Rotate90()
		v[1][j] = m[j].Rotate180()
		v[2][j] = m[j].Rotate270()
	}

	return v
}

Canonical returns a flattened mino translated to 0,0.

// Canonical returns a flattened Mino translated to 0,0.
func (m Mino) Canonical() Mino {
	var (
		ms = m.Origin().String()
		c  = -1
		v  = m.Origin().Variations()
		vs string
	)

	for i := 0; i < 3; i++ {
		vs = v[i].Origin().String()
		if vs < ms {
			c = i
			ms = vs
		}
	}

	if c == -1 {
		return m.Origin().Flatten().Origin()
	}

	return v[c].Origin().Flatten().Origin()
}

Generating additional minos

Starting with a monomino (a mino with a single point: 0,0), we will generate additional minos by adding neighboring points.

                              X                XX   X   X      X   XX  XX
X    ->     XX    ->    XXX  XX    ->    XXXX  XX  XXX  XXX  XXX  XX    XX

Mino generation

Neighborhood returns the Von Neumann neighborhood of a point.

 
//Neighborhood returns the Von Neumann neighborhood of a Point.
func (p Point) Neighborhood() []Point {
	return []Point{
		{p.X - 1, p.Y},
		{p.X, p.Y - 1},
		{p.X + 1, p.Y},
		{p.X, p.Y + 1}}
}

NewPoints calculates the neighborhood of each point of a mino and returns only the new points.

// Neighborhood returns the Von Neumann neighborhood of a Point.
func (m Mino) HasPoint(p Point) bool {
	for _, mp := range m {
		if mp == p {
			return true
		}
	}

	return false
}

// NewPoints calculates the neighborhood of each Point of a Mino and returns only the new Points.
func (m Mino) NewPoints() []Point {
	var newPoints []Point

	for _, p := range m {
		for _, np := range p.Neighborhood() {
			if m.HasPoint(np) {
				continue
			}

			newPoints = append(newPoints, np)
		}
	}

	return newPoints
}

NewMinos returns a new mino for every new neighborhood point of a supplied mino.

// NewMinos returns a new Mino for every new neighborhood Point of a supplied Mino.
func (m Mino) NewMinos() []Mino {
	points := m.NewPoints()

	minos := make([]Mino, len(points))
	for i, p := range points {
		minos[i] = append(m, p).Canonical()
	}

	return minos
}

Generating unique minos

Generate procedurally generates minos of a supplied rank.

We generate minos for the rank below the requested rank and iterate over the variations of each mino, saving and returning all unique variations.

// monomino returns a single-block Mino.
func monomino() Mino {
	return Mino{{0, 0}}
}

// Generate procedurally generates Minos of a supplied rank.
func Generate(rank int) ([]Mino, error) {
	switch {
	case rank < 0:
		return nil, errors.New("invalid rank")
	case rank == 0:
		return []Mino{}, nil
	case rank == 1:
		return []Mino{monomino()}, nil
	default:
		r, err := Generate(rank - 1)
		if err != nil {
			return nil, err
		}

		var (
			minos []Mino
			s     string
			found = make(map[string]bool)
		)
		for _, mino := range r {
			for _, newMino := range mino.NewMinos() {
				s = newMino.Canonical().String()
				if found[s] {
					continue
				}

				minos = append(minos, newMino.Canonical())
				found[s] = true
			}
		}

		return minos, nil
	}
}

Up next: The Matrix

In part two we create a Matrix to hold our Minos and implement SRS rotation.