Maze-Solver-Python/MazeSolver.py at main · tishanravisanka/Maze-Solver-Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
from os import system
import time
import csv

# declare variables
maze = []
m = []
start = 0,0
end = 0,0
mode = 0
length = 0

# clear screen
def clear():
    _=system('cls')

# create a list of zeros with size n
def zeroListMaker(n):
    return ['0'] * n

# check for walls and move in possibe paths
def stepMove():
    global length
    global mode
    # go through the maze
    for i in range(len(m)):
        for j in range(len(m[i])):
            # check the current position in maze
            if m[i][j] == length:
                # travel in forward direction (go through unvisited nodes)
                if mode == 0:
                    if i>0 and m[i-1][j] == 0 and maze[i-1][j] == 0:                #  up
                        m[i-1][j] = length + 1
                    elif j>0 and m[i][j-1] == 0 and maze[i][j-1] == 0:              # left
                        m[i][j-1] = length + 1
                    elif i<len(m)-1 and m[i+1][j] == 0 and maze[i+1][j] == 0:       # down
                        m[i+1][j] = length + 1
                    elif j<len(m[i])-1 and m[i][j+1] == 0 and maze[i][j+1] == 0:    # right
                        m[i][j+1] = length + 1
                    else:
                        # if it is a dead end
                        mode = 1
                        m[i][j] = -1
                        length-=2
                        return

                # travel in reverse direction (go through visited nodes)
                else:
                    length-=1
                    if i>0 and m[i-1][j] == 0 and maze[i-1][j] == 0:                # up
                        mode = 0
                    elif j>0 and m[i][j-1] == 0 and maze[i][j-1] == 0:              # left
                        mode = 0
                    elif i<len(m)-1 and m[i+1][j] == 0 and maze[i+1][j] == 0:       # down
                        mode = 0
                    elif j<len(m[i])-1 and m[i][j+1] == 0 and maze[i][j+1] == 0:    # right
                        mode = 0
                    else:
                        # going through a visited node
                        m[i][j] = -1
                        length-=1
                    return

# set the current position of the robot
def roboMove(m):
    for i in range(len(m)):
        for j in range(len(m[i])):
            if max(map(max,m)) == m[i][j]  and max(map(max,m)) != 0:
                sol[i][j] = 'R'
            elif start == (i,j):
                sol[i][j] = 'S'
            elif end == (i,j):
                sol[i][j] = 'D'
            elif m[i][j] == 0:
                sol[i][j] = 0
            else:
                sol[i][j] = '.'


# set the final path of the robot
def finalPath(m):
    for i in range(len(m)):
        for j in range(len(m[i])):
            if m[i][j]>0:
                sol[i][j] = '+'
            else:
                sol[i][j] = '0'

# print a maze (list)
def printMaze(m):
    for i in range(1,len(m)-1):
        for j in range(1,len(m[i])-1):
            print( str(m[i][j]).ljust(2),end=' ')
        print()


choice = input("Enter the name of maze file : ")

with open(choice + '.csv', 'r') as file:
    reader = csv.reader(file)
    for row in reader:
        # add left and right wall to te maze
        row.insert(0, '0')
        row.append('0')
        maze.append(row)

# add a top and a bottom wall to the maze
maze.append(zeroListMaker(len(maze[0])))
maze.insert(0,zeroListMaker(len(maze[0])))

# create a list as same size as maze
sol = [[0]*len(maze[0]) for _ in range(len(maze))]

# create all zeroes list
for i in range(len(maze)):
    m.append([])
    for j in range(len(maze[i])):
        m[-1].append(0)

# change list to integer and taking the start and end point
i=0
for row in maze:
    j=0
    for cell in row:
        if cell == 'S':
            start = i,j
            maze[i][j] = 0
            m[i][j] = 1
        elif cell == 'D':
            end = i,j
            maze[i][j] = 0
        elif cell == '0':
            maze[i][j] = 1
        else:
            maze[i][j] = 0
        j+=1
    i+=1

# clear screen
clear()
flag = 0

# move the robot until destination
while m[end[0]][end[1]] == 0:
    length += 1
    stepMove()
    roboMove(m)
    flag = 0
    for i in range(len(m)):
        for j in range(len(m[i])):
            # check the current position in maze
            if (m[i][j] != 0 and m[i][j] != -1):
                flag = 1
    if(flag==1):
        printMaze(sol)
    else:
        print('No solution in the maze!!! ')
        break
    time.sleep(1)
    clear()


# displaying final path
if flag == 1:
    print("Final path: ")
    finalPath(m)
    printMaze(sol)

input("\n\nPress any key to continue...")