Building a Sliding Puzzle with Go

Building a game is an excellent way of starting programming. Tons of people have started programming because they wanted to create computer games. Even me, back in 2010, had one of my first projects to write a small game when I was still in my Technician course.

In this course, we used Python to develop a slide puzzle. It was very challenging because I had to learn about the game mechanics and GUI, but I could handle the project. When I started to work with Ruby, I also built one to compare with what I did with Python.

I decided to build a sliding puzzle with Go. The first step was building the core, the main parts of the game. Therefore, I created a struct called Play, which has the table and positions x and y for the nil value. The table could be represented with an array, but I think the quadratic matrix represents it better. Also, to represent the nil value, I chose the 0.

var DEFAULT_TABLE = [3][3]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 0}}

type Play struct {
    Table    [3][3]int
    EmptyRow int
    EmptyCol int
}

After that, we will create a new play with a random table. To randomize it, we go through each cell and change it for another one by random. That guarantees us that we will have a minimum randness at our table.

func NewPlay() *Play {
    t, x, y := generateRandomTable()
    return &Play{
        Table:    t,
        EmptyRow: x,
        EmptyCol: y,
    }
}

func generateRandomTable() ([3][3]int, int, int) {
    t := DEFAULT_TABLE
    s := 3
    xEmpty := 0
    yEmpty := 0

    for i, r := range t {
        for j := range r {
            x := rand.Intn(s)
            y := rand.Intn(s)
            t[i][j], t[x][y] = t[x][y], t[i][j]

            if t[i][j] == 0 {
                xEmpty = i
                yEmpty = j
            }

            if t[x][y] == 0 {
                xEmpty = x
                yEmpty = y
            }
        }
    }

    return t, xEmpty, yEmpty
}

Next, we can implement the moves for up, down, left, and right. Here, we will always move the nil value. If we can't move it, we will return an error.

func (p *Play) Up() error {
    if p.EmptyRow == 0 {
        return fmt.Errorf("can't move up")
    }

    p.Table[p.EmptyRow][p.EmptyCol], p.Table[p.EmptyRow-1][p.EmptyCol] = p.Table[p.EmptyRow-1][p.EmptyCol], p.Table[p.EmptyRow][p.EmptyCol]
    p.EmptyRow = p.EmptyRow - 1

    return nil
}

func (p *Play) Down() error {
    if p.EmptyRow == 2 {
        return fmt.Errorf("can't move down")
    }

    p.Table[p.EmptyRow][p.EmptyCol], p.Table[p.EmptyRow+1][p.EmptyCol] = p.Table[p.EmptyRow+1][p.EmptyCol], p.Table[p.EmptyRow][p.EmptyCol]
    p.EmptyRow = p.EmptyRow + 1

    return nil
}

func (p *Play) Left() error {
    if p.EmptyCol == 0 {
        return fmt.Errorf("can't move left")
    }

    p.Table[p.EmptyRow][p.EmptyCol], p.Table[p.EmptyRow][p.EmptyCol-1] = p.Table[p.EmptyRow][p.EmptyCol-1], p.Table[p.EmptyRow][p.EmptyCol]
    p.EmptyCol = p.EmptyCol - 1

    return nil
}

func (p *Play) Right() error {
    if p.EmptyCol == 2 {
        return fmt.Errorf("can't move right")
    }

    p.Table[p.EmptyRow][p.EmptyCol], p.Table[p.EmptyRow][p.EmptyCol+1] = p.Table[p.EmptyRow][p.EmptyCol+1], p.Table[p.EmptyRow][p.EmptyCol]
    p.EmptyCol = p.EmptyCol + 1

    return nil
}

At last, we can check if the table is in the win position.

func (p *Play) IsWin() bool {
    return p.Table == DEFAULT_TABLE
}

The first GUI that I created was for the terminal's STDOUT. I have defined a View interface, and in order to follow it, we will need the Render function. We also define which keys are valid to play, and we keep a loop that only breaks if:

the user presses the quit key
the user wins

var KEYS = map[string]string{
    "up":    "w",
    "left":  "a",
    "down":  "s",
    "right": "d",
    "quit":  "q",
}

type Stdout struct {
    Play *core.Play
}

func NewStdout() *Stdout {
    return &Stdout{Play: core.NewPlay()}
}

func (s *Stdout) Render() {
    k := ""
    w := false

    for !w && !isQuit(k) {
        s.printTable()

        k = getMove()
        err := s.move(k)
        if err != nil {
            fmt.Println(err)
        }

        w = s.Play.IsWin()
    }

    if w {
        fmt.Println("You win!")
    }
}

func (s *Stdout) move(k string) error {
    switch k {
    case KEYS["up"]:
        return s.Play.Up()
    case KEYS["left"]:
        return s.Play.Left()
    case KEYS["down"]:
        return s.Play.Down()
    case KEYS["right"]:
        return s.Play.Right()
    case KEYS["quit"]:
        return nil
    default:
        return fmt.Errorf("Invalid key. Play again.")
    }
}

