Contents
目的
![maze](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-1024x956.png)
迷路の表現方法
各地点の表現
![maze-encode](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-encode-1024x772.png)
迷路自体の表現(モデル化)
![maze-tree](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-tree1-1024x779.png)
木とは
![tree-model](http://160.16.71.152:12080/wp-content/uploads/2014/06/tree-model-1024x901.png)
深さ優先探索で迷路を解く
![maze-depthfast1](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast1-1024x670.png)
深さ優先探索とは以下の流れで各nodeを処理する方法である。
![maze-depthfast2](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast2-1024x650.png)
![maze-depthfast3](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast3-1024x674.png)
![maze-depthfast4](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast4-1024x670.png)
![maze-depthfast5](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast5-1024x672.png)
![maze-depthfast6](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast6-1024x670.png)
![maze-depthfast7](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast7-1024x670.png)
![maze-depthfast8](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast8-1024x670.png)
![maze-depthfast9](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast9-1024x670.png)
![maze-depthfast10](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast10-1024x672.png)
![maze-depthfast11](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast11-1024x672.png)
![maze-depthfast12](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast12-1024x672.png)
![maze-depthfast13](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-depthfast13-1024x672.png)
プログラム
ルートの表示方法
![maze-route](http://160.16.71.152:12080/wp-content/uploads/2014/06/maze-route-1024x673.png)
コード
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