This is my implementation of Dijkstra's algorithm. It solves any order square mazes.
from copy import deepcopy
from math import inf
import maze_builderV2 as mb
def dijkstra(maze, order, pos, finalpos):
mazemap = {}
def scan(): # Converts raw map/maze into a suitable datastructure.
for x in range(1, order+1):
for y in range(1, order+1):
mazemap[(x, y)] = {}
t = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
for z in t:
# print(z[0], z[1], maze[z[0]][z[1]])
if maze[z[0]][z[1]] == 'X':
pass
else:
mazemap[(x, y)][z] = 1
scan()
unvisited = deepcopy(mazemap)
distances = {} # Stores shortest possible distance of each node
paths = {} # Stores last node through which shortest path was acheived for each node
for node in unvisited: # Initialisation of distance information for each node
if node == pos:
distances[node] = 0 # Starting location...
else:
distances[node] = inf
while unvisited != {}:
curnode = None
for node in unvisited:
if curnode == None:
curnode = node
elif distances[node] < distances[curnode]:
curnode = node
else:
pass
# cannot use unvisited map is it will keep changing in the loop
for childnode, length in mazemap[curnode].items():
if length + distances[curnode] < distances[childnode]:
distances[childnode] = distances[curnode] + length
paths[childnode] = curnode
unvisited.pop(curnode)
def shortestroute(paths, start, end):
shortestpath = []
try:
def rec(start, end):
if end == start:
shortestpath.append(end)
return shortestpath[::-1]
else:
shortestpath.append(end)
return rec(start, paths[end])
return rec(start, end)
except KeyError:
return False
finalpath = shortestroute(paths, pos, finalpos)
if finalpath:
for x in finalpath:
if x == pos or x == finalpos:
pass
else:
maze[x[0]][x[1]] = 'W'
else:
pass
Problem is that it is quite slow, even compared to other implementations I have seen online. Now I could just copy those, but I wrote this from scratch with minimal help online and by just reading descriptions about the algorithm, all for the purpose of learning. So just copying better code would not serve my purpose.
So can someone tell me where and how I can squeeze some more performance out of this?
Note: If there is a need for my custom maze generating code, here it is:
def mazebuilder(maze, order=10, s=(1, 1), e=(10, 10)):
from copy import deepcopy
from random import randint, choice
maze[s[0]][s[1]] = 'S' # Initializing a start position
maze[e[1]][e[1]] = 'O' # Initializing a end position
finalpos = e
pos = s
blocks = []
freespaces = [(x, y) for x in range(1, order+1) for y in range(1, order+1)]
def blockbuilder(kind):
param1 = param2 = 0
double = randint(0, 1)
if kind == 0:
param2 = randint(3, 5)
if double:
param1 = 2
else:
param1 = 1
else:
param1 = randint(3, 5)
if double:
param2 = 2
else:
param2 = 1
for a in range(blockstarter[0], blockstarter[0]+param2):
for b in range(blockstarter[1], blockstarter[1]+param1):
if (a+1, b) in blocks or (a-1, b) in blocks or (a, b+1) in blocks or (a, b-1) in blocks or (a, b) in blocks or (a+1, b+1) in blocks or (a-1, b+1) in blocks or (a+1, b-1) in blocks or (a-1, b-1) in blocks:
pass
else:
if a > order+1 or b > order+1:
pass
else:
if maze[a][b] == 'X':
blocks.append((a, b))
else:
spaces = [(a+1, b), (a-1, b), (a, b+1), (a, b-1)]
for c in spaces:
if maze[c[0]][c[1]] == 'X':
break
else:
maze[a][b] = 'X'
blocks.append((a, b))
for x in range(1, order+1):
for y in range(1, order+1):
if (x, y) in freespaces:
t = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
i = 0
while i < len(t):
if maze[t[i][0]][t[i][1]] == 'X' or (t[i][0], t[i][1]) == pos or (t[i][0], t[i][1]) == finalpos:
del t[i]
else:
i += 1
if len(t) > 2:
blockstarter = t[randint(0, len(t)-1)]
kind = randint(0, 1) # 0 - vertical, 1 - horizontal
blockbuilder(kind)
else:
pass
b = 0
while b < len(blocks):
block = blocks[b]
t = {'d':(block[0]+2, block[1]), 'u':(block[0]-2, block[1]), 'r':(block[0], block[1]+2), 'l':(block[0], block[1]-2)}
rch = choice(['d', 'u', 'r', 'l'])
z = t[rch]
if z[0] > order-2 or z[1] > order-2 or z[0] < 2+2 or z[1] < 2+2: # Decreased chance of having non solvable maze being generated...
pass
else:
if maze[z[0]][z[1]] == 'X':
if randint(0, 1):
set = None
if rch == 'u':
set = (z[0]+1, z[1])
elif rch == 'd':
set = (z[0]-1, z[1])
elif rch == 'r':
set = (z[0], z[1]-1)
elif rch == 'l':
set = (z[0], z[1]+1)
else:
pass
if maze[set[0]][set[1]] == '_':
# Checks so that no walls that block the entire way are formed
# Makes sure maze is solvable
sets, count = [(set[0]+1, set[1]), (set[0]-1, set[1]), (set[0], set[1]+1), (set[0], set[1]-1)], 0
for blyat in sets:
while blyat[0] != 0 and blyat[1] != 0 and blyat[0] != order+1 and blyat[1] != order+1:
ch = [(blyat[0]+1, blyat[1]), (blyat[0]-1, blyat[1]), (blyat[0], blyat[1]+1), (blyat[0], blyat[1]-1)]
suka = []
for i in ch:
if ch not in suka:
if maze[i[0]][i[1]] == 'X':
blyat = i
break
else:
pass
suka.append(ch)
else:
pass
else:
blyat = None
if blyat == None:
break
else:
pass
else:
count += 1
if count < 1:
maze[set[0]][set[1]] = 'X'
blocks.append(set)
else:
pass
else:
pass
else:
pass
b += 1
