Implement-Astar.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, -1, -1, -1, -1, -1],\n",
       " [1, -1, -1, -1, -1, -1],\n",
       " [2, -1, -1, -1, -1, -1],\n",
       " [3, -1, 8, 9, 10, 11],\n",
       " [4, 5, 6, 7, -1, 12]]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# -----------\n",
    "# User Instructions:\n",
    "#\n",
    "# Modify the the search function so that it becomes\n",
    "# an A* search algorithm as defined in the previous\n",
    "# lectures.\n",
    "#\n",
    "# Your function should return the expanded grid\n",
    "# which shows, for each element, the count when\n",
    "# it was expanded or -1 if the element was never expanded.\n",
    "# \n",
    "# If there is no path from init to goal,\n",
    "# the function should return the string 'fail'\n",
    "# ----------\n",
    "\n",
    "grid = [[0, 1, 0, 0, 0, 0],\n",
    "        [0, 1, 0, 0, 0, 0],\n",
    "        [0, 1, 0, 0, 0, 0],\n",
    "        [0, 1, 0, 0, 0, 0],\n",
    "        [0, 0, 0, 0, 1, 0]]\n",
    "        \n",
    "heuristic = [[9, 8, 7, 6, 5, 4],\n",
    "             [8, 7, 6, 5, 4, 3],\n",
    "             [7, 6, 5, 4, 3, 2],\n",
    "             [6, 5, 4, 3, 2, 1],\n",
    "             [5, 4, 3, 2, 1, 0]]\n",
    "\n",
    "init = [0, 0]\n",
    "goal = [len(grid)-1, len(grid[0])-1]\n",
    "cost = 1\n",
    "\n",
    "delta = [[-1, 0 ], # go up\n",
    "         [ 0, -1], # go left\n",
    "         [ 1, 0 ], # go down\n",
    "         [ 0, 1 ]] # go right\n",
    "\n",
    "delta_name = ['^', '<', 'v', '>']\n",
    "\n",
    "def search(grid,init,goal,cost,heuristic):\n",
    "    # ----------------------------------------\n",
    "    # modify the code below\n",
    "    # ----------------------------------------\n",
    "    closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]\n",
    "    closed[init[0]][init[1]] = 1\n",
    "\n",
    "    expand = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))]\n",
    "    action = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))]\n",
    "\n",
    "    x = init[0]\n",
    "    y = init[1]\n",
    "    g = 0\n",
    "    f = g + heuristic[x][y]\n",
    "    open = [[f, g, heuristic[x][y], x, y]]\n",
    "\n",
    "    found = False  # flag that is set when search is complete\n",
    "    resign = False # flag set if we can't find expand\n",
    "    count = 0\n",
    "    \n",
    "    while not found and not resign:\n",
    "        if len(open) == 0:\n",
    "            resign = True\n",
    "            return \"Fail\"\n",
    "        else:\n",
    "            open.sort()\n",
    "            open.reverse()\n",
    "            next = open.pop()\n",
    "            x = next[3]\n",
    "            y = next[4]\n",
    "            g = next[1]\n",
    "            expand[x][y] = count\n",
    "            count += 1\n",
    "            \n",
    "            if x == goal[0] and y == goal[1]:\n",
    "                found = True\n",
    "            else:\n",
    "                for i in range(len(delta)):\n",
    "                    x2 = x + delta[i][0]\n",
    "                    y2 = y + delta[i][1]\n",
    "                    if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]):\n",
    "                        if closed[x2][y2] == 0 and grid[x2][y2] == 0:\n",
    "                            g2 = g + cost \n",
    "                            f = g2 + heuristic[x2][y2]\n",
    "                            open.append([f,g2,heuristic[x2][y2], x2, y2])\n",
    "                            closed[x2][y2] = 1\n",
    "    return expand\n",
    "search(grid,init,goal,cost,heuristic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.12 ('base')",
   "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.9.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "e572caa66b9d49951af5480c4e65bd874b4d163b9e077ed4369f2912d83d117b"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}