【Python】深さ優先探索で迷路の最短経路を求める

探索していない通路を「-1」として表現して
スタートからゴールに到達するまで深さ優先探索で迷路を探索し、
探索した通路はスタートからの距離に数値を置き換える。

import sys
import random
from collections import deque

class Maze:
  PATH = 0
  WALL = 1

  def __init__(self, width, height, seed=0):
    self.width = width
    self.height = height
    if self.width < 5 or self.height < 5:
      sys.exit()
    if self.width % 2 == 0:
      self.width += 1
    if self.height % 2 == 0:
      self.height += 1
    self.maze = [[self.PATH for x in range(self.width)] for y in range(self.height)]
    self.dist = [[-1 for i in range(self.width)] for j in range(self.height)]
    self.start = [1, 1]
    self.goal = [self.width-2, self.height-2]
    random.seed(seed)

  def set_outer_wall(self):
    for y in range(0, self.height):
      for x in range(0, self.width):
        if x == 0 or y == 0 or x == self.width-1 or y == self.height-1:
          self.maze[y][x] = self.WALL
    return self.maze

  def set_inner_wall(self):
    for y in range(2, self.height-1, 2):
      for x in range(2, self.width-1, 2):
        self.maze[y][x] = self.WALL
    return self.maze

  def set_maze_boutaoshi(self):
    self.set_outer_wall()
    self.set_inner_wall()
    for y in range(2, self.height-1, 2):
      for x in range(2, self.width-1, 2):
        while True:
          wall_x = x
          wall_y = y
          if y == 2:
            direction = random.randrange(0, 4)
          else:
            direction = random.randrange(0, 3)
          if direction == 0:
            wall_x += 1
          elif direction == 1:
            wall_y += 1
          elif direction == 2:
            wall_x -= 1
          elif direction == 3:
            wall_y -= 1
          if self.maze[wall_y][wall_x] != self.WALL:
            self.maze[wall_y][wall_x] = self.WALL
            break
    return self.maze

  def set_start_goal(self, start, goal):
    if self.maze[start[1]][start[0]] == self.PATH:
      self.start = start
    if self.maze[goal[1]][goal[0]] == self.PATH:
      self.goal = goal
    return self.maze

  def set_dist_dfs(self,flag=False):
    stack = deque()
    self.dist[self.start[1]][self.start[0]] = 0
    stack.append(self.start)
    while len(stack) > 0:
      point = stack.pop()
      for x in [[0,-1],[1,0],[0,1],[-1,0]]:
        if self.maze[point[1]+x[1]][point[0]+x[0]] == 0 and self.dist[point[1]+x[1]][point[0]+x[0]] == -1:
          self.dist[point[1]+x[1]][point[0]+x[0]] = self.dist[point[1]][point[0]] + 1
          stack.append([point[0]+x[0],point[1]+x[1]])
        if flag != True:
          if point[0]+x[0] == self.goal[0] and point[1]+x[1] == self.goal[1]:
            stack.clear()
            break
    return self.dist

  def set_shortest_path(self):
    point = self.goal
    self.maze[point[1]][point[0]] = '*'
    while self.dist[point[1]][point[0]] > 0:
      for x in [[0,-1],[1,0],[0,1],[-1,0]]:
        if self.dist[point[1]][point[0]]-self.dist[point[1]+x[1]][point[0]+x[0]] == 1:
          if self.dist[point[1]][point[0]] > 0:
            self.maze[point[1]+x[1]][point[0]+x[0]] = '*'
            point = [point[0]+x[0],point[1]+x[1]]
    return self.maze

  def print_maze(self):
    self.maze[self.start[1]][self.start[0]] = 'S'
    self.maze[self.goal[1]][self.goal[0]] = 'G'
    for col in self.maze:
      for cell in col:
        if cell == self.WALL:
          print('#', end='')
        elif cell == self.PATH:
          print(' ', end='')
        elif cell == 'S':
          print('S', end='')
        elif cell == 'G':
          print('G', end='')
        elif cell == '*':
          print('*', end='')
      print()

maze1 = Maze(15, 15)
maze1.set_maze_boutaoshi()
maze1.set_start_goal([5, 5], [9, 11])
maze1.set_dist_dfs()
maze1.set_shortest_path()
maze1.print_maze()

今回は、以下のように出力される。

###############
# # #   # #   #
# # # ### ### #
#*******      #
#*# ###*##### #
#*# #S**    # #
#*########### #
#*****#       #
# ###*##### # #
#   #*****# # #
### ### #*### #
#     # #G#   #
### ### ### # #
#     # #   # #
###############

参考

深さ優先探索 - Algoful
深さ優先探索(DFS)とは子のないノードにたどり着くまで優先的に探索を繰り返すアルゴリズムです。スタック(FILO)を利用して探索を行います。迷路探索のシミュレーションで視覚的に理解できます。C#の実装サンプルがあります。
[Python] 深さ優先探索で迷路を解く
深さ優先探索 深さ優先探索(Depth First Search)は 、グラフを始点から一番奥の末端まで一直線…
DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
0. はじめに --- グラフ探索の動機現代ではコンピュータはとても身近なものになりました。コンピュータの用途としてはシミュレーションなどの大規模計算を行う人工知能をつくるアプリを開発する…
タイトルとURLをコピーしました