Переключение координат X и Y в алгоритме решения лабиринта с использованием стека в Python - PullRequest
Новая
       13

Переключение координат X и Y в алгоритме решения лабиринта с использованием стека в Python

0 голосов
/ 22 сентября 2018

Я пытаюсь разобраться в простом алгоритме решения лабиринтов, используя стек в Python 3.

Я нашел некоторый код и добавил некоторые выходные данные, чтобы отслеживать, что происходит, но человек, которыйнаписал код, использующий координаты x, y (в таком порядке) для двумерного массива.Как я понимаю, вместо него следует использовать y, x (для строки, а затем для столбца).У меня достаточно проблем с выполнением алгоритма без необходимости мысленно переключать x и y, чтобы понять, что происходит.

Я почти уверен, что это крошечное изменение, но кто-то может предложить, пожалуйста, модификацию, которая сделаеткод отображать и отслеживать координаты правильно?Меня не волнует, увеличивается ли ось Y в направлении вверх или вниз.

Мой крошечный лабиринт представлен ниже: 

 ***
  **
* **
* G*

, а код выглядит следующим образом: 

# This program traverses a maze using a stack.

from sq import Stack              # import a Stack type from sq.py

MAZE_SIZE = 4                    # define the size of the maze

def PrintMaze(maze):              # an auxilliary function that prints a maze
    for row in range(MAZE_SIZE):
        print(maze[row], end='')
    print()

def InBounds(xxx_todo_changeme):              # an auxillary function that determines if (x,y) is on the maze
    (x,y) = xxx_todo_changeme
    return (0 <= x < MAZE_SIZE) and (0 <= y < MAZE_SIZE)

def Maze(maze, start):          # traverse 'maze' from starting coordinates 'start'
    s = Stack()                  # create a new Stack named s
    s.push(start);               # push the start coordinates onto s
    while not s.isEmpty():       # loop while s is not empty
        print(s.list)
        input("press Enter to continue ")
        (x, y) = s.pop()          # pop a coordinate off s into the tuple (x,y)
        print('Trying position ({}, {})'.format(x,y))
        if InBounds((x,y)):         # if (x,y) is on the maze then
            if maze[x][y] == 'G':    # if (x,y) is the goal then
                s.empty()             # empty the stack because we're done
            elif maze[x][y] == ' ':  # else if (x,y) is an undiscovered coordinate
                print('filling ({}, {})'.format(x,y))
                maze[x] = maze[x][:y] + 'D' + maze[x][y+1:]  # mark (x,y) discovered with 'D'
                PrintMaze(maze);      # print the maze to show progress so far
                s.push((x+1, y))      # push right neighbor onto stack s
                s.push((x, y+1))      # push lower neighbor onto stack s
                s.push((x-1, y))      # push left neighbor onto stack s
                s.push((x, y-1))      # push upper neighbor onto stack s
        else:
            print('Out of bounds.')

# The following can be used to create a maze and traverse it:

import sys
maze = open('maze2.dat', 'r')     # open the file 'maze.dat' for reading
maze = maze.readlines();         # read the file into maze
Maze(maze, (0,0))                 # traverse the maze starting at (0,0)

1 Ответ

0 голосов
/ 22 сентября 2018

После строки 

input("press Enter to continue ")

Вы можете просто ввести: 

(y, x) = s.pop()

, который переворачивает координаты для всего кода

Я недавно работал над Решателем Лабиринтатоже ... Вот пример лабиринта и функции печати из моего кода: 

maze=[[ 0 ,0,1,1,0,'S'],
      [ 0 ,0,0,0,1, 0 ],
      ['F',1,0,0,0, 0 ],
      [ 0 ,0,0,0,1, 0 ],
      [ 0 ,1,0,0,0, 0 ]]
## 0 represents empty space, 1 represents a wall
def printmaze(maze):
    for i in maze:
        for j in i:
            print('X' if j==1 else (' ' if j==0 else j),end='')
        print()

Также в вашем коде: 

def PrintMaze(maze):              # an auxilliary function that prints a maze
    for row in range(MAZE_SIZE):
        print(maze[row], end='')
    print()

совпадает с: 

def PrintMaze(maze):
    for row in maze:
        print(row)

Для того, чтобы инвертировать печать, вам необходимо: 

for col in range(MAZE_SIZE):
    for row in maze:
        print(row[col],end='')
    print()
...