Раскрасьте плитки, которые ведут к цели, используя.pgm и python

Question

import Labyrinthe laby = Labyrinthe.creer(9,13)

Этот код создаст следующий массив списков:

[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 1, 0, 1, 0]
[0, 1, 1, 1, 1, 1, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 1, 0, 1, 1, 1, 0]
[0, 1, 0, 1, 0, 1, 0, 0, 0]
[0, 1, 0, 1, 0, 1, 1, 1, 0]
[0, 1, 0, 1, 0, 0, 0, 1, 0]
[0, 1, 1, 1, 1, 1, 0, 3, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]

где,

• "0" - это стена
• "1" - это путь
• '2' - стартовая плитка
• "3" - целевой тайл

Я использовал следующий код, чтобы записать пиксели в файл .pgm и установить их цвет в тонах от 0 до 255, где 0(100% белый) - самый светлый тон, а 255 - самый темный (100% черный).

size = 20  #size of a tile in pixels
rows = len(laby)
columns = len(laby[0])
height = size * rows 
width = size * columns

f = open("laby.pgm", "w")
f.write("P2\n" + str(width) + " " + str(height) + "\n255\n") 

for y in range(height):
    for x in range(width):
        indx = x // size
        indy = y // size
        a = laby[indy][indx]
        if a == 0:
            f.write(str(50) + " ")   # colors the pixels
        elif a == 2:
            f.write(str(100) + " ")
        elif a == 3:
            f.write(str(170) + " ")
        else:
            f.write(str(a) + " ")
f.close()

Код выше выведет изображение, как показано ниже:

Какой код мне нужен, чтобы дать компьютеру команду раскрасить плитки, которые ведут к цели?

Answer 1

Чтобы найти путь между A и B, вам нужен алгоритм кратчайшего пути. Большинство из них используют график.

Во-первых, вам нужно преобразовать свой лабиринт в график. Это легкая часть. Узлы - это 1, 2 и 3 в вашем лабиринте, и между всеми узлами, которые соединяются вместе, есть грань. Используйте координаты, чтобы различать узлы. 2 - это (1,1), и он соединяется с 1 (1,2), который соединяется с (1,3), который соединяется с (1,4) и (2,3)...

После этого вы можете реализовать алгоритм кратчайшего пути, чтобы найти путь от A (1,1) до B (11,7). Это сложнее сделать, если вы не знакомы с этим алгоритмом. 2 самых известных - Беллман-Форд и Дейкстра. Я позволю вам искать их, так как они оба имеют свои лучшие случаи, и это зависит от размера графа и от того, могут ли пути быть циклическими.

Когда у вас есть путь, вы окрашиваете его в другой цвет.