Path Finder.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### -Arjun Balamwar C11 1902012"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pygame 2.0.1 (SDL 2.0.14, Python 3.8.5)\n",
      "Hello from the pygame community. https://www.pygame.org/contribute.html\n"
     ]
    }
   ],
   "source": [
    "import pygame\n",
    "from queue import PriorityQueue\n",
    "import time\n",
    "import numpy as np\n",
    "import functools\n",
    "from numba import jit\n",
    "import threading"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "RED = (255, 0, 0)\n",
    "GREEN = (0, 255, 0)\n",
    "BLUE = (0, 0, 255)\n",
    "WHITE = (255, 255, 255)\n",
    "BLACK = (0, 0, 0)\n",
    "BROWN = (133, 2, 1)\n",
    "VISIT1 = (0, 255, 230)\n",
    "VISIT2 = (0, 80, 230)\n",
    "VISIT3 = (1, 106, 106)\n",
    "LOOK = (0, 255, 164)\n",
    "START = (217, 1, 183)\n",
    "END = RED\n",
    "GREY = (63, 63, 63)\n",
    "OPEN = (0, 255, 149)\n",
    "OPEN1 = (0, 106, 0)\n",
    "PATH1 = (255, 200, 0)\n",
    "PATH2 = (255, 254, 0)\n",
    "PATH3 = (0, 200, 0)\n",
    "BG_COLOR = (6, 69, 96)\n",
    "BUTTON_COLOR = (19, 175, 240)\n",
    "SCREEN_COLOR = (204, 230, 255)\n",
    "VISITED = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, row, col, width, total_rows):\n",
    "        self.last = pygame.time.get_ticks()\n",
    "        self.cooldown = 300 \n",
    "        self.row = row\n",
    "        self.col = col\n",
    "        self.x = row*width\n",
    "        self.y = col*width\n",
    "        self.color = WHITE\n",
    "        self.neighbors = []\n",
    "        self.width = width\n",
    "        self.total_rows = total_rows\n",
    "        self.dec_animation = False\n",
    "        self.weight = False\n",
    "        \n",
    "    def get_pos(self):\n",
    "        return self.row, self.col\n",
    "    \n",
    "    def is_visited(self):\n",
    "        return self.color == VISIT1\n",
    "    \n",
    "    def is_open(self):\n",
    "        return self.color == OPEN\n",
    "    \n",
    "    def is_barrier(self):\n",
    "        return self.color == BLACK\n",
    "    \n",
    "    def is_weight(self):\n",
    "        return self.weight\n",
    "    \n",
    "    def is_start(self):\n",
    "        return self.color == START\n",
    "    \n",
    "    def is_end(self):\n",
    "        return self.color == END\n",
    "    \n",
    "    def is_neutral(self):\n",
    "        return self.color == WHITE\n",
    "    \n",
    "    def is_looked(self):\n",
    "        return self.color == LOOK\n",
    "    \n",
    "    def reset(self):\n",
    "        self.color = WHITE\n",
    "        self.weight = False\n",
    "    \n",
    "    def make_visit(self):\n",
    "        if not self.is_weight():\n",
    "            self.color = VISIT2\n",
    "        else:\n",
    "            self.color = VISIT3\n",
    "        \n",
    "        \n",
    "    def make_open(self):\n",
    "        if not self.is_weight():\n",
    "            self.color = OPEN\n",
    "        else:\n",
    "            self.color = OPEN1\n",
    "    \n",
    "    def make_barrier(self):\n",
    "        if not self.is_start() and not self.is_end():\n",
    "            self.color = BLACK\n",
    "            self.weight = False\n",
    "            \n",
    "    def make_weight(self):\n",
    "        if not self.is_start() and not self.is_end():\n",
    "            self.color = BROWN\n",
    "            self.weight = True\n",
    "    \n",
    "    def make_end(self):\n",
    "        self.color = END\n",
    "        self.weight = False\n",
    "    \n",
    "    def make_start(self):\n",
    "        self.color = START\n",
    "        self.weight = False\n",
    "        \n",
    "    def make_path(self):\n",
    "        if not self.is_weight():\n",
    "            self.color = PATH1\n",
    "        else:\n",
    "            self.color = PATH3\n",
    "    \n",
    "    def looking_at(self):\n",
    "        self.color = LOOK\n",
    "    \n",
    "    def draw(self, win):\n",
    "        try:\n",
    "            pygame.draw.rect(win, self.color, (self.x, self.y, self.width, self.width))\n",
    "        except:\n",
    "            print(self.color)\n",
    "            input()\n",
    "#             pygame.draw.rect(win, WHITE, (self.x, self.y, self.width, self.width))\n",
    "\n",
    "    def update_neighbors(self, grid, diag = False):\n",
    "        r = self.row \n",
    "        c = self.col\n",
    "        if r < self.total_rows-1 and not grid[r+1][c].is_barrier():\n",
    "            self.neighbors.append(grid[r+1][c])\n",
    "            \n",
    "        if r > 0 and not grid[r-1][c].is_barrier():\n",
    "            self.neighbors.append(grid[r-1][c])\n",
    "            \n",
    "        if c < self.total_rows-1 and not grid[r][c+1].is_barrier():\n",
    "            self.neighbors.append(grid[r][c+1])\n",
    "            \n",
    "        if c > 0 and not grid[r][c-1].is_barrier():\n",
    "            self.neighbors.append(grid[r][c-1])\n",
    "        \n",
    "        if diag:\n",
    "            if r < self.total_rows-1 and c < self.total_rows-1 and not grid[r+1][c+1].is_barrier():\n",
    "                self.neighbors.append(grid[r+1][c+1])\n",
    "\n",
    "            if r > 0 and c < self.total_rows-1 and not grid[r-1][c+1].is_barrier():\n",
    "                self.neighbors.append(grid[r-1][c+1])\n",
    "\n",
    "            if r > 0 and c > 0 and not grid[r-1][c-1].is_barrier():\n",
    "                self.neighbors.append(grid[r-1][c-1])\n",
    "\n",
    "            if r < self.total_rows-1 and c > 0 and not grid[r+1][c-1].is_barrier():\n",
    "                self.neighbors.append(grid[r+1][c-1])\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class button():\n",
    "    def __init__(self, x, y,width,height, text=''):\n",
    "        self.color = BUTTON_COLOR\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.width = width\n",
    "        self.height = height\n",
    "        self.text = text\n",
    "\n",
    "    def draw(self,win,outline=None):\n",
    "        #Call this method to draw the button on the screen\n",
    "        if outline:\n",
    "            pygame.draw.rect(win, outline, (self.x-2,self.y-2,self.width+4,self.height+4),0)\n",
    "            pygame.draw.circle(win, outline, (self.x, self.y+self.height//2), self.height//2+2)\n",
    "            pygame.draw.circle(win, outline, (self.x+self.width, self.y+self.height//2), self.height//2+2)\n",
    "            \n",
    "        pygame.draw.rect(win, self.color, (self.x,self.y,self.width,self.height),0)\n",
    "        pygame.draw.circle(win, self.color, (self.x, self.y+self.height//2), self.height//2)\n",
    "        pygame.draw.circle(win, self.color, (self.x+self.width, self.y+self.height//2), self.height//2)\n",
    "        \n",
    "        if self.text != '':\n",
    "            font = pygame.font.SysFont('comicsans', 35)\n",
    "            text = font.render(self.text, 1, (0,0,0))\n",
    "            win.blit(text, (self.x + (self.width/2 - text.get_width()/2), self.y + (self.height/2 - text.get_height()/2)))\n",
    "\n",
    "    def is_hover(self, pos):\n",
    "        #Pos is the mouse position or a tuple of (x,y) coordinates\n",
    "        if pos[0] > self.x-self.height//2 and pos[0] < self.x + self.width+self.height//2:\n",
    "            if pos[1] > self.y and pos[1] < self.y + self.height:\n",
    "                return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class screen():\n",
    "    def __init__(self, x,y,width,height, text=''):\n",
    "        self.color = SCREEN_COLOR\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.width = width\n",
    "        self.height = height\n",
    "        self.label1 = \"\"\n",
    "        self.text1 = text\n",
    "        self.text2 = \"\"\n",
    "        self.text3 = \"\"\n",
    "        \n",
    "    def set_label1(self, label):\n",
    "        self.label1 = label\n",
    "    \n",
    "    def set_text1(self, text):\n",
    "        self.text1 = text\n",
    "    def set_text2(self, text):\n",
    "        self.text2 = text\n",
    "    def set_text3(self, text):\n",
    "        self.text3 = text\n",
    "        \n",
    "    def get_text1(self):\n",
    "        return self.text1\n",
    "\n",
    "    def draw(self,win,outline=None):\n",
    "        #Call this method to draw the button on the screen\n",
    "        if outline:\n",
    "            pygame.draw.rect(win, outline, (self.x-2,self.y-2,self.width+4,self.height+4),0)\n",
    "            \n",
    "        pygame.draw.rect(win, self.color, (self.x,self.y,self.width,self.height),0)\n",
    "        \n",
    "        if self.label1 != '':\n",
    "            font = pygame.font.SysFont('comicsans', 20)\n",
    "            label = font.render(self.label1, 1, (0,0,0))\n",
    "            win.blit(label, (self.x + 10, self.y + 10))\n",
    "        \n",
    "        if self.text1 != '':\n",
    "            font = pygame.font.SysFont('comicsans', 30)\n",
    "            text = font.render(self.text1, 1, (0,0,0))\n",
    "            win.blit(text, (self.x + (self.width/2 - text.get_width()/2), self.y + (self.height/2 - text.get_height()/2) - 50))\n",
    "        if self.text2 != '':\n",
    "            font = pygame.font.SysFont('comicsans', 30)\n",
    "            text = font.render(self.text2, 1, (0,0,0))\n",
    "            win.blit(text, (self.x + (self.width/2 - text.get_width()/2), self.y + (self.height/2 - text.get_height()/2)))\n",
    "        if self.text3 != '':\n",
    "            font = pygame.font.SysFont('comicsans', 30)\n",
    "            text = font.render(self.text3, 1, (0,0,0))\n",
    "            win.blit(text, (self.x + (self.width/2 - text.get_width()/2), 50 + self.y + (self.height/2 - text.get_height()/2)))\n",
    "\n",
    "    def is_hover(self, pos):\n",
    "        #Pos is the mouse position or a tuple of (x,y) coordinates\n",
    "        if pos[0] > self.x and pos[0] < self.x + self.width:\n",
    "            if pos[1] > self.y and pos[1] < self.y + self.height:\n",
    "                return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def h(p1, p2):\n",
    "    x1, y1 = p1\n",
    "    x2, y2 = p2\n",
    "    return abs(x1 - x2) + abs(y1 - y2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def visit_animation2(node):\n",
    "    if node.color == VISIT1:\n",
    "        return True\n",
    "    else:\n",
    "        r, g, b = node.color\n",
    "        b += 1\n",
    "        node.color = (r, g, b)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def visit_animation(visited):\n",
    "    for node in visited:\n",
    "        if node.color == VISIT1 or node.color == VISIT3:\n",
    "            visited.remove(node)\n",
    "            continue\n",
    "        r, g, b = node.color\n",
    "        if g < 255:\n",
    "            g += 1\n",
    "        node.color = (r, g, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# def visit_animation(visited):\n",
    "#     for node in visited:\n",
    "#         if node.color[1] == 255:\n",
    "#             if visit_animation2(node):\n",
    "#                 visited.remove(node)\n",
    "#         else:\n",
    "#             r, g, b = node.color\n",
    "#             g += 1\n",
    "#             b-=1\n",
    "#             node.color = (r, g, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def path_animation(path):\n",
    "    for node in path:\n",
    "        if not node.is_start():\n",
    "            r, g, b = node.color\n",
    "            if node.dec_animation:\n",
    "                g -= 1\n",
    "                if g <= PATH1[1]:\n",
    "                    node.dec_animation = False\n",
    "            else:\n",
    "                g += 1\n",
    "                if g >= PATH2[1]:\n",
    "                    node.dec_animation = True\n",
    "        node.color = (r, g, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reconstruct_path(came_from, start, current, draw, visited,  win, width, grid, is_draw = True):\n",
    "    path = []\n",
    "    c = 0\n",
    "    while current in came_from:\n",
    "        visit_animation(visited)\n",
    "        current = came_from[current]\n",
    "        if current.is_weight():\n",
    "            c+= 5\n",
    "        else:\n",
    "            c+=1\n",
    "        if current in visited:\n",
    "            visited.remove(current)\n",
    "        if current != start:\n",
    "            path.insert(0, current)\n",
    "        current.make_path()\n",
    "#         path_animation(path)\n",
    "        if is_draw:\n",
    "            for rows in grid:\n",
    "                for node in rows:\n",
    "                    node.draw(win)\n",
    "            draw_grid(win, len(grid), width)\n",
    "            pygame.display.update()\n",
    "    return path, c-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def A_star(draw, grid, start, end, output, win, width):\n",
    "    count = 0\n",
    "    vis = 0\n",
    "    open_set = PriorityQueue()\n",
    "    open_set.put((0, count, start))\n",
    "    came_from = {}\n",
    "    g_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "    g_score[start] = 0\n",
    "    f_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "    f_score[start] = h(start.get_pos(), end.get_pos())\n",
    "    visited = []\n",
    "    nebrs = []\n",
    "    \n",
    "    open_set_hash = {start}\n",
    "    \n",
    "    while not open_set.empty():\n",
    "#         li = [i for i in end.neighbors if i.is_neutral()]\n",
    "#         if len(li):\n",
    "#             end.reset()\n",
    "#             end = li[np.random.randint(len(li))]\n",
    "#             end.make_end()\n",
    "        for event in pygame.event.get():\n",
    "            if event.type == pygame.QUIT:\n",
    "                pygame.quit()\n",
    "        \n",
    "        current = open_set.get()[2]\n",
    "        open_set_hash.remove(current)\n",
    "        \n",
    "        if current == end:\n",
    "            path, inc = reconstruct_path(came_from, start, end, draw, visited, win, width, grid)\n",
    "            start.make_start()\n",
    "            output.set_text1(f\"Path Length: {inc}\")\n",
    "            output.set_text2(f\"#Visited nodes: {vis}\")\n",
    "            if vis != 0:\n",
    "                output.set_text3(f\"Efficiency: {np.round(inc/vis, decimals=3)}\")\n",
    "            return visited, path\n",
    "        c = 1      \n",
    "        for neighbor in current.neighbors:\n",
    "            if not neighbor.is_barrier():\n",
    "                if neighbor.is_weight():\n",
    "                    c = 5\n",
    "\n",
    "                temp_g_score = g_score[current] + c\n",
    "                temp_f_score = temp_g_score + h(neighbor.get_pos(), end.get_pos())\n",
    "                if temp_g_score < g_score[neighbor]:\n",
    "                    came_from[neighbor] = current\n",
    "                    g_score[neighbor] = temp_g_score\n",
    "                    f_score[neighbor] = temp_f_score\n",
    "                    if neighbor not in open_set_hash:\n",
    "                        count+=1\n",
    "                        open_set.put((f_score[neighbor], count, neighbor))\n",
    "                        open_set_hash.add(neighbor)\n",
    "                    if neighbor != end:\n",
    "                        nebrs.append(neighbor)\n",
    "                        neighbor.make_open()\n",
    "        \n",
    "        if current != start:\n",
    "            vis+=c\n",
    "            visited.append(current)\n",
    "            current.make_visit()\n",
    "#         t = Thread(target = functionname, [args = (arg1, arg2, ...)]\n",
    "        visit_animation(visited)\n",
    "#         nebr_animation(nebrs)\n",
    "        for rows in grid:\n",
    "            for node in rows:\n",
    "                node.draw(win)\n",
    "        draw_grid(win, len(grid), width)\n",
    "        pygame.display.update()\n",
    "            \n",
    "    return visited, False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def A_star_active(draw, grid, start, end, output, win, width):\n",
    "    count = 0\n",
    "    vis = 0\n",
    "    open_set = PriorityQueue()\n",
    "    open_set.put((0, count, start))\n",
    "    came_from = {}\n",
    "    g_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "    g_score[start] = 0\n",
    "    f_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "    f_score[start] = h(start.get_pos(), end.get_pos())\n",
    "    visited = []\n",
    "    nebrs = []\n",
    "    \n",
    "    open_set_hash = {start}\n",
    "    \n",
    "    while not open_set.empty():\n",
    "#         li = [i for i in end.neighbors if i.is_neutral()]\n",
    "#         if len(li):\n",
    "#             end.reset()\n",
    "#             end = li[np.random.randint(len(li))]\n",
    "#             end.make_end()\n",
    "        for event in pygame.event.get():\n",
    "            if event.type == pygame.QUIT:\n",
    "                pygame.quit()\n",
    "        \n",
    "        current = open_set.get()[2]\n",
    "        open_set_hash.remove(current)\n",
    "        \n",
    "        if current == end:\n",
    "            path, inc = reconstruct_path(came_from, start, end, draw, visited, win, width, grid)\n",
    "            start.make_start()\n",
    "            output.set_text1(f\"Path Length: {inc}\")\n",
    "            output.set_text2(f\"#Visited nodes: {vis}\")\n",
    "            if vis != 0:\n",
    "                output.set_text3(f\"Efficiency: {np.round(inc/vis, decimals=3)}\")\n",
    "            return visited, path\n",
    "        \n",
    "        c = 1\n",
    "        for neighbor in current.neighbors:\n",
    "            if not neighbor.is_barrier():\n",
    "                if neighbor.is_weight():\n",
    "                    c = 5\n",
    "\n",
    "                temp_g_score = g_score[current] + c\n",
    "                temp_f_score = temp_g_score + h(neighbor.get_pos(), end.get_pos())\n",
    "                if temp_g_score < g_score[neighbor]:\n",
    "                    came_from[neighbor] = current\n",
    "                    g_score[neighbor] = temp_g_score\n",
    "                    f_score[neighbor] = temp_f_score\n",
    "                    if neighbor not in open_set_hash:\n",
    "                        count+=1\n",
    "                        open_set.put((f_score[neighbor], count, neighbor))\n",
    "                        open_set_hash.add(neighbor)\n",
    "                    if neighbor != end:\n",
    "                        nebrs.append(neighbor)\n",
    "                        neighbor.make_open()\n",
    "        \n",
    "        if current != start:\n",
    "            vis+=c\n",
    "            visited.append(current)\n",
    "            current.make_visit()\n",
    "#         t = Thread(target = functionname, [args = (arg1, arg2, ...)]\n",
    "        visit_animation(visited)\n",
    "#         nebr_animation(nebrs)\n",
    "            \n",
    "    return visited, False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def moded_A_star(draw, grid, start, end, output, win, width, moving_target=False):\n",
    "    count = 0\n",
    "    vis = 0\n",
    "    open_set = PriorityQueue()\n",
    "    open_set.put((0, count, start))\n",
    "    came_from = {}\n",
    "    g_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "    g_score[start] = 0\n",
    "    f_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "    f_score[start] = h(start.get_pos(), end.get_pos())\n",
    "    start_cost = h(start.get_pos(), end.get_pos())\n",
    "    \n",
    "    visited = []\n",
    "    nebrs = []\n",
    "    \n",
    "    open_set_hash = {start}\n",
    "    \n",
    "    while not open_set.empty():\n",
    "        if moving_target:\n",
    "            li = [i for i in end.neighbors if i.is_neutral()]\n",
    "            if len(li):\n",
    "                end.reset()\n",
    "                end = li[np.random.randint(len(li))]\n",
    "                end.make_end()\n",
    "                for rows in grid:\n",
    "                    for node in rows:\n",
    "                        node.draw(win)\n",
    "                        draw_grid(win, len(grid), width)\n",
    "                        pygame.display.update()\n",
    "        for event in pygame.event.get():\n",
    "            if event.type == pygame.QUIT:\n",
    "                pygame.quit()\n",
    "        \n",
    "        current = open_set.get()[2]\n",
    "        open_set_hash.remove(current)\n",
    "        \n",
    "        if current == end:\n",
    "            path, inc = reconstruct_path(came_from, start, end, draw, visited, win, width, grid)\n",
    "            start.make_start()\n",
    "            output.set_text1(f\"Path Length: {inc}\")\n",
    "            output.set_text2(f\"#Visited nodes: {vis}\")\n",
    "            if vis != 0:\n",
    "                output.set_text3(f\"Efficiency: {np.round(inc/vis, decimals=3)}\")\n",
    "            return visited, path\n",
    "        \n",
    "        c = 1\n",
    "        for neighbor in current.neighbors:\n",
    "            if not neighbor.is_barrier() and (neighbor.is_neutral() or neighbor == end or neighbor.color == BROWN or neighbor.is_open()):\n",
    "                if neighbor.is_weight():\n",
    "                    c = 5\n",
    "                temp_g_score = g_score[current] + c\n",
    "                temp_f_score = (temp_g_score**(h(neighbor.get_pos(), end.get_pos())*temp_g_score))\n",
    "                if temp_f_score < f_score[neighbor]:\n",
    "                    came_from[neighbor] = current\n",
    "                    g_score[neighbor] = temp_g_score\n",
    "                    f_score[neighbor] = temp_f_score\n",
    "                    if neighbor not in open_set_hash:\n",
    "                        count+=1\n",
    "                        open_set.put((f_score[neighbor], count, neighbor))\n",
    "                        open_set_hash.add(neighbor)\n",
    "                        if neighbor != end:\n",
    "                            nebrs.append(neighbor)\n",
    "                            neighbor.make_open()\n",
    "\n",
    "        if current != start:\n",
    "            if current in visited:\n",
    "                visited.remove(current)\n",
    "            current.make_visit()\n",
    "            visited.append(current)\n",
    "            vis+=c\n",
    "\n",
    "        visit_animation(visited)\n",
    "#         nebr_animation(nebrs)\n",
    "        for rows in grid:\n",
    "            for node in rows:\n",
    "                node.draw(win)\n",
    "        draw_grid(win, len(grid), width)\n",
    "        pygame.display.update()\n",
    "            \n",
    "    return visited, False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bi_moded_A_star(draw, grid, start, end, output, win, width, moving_target=False):\n",
    "    count = 0\n",
    "    vis = 0\n",
    "    open_set_start = PriorityQueue()\n",
    "    open_set_start.put((0, count, start))\n",
    "    came_from_start = {}\n",
    "    open_set_end = PriorityQueue()\n",
    "    open_set_end.put((0, count, end))\n",
    "    came_from_end = {}\n",
    "    g_score_start = {node: float(\"inf\") for row in grid for node in row}\n",
    "    g_score_end = {node: float(\"inf\") for row in grid for node in row}\n",
    "    g_score_start[start] = 0\n",
    "    g_score_end[end] = 0\n",
    "    f_score_start = {node: float(\"inf\") for row in grid for node in row}\n",
    "    f_score_end = {node: float(\"inf\") for row in grid for node in row}\n",
    "    f_score_start[start] = h(start.get_pos(), end.get_pos())\n",
    "    f_score_end[end] = h(start.get_pos(), end.get_pos())\n",
    "    x1, y1 = start.get_pos()\n",
    "    x2, y2 = end.get_pos()\n",
    "    threshold = max((abs(x1-x2) + abs(y1-y2))//2, len(grid)//3)\n",
    "    lock = False\n",
    "    \n",
    "    visited1 = []\n",
    "    visited2 = []\n",
    "    nebrs = []\n",
    "    v1, v2 = [], []\n",
    "    \n",
    "    open_set_hash_start = {start}\n",
    "    open_set_hash_end = {end}\n",
    "    while len(open_set_hash_start) and len(open_set_hash_end):\n",
    "        if moving_target:\n",
    "            li = [i for i in end.neighbors if i.is_neutral()]\n",
    "            if len(li):\n",
    "                end.reset()\n",
    "                end = li[np.random.randint(len(li))]\n",
    "                end.make_end()\n",
    "                for rows in grid:\n",
    "                    for node in rows:\n",
    "                        node.draw(win)\n",
    "                        draw_grid(win, len(grid), width)\n",
    "                        pygame.display.update()\n",
    "        for event in pygame.event.get():\n",
    "            if event.type == pygame.QUIT:\n",
    "                pygame.quit()\n",
    "        \n",
    "        current = open_set_start.get()[2]\n",
    "        open_set_hash_start.remove(current)\n",
    "        \n",
    "        c = 1\n",
    "        for neighbor in current.neighbors:\n",
    "            if not neighbor.is_barrier():\n",
    "                if (neighbor.is_neutral() or neighbor.color == BROWN or neighbor.is_open()):\n",
    "                    if neighbor.is_weight():\n",
    "                        c = 5\n",
    "                    temp_g_score = g_score_start[current] + c\n",
    "                    temp_f_score = (temp_g_score**(h(neighbor.get_pos(), end.get_pos())*temp_g_score))\n",
    "                    if temp_f_score < f_score_start[neighbor]:\n",
    "                        came_from_start[neighbor] = current\n",
    "                        g_score_start[neighbor] = temp_g_score\n",
    "                        f_score_start[neighbor] = temp_f_score\n",
    "                        if neighbor not in open_set_hash_start:\n",
    "                            count+=1\n",
    "                            open_set_start.put((f_score_start[neighbor], count, neighbor))\n",
    "                            open_set_hash_start.add(neighbor)\n",
    "                            nebrs.append(neighbor)\n",
    "                            neighbor.make_open()\n",
    "                elif neighbor != start and neighbor not in v1:\n",
    "                    neighbor.color = (254, 102, 1)\n",
    "                    draw_grid(win, len(grid), width)\n",
    "                    pygame.display.update()\n",
    "                    came_from_start[neighbor] = current\n",
    "                    path1, inc1 = reconstruct_path(came_from_start, start, neighbor, draw, visited1, win, width, grid)\n",
    "                    start.make_start()\n",
    "                    path2, inc2 = reconstruct_path(came_from_end, end, neighbor, draw, visited1, win, width, grid)\n",
    "                    end.make_end()\n",
    "                    output.set_text1(f\"Path Length: {inc1+inc2+1}\")\n",
    "                    output.set_text2(f\"#Visited nodes: {vis}\")\n",
    "                    if vis != 0:\n",
    "                        output.set_text3(f\"Efficiency: {np.round((inc1+inc2+1+1)/vis, decimals=3)}\")\n",
    "                    return visited1+visited2, path1+path2\n",
    "        if current != start:\n",
    "            if current in visited1:\n",
    "                visited1.remove(current)\n",
    "            current.make_visit()\n",
    "            v1.append(current)\n",
    "            visited1.append(current)\n",
    "            vis+=c\n",
    "\n",
    "        visit_animation(visited1)\n",
    "#         nebr_animation(nebrs)\n",
    "        for rows in grid:\n",
    "            for node in rows:\n",
    "                node.draw(win)\n",
    "        draw_grid(win, len(grid), width)\n",
    "        pygame.display.update()\n",
    "        if not lock:\n",
    "            current = open_set_end.get()[2]\n",
    "            open_set_hash_end.remove(current)\n",
    "            if g_score_end[current] > threshold:\n",
    "                lock = True\n",
    "            c = 1\n",
    "            for neighbor in current.neighbors:\n",
    "                if not neighbor.is_barrier():\n",
    "                    if (neighbor.is_neutral() or neighbor.color == BROWN or neighbor.is_open()):\n",
    "                        if neighbor.is_weight():\n",
    "                            c = 5\n",
    "                        temp_g_score = g_score_end[current] + c\n",
    "                        temp_f_score = temp_g_score\n",
    "                        if temp_f_score < f_score_end[neighbor]:\n",
    "                            came_from_end[neighbor] = current\n",
    "                            g_score_end[neighbor] = temp_g_score\n",
    "                            f_score_end[neighbor] = temp_f_score\n",
    "                            if neighbor not in open_set_hash_end:\n",
    "                                count+=1\n",
    "                                open_set_end.put((f_score_end[neighbor], count, neighbor))\n",
    "                                open_set_hash_end.add(neighbor)\n",
    "                                nebrs.append(neighbor)\n",
    "                                neighbor.make_open()\n",
    "                    elif neighbor != end and neighbor not in v2:\n",
    "                        neighbor.color = (254, 102, 1)\n",
    "                        draw_grid(win, len(grid), width)\n",
    "                        pygame.display.update()\n",
    "                        came_from_end[neighbor] = current\n",
    "                        path1, inc1 = reconstruct_path(came_from_end, end, neighbor, draw, visited2, win, width, grid)\n",
    "                        end.make_end()\n",
    "                        path2, inc2 = reconstruct_path(came_from_start, start, neighbor, draw, visited2, win, width, grid)\n",
    "                        start.make_start()\n",
    "                        output.set_text1(f\"Path Length: {inc1+inc2+1}\")\n",
    "                        output.set_text2(f\"#Visited nodes: {vis}\")\n",
    "                        if vis != 0:\n",
    "                            output.set_text3(f\"Efficiency: {np.round((inc1+inc2+1)/vis, decimals=3)}\")\n",
    "                        return visited2+visited1, path1+path2\n",
    "\n",
    "            if current != end:\n",
    "                if current in visited2:\n",
    "                    visited2.remove(current)\n",
    "                current.make_visit()\n",
    "                v2.append(current)\n",
    "                visited2.append(current)\n",
    "                vis+=c\n",
    "\n",
    "            visit_animation(visited2)\n",
    "    #         nebr_animation(nebrs)\n",
    "            for rows in grid:\n",
    "                for node in rows:\n",
    "                    node.draw(win)\n",
    "            draw_grid(win, len(grid), width)\n",
    "            pygame.display.update()\n",
    "            \n",
    "    return visited2+visited1, False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def DFA_star(draw, grid, start, end, output, win, width, moving_target=False):\n",
    "    count = 0\n",
    "    vis = 0\n",
    "    open_set = PriorityQueue()\n",
    "    open_set.put((0, count, start))\n",
    "    came_from = {}\n",
    "    g_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "    g_score[start] = 0\n",
    "    f_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "    f_score[start] = h(start.get_pos(), end.get_pos())\n",
    "    visited = []\n",
    "    nebrs = []\n",
    "    \n",
    "    open_set_hash = {start}\n",
    "    \n",
    "    while not open_set.empty():\n",
    "        if moving_target:\n",
    "            li = [i for i in end.neighbors if i.is_neutral()]\n",
    "            if len(li):\n",
    "                end.reset()\n",
    "                end = li[np.random.randint(len(li))]\n",
    "                end.make_end()\n",
    "                for rows in grid:\n",
    "                    for node in rows:\n",
    "                        node.draw(win)\n",
    "                        draw_grid(win, len(grid), width)\n",
    "                        pygame.display.update()\n",
    "        for event in pygame.event.get():\n",
    "            if event.type == pygame.QUIT:\n",
    "                pygame.quit()\n",
    "        \n",
    "        current = open_set.get()[2]\n",
    "        open_set_hash.remove(current)\n",
    "        \n",
    "        if current == end:\n",
    "            path, inc = reconstruct_path(came_from, start, end, draw, visited, win, width, grid)\n",
    "            start.make_start()\n",
    "            output.set_text1(f\"Path Length: {inc}\")\n",
    "            output.set_text2(f\"#Visited nodes: {vis}\")\n",
    "            if vis != 0:\n",
    "                output.set_text3(f\"Efficiency: {np.round(inc/vis, decimals=3)}\")\n",
    "            return visited, path\n",
    "        \n",
    "        c = 1\n",
    "        for neighbor in current.neighbors:\n",
    "            if not neighbor.is_barrier() and (neighbor.is_neutral() or neighbor == end or neighbor.color == BROWN or neighbor.is_open()):\n",
    "                if neighbor.is_weight():\n",
    "                    c = 5\n",
    "                temp_g_score = g_score[current] + c\n",
    "                temp_f_score = (h(neighbor.get_pos(), end.get_pos())**2)+(temp_g_score)\n",
    "#                 temp_f_score = (h(neighbor.get_pos(), end.get_pos())-temp_g_score/(h(neighbor.get_pos(), end.get_pos())+1))\n",
    "#                 temp_f_score = (h(neighbor.get_pos(), end.get_pos())**2)+(temp_g_score)\n",
    "                if temp_f_score < f_score[neighbor]:\n",
    "                    came_from[neighbor] = current\n",
    "                    g_score[neighbor] = temp_g_score\n",
    "                    f_score[neighbor] = temp_f_score\n",
    "                    if neighbor not in open_set_hash:\n",
    "                        count+=1\n",
    "                        open_set.put((f_score[neighbor], count, neighbor))\n",
    "                        open_set_hash.add(neighbor)\n",
    "                    if neighbor != end:\n",
    "                        nebrs.append(neighbor)\n",
    "                        neighbor.make_open()\n",
    "        \n",
    "        if current != start:\n",
    "            if current in visited:\n",
    "                visited.remove(current)\n",
    "            visited.append(current)\n",
    "            vis+=c\n",
    "            current.make_visit()\n",
    "        \n",
    "        visit_animation(visited)\n",
    "#         nebr_animation(nebrs)\n",
    "        for rows in grid:\n",
    "            for node in rows:\n",
    "                node.draw(win)\n",
    "        draw_grid(win, len(grid), width)\n",
    "        pygame.display.update()\n",
    "            \n",
    "    return visited, False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def IDA_star(draw, win, width, output,  grid, start, end, threshold=100, moving_target= False, visited_old = []):\n",
    "    if threshold < len(grid)**2:\n",
    "        count = 0\n",
    "        vis = 0\n",
    "        open_set = PriorityQueue()\n",
    "        open_set.put((0, count, start))\n",
    "        came_from = {}\n",
    "        g_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "        g_score[start] = 0\n",
    "        f_score = {node: float(\"inf\") for row in grid for node in row}\n",
    "        f_score[start] = h(start.get_pos(), end.get_pos())\n",
    "\n",
    "        visited = []\n",
    "        nebrs = []\n",
    "        while not open_set.empty():\n",
    "            if moving_target:\n",
    "                li = [i for i in end.neighbors if i.is_neutral()]\n",
    "                if len(li):\n",
    "                    end.reset()\n",
    "                    end = li[np.random.randint(len(li))]\n",
    "                    end.make_end()\n",
    "            for event in pygame.event.get():\n",
    "                if event.type == pygame.QUIT:\n",
    "                    pygame.quit()\n",
    "\n",
    "            current = open_set.get()[2]\n",
    "\n",
    "            if current == end:\n",
    "                path, inc = reconstruct_path(came_from, start, end, draw, visited, win, width, grid)\n",
    "                start.make_start()\n",
    "                output.set_text1(f\"Path Length: {inc}\")\n",
    "                output.set_text2(f\"#Visited nodes: {vis}\")\n",
    "                if vis != 0:\n",
    "                    output.set_text3(f\"Efficiency: {np.round(inc/vis, decimals=3)}\")\n",
    "                return visited, path\n",
    "            \n",
    "            c = 1\n",
    "            if f_score[current] <= threshold:\n",
    "                for neighbor in current.neighbors:\n",
    "                    if not neighbor.is_barrier():\n",
    "                        if neighbor.is_weight():\n",
    "                            c = 5\n",
    "                        temp_g_score = g_score[current] + c\n",
    "                        temp_f_score = temp_g_score + h(neighbor.get_pos(), end.get_pos())\n",
    "                        if temp_f_score < f_score[neighbor]:\n",
    "                            came_from[neighbor] = current\n",
    "                            g_score[neighbor] = temp_g_score\n",
    "                            f_score[neighbor] = temp_f_score\n",
    "                            count+=1\n",
    "                            open_set.put((f_score[neighbor], count, neighbor))\n",
    "                            if neighbor != end:\n",
    "                                nebrs.append(neighbor)\n",
    "                                neighbor.make_open()\n",
    "\n",
    "            if current != start:\n",
    "                visited.append(current)\n",
    "                vis+=c\n",
    "                current.make_visit()\n",
    "\n",
    "            visit_animation(visited)\n",
    "            for rows in grid:\n",
    "                for node in rows:\n",
    "                    node.draw(win)\n",
    "            draw_grid(win, len(grid), width)\n",
    "            pygame.display.update()\n",
    "            \n",
    "        if visited == visited_old:\n",
    "            return visited, False\n",
    "        return IDA_star(draw, win, width, output ,grid, start, end, threshold+10, moving_target, visited)\n",
    "    return [], False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_free(grid, x, y):\n",
    "    count = 0\n",
    "    if y+1 < len(grid) and grid[x][y+1].is_barrier() :\n",
    "        count +=1\n",
    "    if y-1>=0 and grid[x][y-1].is_barrier():\n",
    "        count +=1\n",
    "    if x+1 < len(grid) and grid[x+1][y].is_barrier():\n",
    "        count+=1\n",
    "    if x-1>=0 and grid[x-1][y].is_barrier():\n",
    "        count+=1\n",
    "    if count >= 3:\n",
    "        return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unvisited_n(grid, x, y):\n",
    "    n = []\n",
    "    if y+1 < len(grid) and grid[x][y+1].is_barrier() and is_free(grid, x, y+1):\n",
    "        n.append((x, y+1))\n",
    "    if y-1>=0 and grid[x][y-1].is_barrier() and is_free(grid, x, y-1):\n",
    "        n.append((x, y-1))\n",
    "    if x+1 < len(grid) and grid[x+1][y].is_barrier() and is_free(grid, x+1, y):\n",
    "        n.append((x+1, y))\n",
    "    if x-1>=0 and grid[x-1][y].is_barrier() and is_free(grid, x-1, y):\n",
    "        n.append((x-1, y))\n",
    "    return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_black(grid, win):\n",
    "    for row in grid:\n",
    "        for node in row:\n",
    "            node.make_barrier()\n",
    "            node.draw(win)\n",
    "    pygame.display.update()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs_maze(draw, width, grid, start, end, left, right, top, bottom, win, vertical=True):\n",
    "    make_black(grid, win)\n",
    "    x, y = 1, 1\n",
    "    head = grid[x][y]\n",
    "    head.looking_at()\n",
    "    stack = [(x, y)]\n",
    "    while True:\n",
    "        neighbors = unvisited_n(grid, x, y)\n",
    "        if len(neighbors) > 0:\n",
    "            random_index = np.random.randint(len(neighbors))\n",
    "            x, y = neighbors[random_index]\n",
    "            head = grid[x][y]\n",
    "            head.looking_at()\n",
    "            stack.append((x, y))\n",
    "            head.draw(win)\n",
    "            draw_grid(win, len(grid), width)\n",
    "            pygame.display.update()\n",
    "        else:\n",
    "            if len(stack) > 0:\n",
    "                x, y = stack.pop()\n",
    "                grid[x][y].reset()\n",
    "                grid[x][y].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "            if len(stack) > 0:\n",
    "                x, y = stack[-1]\n",
    "#                 draw()\n",
    "            else:\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_open_up(grid, li, win, width):\n",
    "    n = []\n",
    "    for x, y in li:\n",
    "        if grid[x][y-1].is_neutral():\n",
    "            n.append(grid[x][y])\n",
    "    if len(n)>0:\n",
    "        node = np.random.choice(n)\n",
    "        node.reset()\n",
    "        node.draw(win)\n",
    "        draw_grid(win, len(grid), width)\n",
    "        pygame.display.update()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sidewinder_maze(draw, width, grid, start, end, left, right, top, bottom, win, vertical=True):\n",
    "    make_black(grid, win)\n",
    "    for x in range(1, right-1):\n",
    "        grid[x][1].reset()\n",
    "        grid[x][1].draw(win)\n",
    "        draw_grid(win, len(grid), width)\n",
    "        pygame.display.update()\n",
    "        \n",
    "    for y in range(3, bottom, 2):\n",
    "        x = 1\n",
    "        next_row = False\n",
    "        while not next_row:\n",
    "            lim = x+5\n",
    "            if lim >= right-1:\n",
    "                x_lim = right-1\n",
    "                next_row = True\n",
    "            else:\n",
    "                x_lim = np.random.randint(x+2, lim)\n",
    "            li = []\n",
    "            \n",
    "            for i in range(x, x_lim):\n",
    "                li.append((i, y-1))\n",
    "                grid[i][y].reset()\n",
    "                grid[i][y].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "                \n",
    "            is_open_up(grid, li, win, width)\n",
    "            grid[i][y].draw(win)\n",
    "            draw_grid(win, len(grid), width)\n",
    "            pygame.display.update()\n",
    "            x = x_lim+1\n",
    "            \n",
    "    for x in range(1, right-1):\n",
    "        grid[x][0].make_barrier()\n",
    "        grid[x][0].draw(win)\n",
    "        draw_grid(win, len(grid), width)\n",
    "        pygame.display.update()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def moded_sidewinder_maze(draw, width, grid, start, end, left, right, top, bottom, win, vertical=True):\n",
    "    make_black(grid, win)\n",
    "    for x in range(1, right-1):\n",
    "        grid[x][0].reset()\n",
    "        grid[x][0].draw(win)\n",
    "        draw_grid(win, len(grid), width)\n",
    "        pygame.display.update()\n",
    "        \n",
    "    for y in range(2, bottom, 2):\n",
    "        x = 1\n",
    "        next_row = False\n",
    "        while not next_row:\n",
    "            lim = x+5\n",
    "            if lim >= right-1:\n",
    "                x_lim = right-1\n",
    "                next_row = True\n",
    "            else:\n",
    "                x_lim = np.random.randint(x+2, lim)\n",
    "            li = []\n",
    "            \n",
    "            for i in range(x, x_lim):\n",
    "                li.append((i, y-1))\n",
    "                grid[i][y].reset()\n",
    "                grid[i][y].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "            if (y == 2 and not np.random.randint(0, 5)) or (not next_row and not np.random.randint(0, 5)):\n",
    "                grid[x_lim][y].reset()\n",
    "                grid[x_lim][y].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "                \n",
    "            is_open_up(grid, li, win, width)\n",
    "            x = x_lim+1\n",
    "    for x in range(1, right-1):\n",
    "        grid[x][0].make_barrier()\n",
    "        grid[x][0].draw(win)\n",
    "        draw_grid(win, len(grid), width)\n",
    "        pygame.display.update()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_maze(draw, width, grid, start, end, left, right, top, bottom, win):\n",
    "    if right-left >= 1 and bottom-top >=1:\n",
    "        vertical = True\n",
    "        test = False\n",
    "        if right-left >= bottom-top:\n",
    "            if bottom-top == 1:\n",
    "                if (bottom < len(grid) and grid[left][bottom].is_barrier()) and (top-1 >= 0 and grid[left][top-1].is_barrier()):\n",
    "                    vertical = False\n",
    "            if vertical == True:\n",
    "                l = left\n",
    "                r = right\n",
    "                if left-1>=0 and grid[left-1][top].is_barrier():\n",
    "                    l = left+1\n",
    "                if right<50 and grid[right][top].is_barrier():\n",
    "                    r = right-1\n",
    "                if l >= r:\n",
    "                    vertical = False \n",
    "            if vertical == True:\n",
    "                test = True\n",
    "                rand = np.random.randint(l, r)\n",
    "                if top<bottom and ((bottom - top <= 3) or (top-1 >= 0 and grid[left][top-1].is_neutral() and bottom < len(grid) and grid[left][bottom].is_neutral())):\n",
    "                    br = bottom\n",
    "                if top+1 < bottom-1:\n",
    "                    br = np.random.randint(top+1, bottom-1)\n",
    "                elif top+1 == bottom-1:\n",
    "                    br = top+1\n",
    "                else:\n",
    "                    br = bottom\n",
    "                \n",
    "        elif right-left <= bottom-top:\n",
    "            if right-left == 1:\n",
    "                if (right < len(grid) and grid[right][top].is_barrier()) and (left-1 >= 0 and grid[left-1][top].is_barrier()):\n",
    "                    return \n",
    "            t = top\n",
    "            b = bottom\n",
    "            if top-1>= 0 and grid[left][top-1].is_barrier():\n",
    "                t = top+1\n",
    "            if bottom < 50 and grid[left][bottom].is_barrier():\n",
    "                b = bottom-1\n",
    "            if t >= b:\n",
    "                return\n",
    "            test = True\n",
    "            rand = np.random.randint(t, b)\n",
    "            if left<right and ((right - left<= 3) or (left-1 >= 0 and grid[left-1][bottom].is_neutral() and right < len(grid) and grid[right][bottom].is_neutral())):\n",
    "                    br = bottom\n",
    "            if left+1 < right-1:\n",
    "                br = np.random.randint(left+1, right-1)\n",
    "            elif left+1 == right-1:\n",
    "                br = left+1\n",
    "            else:\n",
    "                br = right\n",
    "            vertical = False\n",
    "        if test == False:\n",
    "            return\n",
    "        prob = 3\n",
    "        if vertical:\n",
    "            for y in range(top, br):\n",
    "                grid[rand][y].make_barrier()\n",
    "                grid[rand][y].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "                \n",
    "            if not np.random.randint(prob) and br - top <= 2:\n",
    "                grid[rand][y+1].make_barrier()\n",
    "                grid[rand][y+1].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "                \n",
    "            for y in range(br+1, bottom):\n",
    "                grid[rand][y].make_barrier()\n",
    "                grid[rand][y].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "        else:\n",
    "            for x in range(left, br):\n",
    "                grid[x][rand].make_barrier()\n",
    "                grid[x][rand].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "                \n",
    "            if not np.random.randint(prob) and br - left <= 2:\n",
    "                grid[x+1][rand].make_barrier()\n",
    "                grid[x+1][rand].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "                \n",
    "            for x in range(br+1, right):\n",
    "                grid[x][rand].make_barrier()\n",
    "                grid[x][rand].draw(win)\n",
    "                draw_grid(win, len(grid), width)\n",
    "                pygame.display.update()\n",
    "        \n",
    "        if vertical:\n",
    "            recursive_maze(draw, width, grid, start, end, rand+1, right, top, br, win)\n",
    "            recursive_maze(draw, width, grid, start, end, left, rand, top, br, win)\n",
    "            recursive_maze(draw, width, grid, start, end, rand+1, right, br+1, bottom, win)\n",
    "            recursive_maze(draw, width, grid, start, end, left, rand, br+1, bottom, win)\n",
    "        else:\n",
    "            recursive_maze(draw, width, grid, start, end, left, br, top, rand, win)\n",
    "            recursive_maze(draw, width, grid, start, end, left, br, rand+1, bottom, win)\n",
    "            recursive_maze(draw, width, grid, start, end, br+1, right, top, rand, win)\n",
    "            recursive_maze(draw, width, grid, start, end, br+1, right, rand+1, bottom, win)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_weight_maze(draw, width, grid, start, end, left, right, top, bottom, win):\n",
    "    weighted = []\n",
    "    if right-left >= 1 and bottom-top >=1:\n",
    "        vertical = True\n",
    "        test = False\n",
    "        if right-left >= bottom-top:\n",
    "            if bottom-top == 1:\n",
    "                if (bottom < len(grid) and grid[left][bottom].is_weight()) and (top-1 >= 0 and grid[left][top-1].is_weight()):\n",
    "                    vertical = False\n",
    "            if vertical == True:\n",
    "                l = left\n",
    "                r = right\n",
    "                if left-1>=0 and grid[left-1][top].is_weight():\n",
    "                    l = left+1\n",
    "                if right<50 and grid[right][top].is_weight():\n",
    "                    r = right-1\n",
    "                if l >= r:\n",
    "                    vertical = False \n",
    "            if vertical == True:\n",
    "                test = True\n",
    "#                 print(\"--->\", l, r)\n",
    "                rand = np.random.randint(l, r)\n",
    "                if top<bottom and ((bottom - top <= 3) or (top-1 >= 0 and grid[left][top-1].is_neutral() and bottom < len(grid) and grid[left][bottom].is_neutral())):\n",
    "                    br = bottom\n",
    "                if top+1 < bottom-1:\n",
    "                    br = np.random.randint(top+1, bottom-1)\n",
    "                elif top+1 == bottom-1:\n",
    "                    br = top+1\n",
    "                else:\n",
    "                    br = bottom\n",
    "                \n",
    "        elif right-left <= bottom-top:\n",
    "            if right-left == 1:\n",
    "                if (right < len(grid) and grid[right][top].is_weight()) and (left-1 >= 0 and grid[left-1][top].is_weight()):\n",
    "                    return weighted\n",
    "            t = top\n",
    "            b = bottom\n",
    "            if top-1>= 0 and grid[left][top-1].is_weight():\n",
    "                t = top+1\n",
    "            if bottom < 50 and grid[left][bottom].is_weight():\n",
    "                b = bottom-1\n",
    "            if t >= b:\n",
    "                return weighted\n",
    "            test = True\n",
    "#             print(\"--->\", t, b)\n",
    "            rand = np.random.randint(t, b)\n",
    "            if left<right and ((right - left<= 3) or (left-1 >= 0 and grid[left-1][bottom].is_neutral() and right < len(grid) and grid[right][bottom].is_neutral())):\n",
    "                    br = bottom\n",
    "            if left+1 < right-1:\n",
    "                br = np.random.randint(left+1, right-1)\n",
    "            elif left+1 == right-1:\n",
    "                br = left+1\n",
    "            else:\n",
    "                br = right\n",
    "            vertical = False\n",
    "        if test == False:\n",
    "            return weighted\n",
    "        prob = 3\n",
    "        if vertical:\n",
    "            for y in range(top, br):\n",
    "#                 print(rand, y)\n",
    "                grid[rand][y].make_weight()\n",
    "                weighted.append(grid[rand][y])\n",
    "                draw()\n",
    "            if not np.random.randint(prob) and br - top <= 2:\n",
    "                grid[rand][y+1].make_weight()\n",
    "                weighted.append(grid[rand][y+1])\n",
    "                draw()\n",
    "            for y in range(br+1, bottom):\n",
    "#                 print(rand, y)\n",
    "                grid[rand][y].make_weight()\n",
    "                weighted.append(grid[rand][y])\n",
    "                draw()\n",
    "        else:\n",
    "            for x in range(left, br):\n",
    "                grid[x][rand].make_weight()\n",
    "                weighted.append(grid[x][rand])\n",
    "                draw()\n",
    "            if not np.random.randint(prob) and br - left <= 2:\n",
    "                grid[x+1][rand].make_weight()\n",
    "                weighted.append(grid[x+1][rand])\n",
    "                draw()\n",
    "            for x in range(br+1, right):\n",
    "                grid[x][rand].make_weight()\n",
    "                weighted.append(grid[x][rand])\n",
    "                draw()\n",
    "        if vertical:\n",
    "            weighted += recursive_weight_maze(draw, width, grid, start, end, rand+1, right, top, br, win)\n",
    "            weighted += recursive_weight_maze(draw, width, grid, start, end, left, rand, top, br, win)\n",
    "            weighted += recursive_weight_maze(draw, width, grid, start, end, rand+1, right, br+1, bottom, win)\n",
    "            weighted += recursive_weight_maze(draw, width, grid, start, end, left, rand, br+1, bottom, win)\n",
    "        else:\n",
    "            weighted += recursive_weight_maze(draw, width, grid, start, end, left, br, top, rand, win)\n",
    "            weighted += recursive_weight_maze(draw, width, grid, start, end, left, br, rand+1, bottom, win)\n",
    "            weighted += recursive_weight_maze(draw, width, grid, start, end, br+1, right, top, rand, win)\n",
    "            weighted += recursive_weight_maze(draw, width, grid, start, end, br+1, right, rand+1, bottom, win)\n",
    "    return weighted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_weight_div(draw, width, grid, start, end, left, right, top, bottom, win, break_at = 0):\n",
    "    li = []\n",
    "    for i in range(right):\n",
    "        grid[0][i].make_weight()\n",
    "        li.append(grid[0][i])\n",
    "        grid[bottom-1][right-1-i].make_weight()\n",
    "        draw()\n",
    "    for i in range(bottom-1):\n",
    "        grid[i][0].make_weight()\n",
    "        li.append(grid[i][0])\n",
    "        grid[bottom-1-i][right-1].make_weight()\n",
    "        draw()\n",
    "    li += recursive_weight_maze(draw, width, grid, start, end, left+1, right-1, top+1, bottom-1, win)\n",
    "    return li"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_div(draw, width, grid, start, end, left, right, top, bottom, win, break_at = 0):\n",
    "    for i in range(right):\n",
    "        grid[0][i].make_barrier()\n",
    "        grid[bottom-1][right-1-i].make_barrier()\n",
    "        draw()\n",
    "    for i in range(bottom-1):\n",
    "        grid[i][0].make_barrier()\n",
    "        grid[bottom-1-i][right-1].make_barrier()\n",
    "        draw()\n",
    "    recursive_maze(draw, width, grid, start, end, left+1, right-1, top+1, bottom-1, win)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_grid(rows, width):\n",
    "    grid = []\n",
    "    gap = width // rows\n",
    "    for i in range(rows):\n",
    "        grid.append([])\n",
    "        for j in range(rows):\n",
    "            node = Node(i, j, gap, rows)\n",
    "            grid[i].append(node)\n",
    "    return np.array(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_grid(win, rows, width):\n",
    "    gap = width // rows\n",
    "    for i in range(rows+1):\n",
    "        pygame.draw.line(win, GREY, (0, i*gap), (rows*gap, i*gap))\n",
    "    for i in range(rows+1):\n",
    "        pygame.draw.line(win, GREY, (i*gap, 0), (i*gap, rows*gap))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_clicked_pos(pos, rows, width):\n",
    "    gap = width//rows\n",
    "    y, x = pos\n",
    "    row = y // gap\n",
    "    col = x // gap\n",
    "    return row, col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw(win, grid, rows, width, algorithms, mazes, options, output, menu = True):\n",
    "    win.fill(BG_COLOR)\n",
    "    for row in grid:\n",
    "        for node in row:\n",
    "            node.draw(win)\n",
    "    draw_grid(win, rows, width)\n",
    "    if menu:\n",
    "        n = 17\n",
    "        delta = 700\n",
    "        ht = 900\n",
    "        width = ht\n",
    "        w = 1600\n",
    "        font = pygame.font.SysFont('comicsans', 35)\n",
    "        text = font.render(\"Algorithms\", 1, WHITE)\n",
    "        top = 0\n",
    "        end = ht//13\n",
    "        win.blit(text, (width+delta//6, (end-top)/2.5))\n",
    "        for algorithm in algorithms:\n",
    "            algorithm.draw(win, BLACK)\n",
    "        \n",
    "        text = font.render(\"Mazes\", 1, WHITE)\n",
    "        but_height = ht//15\n",
    "        top += (4*but_height)\n",
    "        end += (1.9*(3*but_height//2)) + but_height + ht//12\n",
    "        win.blit(text, (width+delta//6, ((end-top)/2) + top))\n",
    "        for maze in mazes:\n",
    "            maze.draw(win, BLACK)\n",
    "            \n",
    "        end += (1.3*(3*but_height//2)) + ht//6\n",
    "        top += (5*but_height//2)\n",
    "        \n",
    "        text = font.render(\"Options\", 1, WHITE)\n",
    "        win.blit(text, (width+delta//6, ((end-top)/2) + top))\n",
    "        for option in options:\n",
    "            option.draw(win, BLACK)\n",
    "        output.draw(win, BLACK)\n",
    "    pygame.display.update()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def main(win, width):\n",
    "    ROWS = 50\n",
    "    w, ht = pygame.display.get_surface().get_size()\n",
    "    width = ht\n",
    "    grid = make_grid(ROWS, width)\n",
    "    delta = w - width\n",
    "    \n",
    "    top_start = ht/13\n",
    "    but_height = ht//15\n",
    "    but_width = delta//4\n",
    "    \n",
    "    algorithms = [\n",
    "        button(width+delta//5, top_start, but_width-but_height, but_height, \"A*\"),\n",
    "        button(width+delta//5+(5*but_width//4), top_start, but_width-but_height, but_height, 'IDA*'),\n",
    "        button(width+delta//5, top_start+(3*but_height//2), but_width-but_height, but_height, 'Modified A*'),\n",
    "        button(width+delta//5+(5*but_width//4), top_start+(3*but_height//2), but_width-but_height, but_height, 'DFA*'),\n",
    "        button(width+delta//5+((5*(but_width-80)//4)//2)-20, top_start+(3*but_height), but_width+delta//8-but_height+60, but_height, 'Modified Bidirectional A*'),\n",
    "    ]\n",
    "    top_start = top_start + (1.9*(3*but_height//2)) + but_height + ht//12\n",
    "    but_height = ht//15\n",
    "    but_width = delta//4+ delta//10\n",
    "    mazes = [\n",
    "        button(width+delta//5, top_start, but_width-delta//8-but_height, but_height, \"DFS\"),\n",
    "        button(width+delta//5+(5*(but_width-80)//4), top_start, but_width-but_height, but_height, 'Recursive Division'),\n",
    "        button(width+delta//5+(5*(but_width-150)//4)//2, top_start+(3*but_height//2), but_width+delta//8-but_height, but_height, 'Modified Sidewinder'),\n",
    "    ]\n",
    "    top_start = top_start + (1.3*(3*but_height//2)) + ht//10\n",
    "    but_height = ht//15\n",
    "    but_width =  delta//10\n",
    "    options = [\n",
    "        button(width+delta//5, top_start, but_width-but_height+20, but_height, \"Clear\"),\n",
    "        button(width+delta//5-20 + delta//5 + (4*(but_width+50)//3), top_start, 0, but_height, \"-\"),\n",
    "        button(width+delta//5 + delta//5 + (4*(but_width+50)//3)+(4*(but_width-30)//3), top_start,0, but_height, \"+\"),\n",
    "    ]\n",
    "    sc_start = ht-240\n",
    "    sc_height = 230\n",
    "    sc_width = delta-delta//4\n",
    "    output = screen(width+delta//8, sc_start, sc_width, sc_height, \"Choose an Algorithm\")\n",
    "    output.set_label1(f\"Number of rows: {ROWS}\")\n",
    "    output.set_text1(\"1. Pick starting node\")\n",
    "    output.set_text2(\"2. Pick ending node\")\n",
    "    output.set_text3(\"3. Choose an algorithm\")\n",
    "    \n",
    "    start = None\n",
    "    end = None\n",
    "    \n",
    "    run = True\n",
    "    started = False\n",
    "    visited = []\n",
    "    weighted = []\n",
    "    path = False\n",
    "    while run:\n",
    "        \n",
    "        \n",
    "        if len(visited):\n",
    "            visit_animation(visited)\n",
    "            \n",
    "        if path:\n",
    "            path_animation(path)\n",
    "            \n",
    "        draw(win, grid, ROWS, width, algorithms, mazes, options, output)\n",
    "        for event in pygame.event.get():\n",
    "            if event.type == pygame.QUIT:\n",
    "                run = False\n",
    "                \n",
    "            if started:\n",
    "                continue\n",
    "                \n",
    "            \n",
    "            if pygame.mouse.get_pressed()[0]:\n",
    "                pos = pygame.mouse.get_pos()\n",
    "                row,col = get_clicked_pos(pos, ROWS, width)\n",
    "                if row>= 0 and row<ROWS and col < ROWS and col >= 0:\n",
    "                    node = grid[row][col]\n",
    "                    if node in visited:\n",
    "                        visited.remove(node)\n",
    "                    if node in weighted:\n",
    "                        weighted.remove(node)\n",
    "                    if path:\n",
    "                        if node in path:\n",
    "                            path.remove(node)\n",
    "                    if not start and node != end:\n",
    "                        if node in visited:\n",
    "                            visited.remove(node)\n",
    "                        start = node\n",
    "                        start.make_start()\n",
    "                    elif not end and node != start:\n",
    "                        end = node\n",
    "                        end.make_end()\n",
    "                    elif node != end and node != start:\n",
    "                        node.make_barrier()\n",
    "                        \n",
    "                elif algorithms[0].is_hover(pos):\n",
    "                    output.draw(win, (0, 0, 0))\n",
    "                    if len(weighted):\n",
    "                        for node in weighted:\n",
    "                            node.make_weight()\n",
    "                    if start and end:\n",
    "                        for row in grid:\n",
    "                            for node in row:\n",
    "                                node.update_neighbors(grid)\n",
    "                                if not node.is_neutral() and node != start and node != end and not node.is_barrier() and not node.is_weight():\n",
    "                                    node.reset()\n",
    "                        visited = []\n",
    "                        path = []\n",
    "                        output.set_text1(\"......\")\n",
    "                        output.set_text2(\"\")\n",
    "                        output.set_text3(\"\")\n",
    "                        output.draw(win, BLACK)\n",
    "                        pygame.display.update()\n",
    "                        visited, path = A_star(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), grid, start, end, output, win, width)\n",
    "                        if not path:\n",
    "                            output.set_text1(\"Path not available\")\n",
    "                            \n",
    "                \n",
    "                elif algorithms[1].is_hover(pos):\n",
    "                    if len(weighted):\n",
    "                        for node in weighted:\n",
    "                            node.make_weight()\n",
    "                    if start and end:\n",
    "                        for row in grid:\n",
    "                            for node in row:\n",
    "                                node.update_neighbors(grid)\n",
    "                                if not node.is_neutral() and node != start and node != end and not node.is_barrier() and not node.is_weight():\n",
    "                                    node.reset()\n",
    "                        visited = []\n",
    "                        path = []\n",
    "                        output.set_text1(\"......\")\n",
    "                        output.set_text2(\"\")\n",
    "                        output.set_text3(\"\")\n",
    "                        output.draw(win, BLACK)\n",
    "                        pygame.display.update()\n",
    "                        visited, path = IDA_star(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), win, width, output, grid, start, end, h(start.get_pos(), end.get_pos()))\n",
    "                        if not path:\n",
    "                            output.set_text1(\"Path not available\")\n",
    "                            \n",
    "                elif algorithms[2].is_hover(pos):\n",
    "                    if len(weighted):\n",
    "                        for node in weighted:\n",
    "                            node.make_weight()\n",
    "                    if start and end:\n",
    "                        for row in grid:\n",
    "                            for node in row:\n",
    "                                node.update_neighbors(grid)\n",
    "                                if not node.is_neutral() and node != start and node != end and not node.is_barrier() and not node.is_weight():\n",
    "                                    node.reset()\n",
    "                        visited = []\n",
    "                        path = []\n",
    "                        output.set_text1(\"......\")\n",
    "                        output.set_text2(\"\")\n",
    "                        output.set_text3(\"\")\n",
    "                        output.draw(win, BLACK)\n",
    "                        pygame.display.update()\n",
    "                        visited, path = moded_A_star(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), grid, start, end, output, win, width)\n",
    "                        if not path:\n",
    "                            output.set_text1(\"Path not available\")\n",
    "                            \n",
    "                elif algorithms[3].is_hover(pos):\n",
    "                    if len(weighted):\n",
    "                        for node in weighted:\n",
    "                            node.make_weight()\n",
    "                    if start and end:\n",
    "                        for row in grid:\n",
    "                            for node in row:\n",
    "                                node.update_neighbors(grid)\n",
    "                                if not node.is_neutral() and node != start and node != end and not node.is_barrier() and not node.is_weight():\n",
    "                                    node.reset()\n",
    "                        visited = []\n",
    "                        path = []\n",
    "                        output.set_text1(\"......\")\n",
    "                        output.set_text2(\"\")\n",
    "                        output.set_text3(\"\")\n",
    "                        output.draw(win, BLACK)\n",
    "                        pygame.display.update()\n",
    "                        visited, path = DFA_star(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), grid, start, end, output, win, width)\n",
    "                        if not path:\n",
    "                            output.set_text1(\"Path not available\")\n",
    "                            \n",
    "                elif algorithms[4].is_hover(pos):\n",
    "                    if len(weighted):\n",
    "                        for node in weighted:\n",
    "                            node.make_weight()\n",
    "                    if start and end:\n",
    "                        for row in grid:\n",
    "                            for node in row:\n",
    "                                node.update_neighbors(grid)\n",
    "                                if not node.is_neutral() and node != start and node != end and not node.is_barrier() and not node.is_weight():\n",
    "                                    node.reset()\n",
    "                        visited = []\n",
    "                        path = []\n",
    "                        output.set_text1(\"......\")\n",
    "                        output.set_text2(\"\")\n",
    "                        output.set_text3(\"\")\n",
    "                        output.draw(win, BLACK)\n",
    "                        pygame.display.update()\n",
    "                        visited, path = bi_moded_A_star(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), grid, start, end, output, win, width)\n",
    "                        if not path:\n",
    "                            output.set_text1(\"Path not available\")\n",
    "                            \n",
    "                elif mazes[0].is_hover(pos):\n",
    "                    output.set_text1(\"......\")\n",
    "                    output.set_text2(\"\")\n",
    "                    output.set_text3(\"\")\n",
    "                    output.draw(win, BLACK)\n",
    "                    pygame.display.update()\n",
    "                    start = None\n",
    "                    end = None\n",
    "                    visited = []\n",
    "                    path = []\n",
    "                    weighted = []\n",
    "                    for row in grid:\n",
    "                        for node in row:\n",
    "                            if node.is_barrier() or node.is_start() or node.is_end():\n",
    "                                node.reset()\n",
    "                    dfs_maze(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), width, grid, start, end, 0, ROWS, 0, ROWS, win)\n",
    "                    output.set_text1(\"1. Pick starting node\")\n",
    "                    output.set_text2(\"2. Pick ending node\")\n",
    "                    output.set_text3(\"3. Choose an algorithm\")\n",
    "                    \n",
    "                elif mazes[1].is_hover(pos):\n",
    "                    output.set_text1(\"......\")\n",
    "                    output.set_text2(\"\")\n",
    "                    output.set_text3(\"\")\n",
    "                    output.draw(win, BLACK)\n",
    "                    pygame.display.update()\n",
    "                    start = None\n",
    "                    end = None\n",
    "                    visited = []\n",
    "                    path = []\n",
    "                    weighted = []\n",
    "                    for row in grid:\n",
    "                        for node in row:\n",
    "#                             if node.is_barrier() or node.is_start() or node.is_end():\n",
    "                            node.reset()\n",
    "                    recursive_div(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output),width, grid, start, end, 0, ROWS, 0, ROWS, win)\n",
    "                    output.set_text1(\"1. Pick starting node\")\n",
    "                    output.set_text2(\"2. Pick ending node\")\n",
    "                    output.set_text3(\"3. Choose an algorithm\")\n",
    "            \n",
    "                elif mazes[2].is_hover(pos):\n",
    "                    output.set_text1(\"......\")\n",
    "                    output.set_text2(\"\")\n",
    "                    output.set_text3(\"\")\n",
    "                    output.draw(win, BLACK)\n",
    "                    pygame.display.update()\n",
    "                    start = None\n",
    "                    end = None\n",
    "                    visited = []\n",
    "                    path = []\n",
    "                    weighted = []\n",
    "                    for row in grid:\n",
    "                        for node in row:\n",
    "                            if node.is_barrier() or node.is_start() or node.is_end():\n",
    "                                node.reset()\n",
    "                    moded_sidewinder_maze(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), width, grid, start, end, 0, ROWS, 0, ROWS, win)\n",
    "                    output.set_text1(\"1. Pick starting node\")\n",
    "                    output.set_text2(\"2. Pick ending node\")\n",
    "                    output.set_text3(\"3. Choose an algorithm\")\n",
    "                    \n",
    "                elif options[0].is_hover(pos):\n",
    "                    output.set_text1(\"1. Pick starting node\")\n",
    "                    output.set_text2(\"2. Pick ending node\")\n",
    "                    output.set_text3(\"3. Choose an algorithm\")\n",
    "                    output.draw(win, BLACK)\n",
    "                    pygame.display.update()\n",
    "                    weighted = []\n",
    "                    start = None\n",
    "                    end = None\n",
    "                    visited = []\n",
    "                    path = []\n",
    "                    weighted = []\n",
    "                    for row in grid:\n",
    "                        for node in row:\n",
    "                            node.reset()\n",
    "                            \n",
    "                elif options[1].is_hover(pos):\n",
    "                    weighted = []\n",
    "                    start = None\n",
    "                    end = None\n",
    "                    visited = []\n",
    "                    path = []\n",
    "                    weighted = []\n",
    "                    for row in grid:\n",
    "                        for node in row:\n",
    "                            node.reset()\n",
    "                    if ROWS>5:\n",
    "                        ROWS-=1\n",
    "                        grid = make_grid(ROWS, width)\n",
    "                    output.set_label1(f\"Number of rows: {ROWS}\")\n",
    "                        \n",
    "                elif options[2].is_hover(pos):\n",
    "                    weighted = []\n",
    "                    start = None\n",
    "                    end = None\n",
    "                    visited = []\n",
    "                    path = []\n",
    "                    weighted = []\n",
    "                    for row in grid:\n",
    "                        for node in row:\n",
    "                            node.reset()\n",
    "                    if ROWS<100:\n",
    "                        ROWS+=1\n",
    "                        grid = make_grid(ROWS, width)\n",
    "                    output.set_label1(f\"Number of rows: {ROWS}\")\n",
    "                        \n",
    "            elif pygame.mouse.get_pressed()[2]:\n",
    "                pos = pygame.mouse.get_pos()\n",
    "                row,col = get_clicked_pos(pos, ROWS, width)\n",
    "                if row>= 0 and row<ROWS and col < ROWS and col >= 0:\n",
    "                    node = grid[row][col]\n",
    "                    if path:\n",
    "                        if node in path:\n",
    "                            path.remove(node)\n",
    "                    if node in visited:\n",
    "                        visited.remove(node)\n",
    "                    if node in weighted:\n",
    "                        weighted.remove(node)\n",
    "                    node.reset()\n",
    "                    if node == start:\n",
    "                        start = None\n",
    "                    elif node == end:\n",
    "                        end = None\n",
    "            \n",
    "            elif event.type == pygame.KEYDOWN:\n",
    "                if event.key == pygame.K_ESCAPE:\n",
    "                    run = False\n",
    "            \n",
    "#             if event.type == pygame.KEYDOWN:\n",
    "                \n",
    "# #                 if event.key == pygame.K_w:\n",
    "# #                     pos = pygame.mouse.get_pos()\n",
    "# #                     row,col = get_clicked_pos(pos, ROWS, width)\n",
    "# #                     if row>= 0 and row<ROWS and col < ROWS and col >= 0:\n",
    "# #                         node = grid[row][col]\n",
    "# #                         if node in visited:\n",
    "# #                             visited.remove(node)\n",
    "# #                         if path:\n",
    "# #                             if node in path:\n",
    "# #                                 path.remove(node)\n",
    "# #                         if not start and node != end:\n",
    "# #                             start = node\n",
    "# #                             start.make_start()\n",
    "# #                         elif not end and node != start:\n",
    "# #                             end = node\n",
    "# #                             end.make_end()\n",
    "# #                         elif node != end and node != start and not node.is_barrier():\n",
    "# #                             weighted.append(node)\n",
    "# #                             node.make_weight()\n",
    "                \n",
    "#                 if event.key == pygame.K_i and not started:\n",
    "#                     if len(weighted):\n",
    "#                         for node in weighted:\n",
    "#                             node.make_weight()\n",
    "#                     if start and end:\n",
    "#                         for row in grid:\n",
    "#                             for node in row:\n",
    "#                                 node.update_neighbors(grid)\n",
    "#                                 if not node.is_neutral() and node != start and node != end and not node.is_barrier() and not node.is_weight():\n",
    "#                                     node.reset()\n",
    "#                         visited = []\n",
    "#                         path = []\n",
    "#                         visited, path = IDA_star(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), win, width, output, grid, start, end, h(start.get_pos(), end.get_pos()))\n",
    "                \n",
    "#                 if event.key == pygame.K_a and not started:\n",
    "#                     if len(weighted):\n",
    "#                         for node in weighted:\n",
    "#                             node.make_weight()\n",
    "#                     if start and end:\n",
    "#                         for row in grid:\n",
    "#                             for node in row:\n",
    "#                                 node.update_neighbors(grid)\n",
    "#                                 if not node.is_neutral() and node != start and node != end and not node.is_barrier() and not node.is_weight():\n",
    "#                                     node.reset()\n",
    "#                         visited = []\n",
    "#                         path = []\n",
    "#                         visited, path = A_star(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), grid, start, end, output)\n",
    "                \n",
    "#                 if event.key == pygame.K_m and not started:\n",
    "#                     if len(weighted):\n",
    "#                         for node in weighted:\n",
    "#                             node.make_weight()\n",
    "#                     if start and end:\n",
    "#                         for row in grid:\n",
    "#                             for node in row:\n",
    "#                                 node.update_neighbors(grid)\n",
    "#                                 if not node.is_neutral() and node != start and node != end and not node.is_barrier() and not node.is_weight():\n",
    "#                                     node.reset()\n",
    "#                         visited = []\n",
    "#                         path = []\n",
    "#                         visited, path = moded_A_star(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), grid, start, end, output)\n",
    "                        \n",
    "#                 if event.key == pygame.K_d and not started:\n",
    "#                     if len(weighted):\n",
    "#                         for node in weighted:\n",
    "#                             node.make_weight()\n",
    "#                     if start and end:\n",
    "#                         for row in grid:\n",
    "#                             for node in row:\n",
    "#                                 node.update_neighbors(grid)\n",
    "#                                 if not node.is_neutral() and node != start and node != end and not node.is_barrier() and not node.is_weight():\n",
    "#                                     node.reset()\n",
    "#                         visited = []\n",
    "#                         path = []\n",
    "#                         visited, path = DFA_star(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), grid, start, end, output)\n",
    "            \n",
    "#                 if event.key == pygame.K_LEFT and not started:\n",
    "#                     start = None\n",
    "#                     end = None\n",
    "#                     visited = []\n",
    "#                     path = []\n",
    "#                     weighted = []\n",
    "#                     for row in grid:\n",
    "#                         for node in row:\n",
    "#                             if node.is_barrier() or node.is_start() or node.is_end():\n",
    "#                                 node.reset()\n",
    "#                     dfs_maze(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), width, grid, start, end, 0, ROWS, 0, ROWS, win)\n",
    "                \n",
    "#                 if event.key == pygame.K_UP and not started:\n",
    "#                     start = None\n",
    "#                     end = None\n",
    "#                     visited = []\n",
    "#                     path = []\n",
    "#                     weighted = []\n",
    "#                     for row in grid:\n",
    "#                         for node in row:\n",
    "#                             if node.is_barrier() or node.is_start() or node.is_end():\n",
    "#                                 node.reset()\n",
    "#                     moded_sidewinder_maze(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), width, grid, start, end, 0, ROWS, 0, ROWS, win)\n",
    "                \n",
    "#                 if event.key == pygame.K_DOWN and not started:\n",
    "#                     start = None\n",
    "#                     end = None\n",
    "#                     visited = []\n",
    "#                     path = []\n",
    "#                     weighted = []\n",
    "#                     for row in grid:\n",
    "#                         for node in row:\n",
    "#                             node.reset()\n",
    "#                     recursive_div(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), width, grid, start, end, 0, ROWS, 0, ROWS, win)\n",
    "# #                     weighted = recursive_weight_div(lambda: draw(win, grid, ROWS, width, algorithms, mazes, options, output), width, grid, start, end, 0, ROWS, 0, ROWS)\n",
    "                \n",
    "#                 if event.key == pygame.K_c and not started:\n",
    "#                     weighted = []\n",
    "#                     start = None\n",
    "#                     end = None\n",
    "#                     visited = []\n",
    "#                     path = []\n",
    "#                     weighted = []\n",
    "#                     for row in grid:\n",
    "#                         for node in row:\n",
    "#                             node.reset()\n",
    "            \n",
    "    pygame.quit()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "pygame.init()\n",
    "WIDTH = 800\n",
    "WIN = pygame.display.set_mode((WIDTH+700, WIDTH))\n",
    "\n",
    "pygame.display.set_caption(\"Path Finder\")\n",
    "main(WIN, WIDTH)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pygame",
   "language": "python",
   "name": "pygame"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}