You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
426 lines
14 KiB
426 lines
14 KiB
#!/usr/bin/env python3
|
|
#(height, width)
|
|
import random as rnd
|
|
import os
|
|
import itertools
|
|
from enum import Enum
|
|
import time
|
|
import math
|
|
from queue import PriorityQueue as pq
|
|
import threading
|
|
|
|
DEBUG=True
|
|
# DEBUG=False
|
|
graphical=False
|
|
|
|
clear="clear"
|
|
if os.name == "nt":
|
|
clear="cls"
|
|
|
|
def resource_path(relative_path):
|
|
try:
|
|
# PyInstaller creates a temp folder and stores path in _MEIPASS
|
|
base_path = sys._MEIPASS;
|
|
except Exception:
|
|
base_path = os.path.abspath("./");
|
|
return os.path.join(base_path, relative_path);
|
|
|
|
figNum=2
|
|
ans = input("Figure Number 1/2/3(other input to default 2): ")
|
|
match ans:
|
|
case "1":
|
|
figNum = 1;
|
|
case "3":
|
|
figNum = 3;
|
|
file = resource_path(f"figures/figure{figNum}.txt");
|
|
tickDelay = float(input("Tick Delay(s): "))
|
|
|
|
imgSpacing = 5 #pixels
|
|
|
|
class SquareType(Enum):
|
|
AISLE = 0
|
|
SEAT = 1
|
|
WALL = 2
|
|
|
|
height=0
|
|
width=0
|
|
|
|
tiles = [];
|
|
imageDims = (30, 30);
|
|
root = None;
|
|
|
|
grid=[]
|
|
# entries=[(3,0)]
|
|
entries=[(0,3)]
|
|
# entries=[(7,3),(7,43)]
|
|
# entries=[(7,3)]
|
|
|
|
passengers = []
|
|
|
|
|
|
class GridSquare:
|
|
#typ: SquareType, occupant: index
|
|
def __init__(self, typ, occupant):
|
|
self.typ = typ
|
|
self.occupant = occupant
|
|
def __str__(self):
|
|
return "(%s|%s)" % (str(self.typ), str(self.occupant))
|
|
def __repr__(self):
|
|
return str(self)
|
|
|
|
def makeGrid():
|
|
return [[GridSquare(SquareType.AISLE, None) for x in range(0,width)] for y in range(0,height)]
|
|
|
|
class Passenger:
|
|
shuffled = 0
|
|
inter = None
|
|
interback = None
|
|
path = []
|
|
recalc = True
|
|
#dest and curr are both 2-tuples
|
|
def __init__(self, dest, curr):
|
|
self.dest = dest
|
|
self.curr = curr
|
|
def __str__(self):
|
|
return "(%s|%s)" % (dest, curr)
|
|
|
|
def manhattanDistance(pos1, pos2):
|
|
return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])
|
|
|
|
def mooreNeighbourhood(pos):
|
|
return [i for i in [(pos[0]+1, pos[1]), (pos[0], pos[1]+1), (pos[0]-1, pos[1]), (pos[0], pos[1]-1)] if
|
|
i[0] >= 0 and i[1] >= 0 and i[0] < height and i[1] < width]
|
|
|
|
def Dims():
|
|
global height
|
|
global width
|
|
arrFile = open(file)
|
|
height=int(arrFile.readline())
|
|
width=int(arrFile.readline())
|
|
|
|
def nextSquare(passenger, grid):
|
|
passenger.recalc = False
|
|
passenger.path=[]
|
|
dist=[[0 for x in range(0,width)] for y in range(0,height)]
|
|
prev=[[None for x in range(0,width)] for y in range(0,height)]
|
|
|
|
dest = None
|
|
|
|
if passenger.inter == None:
|
|
dest = passenger.dest
|
|
else:
|
|
dest = passenger.inter
|
|
|
|
q = pq()
|
|
|
|
for y in range(0,height):
|
|
for x in range(0,width):
|
|
if x != passenger.curr[1] or y != passenger.curr[0]:
|
|
dist[y][x] = 10**10
|
|
|
|
mn = mooreNeighbourhood(passenger.curr)
|
|
for (i, man) in enumerate(mn):
|
|
if (grid[passenger.curr[0]][passenger.curr[1]].typ != SquareType.SEAT or man[1] == passenger.curr[1]) and grid[man[0]][man[1]].typ != SquareType.WALL and not (grid[man[0]][man[1]].typ == SquareType.AISLE and grid[man[0]][man[1]].occupant is not None):
|
|
q.put((1, man, i))
|
|
dist[man[0]][man[1]] = 1
|
|
prev[man[0]][man[1]] = (0, passenger.curr, 0)
|
|
|
|
while not q.empty():
|
|
u = q.get()
|
|
if u[1] == dest:
|
|
while prev[u[1][0]][u[1][1]] != None:
|
|
passenger.path.append(u[1])
|
|
u=prev[u[1][0]][u[1][1]]
|
|
return
|
|
for x in mooreNeighbourhood(u[1]):
|
|
# if not( grid[x[0]][x[1]].typ == SquareType.SEAT and u[1][1] != x[1]) and grid[x[0]][x[1]].typ != SquareType.WALL and (grid[x[0]][x[1]].occupant == None or grid[x[0]][x[1]].typ == SquareType.SEAT):
|
|
if not( grid[x[0]][x[1]].typ == SquareType.SEAT and u[1][1] != x[1]) and grid[x[0]][x[1]].typ != SquareType.WALL:
|
|
alt = 0
|
|
if grid[x[0]][x[1]].typ == SquareType.SEAT or grid[u[1][0]][u[1][1]].typ == SquareType.SEAT:
|
|
if grid[x[0]][x[1]].occupant != None:
|
|
alt = dist[u[1][0]][u[1][1]] + 5 + 10
|
|
else:
|
|
alt = dist[u[1][0]][u[1][1]] + 5
|
|
else:
|
|
alt = dist[u[1][0]][u[1][1]] + 1
|
|
# if alt == 0:
|
|
# if x == dest:
|
|
# print("mn: " + str(x) + ", alt: " + str(alt))
|
|
# print("dist" + str(x) + ": " + str(dist[x[0]][x[1]]))
|
|
if alt < dist[x[0]][x[1]]:
|
|
dist[x[0]][x[1]] = alt
|
|
prev[x[0]][x[1]] = u
|
|
q.put((alt, x, u[2]))
|
|
|
|
passenger.path = [passenger.curr]
|
|
|
|
|
|
def GenPassList():
|
|
global height
|
|
global width
|
|
global grid
|
|
global tiles
|
|
border=[]
|
|
arrFile = open(file)
|
|
|
|
height=int(arrFile.readline())
|
|
width=int(arrFile.readline())
|
|
print(f"{file} Dimensions: {height}, {width}")
|
|
|
|
grid = [[GridSquare(SquareType.AISLE, None) for x in range(0,width)] for y in range(0,height)]
|
|
|
|
for y in range(0,height):
|
|
temp = []
|
|
for x in range(0,width+1):
|
|
char = arrFile.read(1);
|
|
matched = False;
|
|
match char:
|
|
case 'S':
|
|
grid[y][x].typ = SquareType.SEAT
|
|
border.append(Passenger((y,x),(-1,-1)))
|
|
case 'W':
|
|
grid[y][x].typ = SquareType.WALL
|
|
case '.':
|
|
grid[y][x].typ = SquareType.AISLE
|
|
if graphical and x < width:
|
|
temp.append(Tile(root, imageDims[0], imageDims[1], x, y, 0, grid[y][x].typ, f"{x}|{y}"));
|
|
if graphical:
|
|
tiles.append(temp);
|
|
|
|
for x in border:
|
|
sign=(-1)**rnd.randint(0,1)
|
|
for i in range(1,7):
|
|
inc = (-1)**i * sign * math.floor((i+1)/2)
|
|
if (inc + x.dest[0] > 0) and (inc + x.dest[0] < height) and (grid[x.dest[0]+inc][x.dest[1]].typ == SquareType.AISLE):
|
|
x.inter=(inc + x.dest[0], x.dest[1])
|
|
x.interback = x.inter
|
|
|
|
return border
|
|
|
|
def nunty(x):
|
|
if x is None: return -1
|
|
return x
|
|
|
|
btime = 3 #passengers board every btime ticks
|
|
|
|
def tick(t, toad):
|
|
done=True
|
|
global btime
|
|
# print grid
|
|
if DEBUG:
|
|
print(chr(0x3000), end="")
|
|
print(chr(0x3000), end="")
|
|
for x in range(0, width):
|
|
if x % 10 == 0:
|
|
print(chr(0xFF10 + int(x / 10)), end="")
|
|
else:
|
|
print(chr(0x3000), end="")
|
|
print()
|
|
print(chr(0x3000), end="")
|
|
print(chr(0x3000), end="")
|
|
for x in range(0, width):
|
|
print(chr(0xFF10 + (x % 10)), end="")
|
|
print()
|
|
for (i, row) in enumerate(grid):
|
|
if i % 10 == 0:
|
|
print(chr(0xFF10 + int(i / 10)), end="")
|
|
else:
|
|
print(chr(0x3000), end="")
|
|
print(chr(0xFF10 + (i % 10)), end="")
|
|
|
|
for j in range(len(row)):
|
|
guy=row[j]
|
|
o=0
|
|
if guy.occupant is not None:
|
|
print(chr(0x20000 + guy.occupant), end="")
|
|
o=1
|
|
elif guy.typ == SquareType.SEAT:
|
|
print(":", end="")
|
|
elif guy.typ == SquareType.WALL:
|
|
print("W", end="")
|
|
else:
|
|
print("_", end="")
|
|
if graphical:
|
|
#print(f"{i},{j},{len(tiles)},{len(tiles[i])}")
|
|
if tiles[i][j].occ != o: #if value has changed since last tick
|
|
tiles[i][j].Update(o);
|
|
print()
|
|
print("---")
|
|
# print(grid[3][0].occupant, grid[3][1].occupant, passengers[nunty(grid[3][1].occupant)].dest)
|
|
elif graphical:
|
|
for (i, row) in enumerate(grid):
|
|
for j in range(len(row)):
|
|
o=0
|
|
if row[j].occupant is not None:
|
|
o=1
|
|
#print(f"{i},{j},{len(tiles)},{len(tiles[i])}")
|
|
#print(f"{i},{j},{len(tiles)}")
|
|
if tiles[i][j].occ != o: #if value has changed since last tick
|
|
tiles[i][j].Update(o);
|
|
time.sleep(tickDelay);
|
|
if t % btime == 0:
|
|
for x in entries:
|
|
if toad < len(passengers) and grid[x[0]][x[1]].occupant is None:
|
|
grid[x[0]][x[1]].occupant = toad #added
|
|
passengers[toad].curr = (x[0], x[1])
|
|
toad += 1
|
|
for (i, man) in enumerate(passengers):
|
|
if man.curr == man.dest:
|
|
continue
|
|
if man.inter is not None and man.curr == man.inter:
|
|
man.shuffled = 3
|
|
man.inter = None
|
|
# man.recalc = True
|
|
if man.curr == (-1, -1):
|
|
continue
|
|
# if i == 36 and DEBUG:
|
|
# print(nextSquare(man, grid))
|
|
done=False
|
|
#im sexist
|
|
if len(man.path) == 0 or man.recalc:
|
|
# if DEBUG:
|
|
# print("Recalculating: " + str(man.curr))
|
|
nextSquare(man, grid)
|
|
|
|
nextS = man.path.pop()
|
|
|
|
if DEBUG:
|
|
print(str(man.curr) + ", " + str(man.interback) + ", " + str(man.dest) + ", " + str(nextS) + ", " + str(man.inter))
|
|
|
|
if passengers[i].shuffled == 0 and not ( grid[nextS[0]][nextS[1]].typ == SquareType.AISLE and grid[nextS[0]][nextS[1]].occupant is not None):
|
|
cp = man.curr
|
|
man.curr = nextS
|
|
other = grid[cp[0]][cp[1]]
|
|
other.occupant = grid[man.curr[0]][man.curr[1]].occupant #they move out of there
|
|
if other.occupant is not None:
|
|
passengers[other.occupant].curr = cp
|
|
passengers[other.occupant].shuffled = 5
|
|
passengers[other.occupant].recalc = True
|
|
man.recalc = True
|
|
grid[man.curr[0]][man.curr[1]].occupant = i
|
|
for man in passengers:
|
|
if man.shuffled != 0:
|
|
man.shuffled-=1
|
|
if DEBUG:
|
|
# time.sleep(1.0)
|
|
# time.sleep(0.5)
|
|
# time.sleep(0.1)
|
|
# time.sleep(0.05)
|
|
# time.sleep(0.02)
|
|
time.sleep(0.01)
|
|
# time.sleep(0.001)
|
|
os.system(clear)
|
|
if done and toad >= len(passengers):
|
|
print("Number of ticks: " + str(t))
|
|
time.sleep(10)
|
|
return -1
|
|
# exit()
|
|
return toad
|
|
|
|
def run():
|
|
toad = 0
|
|
t = 0
|
|
while toad != -1:
|
|
toad = tick(t,toad)
|
|
t += 1
|
|
|
|
def main():
|
|
global passengers
|
|
global tiles
|
|
#boarding order
|
|
|
|
startSeed=43
|
|
for seediter in range(startSeed,2000):
|
|
if seediter != startSeed:
|
|
tiles = []
|
|
passengers = GenPassList()
|
|
print("Seed: " + str(seediter))
|
|
rnd.seed(seediter)
|
|
# passengers.reverse()
|
|
rnd.shuffle(passengers)
|
|
run()
|
|
|
|
def execute():
|
|
th1 = threading.Thread(target=main);
|
|
th1.daemon = True;
|
|
th1.start();
|
|
|
|
# ========================================================================================================================================
|
|
# GUI IMPLEMENTATION
|
|
if graphical:
|
|
import tkinter as tk;
|
|
from tkinter import ttk;
|
|
import tkinter.constants as const;
|
|
from PIL import ImageTk, Image;
|
|
import threading;
|
|
|
|
imgs = [];
|
|
|
|
class Tile:
|
|
def __init__(self, r, w, h, x, y, occ, typ, name="--"):
|
|
global imgSpacing
|
|
self.occ = occ;
|
|
self.typ = typ;
|
|
self.img = None;
|
|
if self.typ == SquareType.AISLE or self.typ == SquareType.WALL:
|
|
self.name = "█";
|
|
if self.typ == SquareType.WALL:
|
|
self.img = seatImg
|
|
else:
|
|
self.img = imgs[self.occ];
|
|
else:
|
|
self.name = name;
|
|
self.frame = ttk.LabelFrame(root, text=self.name, width=w, height=h);
|
|
self.frame.place(x = x * imageDims[0], y = y * (imageDims[1] + imgSpacing));
|
|
self.panel = ttk.Label(self.frame, image=self.img);
|
|
self.panel.pack(side = "top", fill = "both", expand = "yes")
|
|
def __str__(self):
|
|
return f"{self.name}|{self.occ}|{self.typ}|{self.img}";
|
|
def Update(self, occ, typ=None):
|
|
self.occ = occ;
|
|
if typ != None:
|
|
self.typ = typ;
|
|
if self.typ == SquareType.AISLE:
|
|
self.panel.configure(image=imgs[0]);
|
|
elif self.typ == SquareType.WALL:
|
|
self.panel.configure(image=ImageTk.PhotoImage(Image.open(resource_path("imgs/wall.png"))));
|
|
else:
|
|
self.panel.configure(image=imgs[self.occ]);
|
|
|
|
if __name__ == "__main__":
|
|
if graphical:
|
|
Dims();
|
|
|
|
# Create the window
|
|
root = tk.Tk();
|
|
root.title('IMMC 2022');
|
|
#root.iconbitmap(resource_path("icon.ico"));
|
|
#root.resizable(0, 0);
|
|
|
|
# Place the window in the center of the screen
|
|
windowWidth = width * imageDims[0] + 10;#was 510
|
|
windowHeight = height * (imageDims[1] + imgSpacing) + 10; # was 332
|
|
screenWidth = root.winfo_screenwidth();
|
|
screenHeight = root.winfo_screenheight();
|
|
xCordinate = int((screenWidth/2) - (windowWidth/2));
|
|
yCordinate = int((screenHeight/2) - (windowHeight/2));
|
|
root.geometry("{}x{}+{}+{}".format(windowWidth, windowHeight, xCordinate, yCordinate));
|
|
|
|
# Create a style
|
|
style = ttk.Style(root);
|
|
style.configure("Button", background="red");
|
|
style.map('Button', background=[('active','red')]);
|
|
# Import the tcl file
|
|
root.tk.call('source', resource_path('theme/dark.tcl'));
|
|
# Set the theme with the theme_use method
|
|
style.theme_use('azure-dark');
|
|
|
|
seatImg = ImageTk.PhotoImage(Image.open(resource_path("imgs/wall.png")));
|
|
imgs = [ImageTk.PhotoImage(Image.open(resource_path("imgs/occ0.png"))), ImageTk.PhotoImage(Image.open(resource_path("imgs/occ1.png")))]
|
|
|
|
accentbutton_engage = ttk.Button(root, text='Start', style='Accent.TButton', command=execute);
|
|
accentbutton_engage.place(x=0, y=0);
|
|
|
|
root.mainloop();
|
|
else:
|
|
main()
|