Search_Algorithm_on_Maze.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Classes of Maze and Weighted Maze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Maze(object):\n",
    "    def __init__(self, width, height):\n",
    "        self.width = width\n",
    "        self.height = height\n",
    "        self.walls = []\n",
    "    \n",
    "    def in_bounds(self, id):\n",
    "        (x, y) = id\n",
    "        return 0 <= x < self.width and 0 <= y < self.height\n",
    "    \n",
    "    def passable(self, id):\n",
    "        return id not in self.walls\n",
    "    \n",
    "    def neighbors(self, id):\n",
    "        (x, y) = id\n",
    "        results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)]\n",
    "        results = filter(self.in_bounds, results)\n",
    "        results = filter(self.passable, results)\n",
    "        return results\n",
    "    \n",
    "class MazeWithWeights(Maze):\n",
    "    def __init__(self, width, height):\n",
    "        super(MazeWithWeights, self).__init__(width, height)\n",
    "        self.weights = {}\n",
    "    \n",
    "    def cost(self, from_node, to_node):\n",
    "        return self.weights.get(to_node, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Draw Maze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def draw_tile(graph, id, style, width):\n",
    "    r = \".\"\n",
    "    if 'number' in style and id in style['number']: r = \"%d\" % style['number'][id]\n",
    "    if 'point_to' in style and style['point_to'].get(id, None) is not None:\n",
    "        (x1, y1) = id\n",
    "        (x2, y2) = style['point_to'][id]\n",
    "        if x2 == x1 + 1: r = u\"\\u2192\"\n",
    "        if x2 == x1 - 1: r = u\"\\u2190\"\n",
    "        if y2 == y1 + 1: r = u\"\\u2193\"\n",
    "        if y2 == y1 - 1: r = u\"\\u2191\"\n",
    "    if 'start' in style and id == style['start']: r = \"S\"\n",
    "    if 'goal' in style and id == style['goal']: r = \"G\"\n",
    "    if 'path' in style and id in style['path']: r = \"o\"\n",
    "    if id in graph.walls: r = u\"\\u254b\" #u\"\\u2588\"\n",
    "    return r\n",
    "\n",
    "def draw_grid(graph, width=2, **style):\n",
    "    for y in range(graph.height):\n",
    "        for x in range(graph.width):\n",
    "            print\"%%-%ds\" % width % draw_tile(graph, (x, y), style, width),\n",
    "        print \"\";"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dijkstra search \n",
    "\n",
    "Dijkstra's algorithm is an algorithm to use a single node as the \"source\" node and finds shortest paths from the source to all other nodes in the graph.\n",
    "https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import heapq\n",
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.elements = []\n",
    "    \n",
    "    def empty(self):\n",
    "        return len(self.elements) == 0\n",
    "    \n",
    "    def put(self, item, priority):\n",
    "        heapq.heappush(self.elements, (priority, item))\n",
    "    \n",
    "    def get(self):\n",
    "        return heapq.heappop(self.elements)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def reconstruct_path(came_from, start, goal):\n",
    "    current = goal\n",
    "    path = [current]\n",
    "    while current != start:\n",
    "        current = came_from[current]\n",
    "        path.append(current)\n",
    "    path.append(start) # optional\n",
    "    path.reverse() # optional\n",
    "    return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def dijkstra_search(graph, start, goal):\n",
    "    frontier = PriorityQueue()\n",
    "    frontier.put(start, 0)\n",
    "    came_from = {}\n",
    "    cost_so_far = {}\n",
    "    came_from[start] = None\n",
    "    cost_so_far[start] = 0\n",
    "    \n",
    "    while not frontier.empty():\n",
    "        current = frontier.get()\n",
    "        \n",
    "        if current == goal:\n",
    "            break\n",
    "        \n",
    "        for next in graph.neighbors(current):\n",
    "            new_cost = cost_so_far[current] + graph.cost(current, next)\n",
    "            if next not in cost_so_far or new_cost < cost_so_far[next]:\n",
    "                cost_so_far[next] = new_cost\n",
    "                priority = new_cost\n",
    "                frontier.put(next, priority)\n",
    "                came_from[next] = current\n",
    "    \n",
    "    return came_from, cost_so_far"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Draw a Maze Table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".  .  .  .  .  .  .  .  .  G  \n",
      ".  ╋  ╋  ╋  ╋  ╋  ╋  ╋  ╋  .  \n",
      ".  .  .  .  .  ╋  .  .  ╋  .  \n",
      "╋  ╋  .  ╋  .  .  .  ╋  ╋  .  \n",
      ".  ╋  .  ╋  ╋  ╋  .  .  ╋  .  \n",
      ".  ╋  .  .  ╋  .  ╋  .  ╋  .  \n",
      ".  ╋  ╋  .  ╋  .  ╋  .  ╋  .  \n",
      ".  .  .  .  .  .  ╋  .  ╋  .  \n",
      ".  ╋  ╋  ╋  ╋  .  ╋  .  ╋  .  \n",
      "S  .  .  ╋  .  .  ╋  .  .  .  \n"
     ]
    }
   ],
   "source": [
    "maze = MazeWithWeights(10, 10)\n",
    "maze.walls = [(1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1), (7, 1), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8),\n",
    "                 (0, 3),(1, 3),(1, 4),(1, 5),(1, 6),(1, 8),(2, 8),(3, 8),(4, 8),(3, 9),(3,3),(5,2),(7,3),(3,4),(4,4),(5,4),(4,5),(4,6),(2,6),(6,5),(6,6),(6,7),(6,8),(6,9)]\n",
    "\n",
    "s=(0, 9) #start point\n",
    "g=(9, 0) #goal point\n",
    "draw_grid(maze, start=s, goal=g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Do Djkstra Search on the Maze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "↓   ←   ←   ←   ←   ←   ←   ←   ←   G   \n",
      "↓   ╋   ╋   ╋   ╋   ╋   ╋   ╋   ╋   .   \n",
      "→   →   ↓   ←   ←   ╋   ↓   ←   ╋   .   \n",
      "╋   ╋   ↓   ╋   ↑   ←   ←   ╋   ╋   .   \n",
      "↓   ╋   ↓   ╋   ╋   ╋   ↑   ←   ╋   .   \n",
      "↓   ╋   →   ↓   ╋   ↓   ╋   ↑   ╋   .   \n",
      "↓   ╋   ╋   ↓   ╋   ↓   ╋   ↑   ╋   .   \n",
      "↓   ←   ←   ←   ←   ←   ╋   ↑   ╋   .   \n",
      "↓   ╋   ╋   ╋   ╋   ↑   ╋   ↑   ╋   .   \n",
      "S   ←   ←   ╋   →   ↑   ╋   ↑   ←   ←   \n",
      "\n",
      "15  16  17  18  19  20  21  22  23  G   \n",
      "14  ╋   ╋   ╋   ╋   ╋   ╋   ╋   ╋   .   \n",
      "13  12  11  12  13  ╋   17  18  ╋   .   \n",
      "╋   ╋   10  ╋   14  15  16  ╋   ╋   .   \n",
      "5   ╋   9   ╋   ╋   ╋   17  18  ╋   .   \n",
      "4   ╋   8   7   ╋   9   ╋   19  ╋   .   \n",
      "3   ╋   ╋   6   ╋   8   ╋   20  ╋   .   \n",
      "2   3   4   5   6   7   ╋   21  ╋   .   \n",
      "1   ╋   ╋   ╋   ╋   8   ╋   22  ╋   .   \n",
      "S   1   2   ╋   10  9   ╋   23  24  25  \n",
      "\n",
      "o   o   o   o   o   o   o   o   o   o   \n",
      "o   ╋   ╋   ╋   ╋   ╋   ╋   ╋   ╋   .   \n",
      "o   o   o   .   .   ╋   .   .   ╋   .   \n",
      "╋   ╋   o   ╋   .   .   .   ╋   ╋   .   \n",
      ".   ╋   o   ╋   ╋   ╋   .   .   ╋   .   \n",
      ".   ╋   o   o   ╋   .   ╋   .   ╋   .   \n",
      ".   ╋   ╋   o   ╋   .   ╋   .   ╋   .   \n",
      "o   o   o   o   .   .   ╋   .   ╋   .   \n",
      "o   ╋   ╋   ╋   ╋   .   ╋   .   ╋   .   \n",
      "o   .   .   ╋   .   .   ╋   .   .   .   \n"
     ]
    }
   ],
   "source": [
    "came_from, cost_so_far = dijkstra_search(maze, s, g)\n",
    "draw_grid(maze, width=3, point_to=came_from, start=s, goal=g)\n",
    "print('')\n",
    "draw_grid(maze, width=3, number=cost_so_far, start=s, goal=g)\n",
    "print('')\n",
    "draw_grid(maze, width=3, path=reconstruct_path(came_from, start=s, goal=g))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}