6
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

I believe the code is slow because you are using normal Dijkstra, which takes O(V^2) where V is the number of vertices (Here, V would be N*M).

This is because you are searching for the minimum by iterating through all the unvisited elements, which takes O(V) time. Repeat this for V times and it becomes O(V^2).

You can reduce this to O(V * log V) by using a heap, which would increase your code's performance dramatically.

This is a trick most competitive programmers use ;-)

You can refer on how to use the heaps here:
https://courses.cs.washington.edu/courses/cse326/07au/lectures/lect22.pdf

(This one is for graphs, but you can incorporate it for mazes as well)

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks so much! \$\endgroup\$ – Prithvidiamond Feb 10 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.