we can find the path using bfs(blue) and astar(yellow) from tkinter import * import time import random
print(random.randint(0, 9)) window = Tk() window.title("Misbah")
uncomment at Walls, rows, randomwalls
Walls = [] rows = 30 cols = 30 player = (0, 0) end = (cols-2, rows-2)
random walls creation
for i in range(cols): for j in range(rows): if random.randint(0, 9) < 2 and (i, j) not in player and (i, j) not in end: Walls.append((i, j))
Walls = [(1,0),(1,1),(1,2,),(1,3),(1,4),(1,5),(1,7),(1,8),(3,1),(3,2),(3,3),(3,4),(3,5),(3,7),(4,1),(4,3),(4,5),(4,7),(5,1),(5,3),(5,5),(5,6),(5,7),(6,5),(6,7),(7,0),(7,1),(7,2),(7,3),(7,5),(7,7)]
rows = 9
cols = 9
player = (0, 0)
end = (4, 2)
width to set inner-square size
Width = 500/rows
platform = Canvas(window, width=cols*Width, height=rows*Width) platform.pack()
def render_grid(): global rows, cols, Width, player, end for i in range(cols): for j in range(rows): platform.create_rectangle( i*Width, j*Width, (i+1)*Width, (j+1)*Width, fill="white", width=1)
platform.create_rectangle(player[0]*Width, player[1]*Width,
(player[0]+1)*Width, (player[1]+1)*Width, fill="blue", width=1)
platform.create_rectangle(
end[0]*Width, end[1]*Width, (end[0]+1)*Width, (end[1]+1)*Width, fill="green", width=1)
for (i, j) in Walls:
platform.create_rectangle(
i*Width, j*Width, (i+1)*Width, (j+1)*Width, fill="black", width=1)
render_grid()
def render_path(path,color): global Width for (i, j) in path: platform.create_rectangle( i*Width, j*Width, (i+1)*Width, (j+1)*Width, fill=color, width=1) time.sleep(0.1)
def start_game(): window.mainloop()
my.py:
import Board import threading import heapq from collections import deque
class SquareGrid: def init(self, width, height): self.width = width self.height = height self.walls = []
def in_bounds(self, id):
(x, y) = id
return 0 <= x < self.width and 0 <= y < self.height
def passable(self, id):
return id not in self.walls
def neighbors(self, id):
(x, y) = id
results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)]
if (x + y) % 2 == 0:
results.reverse() # aesthetics
results = filter(self.passable, results)
results = filter(self.in_bounds, results)
return results
def depth_first_neighbors(self, id):
(x, y) = id
results = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
if (x + y) % 2 == 0:
results.reverse() # aesthetics
results = filter(self.in_bounds, results)
results = filter(self.passable, results)
return results
def cost(self, from_node, to_node):
return 1
rows = Board.rows cols = Board.cols Width = Board.Width start = Board.player goal = Board.end
start, goal = (0, 0), (3, 2)
diagram1 =SquareGrid(cols, rows)
[(1, 2), (1, 7), (1, 8), (2, 7), (2, 8), (3, 7), (3, 8)]
diagram1.walls = Board.Walls
class PriorityQueue: def init(self): self.elements = []
def empty(self):
return len(self.elements) == 0
def put(self, item, priority):
heapq.heappush(self.elements, (priority, item))
def get(self):
return heapq.heappop(self.elements)[1]
def heuristic(a, b): (x1, y1) = a (x2, y2) = b return abs(x1 - x2) + abs(y1 - y2)
def a_star_search(graph, start, goal): openLoop = PriorityQueue() openLoop.put(start, 0) closedLoop = [] came_from = {} cost_so_far = {} cost_so_far[start] = 0 came_from[start] = None
while not openLoop.empty():
current = openLoop.get()
#print ("current = ", current)
if current == goal:
print("goal reached")
break
for next in graph.neighbors(current):
tentative_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or tentative_cost < cost_so_far[next]:
cost_so_far[next] = tentative_cost
priority = tentative_cost = heuristic(goal, next)
openLoop.put(next, priority)
came_from[next] = current
return came_from, cost_so_far
def bfs_search(graph,start,goal): openLoop = PriorityQueue() openLoop.put(start, 0) closedLoop = [] came_from = {} cost_so_far = {} cost_so_far[start] = 0 came_from[start] = None
while not openLoop.empty():
current = openLoop.get()
#print ("current = ", current)
if current == goal:
print("goal reached")
break
for next in graph.neighbors(current):
tentative_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or tentative_cost < cost_so_far[next]:
cost_so_far[next] = tentative_cost
# priority = tentative_cost = heuristic(goal, next)
priority = tentative_cost
openLoop.put(next, priority)
came_from[next] = current
return came_from, cost_so_far
def reconstruct_path(came_from, start, goal): current = goal path = [] while current != start: path.append(current) current = came_from[current] path.append(start) path.reverse() return path
came_from_bs, cost_so_far = bfs_search(diagram1, start, goal) total_path_bs = reconstruct_path(came_from_bs, start, goal)
came_from_a_star, cost_so_far3 = a_star_search(diagram1, start, goal) total_path_a_star = reconstruct_path(came_from_a_star, start, goal)
print (total_path)
def run(): global total_path_bs,total_path_ds,total_path_a_search Board.render_path(total_path_bs,"blue") Board.render_path(total_path_a_star,"yellow")
t = threading.Thread(target=run) t.daemon = True t.start() Board.start_game()
Log in or sign up for Devpost to join the conversation.