プログラミング、アカデミック、何か面白いこと。 記載されているものは基本的に私が所属する団体とは関係がありません。

  1. プログラミング
  2. 10 view

[Algorithm]深さ優先探索 で迷路を解く

目的

深さ優先探索 で迷路を解く。
maze

迷路の表現方法

各地点の表現

maze-encode

迷路自体の表現(モデル化)

maze-tree

木とは

tree-model

深さ優先探索で迷路を解く

深さ優先探索というアルゴリズムで迷路を解くことが出来る。
深さ優先探索とは以下の流れで各nodeを処理する方法である。
maze-depthfast1

maze-depthfast2

maze-depthfast3

maze-depthfast4

maze-depthfast5

maze-depthfast6

maze-depthfast7

maze-depthfast8

maze-depthfast9

maze-depthfast10

maze-depthfast11

maze-depthfast12

maze-depthfast13

プログラム

ルートの表示方法

maze-route

コード

Go言語での実装

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

プログラミングの最近記事

  1. sbt1.0.0のインストールとサンプル実行

  2. [機械学習]各種Pythonライブラリ入りの実験用Dockerイメージを作った

  3. [Node.js]バッチスクリプトの書き方

  4. [Play][Scala]PlayFrameworkでリクエスト駆動のバッチを作る

  5. [OpenCV][Ruby]Webページのデザイン崩れ確認の自動化

関連記事

PAGE TOP