golang maze code implementation

golang Maze Code Implementation

The maze game is a very classic algorithm problem in the field of computer programming, and it is also a good case for exercising programming skills and algorithmic thinking. This article will introduce how to implement the maze game code in GO language.

1. Initialize the maze map

First, we need to initialize the maze map and create a matrix to represent the maze. During the implementation process, we can regard each maze cell as a node and represent it as a two-dimensional array. The value of the maze cell can indicate whether the current position can be walked or cannot be walked.

We can represent the walls of the maze as 0 and the movable space as 1. When initializing the maze map, set all initial grids to 0. Set the grid on the edge of the maze to 0, indicating that you cannot walk. The setting of the edge of the maze allows us to handle edge nodes more conveniently when looking for solutions.

The following is the code implementation:

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. Getting out of the maze

We can use the depth-first search (DFS) algorithm to achieve the path from the maze From the starting point to the ending point, all pathways are marked. The DFS algorithm relies on the stack method to continue walking in one direction until it reaches a certain end point, or reaches a position where it cannot continue. If we reach a position where we cannot proceed, we will backtrack to the previous position and repeat the process until we find the end point or all paths have been traversed.

The following is the code implemented using the DFS algorithm:

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. Find the shortest path in the maze

Although the DFS algorithm can find all the paths leading to the end path, but it does not find the shortest path. In order to find the shortest path, we need to use the Breadth First Search (BFS) algorithm. The BFS algorithm is an algorithm for finding the shortest path.

The BFS algorithm relies on the queue method, starting from the starting point and expanding all neighbor nodes of the current queue until it reaches the end point. When we find the end point, we need to backtrack in the opposite direction and mark the shortest path.

The following is the code implemented using the BFS algorithm:

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
            }
        }
    }
}

In the above code, we define a node structure, which includes the node coordinates and the distance to the node. In the BFS algorithm, we use a queue to store the nodes that currently need to be searched, and use a map to record the nodes that have been visited to avoid repeated searches. During the search process, we record the distance of each node to the starting point until the end point is found. We then backtrack and traverse the shortest path and label the path as path.

The above is the detailed content of golang maze code implementation. For more information, please follow other related articles on the PHP Chinese website!