golang maze コードの実装

golang 迷路コードの実装

迷路ゲームは、コンピューター プログラミングの分野における非常に古典的なアルゴリズムの問​​題であり、プログラミング スキルとアルゴリズム的思考を訓練するのにも適しています。この記事では、GO言語で迷路ゲームのコードを実装する方法を紹介します。

1. 迷路マップを初期化する

まず、迷路マップを初期化し、迷路を表す行列を作成する必要があります。実装プロセス中、迷路の各セルをノードと見なし、それを 2 次元配列として表すことができます。迷路セルの値は、現在位置が歩行可能か歩行不可能かを示すことができます。

迷路の壁を 0、移動可能な空間を 1 として表すことができます。迷路マップを初期化するときは、すべての初期グリッドを 0 に設定します。迷路の端のグリッドを 0 に設定します。これは、歩くことができないことを示します。迷路のエッジを設定すると、解決策を探すときにエッジ ノードをより便利に処理できるようになります。

次はコードの実装です:

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. 迷路からの脱出

深さ優先検索 (DFS) アルゴリズムを使用して、次のことができます。迷路からの道をたどる 開始点から終了点まで、すべての経路にマークが付けられています。 DFS アルゴリズムはスタック メソッドに依存し、特定の終点に到達するか、継続できない位置に到達するまで一方向に歩き続けます。先に進めない位置に到達した場合は、前の位置に戻り、終点が見つかるかすべてのパスが通過し終わるまでプロセスを繰り返します。

次は、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. 迷路の最短経路を見つける

DFS アルゴリズムはすべてを見つけることができますが、最後のパスにつながるパスを探しますが、最短パスは見つかりません。最短パスを見つけるには、Breadth First Search (BFS) アルゴリズムを使用する必要があります。 BFS アルゴリズムは、最短経路を見つけるアルゴリズムです。

BFS アルゴリズムはキュー方式に依存しており、開始点から開始して、現在のキューのすべての隣接ノードを終了点に到達するまで拡張します。終点を見つけたら、逆方向に戻り、最短経路をマークする必要があります。

以下は、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
            }
        }
    }
}

上記のコードでは、ノードの座標とノードまでの距離を含むノード構造を定義します。 BFS アルゴリズムでは、キューを使用して現在検索する必要があるノードを保存し、マップを使用してアクセスされたノードを記録し、検索の繰り返しを回避します。検索プロセス中に、終点が見つかるまでの始点までの各ノードの距離を記録します。次に、最短パスをバックトラックして横断し、そのパスにパスとしてラベルを付けます。

以上がgolang maze コードの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。