pelaksanaan kod maze golang

Pelaksanaan kod maze Golang

Permainan maze ialah masalah algoritma yang sangat klasik dalam bidang pengaturcaraan komputer, dan ia juga merupakan kes yang baik untuk melatih kemahiran pengaturcaraan dan pemikiran algoritma. Artikel ini akan memperkenalkan cara melaksanakan kod permainan maze dalam bahasa GO.

1. Memulakan peta maze

Mula-mula, kita perlu memulakan peta maze dan mencipta matriks untuk mewakili maze. Semasa proses pelaksanaan, kita boleh menganggap setiap sel maze sebagai nod dan mewakilinya sebagai tatasusunan dua dimensi. Nilai sel maze boleh menunjukkan sama ada kedudukan semasa boleh berjalan atau tidak boleh berjalan.

Kita boleh mewakili dinding mez sebagai 0 dan ruang bergerak sebagai 1. Apabila memulakan peta maze, tetapkan semua grid awal kepada 0. Tetapkan grid di pinggir labirin kepada 0, menunjukkan bahawa anda tidak boleh berjalan. Tetapan tepi labirin membolehkan kami mengendalikan nod tepi dengan lebih mudah apabila mencari penyelesaian.

Berikut ialah pelaksanaan kod:

type point struct{x, y int}

func (p point)add(other point)point {
    return point{p.x + other.x, p.y + other.y}
}

var directions = [4]point{
    {-1, 0}, {0, -1}, {1, 0}, {0, 1},
}

func (g Grid)at(p point) gridValue {
    if p.x < 0 || p.x >= g.width {
        return wall
    }
    if p.y < 0 || p.y >= g.height {
        return wall
    }
    return g.cells[p.y][p.x]
}

func (g Grid)set(p point, v gridValue) {
    g.cells[p.y][p.x] = v
}

type Grid struct {
    width, height int
    cells         [][]gridValue
}

type gridValue byte

const (
    empty gridValue = iota
    wall
    start
    end
    path
)

func newGrid(width, height int) Grid {
    cells := make([][]gridValue, height)
    for i := range cells {
        cells[i] = make([]gridValue, width)
        for j := range cells[i] {
            cells[i][j] = empty
        }
    }
    return Grid{width: width, height: height, cells: cells}
}

2. Keluar dari labirin

Kita boleh menggunakan algoritma carian pertama mendalam (DFS) untuk mencapai laluan dari labirin Dari titik permulaan hingga ke titik penamat, semua laluan ditanda. Algoritma DFS bergantung pada kaedah tindanan untuk terus berjalan ke satu arah sehingga ia mencapai titik akhir tertentu atau mencapai kedudukan yang tidak dapat diteruskan. Jika kita mencapai kedudukan di mana kita tidak boleh meneruskan, kita akan berundur ke kedudukan sebelumnya dan mengulangi proses sehingga kita menemui titik akhir atau semua laluan telah dilalui.

Berikut ialah kod yang dilaksanakan menggunakan algoritma DFS:

func (g Grid)solveDFS() {
    start := g.findStart()
    g.dfsRecursive(start)
}

func (g Grid)findStart() point {
    for y, row := range g.cells {
        for x, value := range row {
            if value == start {
                return point{x, y}
        }
    }
  }
  panic("start point not found")
}

func (g Grid)dfsRecursive(current point) {
    if !g.inBounds(current) || g.at(current) == wall {
        return
    }
    if g.at(current) == end {
        return
    }
    g.set(current, path)
    for _, direction := range directions {
        g.dfsRecursive(current.add(direction))
    }
}

3. Cari laluan terpendek dalam maze

Walaupun algoritma DFS boleh mencari semua laluan yang menuju ke jalan akhir, tetapi ia tidak menemui jalan terpendek. Untuk mencari laluan terpendek, kita perlu menggunakan algoritma Breadth First Search (BFS). Algoritma BFS ialah algoritma untuk mencari laluan terpendek.

Algoritma BFS bergantung pada kaedah baris gilir, bermula dari titik permulaan dan mengembangkan semua nod jiran baris gilir semasa sehingga ia mencapai titik akhir. Apabila kita menemui titik akhir, kita perlu mengundur ke arah yang bertentangan dan menandakan laluan terpendek.

Berikut ialah kod yang dilaksanakan menggunakan algoritma BFS:

type node struct {
    point
    distance int
}

func (g Grid)solveBFS() {
    start := g.findStart()
    queue := []node{{point: start}}
    seen := map[point]bool{start: true}
    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        if g.at(current.point) == end {
            g.markShortestPath(current)
            return
        }
        for _, direction := range directions {
            next := current.add(direction)
            if !g.inBounds(next) || seen[next] || g.at(next) == wall {
                continue
            }
            seen[next] = true
            queue = append(queue, node{point: next, distance: current.distance + 1})
        }
    }
}

func (g Grid)markShortestPath(current node) {
    for ; g.at(current.point) != start; current.distance-- {
        g.set(current.point, path)
        for _, direction := range directions {
            next := current.add(direction)
            if g.at(next) == path && current.distance - 1 == g.at(next).distance {
                current.point = next
                break
            }
        }
    }
}

Dalam kod di atas, kami mentakrifkan struktur nod, yang merangkumi koordinat nod dan jarak ke nod. Dalam algoritma BFS, kami menggunakan baris gilir untuk menyimpan nod yang perlu dicari pada masa ini, dan menggunakan peta untuk merekodkan nod yang telah dilawati untuk mengelakkan carian berulang. Semasa proses carian, kami merekodkan jarak setiap nod ke titik permulaan sehingga titik akhir ditemui. Kami kemudian berundur dan melintasi laluan terpendek dan melabel laluan itu sebagai laluan.

Atas ialah kandungan terperinci pelaksanaan kod maze golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!