Target

Solve a maze by Depth-First Search.

Representation of Maze

Representation of a Point

Model

What’s Tree

What’s Depth-First Search

Depth-First Search is a algorithm like following.

Program

How to output route

Code

Implementation of golang.

package main

import (
  "bufio"
  "fmt"
  "os"
)

type Point struct {
  X int
  Y int
}

type Content struct {
  Type string
  IsChecked bool
}

type Node struct {
  Parent *Node
  Pos Point
}

type Stack struct {
  Values []*Node
  Size int
}
func (s *Stack) Length() int {
  return s.Size
}
func (s *Stack) Push(n *Node) {
  s.Values[s.Size] = n
  s.Size += 1
}
func (s *Stack) Pop() *Node {
  if s.Size > 0 {
    s.Size -= 1
    return s.Values[s.Size]
  }
  return nil
}

func IsWay(maze [][]Content, x int, y int) bool {
  if x >= 0 && x <= 11 && y >= 0 && y <= 11 && maze[y][x].Type != "WALL" && maze[y][x].IsChecked == false {
    return true
  } else {
    return false
  }
}

var endNode *Node
func SolveMaze(maze [][]Content, start Node) {
  stack := Stack{make([]*Node, 1000), 0}
  stack.Push(&start)

  cur := &start
  for ; maze[cur.Pos.Y][cur.Pos.X].Type != "END"; cur=stack.Pop() {
    fmt.Printf("(%v,%v) Stack Size : %v\n", cur.Pos.X, cur.Pos.Y, stack.Length())
    maze[cur.Pos.Y][cur.Pos.X].IsChecked = true
    if IsWay(maze, cur.Pos.X, cur.Pos.Y-1) {
      child := Node{cur, Point{cur.Pos.X, cur.Pos.Y-1}}
      stack.Push(&child)
    }
    if IsWay(maze, cur.Pos.X, cur.Pos.Y+1) {
      child := Node{cur, Point{cur.Pos.X, cur.Pos.Y+1}}
      stack.Push(&child)
    }
    if IsWay(maze, cur.Pos.X-1, cur.Pos.Y) {
      child := Node{cur, Point{cur.Pos.X-1, cur.Pos.Y}}
      stack.Push(&child)
    }
    if IsWay(maze, cur.Pos.X+1, cur.Pos.Y) {
      child := Node{cur, Point{cur.Pos.X+1, cur.Pos.Y}}
      stack.Push(&child)
    }
  }

  endNode = cur
}

func main() {
  MAX_X := 11
  MAX_Y := 11

  // File open
  var fp *os.File
  fp, err := os.Open("maze.txt")
  if err != nil {
    panic(err)
  }
  defer fp.Close()

  // Convert maze string to array of point
  var startX, startY int
  maze := make([][]Content, MAX_Y+1)
  for y:= 0; y <= MAX_Y; y++ {
    maze[y] = make([]Content, MAX_X+1)
  }
  counter := 0
  y := -1
  scanner := bufio.NewScanner(fp)
  for scanner.Scan() {
    y += 1
    x := -1
    for _, char := range scanner.Text() {
      x += 1
      switch char {
        case 'S':
          maze[y][x] = Content{"START", false}
          startX = x
          startY = y
        case 'G':
          maze[y][x] = Content{"END", false}
        case '.':
          maze[y][x] = Content{"WAY", false}
        case '#':
          maze[y][x] = Content{"WALL", false}
      }
      counter += 1
    }
  }
  if err := scanner.Err(); err != nil {
    panic(err)
  }
  fmt.Println(maze)

  // Convert maze to binary tree
  start := Node{nil, Point{startX, startY}}
  SolveMaze(maze, start)
  fmt.Println(endNode)

  // Print Route
  cur := endNode
  for ; cur.Parent != nil; cur = cur.Parent {
    fmt.Println(cur.Pos)
  }
  fmt.Println(cur.Pos)
}

実行結果

{9 11}  # End
{9 10}
{8 10}
{7 10}
{6 10}
{6 9}
{6 8}
{7 8}
{8 8}
{9 8}
{9 7}
{9 6}
{8 6}
{7 6}
{6 6}
{6 5}
{6 4}
{6 3}
{6 2}
{5 2}
{4 2}
{3 2}
{2 2}
{2 1}
{2 0}  # Start