implémentation du code du labyrinthe Golang

Implémentation du code du labyrinthe Golang

Le jeu de labyrinthe est un problème d'algorithme très classique dans le domaine de la programmation informatique, et c'est également un bon cas pour exercer les compétences en programmation et la pensée algorithmique. Cet article présentera comment implémenter le code du jeu de labyrinthe en langage GO.

1. Initialiser la carte du labyrinthe

Tout d'abord, nous devons initialiser la carte du labyrinthe et créer une matrice pour représenter le labyrinthe. Au cours du processus de mise en œuvre, nous pouvons considérer chaque cellule du labyrinthe comme un nœud et la représenter comme un tableau bidimensionnel. La valeur de la cellule du labyrinthe peut indiquer si la position actuelle peut être parcourue ou non.

Nous pouvons représenter les murs du labyrinthe par 0 et l'espace mobile par 1. Lors de l'initialisation de la carte du labyrinthe, définissez toutes les grilles initiales sur 0. Réglez la grille au bord du labyrinthe sur 0, indiquant que vous ne pouvez pas marcher. Le paramétrage du bord du labyrinthe nous permet de gérer plus facilement les nœuds de bord lors de la recherche de solutions.

Voici l'implémentation du code :

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. Sortir du labyrinthe

Nous pouvons utiliser l'algorithme de recherche en profondeur (DFS) pour aller du point de départ du labyrinthe à la fin et marquer tous les chemins. L'algorithme DFS s'appuie sur la méthode de la pile pour continuer à marcher dans une direction jusqu'à ce qu'il atteigne un certain point final ou atteigne une position où il ne peut pas continuer. Si nous atteignons une position où nous ne pouvons pas continuer, nous reviendrons à la position précédente et répéterons le processus jusqu'à ce que nous trouvions le point final ou que tous les chemins aient été parcourus.

Voici le code implémenté à l'aide de l'algorithme 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. Trouver le chemin le plus court dans le labyrinthe

Bien que l'algorithme DFS puisse trouver tous les chemins jusqu'à la fin, il ne peut pas trouver le chemin le plus court. Afin de trouver le chemin le plus court, nous devons utiliser l’algorithme Breadth First Search (BFS). L'algorithme BFS est un algorithme permettant de trouver le chemin le plus court.

L'algorithme BFS repose sur la méthode de file d'attente, en partant du point de départ et en étendant tous les nœuds voisins de la file d'attente actuelle jusqu'à ce qu'elle atteigne le point final. Lorsque nous trouvons le point final, nous devons revenir en arrière dans la direction opposée et marquer le chemin le plus court.

Voici le code implémenté à l'aide de l'algorithme 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
            }
        }
    }
}

Dans le code ci-dessus, nous définissons une structure de nœud, qui inclut les coordonnées du nœud et la distance jusqu'au nœud. Dans l'algorithme BFS, nous utilisons une file d'attente pour stocker les nœuds qui doivent actuellement être recherchés et utilisons une carte pour enregistrer les nœuds qui ont été visités afin d'éviter des recherches répétées. Pendant le processus de recherche, nous enregistrons la distance de chaque nœud jusqu'au point de départ jusqu'à ce que le point final soit trouvé. Nous revenons ensuite en arrière et parcourons le chemin le plus court et étiquetons le chemin comme chemin.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!