func (s *Stdout) printTable() {
    for _, row := range s.Play.Table {
        for _, col := range row {
            fmt.Printf("%d ", col)
        }
        fmt.Printf("\n")
    }
}

func isQuit(k string) bool {
    return KEYS["quit"] == k
}

func getMove() string {
    reader := bufio.NewReader(os.Stdin)
    t, _ := reader.ReadString('\n')
    return strings.TrimSuffix(t, "\n")
}

But when I played it sometimes, I noticed that some games were impossible to solve. Researching a bit, I discovered that my randomization was causing the issue because when changing a cell for another one, we can make some moves that will never occur in a real table. But we can identify and fix this issue by counting the number of inversions needed to solve the game. If the number of inversions is even, it is solvable. If it is odd, it is not.

func solvablePuzzle(t [3][3]int) bool {
    inversions := 0
    for i, r := range t {
        for j, c := range r {
            if c == 0 {
                continue
            }
            for x := i; x < 3; x++ {
                for y := 0; y < 3; y++ {
                    if x == i && y <= j {
                        continue
                    }
                    if t[x][y] == 0 {
                        continue
                    }
                    if t[x][y] < c {
                        inversions += 1
                    }
                }
            }
        }
    }

    if inversions%2 == 0 {
        return true
    }

    return false
}

If the game is unsolvable, we make a last change that guarantees the game has a solution.

func generateRandomTable() ([3][3]int, int, int) {
    // ...

    if !solvablePuzzle(t) {
        t[0][0], t[0][1] = t[0][1], t[0][0]
    }

    return t, xEmpty, yEmpty
}

We finally have a functional game! Now, we can work on a GUI for our sliding puzzle. I've choose Ebiten, an open source engine that allows us to build 2D games. It makes us implement an interface with the functions Update, Draw e Layout.

Implementing Layout is the simplest one: it defines the windows size.

func (u *UI) Layout(outsideWidth, outsideHeight int) (screenWidth, screenHeight int) {
    return 900, 900
}

Draw is responsible for drawing what is shown on the screen and runs for every frame. To represent our table, I had chosen to use 300x300 images for each one of the valid numbers. So, at each iteration, the functions look at the table and represent it visually. If the game is at the win state, it renders the congratulations image.

//go:embed assets/*
var assets embed.FS

func (u *UI) Draw(screen *ebiten.Image) {
    for x, row := range u.Play.Table {
        for y, value := range row {
            if value == 0 {
                continue
            }

            img := loadImage(fmt.Sprint(value))
            op := &ebiten.DrawImageOptions{}
            fX := float64(x)
            fY := float64(y)
            op.GeoM.Translate(300*fY, 300*fX)

            screen.DrawImage(img, op)
        }
    }

    if u.Play.IsWin() {
        screen.Clear()
        img := loadImage("win")
        screen.DrawImage(img, nil)
    }
}

func loadImage(name string) *ebiten.Image {
    fName := fmt.Sprintf("assets/%s.png", name)
    f, err := assets.Open(fName)
    if err != nil {
        panic(err)
    }
    defer f.Close()

    img, _, err := image.Decode(f)
    if err != nil {
        panic(err)
    }

    return ebiten.NewImageFromImage(img)
}

The Update function is responsible for updating the game itself. In other words, it makes something happen by defining the behavior when pressing any key. At the core, we mapped any action to the zero value, but when translating to a GUI, it makes more sense to reverse the logic. The user hits down because he wants to move the number below, not the zero.

func (u *UI) Update() error {
    if inpututil.IsKeyJustPressed(ebiten.KeyQ) {
        return fmt.Errorf("Quit")
    }
    if u.Play.IsWin() {
        return nil
    }
    if inpututil.IsKeyJustPressed(ebiten.KeyDown) {
        u.Play.Up()
    }
    if inpututil.IsKeyJustPressed(ebiten.KeyUp) {
        u.Play.Down()
    }
    if inpututil.IsKeyJustPressed(ebiten.KeyLeft) {
        u.Play.Right()
    }
    if inpututil.IsKeyJustPressed(ebiten.KeyRight) {
        u.Play.Left()
    }

    return nil
}

We also define our function Render, so the View contract is followed.

type UI struct {
    Play *core.Play
}

func NewUI() *UI {
    return &UI{Play: core.NewPlay()}
}

func (u *UI) Render() {
    ebiten.SetWindowSize(900, 900)
    ebiten.SetWindowTitle("Puzzle Game")

    if err := ebiten.RunGame(u); err != nil {
        log.Fatal(err)
    }
}

And our game is ready! It was a really cool project to work on. It showed me that building games is always a great way to learn new things, and it is also a way to reinforce knowledge. Also, Ebiten allows us to build 2D games using our favorite language, and we can distribute it to several platforms, including Web with WebAssembly or even XBOX. If you wish to run the code, you can find it here. Please give me some feedback about this blog post, and I have one last question for you: which game do you want to build using Go?

You can also read it and other blog posts on my website

Blog

Building a Sliding Puzzle with Go

Matheus Mina

Join Our Newsletter. No Spam, Only the good stuff.

Related