Maze Solver.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import pandas as pd\n",
    "import os\n",
    "import math\n",
    "import heapq\n",
    "import collections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "metadata": {},
   "outputs": [],
   "source": [
    "class grid_cell():\n",
    "    def __init__(self,parent_i,parent_j,f,g,h):\n",
    "        self.parent_i = parent_i\n",
    "        self.parent_j = parent_j\n",
    "        self.f = f\n",
    "        self.g = g\n",
    "        self.h = h\n",
    "    def getParent_i(self):\n",
    "        return self.parent_i\n",
    "    def getParent_j(self):\n",
    "        return self.parent_j\n",
    "    def getF(self):\n",
    "        return self.f\n",
    "    def getG(self):\n",
    "        return self.g\n",
    "    def getH(self):\n",
    "        return self.h\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValid(row,col,n,m):\n",
    "    if(row>=0 and row<n and col>=0 and col<m):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def isUnBlock(grid,row,col):\n",
    "    if(grid[row][col]==1):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "    \n",
    "def isDestination(pair,dest):\n",
    "    if(pair[0]==dest[0] and pair[1]==dest[1]):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "    \n",
    "def calValH(row,col,dest):\n",
    "    val = float(math.sqrt((row-dest[0])*(row-dest[0])+(col-dest[1])*(col-dest[1])))\n",
    "    return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "metadata": {},
   "outputs": [],
   "source": [
    "line_path=[]\n",
    "def tracePath(cellDetail,dest):\n",
    "    print(\"Path is\")\n",
    "    row = dest[0]\n",
    "    col = dest[1]\n",
    "    path_list = []\n",
    "    while(not(cellDetail[row][col].parent_i==row and cellDetail[row][col].parent_j==col)):\n",
    "        path_list.append((row,col))\n",
    "        temp_row= cellDetail[row][col].parent_i\n",
    "        temp_col = cellDetail[row][col].parent_j\n",
    "        row = temp_row\n",
    "        col = temp_col\n",
    "    path_list.append((row,col))\n",
    "    line_path=path_list\n",
    "    val=[]\n",
    "    for i in range(len(grid)):\n",
    "        l=[]\n",
    "        for j in range(len(grid[0])):\n",
    "            l.append(0)\n",
    "        val.append(l)\n",
    "    for x,y in path_list:\n",
    "        val[x][y]=1\n",
    "    for i in range(len(val)):\n",
    "        for j in range(len(val[0])):\n",
    "            print(val[i][j],end=\" \")\n",
    "        print(\"\\n\")\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "metadata": {},
   "outputs": [],
   "source": [
    "def aStarSearch(grid,src,dest):\n",
    "    n = len(grid)\n",
    "    m = len(grid[0])\n",
    "    if(isValid(src[0],src[1],n,m)==False):\n",
    "        print(\"Source is Invalid\")\n",
    "        return\n",
    "    if(isValid(dest[0],dest[1],n,m)==False):\n",
    "        print(\"Destination is Invalid\")\n",
    "        return\n",
    "    if(isUnBlock(grid,src[0],src[1])==False):\n",
    "        print(\"Source is blocked\")\n",
    "        return\n",
    "    if( isUnBlock(grid,dest[0],dest[1])==False):\n",
    "        print(\"Destination is blocked\")\n",
    "        return\n",
    "    if( isDestination(src,dest)==True):\n",
    "        print(\"Already on Destination\")\n",
    "        return\n",
    "    \n",
    "    closedList=[]\n",
    "    for i in range(n):\n",
    "        l=[]\n",
    "        for j in range(m):\n",
    "            l.append(False)\n",
    "        closedList.append(l)\n",
    "    #printData(closedList)\n",
    "    cellDetail=[]\n",
    "    i=0\n",
    "    j=0;\n",
    "    for i in range(n):\n",
    "        l=[]\n",
    "        for j in range(m):\n",
    "            data= grid_cell(-1,-1,float(\"inf\"),float(\"inf\"),float(\"inf\"))\n",
    "            l.append(data)\n",
    "        cellDetail.append(l)\n",
    "    #printData(cellDetail)\n",
    "    i,j= src\n",
    "    cellDetail[i][j].f=0.0\n",
    "    cellDetail[i][j].g=0.0\n",
    "    cellDetail[i][j].h=0.0\n",
    "    cellDetail[i][j].parent_i=i\n",
    "    cellDetail[i][j].parent_j=j\n",
    "    heap=[]\n",
    "    heapq.heappush(heap,(0.0,i,j))\n",
    "    foundDest=False\n",
    "    \n",
    "    while heap:\n",
    "        #p = openList.pop()\n",
    "        p= heapq.heappop(heap)\n",
    "        #print(p)\n",
    "        i=p[1]\n",
    "        j=p[2]\n",
    "        closedList[i][j]=True\n",
    "        gNew= float(\"0.0\")\n",
    "        hNew= float(\"0.0\")\n",
    "        fNew= float(\"0.0\")\n",
    "        \n",
    "        mov_x = [0,1,0,-1,0,-1,1,-1]\n",
    "        mov_y = [0,0,1,0,-1,1,-1,-1]\n",
    "        \n",
    "        for x in mov_x:\n",
    "            for y in mov_y:\n",
    "                if(isValid(i+x,j+y,n,m)==True):\n",
    "                    val_src = [i+x,j+y]\n",
    "                    if(isDestination(val_src,dest)==True):\n",
    "                        cellDetail[i+x][j+y].parent_i = i\n",
    "                        cellDetail[i+x][j+y].parent_j = j\n",
    "                        print(\"Destination Found\")\n",
    "                        tracePath(cellDetail,dest)\n",
    "                        foundDest=True\n",
    "                        return\n",
    "\n",
    "                    elif(closedList[i+x][j+y]==False and isUnBlock(grid,i+x,j+y)==True):\n",
    "                        gNew = cellDetail[i][j].g+1.414\n",
    "                        hNew = calValH(i+x,j+y,dest)\n",
    "                        fNew = gNew+hNew\n",
    "\n",
    "                        if(cellDetail[i+x][j+y].f==float(\"inf\") or cellDetail[i+x][j+y].f>fNew):\n",
    "#                             openList.append((fNew,i+x,j+y))\n",
    "                            heapq.heappush(heap,(fNew,i+x,j+y))\n",
    "#                             [openList.append(x) for x in openList if x not in openList]\n",
    "                            cellDetail[i+x][j+y].f=fNew\n",
    "                            cellDetail[i+x][j+y].g=gNew\n",
    "                            cellDetail[i+x][j+y].h=hNew\n",
    "                            cellDetail[i+x][j+y].parent_i=i\n",
    "                            cellDetail[i+x][j+y].parent_j=j\n",
    "                            \n",
    "#                     openList.sort(key = lambda ky:ky[0])\n",
    "        \n",
    "        #print(openList)\n",
    "    #printData(cellDetail)\n",
    "    if(foundDest == False):\n",
    "        print(\"Failed to find the Destination Cell\") \n",
    "    return; "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 232,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Destination Found\n",
      "Path is\n",
      "1 0 0 0 0 0 0 0 0 0 \n",
      "\n",
      "0 1 0 0 0 0 0 0 0 0 \n",
      "\n",
      "0 0 1 0 0 0 0 0 0 0 \n",
      "\n",
      "0 0 1 0 0 0 0 0 0 0 \n",
      "\n",
      "0 0 1 0 0 0 0 0 0 0 \n",
      "\n",
      "0 0 0 1 1 0 0 0 0 0 \n",
      "\n",
      "0 0 0 0 0 1 0 0 0 0 \n",
      "\n",
      "0 0 0 0 0 1 0 1 1 0 \n",
      "\n",
      "0 0 0 0 0 0 1 0 0 1 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "if __name__ == '__main__':\n",
    "    grid =[\n",
    "        [1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ], \n",
    "        [1, 1, 1, 0, 1, 1, 1, 0, 1, 1 ], \n",
    "        [ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1], \n",
    "        [ 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 ], \n",
    "        [ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 ], \n",
    "        [ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 ], \n",
    "        [ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 ], \n",
    "        [ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ], \n",
    "        [ 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 ] \n",
    "    ];\n",
    "    src = [0,0]\n",
    "    dest = [8,9]\n",
    "    aStarSearch(grid,src,dest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}