Color the tiles that lead to the target using .pgm and python

Question

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

This code will create the following array of lists:

[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]

where,

• '0' - is a wall
• '1' - is the path
• '2' - the starting tile
• '3' - the target tile

I used the following code in order to write the pixels to a .pgm file and set their color in tones ranging from 0 to 255, where 0(100% white) is the lightest tone and 255 is the darkest(100% black).

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()

The code above will output an image as inserted below:

What code do I need in order to instruct the computer to color the tiles that lead to the target?

Answer 1

To find the path between A and B, you need a shortest-path algorithm. Most of them use graph.

First, you need to convert your labyrinth into a graph. This is the easy part. The nodes are the 1, 2 and 3 in your labyrinth and there is an edge between all the nodes that connect together. Use the coordinates to distinguish the nodes. 2 is (1,1) and it connects to a 1 (1,2), that connects to (1,3) that connects to (1,4) and (2,3)...

After that, you can implement a shortest-path algorithm to find the path from A (1,1) to B (11,7). This is harder to do if you are not familiar with this kind of algorithm. The 2 most known are Bellman-Ford and Dijkstra. I'll let you search about them since they both have their best cases and it depends of the graph's size and if the paths can be cyclic.

When you have the path, you color the pixels of the path in an other color.