######################################################################## # A class implementing and displating a 2D grid where the breadth-first, # depth-first, A*, and other search algorithms can be implemented. # Author: Dana Vrajitoru # Class: IUSB, C463/B551/I400 ######################################################################## import tkinter as tk from random import * from time import * # A class handling a searchable 2D grid class Grid: # static attributes wall = 0 space = 1 goal = 2 width = 800 height = 600 # constructor with number of rows and columns def __init__(self, rows, cols): self.app = None self.canvas = None self.cell_size = min([(Grid.height-20) // (rows+2), \ (Grid.width-20) // (cols+2)]) self.table = [] self.padr = self.padc = 0 self.target = None for i in range(rows): row = [Grid.wall for j in range(cols)] self.table.append(row) self.padr = (Grid.height - self.x(rows+1)) // 2 self.padc = (Grid.width - self.y(cols+1)) // 2 # Returns the number of rows in the table def rows(self): return len(self.table) # Returns the number of rows in the table def cols(self): if len(self.table): return len(self.table[0]) else: return 0 # Re-initializes the table with random values, with the parameter # being the percentage of spaces. It also places the target at a random # position and the player in the middle of the table. def randomize(self, percent = 0.6): for r in range(self.rows()): for c in range(self.cols()): if random() <= percent: self.table[r][c] = Grid.space else: self.table[r][c] = Grid.wall # set the target self.target = (randint(0, self.rows()-1), randint(0, self.cols()-1)) self.table[self.target[0]][self.target[1]] = Grid.goal # Place the player self.player_pos = [self.rows()//2, self.cols()//2] print(self.table) # Randomizes the table and redraws it. def randomize_draw(self): # clear the area self.canvas.delete("all") self.randomize() self.draw_grid() self.label.configure(text="Grid Exploration") # Converts a number of columns into an x position on the canvas def x(self, col): return self.padc + self.cell_size * (col + 1) # Converts a number of rows into a y position on the canvas def y(self, row): return self.padr + self.cell_size * (row + 1) # Draws the grid on the canvas: a big dark blue block for the overall, # and small light blue squares for the spaces. def draw_grid(self): cell = self.cell_size width = cell * (self.cols() + 2) height = cell * (self.rows() + 2) # the big square covering everything self.canvas.create_rectangle(self.x(-1), self.y(-1), self.x(self.cols()+1), \ self.y(self.rows()+1), fill="darkblue", \ outline="green", width=1) for r in range(self.rows()): for c in range(self.cols()): # add squares for the spaces and the target if self.table[r][c] == Grid.space: self.canvas.create_rectangle(self.x(c), self.y(r), self.x(c+1), self.y(r+1), \ fill="lightblue", outline="blue", width=1) elif self.table[r][c] == Grid.goal: self.canvas.create_rectangle(self.x(c), self.y(r), self.x(c+1), self.y(r+1), \ fill="red", outline="blue", width=1) self.draw_player() # Draws the player at the current position as a yellow circle with a black border def draw_player(self): r = self.player_pos[0] c = self.player_pos[1] self.player = self.canvas.create_oval(self.x(c), self.y(r), self.x(c+1), self.y(r+1), \ fill="yellow", outline="black", width=2) # Moves the player to a new row and column. Updates the coordinates of the # circle on the canvas, and the position stored in the Grid object. def place_player(self, r, c): self.canvas.coords(self.player, self.x(c), self.y(r), self.x(c+1), self.y(r+1)) self.player_pos = (r, c) # Places the player back to the center of the table def reset_player(self): self.place_player(self.rows()//2, self.cols()//2) self.label.configure(text="Grid Exploration") # Moves the player up if possible and return True if possible. def move_up(self): r = self.player_pos[0] c = self.player_pos[1] if r > 0 and (self.table[r-1][c] == Grid.space or \ self.table[r-1][c] == Grid.goal): self.place_player(r-1, c) return True else: return False # Returns a list of all the neighbors of a cell that are either spaces or \ # the goal. The neighbors are stored as tuples of (row, column). def neighbors(self, r, c): n = [] if r > 0 and (self.table[r-1][c] == Grid.space or \ self.table[r-1][c] == Grid.goal): n.append((r-1, c)) return n # Checks if the player's current position coincides with the target. # If yes, it updates the label at the bottom. def target_check(self): rp = self.player_pos[0] cp = self.player_pos[1] rt = self.target[0] ct = self.target[1] if rp == rt and cp == ct: self.label.configure(text="Target found") return True else: return False # Handles keyboard input from the user, mostly the WASD keys for walking def key_press(self, event): if event.char == 'w' or event.char == 'W': self.move_up() self.target_check() # Creates the window in tkinter and adds all the elements to it def open_window(self): # Create the window self.app = tk.Tk() self.app.title("Maze Traversal") # Create a frame to contain the buttons frame = tk.Frame(self.app, borderwidth=2, relief="groove") frame.pack() # Add the buttons with left alignment so they all show in a row button1 = tk.Button(frame, text="Randomize", command=self.randomize_draw) button1.pack(side='left') button2 = tk.Button(frame, text="Reset Player", command=self.reset_player) button2.pack(side='left') button3 = tk.Button(frame, text="Breadth First", command=self.breadth_first_search) button3.pack(side='left') # Add a canvas for displaying the grid self.canvas = tk.Canvas(self.app, width=Grid.width, height=Grid.height, \ bg="lightblue", bd=2, relief="sunken") self.canvas.pack(pady=5, padx=5) self.draw_grid() # Add key movements for k in ('w', 'W'): self.app.bind(k, self.key_press) # Add a label where we can display some text for the user self.label = tk.Label(self.app, text="Grid exploration") self.label.pack() def print_path(self, parent): path = [self.target] state = self.target # start from the end point while parent[state] != (-1, -1): state = parent[state] path.insert(0, state) # insert this state at the beginning self.label.configure(text="Target found. Path: " + str(path)) return path # Search for the target from the player's current position # in a breadth-first order. def breadth_first_search(self): #add initial position to the queue initialr = self.player_pos[0] initialc = self.player_pos[1] flagged = {(initialr, initialc): True} # flag previously seen states parent = {(initialr, initialc): (-1, -1)} # store the state's parent in the search tree queue = [(initialr, initialc)] # this is the open list of states to be expanded while queue: pos = queue[0] # front of the queue queue.remove(pos) self.place_player(pos[0], pos[1]) self.app.update() # refresh the window sleep(0.5) # delay by half a second # if we found the target, end the search if self.target_check(): self.print_path(parent) return True children = self.neighbors(pos[0], pos[1]) for child in children: if not child in flagged.keys(): parent[child] = pos flagged[child] = True queue.append(child) # if the loop ended without finding the target self.label.configure(text="Target not found") return False if __name__ == '__main__': g = Grid(10, 10) g.randomize(0.65) g.open_window() g.app.mainloop()