Advertisement
Guest User

Maze Finding alorithm

a guest
Jan 10th, 2020
1,144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.59 KB | None | 0 0
  1. import sys
  2. import time
  3. import numpy as np
  4. import matplotlib.pyplot as plt
  5. import os
  6. sys.setrecursionlimit(99999)
  7.  
  8. inpt1 = sys.argv[1]
  9.  
  10. blank = "0"
  11. wall = "250"
  12.  
  13. mazel = []
  14. with open(inpt1,"r") as file:
  15.     row = 0
  16.     for line in file:
  17.         templ = []
  18.         col = 0
  19.         for char in line:
  20.             if char != "\n":
  21.                 if char == "F" or char == "S":
  22.                     templ.append(char + (len(blank)-1)*blank[0])
  23.                 elif char == "P":
  24.                     templ.append(blank)
  25.                 elif char == "W":
  26.                     templ.append(wall)
  27.             if char == "F":
  28.                 fx,fy = col,row
  29.  
  30.             if char == "S":
  31.                 sx,sy = col,row
  32.             col += 1
  33.         ma_col = col
  34.         row += 1
  35.         mazel.append(templ)
  36.     ma_row = row
  37.     pic = np.full((ma_col-1,ma_row),0)
  38.  
  39. print(f"Start cell {sx},{sy} --- Finish cell {fx},{fy}\n\nHeight: {ma_row}\nWidth: {ma_col}")
  40.  
  41. def around(x,y,p):
  42.     u,d,l,r = False,False,False,False
  43.     if y != 0:
  44.         if mazel[y-1][x] == blank or mazel[y-1][x] == "F"+(len(blank)-1)*blank[0] or mazel[y-1][x] == 450:
  45.             if (x,y-1) not in p:
  46.                 u = True
  47.     if y != (len(mazel)-1):
  48.         if mazel[y+1][x] == blank or mazel[y+1][x] == "F"+(len(blank)-1)*blank[0] or mazel[y+1][x] == 450:
  49.             if (x,y+1) not in p:
  50.                 d = True
  51.     if x != (len(mazel[0])-1):
  52.         if mazel[y][x+1] == blank or mazel[y][x+1] == "F"+(len(blank)-1)*blank[0] or mazel[y][x+1] == 450:
  53.             if (x+1,y) not in p:
  54.                 r = True
  55.     if x != 0:
  56.         if mazel[y][x-1] == blank or mazel[y][x-1] == "F"+(len(blank)-1)*blank[0] or mazel[y][x-1] == 450:
  57.             if (x-1,y) not in p:
  58.                 l = True
  59.     return (u,d,l,r)
  60.  
  61. mazel[sy][sx] = 450
  62. mazel[fy][fx] = 450
  63.  
  64. intersect = []
  65. vis = []
  66. path = []
  67. success_path = []
  68.  
  69. stime = time.time()
  70. def li_copier(f):
  71.     temp = []
  72.     t = []
  73.     for i in f:
  74.         t.append(i[:])
  75.     return t
  76. takenpath = 0
  77. def print_m(using,sym):
  78.     global takenpath
  79.     tempm = li_copier(mazel)
  80.     for i,j in using:
  81.         if tempm[j][i] == blank:
  82.             tempm[j][i] = sym
  83.  
  84.     a = np.array(tempm, dtype=int)
  85.     plt.pcolor(a,cmap="inferno")
  86.     plt.axis("off")
  87.     plt.title(f"Looked through {takenpath} cells in total\nCurrent lenght of the path is {len(using)-1}")
  88.     plt.savefig(f"{takenpath}.png")
  89.     plt.clf()
  90.     takenpath += 1
  91.  
  92. def solver(start,finish,taken):
  93.     global takenpath
  94.     for i in intersect:
  95.         if i not in taken:
  96.             l,y = i
  97.             mazel[y][l] = 0
  98.     x,y = start
  99.     branch = taken[:]
  100.     branch.append(start)
  101.     if start != (fx,fy):
  102.         vis.append(start)
  103.     print_m(branch,365)
  104.     #print("----",branch)
  105.     if start == finish:
  106.         #print("Solution found!")
  107.         #print(branch)
  108.         success_path.append(branch[:])
  109.         print("Total cells looked through",takenpath,"cells")
  110.     else:
  111.         #print(x,y)
  112.         u,d,l,r = around(x,y,vis)
  113.         if sum([u,d,l,r]) > 1:
  114.             mazel[y][x] = 450
  115.             intersect.append((x,y))
  116.         if d:
  117.             solver((x,y+1),finish,branch)
  118.         if r:
  119.             solver((x+1,y),finish,branch)
  120.         if l:
  121.             solver((x-1,y),finish,branch)
  122.         if u:
  123.             solver((x,y-1),finish,branch)
  124.  
  125.  
  126. try:
  127.     os.mkdir(f"{inpt1[:-4]}out")
  128. except:
  129.     pass
  130. os.chdir(f"{inpt1[:-4]}out")
  131. solver((sx,sy),(fx,fy),path)
  132. min_path = success_path[0]
  133. for i in success_path:
  134.     if len(i) < len(min_path):
  135.         min_path = i
  136. print(takenpath)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement