Tag: working

This algorithm code from my dijkstra … it solves all square order 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

The problem is that it is quite slow ... even compared to the other implementations that I have seen online ... Now I could just copy them, but I wrote this from zero with minimal online help and just reading the descriptions of the algorithm, all for the purpose of learning ... So just copying better code, would not serve my purpose.

So can anyone tell me where and how can I get more performance out of it?

Note: If there is a need for my custom maze generation 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