{ "nbformat": 4, "nbformat_minor": 0, "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.4" }, "colab": { "name": "kl_python_labirintus.ipynb", "provenance": [], "collapsed_sections": [], "toc_visible": true, "include_colab_link": true } }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "view-in-github", "colab_type": "text" }, "source": [ "\"Open" ] }, { "cell_type": "markdown", "metadata": { "id": "rGY8IlGNNFA6", "colab_type": "text" }, "source": [ "# Labirintus\n", "\n", "##Labirintus készítés\n", "12 klasszikus algoritmus választható generálására „tökéletes” mazes. \n", "\n", "\n", "\n", "http://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm\n", "http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm\n", "http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking\n", "http://weblog.jamisbuck.org/2011/1/17/maze-generation-aldous-broder-algorithm\n", "http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm\n", "http://weblog.jamisbuck.org/2011/1/24/maze-generation-hunt-and-kill-algorithm\n", "http://weblog.jamisbuck.org/2011/1/20/maze-generation-wilson-s-algorithm\n", "http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm\n", "https://en.wikipedia.org/wiki/Maze_generation_algorithm#Cellular_automaton_algorithms\n", "http://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm\n", "http://weblog.jamisbuck.org/2011/2/3/maze-generation-sidewinder-algorithm\n", "\n", "\n", "A labirintus tökéletes, ha van megoldása, és csak egy megoldás létezik. \n", "\n", "\n", "Íme WEB-es algoritmus megvalósításra:\n", "\n", "http://www.astrolog.org/labyrnth/algrithm.htm\n", "\n", "Online python oktatás:\n", "https://trinket.io/features/python3\n", "https://repl.it/@prasanththangavel/Maze-Game\n", "https://runestone.academy/runestone/books/published/pythonds/index.html" ] }, { "cell_type": "code", "metadata": { "id": "XKEgsO4XNFA8", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 1000 }, "outputId": "ce8b5ab5-6ff2-47b5-a15d-c996103b41e5" }, "source": [ "import random\n", "\n", "# Ötlet \n", "# https://scipython.com/blog/making-a-maze/ \n", "\n", "class Cell:\n", " \"\"\"A cell in the maze.\n", "\n", " A maze \"Cell\" is a point in the grid which may be surrounded by walls to\n", " the north, east, south or west.\n", "\n", " \"\"\"\n", "\n", " # A wall separates a pair of cells in the N-S or W-E directions.\n", " wall_pairs = {'N': 'S', 'S': 'N', 'E': 'W', 'W': 'E'}\n", "\n", " def __init__(self, x, y):\n", " \"\"\"Initialize the cell at (x,y). At first it is surrounded by walls.\"\"\"\n", "\n", " self.x, self.y = x, y\n", " self.walls = {'N': True, 'S': True, 'E': True, 'W': True}\n", "\n", " def has_all_walls(self):\n", " \"\"\"Does this cell still have all its walls?\"\"\"\n", "\n", " return all(self.walls.values())\n", "\n", " def knock_down_wall(self, other, wall):\n", " \"\"\"Knock down the wall between cells self and other.\"\"\"\n", "\n", " self.walls[wall] = False\n", " other.walls[Cell.wall_pairs[wall]] = False\n", "\n", "class Maze:\n", " \"\"\"A Maze, represented as a grid of cells.\"\"\"\n", "\n", " def __init__(self, nx, ny, ix=0, iy=0):\n", " \"\"\"Initialize the maze grid.\n", " The maze consists of nx x ny cells and will be constructed starting\n", " at the cell indexed at (ix, iy).\n", "\n", " \"\"\"\n", "\n", " self.nx, self.ny = nx, ny\n", " self.ix, self.iy = ix, iy\n", " self.maze_map = [[Cell(x, y) for y in range(ny)] for x in range(nx)]\n", "\n", " def cell_at(self, x, y):\n", " \"\"\"Return the Cell object at (x,y).\"\"\"\n", "\n", " return self.maze_map[x][y]\n", "\n", " def __str__(self):\n", " \"\"\"Return a (crude) string representation of the maze.\"\"\"\n", "\n", " maze_rows = ['-' * nx*2]\n", " for y in range(ny):\n", " maze_row = ['|']\n", " for x in range(nx):\n", " if self.maze_map[x][y].walls['E']:\n", " maze_row.append(' |')\n", " else:\n", " maze_row.append(' ')\n", " maze_rows.append(''.join(maze_row))\n", " maze_row = ['|']\n", " for x in range(nx):\n", " if self.maze_map[x][y].walls['S']:\n", " maze_row.append('-+')\n", " else:\n", " maze_row.append(' +')\n", " maze_rows.append(''.join(maze_row))\n", " return '\\n'.join(maze_rows)\n", "\n", " def write_svg(self, filename):\n", " \"\"\"Write an SVG image of the maze to filename.\"\"\"\n", "\n", " aspect_ratio = self.nx / self.ny\n", " # Pad the maze all around by this amount.\n", " padding = 10\n", " # Height and width of the maze image (excluding padding), in pixels\n", " height = 500\n", " width = int(height * aspect_ratio)\n", " # Scaling factors mapping maze coordinates to image coordinates\n", " scy, scx = height / ny, width / nx\n", "\n", " def write_wall(f, x1, y1, x2, y2):\n", " \"\"\"Write a single wall to the SVG image file handle f.\"\"\"\n", "\n", " print(''\n", " .format(x1, y1, x2, y2), file=f)\n", "\n", " # Write the SVG image file for maze\n", " with open(filename, 'w') as f:\n", " # SVG preamble and styles.\n", " print('', file=f)\n", " print(''\n", " .format(width+2*padding, height+2*padding,\n", " -padding, -padding, width+2*padding, height+2*padding),\n", " file=f)\n", " print('\\n\\n', file=f)\n", " # Draw the \"South\" and \"East\" walls of each cell, if present (these\n", " # are the \"North\" and \"West\" walls of a neighbouring cell in\n", " # general, of course).\n", " for x in range(nx):\n", " for y in range(ny):\n", " if maze.cell_at(x,y).walls['S']:\n", " x1, y1, x2, y2 = x*scx, (y+1)*scy, (x+1)*scx, (y+1)*scy\n", " write_wall(f, x1, y1, x2, y2)\n", " if maze.cell_at(x,y).walls['E']:\n", " x1, y1, x2, y2 = (x+1)*scx, y*scy, (x+1)*scx, (y+1)*scy\n", " write_wall(f, x1, y1, x2, y2)\n", " # Draw the North and West maze border, which won't have been drawn\n", " # by the procedure above. \n", " print(''.format(width), file=f)\n", " print(''.format(height),file=f)\n", " print('', file=f)\n", "\n", " def find_valid_neighbours(self, cell):\n", " \"\"\"Return a list of unvisited neighbours to cell.\"\"\"\n", "\n", " delta = [('W', (-1,0)),\n", " ('E', (1,0)),\n", " ('S', (0,1)),\n", " ('N', (0,-1))]\n", " neighbours = []\n", " for direction, (dx,dy) in delta:\n", " x2, y2 = cell.x + dx, cell.y + dy\n", " if (0 <= x2 < nx) and (0 <= y2 < ny):\n", " neighbour = maze.cell_at(x2, y2)\n", " if neighbour.has_all_walls():\n", " neighbours.append((direction, neighbour))\n", " return neighbours\n", "\n", " def make_maze(self):\n", " # Total number of cells.\n", " n = self.nx * self.ny\n", " cell_stack = []\n", " current_cell = self.cell_at(ix, iy)\n", " # Total number of visited cells during maze construction.\n", " nv = 1\n", "\n", " while nv < n:\n", " neighbours = self.find_valid_neighbours(current_cell)\n", "\n", " if not neighbours:\n", " # We've reached a dead end: backtrack.\n", " current_cell = cell_stack.pop()\n", " continue\n", "\n", " # Choose a random neighbouring cell and move to it.\n", " direction, next_cell = random.choice(neighbours)\n", " current_cell.knock_down_wall(next_cell, direction)\n", " cell_stack.append(current_cell)\n", " current_cell = next_cell\n", " nv += 1\n", "\n", "# Maze dimensions (ncols, nrows)\n", "nx, ny = 40, 40\n", "# Maze entry position\n", "ix, iy = 0, 0\n", "\n", "maze = Maze(nx, ny, ix, iy)\n", "maze.make_maze()\n", "\n", "print(maze)\n", "maze.write_svg('maze.svg')" ], "execution_count": 1, "outputs": [ { "output_type": "stream", "text": [ "--------------------------------------------------------------------------------\n", "| | | | | | | | |\n", "|-+ + +-+ + +-+ +-+-+-+-+ +-+-+ + +-+-+ +-+-+ + +-+-+-+ +-+-+ + + +-+-+-+ +-+ + +\n", "| | | | | | | | | | | | | | | | | | | | | |\n", "| +-+-+ +-+-+ +-+ + + + + +-+-+ +-+ + +-+-+ +-+ + +-+-+ + +-+-+ + + +-+-+-+ +-+ +\n", "| | | | | | | | | | | | | | | | | | |\n", "|-+-+-+-+ +-+-+ +-+-+-+ +-+-+ + + +-+ + +-+-+ +-+-+ +-+-+ +-+-+ + + + +-+-+-+ +-+\n", "| | | | | | | | | | | | | | | | | | |\n", "|-+-+ +-+-+-+ +-+ + + +-+-+ + +-+ +-+-+-+-+ +-+ + +-+ + + + +-+ + + +-+-+ +-+-+ +\n", "| | | | | | | | | | | | | | | | | | |\n", "| +-+ + +-+-+-+ +-+-+-+-+ + + +-+-+ +-+-+ +-+ +-+-+-+-+-+-+ + +-+-+-+ + +-+ + +-+\n", "| | | | | | | | | | | | | | | | | | | |\n", "| +-+-+-+-+-+ +-+-+ +-+ +-+ + + +-+-+ +-+ + +-+-+ + + + +-+-+-+ + + +-+-+ + +-+ +\n", "| | | | | | | | | | | | | | | | | | | | |\n", "| +-+ + + + + + + + + +-+ + +-+-+-+ + +-+-+ + +-+-+-+-+ + +-+-+-+-+-+-+ +-+ + +-+\n", "| | | | | | | | | | | | | | | | | | | | | | | |\n", "|-+-+ + + + +-+-+-+-+ +-+ + + +-+ + +-+ + +-+ +-+ + + + + + +-+ +-+-+ + + +-+-+ +\n", "| | | | | | | | | | | | | | | | | | | | | | | | |\n", "| +-+-+ + + + + + +-+ + +-+-+-+ +-+-+ + + +-+-+ + + + + + +-+ +-+ +-+ + + +-+-+-+\n", "| | | | | | | | | | | | | | | | | | | | | |\n", "| +-+ +-+-+-+ + + +-+-+ +-+-+-+-+-+ + + +-+-+ + +-+ + +-+-+ +-+ +-+ +-+-+-+-+-+ +\n", "| | | | | | | | | | | | | | | | | | |\n", "| + +-+ + +-+ + +-+-+ +-+-+ + + +-+-+ +-+ +-+ + +-+-+ + +-+-+ +-+-+-+-+ +-+ + +-+\n", "| | | | | | | | | | | | | | | | | | | | |\n", "| + + + + +-+-+ + + +-+-+-+-+ +-+ +-+-+ + + +-+-+-+-+ +-+-+ + +-+-+ +-+-+ + + + +\n", "| | | | | | | | | | | | | | | | | | | | | | |\n", "| +-+ + + + + + +-+ + +-+ +-+ + + + + +-+-+-+-+-+-+-+-+ + +-+-+ + +-+-+-+ + + + +\n", "| | | | | | | | | | | | | | | | | | | | | | | | |\n", "| + + + +-+-+-+-+ +-+ + +-+-+-+ +-+-+-+-+-+ + +-+ + + +-+ + +-+-+-+ + + +-+ +-+ +\n", "| | | | | | | | | | | | | | | | | |\n", "| + +-+-+-+-+-+ +-+-+-+ +-+ + + + +-+-+ + + + +-+-+-+-+-+ + + +-+-+-+-+ + +-+ + +\n", "| | | | | | | | | | | | | | | | | | |\n", "| +-+-+-+ + +-+ + +-+-+ + +-+ + +-+-+ + +-+-+-+ +-+-+-+-+-+ + + +-+-+-+-+ + +-+ +\n", "| | | | | | | | | | | | | | | | | | | |\n", "|-+-+-+-+ + +-+ + + +-+ +-+ +-+-+ + + +-+-+-+-+-+ + +-+ + + + +-+-+-+-+-+ + +-+-+\n", "| | | | | | | | | | | | | | | | | | | |\n", "| + +-+-+-+-+ +-+-+ +-+-+ +-+ + + + +-+-+ + +-+ + +-+ +-+ + + + +-+-+-+ + + +-+ +\n", "| | | | | | | | | | | | | | | | | | | | | | | | | |\n", "| + + + + +-+-+ + + + +-+-+ + +-+ + + + +-+ +-+-+-+ +-+ + +-+ + +-+-+ + + +-+ + +\n", "| | | | | | | | | | | | | | | | | | | | | | | |\n", "| +-+-+-+-+ +-+-+ + + + + + + + +-+ + +-+ +-+ +-+ +-+-+ + + +-+-+-+-+ +-+-+ +-+-+\n", "| | | | | | | | | | | | | | | | | |\n", "| + + +-+-+-+-+ + +-+-+-+-+-+ + +-+-+-+ +-+-+-+ +-+-+-+-+ + +-+-+ + +-+ +-+-+-+ +\n", "| | | | | | | | | | | | | | | | | |\n", "| + +-+ +-+ + +-+ + + + + +-+-+-+-+-+ + +-+ + +-+-+ + +-+-+-+-+ + +-+ +-+-+ + +-+\n", "| | | | | | | | | | | | | | | | | | | | | | | |\n", "|-+-+-+-+ +-+ + +-+ + +-+ + +-+ +-+ + + + +-+-+ + +-+-+ +-+ +-+-+ +-+ +-+ + + + +\n", "| | | | | | | | | | | | | | | | | | | | | | | |\n", "| +-+-+-+-+ +-+ +-+ +-+ +-+-+ + + +-+ + + + + +-+ +-+ +-+ +-+ + +-+ +-+-+-+ +-+ +\n", "| | | | | | | | | | | | | | | | | | | | |\n", "| + +-+ + + + +-+ +-+-+ +-+ + +-+ + +-+-+ + +-+ +-+ + + +-+ +-+-+-+-+ +-+ +-+ + +\n", "| | | | | | | | | | | | | | | | | | | | | | | | |\n", "|-+-+ + + + + + +-+ +-+-+ + + + +-+-+-+ +-+-+ +-+ + + + +-+-+ + +-+-+-+ +-+-+-+ +\n", "| | | | | | | | | | | | | | | | | | | | |\n", "| +-+-+ +-+ + + + +-+-+ + + + +-+-+-+ +-+-+-+-+ + +-+ +-+ +-+ + +-+-+ + + +-+-+ +\n", "| | | | | | | | | | | | | | | | | | | | |\n", "| + + + + +-+-+-+-+-+ + + + +-+ +-+-+-+ +-+-+-+ +-+ +-+ +-+ +-+-+-+-+-+ +-+ +-+ +\n", "| | | | | | | | | | | | | | | | | |\n", "| +-+-+-+ + + + +-+-+ + +-+ +-+-+ +-+ +-+-+-+-+ + +-+ +-+ +-+ +-+-+ +-+-+ + +-+-+\n", "| | | | | | | | | | | | | | | | | | |\n", "| +-+-+ +-+-+ +-+-+-+-+-+ +-+ + + + +-+-+-+ + +-+-+ + +-+-+ +-+ + +-+ +-+ +-+-+ +\n", "| | | | | | | | | | | | | | | | | | | |\n", "| + + +-+-+-+-+ +-+ +-+ + + +-+-+-+ +-+ +-+ + +-+ + +-+ +-+-+-+-+ + +-+ +-+-+-+ +\n", "| | | | | | | | | | | | | | | | | | | |\n", "| +-+-+-+-+ +-+ + +-+-+-+ +-+-+ +-+-+ +-+ +-+-+ + + + +-+ +-+ + +-+-+-+ + + + +-+\n", "| | | | | | | | | | | | | | | | | | | | | | |\n", "| + + + + + + +-+-+-+ + + + + +-+-+ + + +-+ + +-+ +-+-+-+-+ + + + +-+ + +-+-+-+ +\n", "| | | | | | | | | | | | | | | | | | | | | | | | |\n", "|-+ + +-+ +-+-+ + + +-+-+-+ + + + + + +-+ + +-+ +-+ +-+ +-+-+ + + +-+ + + + +-+-+\n", "| | | | | | | | | | | | | | | | | | | | | | |\n", "| +-+-+ + + + +-+-+-+ +-+-+-+ +-+-+ + + +-+-+ +-+-+-+ +-+ + +-+-+-+ + +-+ +-+-+ +\n", "| | | | | | | | | | | | | | | | | | | |\n", "| + + +-+-+-+-+-+ + +-+ +-+ + + + +-+-+ + + +-+-+ + + + + +-+ +-+-+-+-+ +-+-+ + +\n", "| | | | | | | | | | | | | | | | | | | | | |\n", "| + + +-+ +-+-+ + +-+-+-+ + +-+-+-+-+-+-+ +-+-+-+-+-+-+ +-+ +-+ +-+-+ + + + +-+ +\n", "| | | | | | | | | | | | | | | |\n", "| +-+ +-+-+ + +-+-+ + +-+-+-+-+ + + + +-+-+-+ + + +-+-+-+ + +-+-+-+ +-+-+ + + +-+\n", "| | | | | | | | | | | | | | | | | | | | | | | |\n", "| + +-+ + +-+-+-+-+-+ + +-+ + +-+ + + + +-+ +-+ +-+ + + + + + +-+-+-+ + + +-+-+ +\n", "| | | | | | | | | | | | |\n", "|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n" ], "name": "stdout" } ] }, { "cell_type": "code", "metadata": { "id": "fsNyh8Q7NFBA", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 306 }, "outputId": "2cde9ade-bfe2-43da-d8f3-7bfdba0865d7" }, "source": [ "import numpy\n", "from numpy.random import randint as rand\n", "import matplotlib.pyplot as pyplot\n", "\n", "def generate_maze(width=81, height=51, complexity=.75, density=.75):\n", " \"\"\"Generate a maze using a maze generation algorithm.\"\"\"\n", " # Only odd shapes\n", " shape = ((height // 2) * 2 + 1, (width // 2) * 2 + 1)\n", " # Adjust complexity and density relative to maze size\n", " complexity = int(complexity * (5 * (shape[0] + shape[1]))) # Number of components\n", " density = int(density * ((shape[0] // 2) * (shape[1] // 2))) # Size of components\n", " # Build actual maze\n", " Z = numpy.zeros(shape, dtype=bool)\n", " # Fill borders\n", " Z[0, :] = Z[-1, :] = 1\n", " Z[:, 0] = Z[:, -1] = 1\n", " # Make aisles\n", " for i in range(density):\n", " x, y = rand(0, shape[1] // 2) * 2, rand(0, shape[0] // 2) * 2 # Pick a random position\n", " Z[y, x] = 1\n", " for j in range(complexity):\n", " neighbours = []\n", " if x > 1: neighbours.append((y, x - 2))\n", " if x < shape[1] - 2: neighbours.append((y, x + 2))\n", " if y > 1: neighbours.append((y - 2, x))\n", " if y < shape[0] - 2: neighbours.append((y + 2, x))\n", " if len(neighbours):\n", " y_, x_ = neighbours[rand(0, len(neighbours) - 1)]\n", " if Z[y_, x_] == 0:\n", " Z[y_, x_] = 1\n", " Z[y_ + (y - y_) // 2, x_ + (x - x_) // 2] = 1\n", " x, y = x_, y_\n", " return Z\n", "\n", "pyplot.figure(figsize=(10, 5))\n", "pyplot.imshow(generate_maze(80, 40), cmap=pyplot.cm.binary, interpolation='nearest')\n", "pyplot.xticks([]), pyplot.yticks([])\n", "pyplot.show()" ], "execution_count": 2, "outputs": [ { "output_type": "display_data", "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAioAAAEhCAYAAABRH4vtAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0\ndHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAALDklEQVR4nO3dMY7suBWG0SrDuZfg/e/Ae3Hk3JE3\n0A4msDF4UqP5KNZH6ZzwAdO6pFTqH5y6fd9fX18vAICiv3y6AACAI4IKAJAlqAAAWYIKAJAlqAAA\nWT8KKu/3+x9XFQIAPNdRxnj/pD35/X7rZQYArvCfr6+vv/35H/2vHwCg4J+/+kdBBQDIElQAgCxB\nBQDIElQAgKy/zvpBhhsCAGfe7/eP/xsnKgBAlqACAGQJKgBAlqACAGQJKgBA1rSunyMj3/B9mrOO\nKfsHP+Pz9HvsHzPM7AR2ogIAZAkqAECWoAIAZAkqAECWoAIAZAkqAEDW5e3JhhX+z8zWPvsKc/lM\njbN3XMmJCgCQJagAAFmCCgCQJagAAFmCCgCQJagAAFmmJ29qdF+P2ggL96k+tbVe34j6mgr12Yff\nU6hv5/3blenJAMAjCCoAQJagAgBkCSoAQJagAgBkXd71c8Ygq++N7NHIt9hH78XRtVbe2/pzVK/v\niLqv+XkrFWov1HCmXN/Zu7xc92xOVACALEEFAMgSVACALEEFAMgSVACALEEFAMj6aHvymZmDou44\nkGp2O/HsaxVapOtm1+05/96qPa/sd6UO1ir8/jSUEAB4BEEFAMgSVACALEEFAMgSVACArGzXT73T\npGzV3q2+1swaCur3aZWVnSmeV56g8JzP5EQFAMgSVACALEEFAMgSVACALEEFAMgSVACArGx78lGr\n1N3arla74/7V6yt40h7V11pox67vEfw/JyoAQJagAgBkCSoAQJagAgBkCSoAQJagAgBkZduTR5hK\n+oenTXut11e2896tqr0+lf1pn3eex4kKAJAlqAAAWYIKAJAlqAAAWYIKAJD10a6fkW+rz/4G/spv\nzM+8VuWb+eU1Gbz2e3bdv5Wf9/r7aLZ6fZ+2870tc6ICAGQJKgBAlqACAGQJKgBAlqACAGQJKgBA\n1uXtyYZzrb/Oyj2vtEn/1K51V9xx/8prqtRWqePTdv1dsysnKgBAlqACAGQJKgBAlqACAGQJKgBA\nlqACAGRd3p58xzaulVMw6xM36/WNWPXM7jq5+8zOa9r1WfY++l7hszFi58/TzN/VTlQAgCxBBQDI\nElQAgCxBBQDIElQAgKzLu37OFDp4Rhj6971d6369GrXvOqjyjnu3s12fo4L6Wp/0mXaiAgBkCSoA\nQJagAgBkCSoAQJagAgBkCSoAQNZH25NHhiCNtEqNDlsqD6vadcjW69Wob/azVxiQt/MzcWR2a+TT\n9qG83p2f10J99UGjhhICAI8gqAAAWYIKAJAlqAAAWYIKAJB1edfPym+rF4YnzTb7m92FPSrUcKb8\n7BW+gX9Xu+5Rve5Cd+cdB/jV7/tMTlQAgCxBBQDIElQAgCxBBQDIElQAgCxBBQDIurw9eXbL2Mph\nUEf17dwyXBimdWTlkLKVz96q5+jM0bV2Hgy3ys77UH6HVVrt68P9Pn2t0XeEoYQAwCMIKgBAlqAC\nAGQJKgBAlqACAGQJKgBAVnZ68q6TIQt1F2o4U2iNnP3zChNiV6o/YzPV17py2veTnvOdJyHvuudH\nnKgAAFmCCgCQJagAAFmCCgCQJagAAFkfHUq4ysrBa4X1FmoodEoU9uH1WtuV8VMrn//ygLwr6phJ\nl07Lrr83Cu/lEU5UAIAsQQUAyBJUAIAsQQUAyBJUAIAsQQUAyMoOJTxq19p5UNQqs9sLCwOzytcZ\ntbKlszxoceefN9uu7cT1fV3FPlzDiQoAkCWoAABZggoAkCWoAABZggoAkCWoAABZ09qTC9MzV7U0\nF9Y6OhG60Ka6av8K96li9mej0Lo8sqY7PhMr/7TAiEIr9EgNu05IPlN4HkY4UQEAsgQVACBLUAEA\nsgQVACBLUAEAsqZ1/RS+TXzHYXeruitWdn/MrqF+rYLycL/KvajUUVa+7/UBuHd8vlatyYkKAJAl\nqAAAWYIKAJAlqAAAWYIKAJAlqAAAWdPak48UBjGNWlX7qiFbo1a1oI2u6Y5DJ2czCPJ7O9d+pDxY\nr/4Oqz8PI8M3V74rZ17LiQoAkCWoAABZggoAkCWoAABZggoAkCWoAABZl7cnn7njNMnZ7tgaXG8V\nfNJz+bSJ1bOfvcKaCnbeh3LtlT/Z8GlOVACALEEFAMgSVACALEEFAMgSVACArI92/dSHPt1RueOm\n8k11z+UfygPtrjDz+aus9WhNK+sr7MXIAL+Vyu/lAicqAECWoAIAZAkqAECWoAIAZAkqAECWoAIA\nZF3enlxpOX2Skba10ft0dK073vc7runMHde78rOx6ufNtut6Z7frFu5T/b28ao+cqAAAWYIKAJAl\nqAAAWYIKAJAlqAAAWZd3/TxpcNLr1R9+deSsttnf7C50Co3ci5X3rzBM7sxIfavWNLtTYva1Zl9n\n1wGDlTWVazhTH2Q4833uRAUAyBJUAIAsQQUAyBJUAIAsQQUAyBJUAICsy9uTzxSGPhU8bR9Wrbe+\nr4UBeXWFIWqFIZ+jdt2/2TWs/HlHVv4JiMKaZnKiAgBkCSoAQJagAgBkCSoAQJagAgBkCSoAQNa0\n9uTZbUpPmtJ5pl7fkULrbWXvCi2xIxOrK/t35I5rWmW0Vba8f4XaKm3pR3a9t05UAIAsQQUAyBJU\nAIAsQQUAyBJUAICsaV0/haFK9eFX5RpG965wn0bsem8Le/d6zd2/0Z9VeOfwh8Lerayh0NV4ZlXX\n7CpOVACALEEFAMgSVACALEEFAMgSVACALEEFAMia1p58pNJOOaJce2W4VHmPRt1xTUfKw0QrCmsq\n1DBqZHjkyM87U3hf7noPV/7piiNOVACALEEFAMgSVACALEEFAMgSVACALEEFAMi6vD35TGEqY6GG\nM7tOhL7jZNtCDaMKtRdqmO2Oa6rb9R1WudbMGla1XDtRAQCyBBUAIEtQAQCyBBUAIEtQAQCyPtr1\nc2bXAU4jVn7ju7CvhRpmW9WddXadwuC1EeXaRlXWtOrdUljvHYexFva10JHkRAUAyBJUAIAsQQUA\nyBJUAIAsQQUAyBJUAICsbHtyoSWq4I7D/Y6Ua/vOrrXX667Xd+Suf3KgPLjujEGGe3OiAgBkCSoA\nQJagAgBkCSoAQJagAgBkCSoAQNZH25NH2tZGJsTuOlV2pVXTf1fWsFJh/0aM1j0y3Xm2wvNS2IeV\n7riuwiTk2Z/3u90nJyoAQJagAgBkCSoAQJagAgBkCSoAQNblXT+j32Ze9a3lJw12GnXHgV6zrepy\nGt2jO97DcmfUzs/yiMLw1EINFTvX/itOVACALEEFAMgSVACALEEFAMgSVACALEEFAMi6vD159iCm\nkVbBuw1o+h31NtqZNcxWaPkr7MPr1R7GVxhCWtiHUbNrv+Ow2EJ9hRrOzHxfOlEBALIEFQAgS1AB\nALIEFQAgS1ABALIu7/oZVeiweBLDI/ewch9m39vCPawPZxzpkKm747DA+nN0N05UAIAsQQUAyBJU\nAIAsQQUAyBJUAIAsQQUAyPpoe3J9qBJreR6+d8c9uuOazqwaDHp2rZWt5wZBXqOw52cMJQQAHkFQ\nAQCyBBUAIEtQAQCyBBUAIEtQAQCyLm9PNv2RP/NMjKvv3Uh99TWtdMepvHdcU93d9sKJCgCQJagA\nAFmCCgCQJagAAFmCCgCQNa3rpzAECQC4FycqAECWoAIAZAkqAECWoAIAZAkqAECWoAIAZP20Pfnf\nr9frX1cUAgA82t9/9Y/vu01ZBADuw//6AQCyBBUAIEtQAQCyBBUAIEtQAQCyBBUAIEtQAQCyBBUA\nIEtQAQCy/gtbr3BRcnuKJQAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "tags": [] } } ] }, { "cell_type": "code", "metadata": { "id": "bSzr5v6dNFBC", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "outputId": "282be929-5a5e-4c18-c1ab-ec630a0680cd" }, "source": [ "def Dijkstra(Graph, source):\n", " '''\n", " + +---+---+\n", " | 0 1 2 |\n", " +---+ + +\n", " | 3 4 | 5 \n", " +---+---+---+\n", " \n", " >>> graph = ( # or ones on the diagonal\n", " ... (0,1,0,0,0,0,),\n", " ... (1,0,1,0,1,0,),\n", " ... (0,1,0,0,0,1,),\n", " ... (0,0,0,0,1,0,),\n", " ... (0,1,0,1,0,0,),\n", " ... (0,0,1,0,0,0,),\n", " ... )\n", " ...\n", " >>> Dijkstra(graph, 0)\n", " ([0, 1, 2, 3, 2, 3], [1e+140, 0, 1, 4, 1, 2])\n", " >>> display_solution([1e+140, 0, 1, 4, 1, 2])\n", " 5<2<1<0\n", " '''\n", " # Graph[u][v] is the weight from u to v (however 0 means infinity)\n", " infinity = float('infinity')\n", " n = len(graph)\n", " dist = [infinity]*n # Unknown distance function from source to v\n", " previous = [infinity]*n # Previous node in optimal path from source\n", " dist[source] = 0 # Distance from source to source\n", " Q = list(range(n)) # All nodes in the graph are unoptimized - thus are in Q\n", " while Q: # The main loop\n", " u = min(Q, key=lambda n:dist[n]) # vertex in Q with smallest dist[]\n", " Q.remove(u)\n", " if dist[u] == infinity:\n", " break # all remaining vertices are inaccessible from source\n", " for v in range(n): # each neighbor v of u\n", " if Graph[u][v] and (v in Q): # where v has not yet been visited\n", " alt = dist[u] + Graph[u][v]\n", " if alt < dist[v]: # Relax (u,v,a)\n", " dist[v] = alt\n", " previous[v] = u\n", " return dist,previous\n", " \n", "def display_solution(predecessor):\n", " cell = len(predecessor)-1\n", " while cell:\n", " print(cell,end='<')\n", " cell = predecessor[cell]\n", " print(0)\n", " \n", "graph = ( # or ones on the diagonal\n", " (0,1,0,0,0,0,),\n", " (1,0,1,0,1,0,),\n", " (0,1,0,0,0,1,),\n", " (0,0,0,0,1,0,),\n", " (0,1,0,1,0,0,),\n", " (0,0,1,0,0,0,),\n", " )\n", " \n", "Dijkstra(graph, 0)\n" ], "execution_count": 3, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "([0, 1, 2, 3, 2, 3], [inf, 0, 1, 4, 1, 2])" ] }, "metadata": { "tags": [] }, "execution_count": 3 } ] }, { "cell_type": "code", "metadata": { "id": "F1W5vWM9NFBE", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 557 }, "outputId": "99e58d64-92c8-401d-975f-f072114504fc" }, "source": [ "#!/usr/bin/env python3\n", "import os\n", "import cv2\n", "import glob\n", "import shutil\n", "import random\n", "import imageio\n", "from PIL import Image\n", "from queue import Queue\n", "from time import perf_counter\n", "\n", "\n", "class MazeSolver:\n", " \"\"\"\n", " Solve a 2-color(wall color and path color) maze using several algorithm choices:\n", " - Breadth-First Search Algorithm(BFS).\n", " \"\"\"\n", "\n", " def __init__(\n", " self,\n", " maze_path,\n", " marking_color,\n", " start_end=None,\n", " solution_size=(500, 500),\n", " downsize=(150, 150),\n", " ):\n", " \"\"\"\n", " Initialize maze image, mark start and end points.\n", " maze_path: a string (path to maze image).\n", " marking_color: RGB tuple of color to use for drawing the solution path.\n", " solution_size: a tuple (height, width) of the solved version size.\n", " start_end: a tuple of x, y coordinates of maze start and x, y coordinates of maze end or\n", " 'a' for automatic mode.\n", " \"\"\"\n", " self.path = input(\n", " \"Enter folder path to save images and GIF frames: \"\n", " ).rstrip()\n", " while not os.path.exists(self.path):\n", " print(f\"Invalid folder path {self.path}\")\n", " self.path = input(\n", " \"Enter folder path to save images and gifs: \"\n", " ).rstrip()\n", " self.maze = Image.open(maze_path).resize(downsize)\n", " self.downsize = downsize\n", " self.height, self.width = self.maze.size\n", " self.maze_path = maze_path\n", " self.marking_color = marking_color\n", " if start_end == \"a\":\n", " self.initial_coordinates = []\n", " self._automatic_start_end()\n", " self.start, self.end = self.initial_coordinates\n", " if start_end and start_end != \"a\":\n", " self.start, self.end = start_end\n", " if not start_end:\n", " self.initial_coordinates = []\n", " self.titles = [\"(End)\", \"(Start)\"]\n", " self._set_start_end()\n", " self.start, self.end = self.initial_coordinates\n", " self.path_color = self.maze.getpixel(\n", " (self.start[0], self.start[1])\n", " )\n", " self.wall_color = self.maze.getpixel((0, 0))\n", " self.solution_name = (\n", " str(random.randint(10 ** 6, 10 ** 8))\n", " + \" Maze solution\"\n", " )\n", " self.output_image_size = solution_size\n", " self.configurations = {\n", " \"bfs\": self._breadth_first_search()\n", " }\n", " self.algorithm_names = {\n", " \"bfs\": \"BREADTH-FIRST SEARCH \"\n", " }\n", "\n", " def _automatic_start_end(self):\n", " \"\"\"Determine start and end automatically\"\"\"\n", " start = 0\n", " end_rows, end_columns = (\n", " self.height - 1,\n", " self.width - 1,\n", " )\n", " border_color = self.maze.getpixel((0, 0))\n", " while (\n", " self.maze.getpixel((start, start))\n", " == border_color\n", " ):\n", " start += 1\n", " while (\n", " self.maze.getpixel((end_rows, end_columns))\n", " == border_color\n", " ):\n", " end_rows -= 1\n", " end_columns -= 1\n", " self.initial_coordinates.append((start, start))\n", " self.initial_coordinates.append(\n", " (end_rows, end_columns)\n", " )\n", "\n", " def _set_start_end(self):\n", " \"\"\"\n", " Show maze image to determine coordinates.\n", " You will be shown the maze, click twice, first to indicate the starting point\n", " and second to indicate ending point and then press any key to proceed.\n", " \"\"\"\n", " maze_image = cv2.imread(self.maze_path)\n", " resized_image = cv2.resize(\n", " maze_image, self.downsize\n", " )\n", " cv2.namedWindow(\"Maze to solve\")\n", " cv2.setMouseCallback(\n", " \"Maze to solve\", self._get_mouse_click\n", " )\n", " cv2.imshow(\"Maze to solve\", resized_image)\n", " cv2.waitKey(0)\n", " cv2.destroyAllWindows()\n", " if len(self.initial_coordinates) != 2:\n", " raise ValueError(\n", " f\"Expected 2 clicks for start and end \"\n", " f\"respectively, got {len(self.initial_coordinates)}\"\n", " )\n", "\n", " def _get_mouse_click(self, event, x, y, flags, param):\n", " \"\"\"Get x, y coordinates for mouse clicks on maze image.\"\"\"\n", " if event == cv2.EVENT_LBUTTONDOWN:\n", " self.initial_coordinates.append((x, y))\n", " print(\n", " f\"Clicked on coordinates {x, y} {self.titles.pop()} color: {self.maze.getpixel((x, y))}\"\n", " )\n", "\n", " def _get_neighbor_coordinates(self, coordinates):\n", " \"\"\"\n", " Return a list of adjacent pixel coordinates that represent a path.\"\"\"\n", " x, y = coordinates\n", " north = (x - 1, y)\n", " if north[0] < 0:\n", " north = None\n", " if (\n", " north\n", " and self.maze.getpixel(north) == self.wall_color\n", " ):\n", " north = None\n", " south = (x + 1, y)\n", " if south[0] > self.height:\n", " south = None\n", " if (\n", " south\n", " and self.maze.getpixel(south) == self.wall_color\n", " ):\n", " south = None\n", " east = (x, y + 1)\n", " if east[1] > self.width:\n", " east = None\n", " if (\n", " east\n", " and self.maze.getpixel(east) == self.wall_color\n", " ):\n", " east = None\n", " west = (x, y - 1)\n", " if west[1] < 0:\n", " west = None\n", " if (\n", " west\n", " and self.maze.getpixel(west) == self.wall_color\n", " ):\n", " west = None\n", " return [\n", " neighbor\n", " for neighbor in (north, south, east, west)\n", " if neighbor\n", " ]\n", "\n", " def _breadth_first_search(self):\n", " \"\"\"Return path and visited pixels solved by a breadth-first search algorithm.\"\"\"\n", " check = Queue()\n", " check.put([self.start])\n", " visited = []\n", " while not check.empty():\n", " path = check.get()\n", " last = path[-1]\n", " if last == self.end:\n", " return path, visited\n", " if last not in visited:\n", " neighbor_coordinates = self._get_neighbor_coordinates(\n", " last\n", " )\n", " valid_coordinates = [\n", " neighbor\n", " for neighbor in neighbor_coordinates\n", " if neighbor not in visited\n", " ]\n", " for valid_coordinate in valid_coordinates:\n", " new_path = list(path)\n", " new_path.append(valid_coordinate)\n", " check.put(new_path)\n", " visited.append(last)\n", " raise ValueError(\n", " f\"Too low downsize rate {self.downsize}\"\n", " )\n", "\n", " def produce_path_image(self, configuration):\n", " \"\"\"\n", " Draw path in maze and return solved maze picture.\n", " configuration: a string representing the algorithm:\n", " - 'bfs': solve using breadth-first search algorithm.\n", " \"\"\"\n", " start_time = perf_counter()\n", " os.chdir(self.path)\n", " if configuration not in self.configurations:\n", " raise ValueError(\n", " f\"Invalid configuration {configuration}\"\n", " )\n", " path, visited = self.configurations[configuration]\n", " for coordinate in path:\n", " self.maze.putpixel(\n", " coordinate, self.marking_color\n", " )\n", " if \"Solutions\" not in os.listdir(self.path):\n", " os.mkdir(\"Solutions\")\n", " os.chdir(\"Solutions\")\n", " maze_name = \"\".join(\n", " [\n", " self.algorithm_names[configuration],\n", " self.solution_name,\n", " \".png\",\n", " ]\n", " )\n", " resized_maze = self.maze.resize(\n", " self.output_image_size\n", " )\n", " resized_maze.save(maze_name)\n", " end_time = perf_counter()\n", " print(f\"Time: {end_time - start_time} seconds.\")\n", " return resized_maze\n", "\n", " def produce_maze_solving_visualization(\n", " self, configuration, frame_speed, new_size=None\n", " ):\n", " \"\"\"\n", " Generate GIF for the solution of the maze by the selected algorithm:\n", " configuration: a string:\n", " - 'bfs': Breadth-first search algorithm.\n", " frame_speed: frame speed in ms\n", " new_size: a tuple containing new (height, width)\n", " \"\"\"\n", " start_time = perf_counter()\n", " initial_image = Image.open(self.maze_path).resize(\n", " self.downsize\n", " )\n", " os.chdir(self.path)\n", " if configuration not in self.configurations:\n", " raise ValueError(\n", " f\"Invalid configuration {configuration}\"\n", " )\n", " path, visited = self.configurations[configuration]\n", " count = 1\n", " for coordinate in visited:\n", " self.maze.putpixel(\n", " coordinate, self.marking_color\n", " )\n", " if new_size:\n", " resized = self.maze.resize(new_size)\n", " resized.save(str(count) + \".png\")\n", " else:\n", " self.maze.save(str(count) + \".png\")\n", " count += 1\n", " if new_size:\n", " resized = initial_image.resize(new_size)\n", " resized.save(str(count) + \".png\")\n", " else:\n", " initial_image.save(str(count) + \".png\")\n", " count += 1\n", " for coordinate in path[::-1]:\n", " initial_image.putpixel(\n", " coordinate, self.marking_color\n", " )\n", " if new_size:\n", " resized = initial_image.resize(new_size)\n", " resized.save(str(count) + \".png\")\n", " else:\n", " initial_image.save(str(count) + \".png\")\n", " count += 1\n", " os.mkdir(self.solution_name)\n", " for file in os.listdir(self.path):\n", " if file.endswith(\".png\"):\n", " shutil.move(file, self.solution_name)\n", " os.chdir(self.solution_name)\n", " frames = glob.glob(\"*.png\")\n", " frames.sort(key=lambda x: int(x.split(\".\")[0]))\n", " frames = [imageio.imread(frame) for frame in frames]\n", " imageio.mimsave(\n", " self.path + str(self.solution_name) + \".gif\",\n", " frames,\n", " \"GIF\",\n", " duration=frame_speed,\n", " )\n", " end_time = perf_counter()\n", " print(f\"Time: {end_time - start_time} seconds.\")\n", "\n", "\n", "#if __name__ == \"__main__\":\n", "test = MazeSolver(\"/content/sample_data/test.png\", (255, 0, 0), \"a\")\n", "test.produce_path_image(\"bfs\").show()" ], "execution_count": 9, "outputs": [ { "output_type": "error", "ename": "KeyboardInterrupt", "evalue": "ignored", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)", "\u001b[0;32m/usr/local/lib/python3.6/dist-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36m_input_request\u001b[0;34m(self, prompt, ident, parent, password)\u001b[0m\n\u001b[1;32m 729\u001b[0m \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 730\u001b[0;31m \u001b[0mident\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mreply\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msession\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrecv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstdin_socket\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 731\u001b[0m \u001b[0;32mexcept\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m/usr/local/lib/python3.6/dist-packages/jupyter_client/session.py\u001b[0m in \u001b[0;36mrecv\u001b[0;34m(self, socket, mode, content, copy)\u001b[0m\n\u001b[1;32m 802\u001b[0m \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 803\u001b[0;31m \u001b[0mmsg_list\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msocket\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrecv_multipart\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmode\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcopy\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mcopy\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 804\u001b[0m \u001b[0;32mexcept\u001b[0m \u001b[0mzmq\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mZMQError\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0me\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m/usr/local/lib/python3.6/dist-packages/zmq/sugar/socket.py\u001b[0m in \u001b[0;36mrecv_multipart\u001b[0;34m(self, flags, copy, track)\u001b[0m\n\u001b[1;32m 465\u001b[0m \"\"\"\n\u001b[0;32m--> 466\u001b[0;31m \u001b[0mparts\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrecv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mflags\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcopy\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mcopy\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtrack\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mtrack\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 467\u001b[0m \u001b[0;31m# have first part already, only loop while more to receive\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32mzmq/backend/cython/socket.pyx\u001b[0m in \u001b[0;36mzmq.backend.cython.socket.Socket.recv\u001b[0;34m()\u001b[0m\n", "\u001b[0;32mzmq/backend/cython/socket.pyx\u001b[0m in \u001b[0;36mzmq.backend.cython.socket.Socket.recv\u001b[0;34m()\u001b[0m\n", "\u001b[0;32mzmq/backend/cython/socket.pyx\u001b[0m in \u001b[0;36mzmq.backend.cython.socket._recv_copy\u001b[0;34m()\u001b[0m\n", "\u001b[0;32m/usr/local/lib/python3.6/dist-packages/zmq/backend/cython/checkrc.pxd\u001b[0m in \u001b[0;36mzmq.backend.cython.checkrc._check_rc\u001b[0;34m()\u001b[0m\n", "\u001b[0;31mKeyboardInterrupt\u001b[0m: ", "\nDuring handling of the above exception, another exception occurred:\n", "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 298\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 299\u001b[0m \u001b[0;31m#if __name__ == \"__main__\":\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 300\u001b[0;31m \u001b[0mtest\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMazeSolver\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"/content/sample_data/test.png\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m255\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"a\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 301\u001b[0m \u001b[0mtest\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mproduce_path_image\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"bfs\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, maze_path, marking_color, start_end, solution_size, downsize)\u001b[0m\n\u001b[1;32m 33\u001b[0m \"\"\"\n\u001b[1;32m 34\u001b[0m self.path = input(\n\u001b[0;32m---> 35\u001b[0;31m \u001b[0;34m\"Enter folder path to save images and GIF frames: \"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 36\u001b[0m ).rstrip()\n\u001b[1;32m 37\u001b[0m \u001b[0;32mwhile\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mos\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexists\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpath\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m/usr/local/lib/python3.6/dist-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36mraw_input\u001b[0;34m(self, prompt)\u001b[0m\n\u001b[1;32m 703\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_parent_ident\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 704\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_parent_header\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 705\u001b[0;31m \u001b[0mpassword\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mFalse\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 706\u001b[0m )\n\u001b[1;32m 707\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m/usr/local/lib/python3.6/dist-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36m_input_request\u001b[0;34m(self, prompt, ident, parent, password)\u001b[0m\n\u001b[1;32m 733\u001b[0m \u001b[0;32mexcept\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 734\u001b[0m \u001b[0;31m# re-raise KeyboardInterrupt, to truncate traceback\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 735\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 736\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 737\u001b[0m \u001b[0;32mbreak\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mKeyboardInterrupt\u001b[0m: " ] } ] }, { "cell_type": "code", "metadata": { "id": "DH940FjzNFBG", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 375 }, "outputId": "dee37c6d-8371-4816-d7be-10d5abeeed1b" }, "source": [ "\"\"\"\n", "Sample Python/Pygame Programs\n", "Simpson College Computer Science\n", "http://programarcadegames.com/\n", "http://simpson.edu/computer-science/\n", " \n", "From:\n", "http://programarcadegames.com/python_examples/f.php?file=maze_runner.py\n", " \n", "Explanation video: http://youtu.be/5-SbFanyUkQ\n", " \n", "Part of a series:\n", "http://programarcadegames.com/python_examples/f.php?file=move_with_walls_example.py\n", "http://programarcadegames.com/python_examples/f.php?file=maze_runner.py\n", "http://programarcadegames.com/python_examples/f.php?file=platform_jumper.py\n", "http://programarcadegames.com/python_examples/f.php?file=platform_scroller.py\n", "http://programarcadegames.com/python_examples/f.php?file=platform_moving.py\n", "http://programarcadegames.com/python_examples/sprite_sheets/\n", "\"\"\"\n", "import pygame\n", " \n", "BLACK = (0, 0, 0)\n", "WHITE = (255, 255, 255)\n", "BLUE = (0, 0, 255)\n", "GREEN = (0, 255, 0)\n", "RED = (255, 0, 0)\n", "PURPLE = (255, 0, 255)\n", " \n", " \n", "class Wall(pygame.sprite.Sprite):\n", " \"\"\"This class represents the bar at the bottom that the player controls \"\"\"\n", " \n", " def __init__(self, x, y, width, height, color):\n", " \"\"\" Constructor function \"\"\"\n", " \n", " # Call the parent's constructor\n", " super().__init__()\n", " \n", " # Make a BLUE wall, of the size specified in the parameters\n", " self.image = pygame.Surface([width, height])\n", " self.image.fill(color)\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", " \n", " \n", "class Player(pygame.sprite.Sprite):\n", " \"\"\" This class represents the bar at the bottom that the\n", " player controls \"\"\"\n", " \n", " # Set speed vector\n", " change_x = 0\n", " change_y = 0\n", " \n", " def __init__(self, x, y):\n", " \"\"\" Constructor function \"\"\"\n", " \n", " # Call the parent's constructor\n", " super().__init__()\n", " \n", " # Set height, width\n", " self.image = pygame.Surface([15, 15])\n", " self.image.fill(WHITE)\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", " \n", " def changespeed(self, x, y):\n", " \"\"\" Change the speed of the player. Called with a keypress. \"\"\"\n", " self.change_x += x\n", " self.change_y += y\n", " \n", " def move(self, walls):\n", " \"\"\" Find a new position for the player \"\"\"\n", " \n", " # Move left/right\n", " self.rect.x += self.change_x\n", " \n", " # Did this update cause us to hit a wall?\n", " block_hit_list = pygame.sprite.spritecollide(self, walls, False)\n", " for block in block_hit_list:\n", " # If we are moving right, set our right side to the left side of\n", " # the item we hit\n", " if self.change_x > 0:\n", " self.rect.right = block.rect.left\n", " else:\n", " # Otherwise if we are moving left, do the opposite.\n", " self.rect.left = block.rect.right\n", " \n", " # Move up/down\n", " self.rect.y += self.change_y\n", " \n", " # Check and see if we hit anything\n", " block_hit_list = pygame.sprite.spritecollide(self, walls, False)\n", " for block in block_hit_list:\n", " \n", " # Reset our position based on the top/bottom of the object.\n", " if self.change_y > 0:\n", " self.rect.bottom = block.rect.top\n", " else:\n", " self.rect.top = block.rect.bottom\n", " \n", " \n", "class Room(object):\n", " \"\"\" Base class for all rooms. \"\"\"\n", " \n", " # Each room has a list of walls, and of enemy sprites.\n", " wall_list = None\n", " enemy_sprites = None\n", " \n", " def __init__(self):\n", " \"\"\" Constructor, create our lists. \"\"\"\n", " self.wall_list = pygame.sprite.Group()\n", " self.enemy_sprites = pygame.sprite.Group()\n", " \n", " \n", "class Room1(Room):\n", " \"\"\"This creates all the walls in room 1\"\"\"\n", " def __init__(self):\n", " super().__init__()\n", " # Make the walls. (x_pos, y_pos, width, height)\n", " \n", " # This is a list of walls. Each is in the form [x, y, width, height]\n", " walls = [[0, 0, 20, 250, WHITE],\n", " [0, 350, 20, 250, WHITE],\n", " [780, 0, 20, 250, WHITE],\n", " [780, 350, 20, 250, WHITE],\n", " [20, 0, 760, 20, WHITE],\n", " [20, 580, 760, 20, WHITE],\n", " [390, 50, 20, 500, BLUE]\n", " ]\n", " \n", " # Loop through the list. Create the wall, add it to the list\n", " for item in walls:\n", " wall = Wall(item[0], item[1], item[2], item[3], item[4])\n", " self.wall_list.add(wall)\n", " \n", " \n", "class Room2(Room):\n", " \"\"\"This creates all the walls in room 2\"\"\"\n", " def __init__(self):\n", " super().__init__()\n", " \n", " walls = [[0, 0, 20, 250, RED],\n", " [0, 350, 20, 250, RED],\n", " [780, 0, 20, 250, RED],\n", " [780, 350, 20, 250, RED],\n", " [20, 0, 760, 20, RED],\n", " [20, 580, 760, 20, RED],\n", " [190, 50, 20, 500, GREEN],\n", " [590, 50, 20, 500, GREEN]\n", " ]\n", " \n", " for item in walls:\n", " wall = Wall(item[0], item[1], item[2], item[3], item[4])\n", " self.wall_list.add(wall)\n", " \n", " \n", "class Room3(Room):\n", " \"\"\"This creates all the walls in room 3\"\"\"\n", " def __init__(self):\n", " super().__init__()\n", " \n", " walls = [[0, 0, 20, 250, PURPLE],\n", " [0, 350, 20, 250, PURPLE],\n", " [780, 0, 20, 250, PURPLE],\n", " [780, 350, 20, 250, PURPLE],\n", " [20, 0, 760, 20, PURPLE],\n", " [20, 580, 760, 20, PURPLE]\n", " ]\n", " \n", " for item in walls:\n", " wall = Wall(item[0], item[1], item[2], item[3], item[4])\n", " self.wall_list.add(wall)\n", " \n", " for x in range(100, 800, 100):\n", " for y in range(50, 451, 300):\n", " wall = Wall(x, y, 20, 200, RED)\n", " self.wall_list.add(wall)\n", " \n", " for x in range(150, 700, 100):\n", " wall = Wall(x, 200, 20, 200, WHITE)\n", " self.wall_list.add(wall)\n", " \n", " \n", "def main():\n", " \"\"\" Main Program \"\"\"\n", " \n", " # Call this function so the Pygame library can initialize itself\n", " pygame.init()\n", " \n", " # Create an 800x600 sized screen\n", " screen = pygame.display.set_mode([800, 600])\n", " \n", " # Set the title of the window\n", " pygame.display.set_caption('Maze Runner')\n", " \n", " # Create the player paddle object\n", " player = Player(50, 50)\n", " movingsprites = pygame.sprite.Group()\n", " movingsprites.add(player)\n", " \n", " rooms = []\n", " \n", " room = Room1()\n", " rooms.append(room)\n", " \n", " room = Room2()\n", " rooms.append(room)\n", " \n", " room = Room3()\n", " rooms.append(room)\n", " \n", " current_room_no = 0\n", " current_room = rooms[current_room_no]\n", " \n", " clock = pygame.time.Clock()\n", " \n", " done = False\n", " \n", " while not done:\n", " \n", " # --- Event Processing ---\n", " \n", " for event in pygame.event.get():\n", " if event.type == pygame.QUIT:\n", " done = True\n", " \n", " if event.type == pygame.KEYDOWN:\n", " if event.key == pygame.K_LEFT:\n", " player.changespeed(-5, 0)\n", " if event.key == pygame.K_RIGHT:\n", " player.changespeed(5, 0)\n", " if event.key == pygame.K_UP:\n", " player.changespeed(0, -5)\n", " if event.key == pygame.K_DOWN:\n", " player.changespeed(0, 5)\n", " \n", " if event.type == pygame.KEYUP:\n", " if event.key == pygame.K_LEFT:\n", " player.changespeed(5, 0)\n", " if event.key == pygame.K_RIGHT:\n", " player.changespeed(-5, 0)\n", " if event.key == pygame.K_UP:\n", " player.changespeed(0, 5)\n", " if event.key == pygame.K_DOWN:\n", " player.changespeed(0, -5)\n", " \n", " # --- Game Logic ---\n", " \n", " player.move(current_room.wall_list)\n", " \n", " if player.rect.x < -15:\n", " if current_room_no == 0:\n", " current_room_no = 2\n", " current_room = rooms[current_room_no]\n", " player.rect.x = 790\n", " elif current_room_no == 2:\n", " current_room_no = 1\n", " current_room = rooms[current_room_no]\n", " player.rect.x = 790\n", " else:\n", " current_room_no = 0\n", " current_room = rooms[current_room_no]\n", " player.rect.x = 790\n", " \n", " if player.rect.x > 801:\n", " if current_room_no == 0:\n", " current_room_no = 1\n", " current_room = rooms[current_room_no]\n", " player.rect.x = 0\n", " elif current_room_no == 1:\n", " current_room_no = 2\n", " current_room = rooms[current_room_no]\n", " player.rect.x = 0\n", " else:\n", " current_room_no = 0\n", " current_room = rooms[current_room_no]\n", " player.rect.x = 0\n", " \n", " # --- Drawing ---\n", " screen.fill(BLACK)\n", " \n", " movingsprites.draw(screen)\n", " current_room.wall_list.draw(screen)\n", " \n", " pygame.display.flip()\n", " \n", " clock.tick(60)\n", " \n", " pygame.quit()\n", " \n", "if __name__ == \"__main__\":\n", " main()" ], "execution_count": 10, "outputs": [ { "output_type": "error", "ename": "ModuleNotFoundError", "evalue": "ignored", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mModuleNotFoundError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 18\u001b[0m \u001b[0mhttp\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m//\u001b[0m\u001b[0mprogramarcadegames\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcom\u001b[0m\u001b[0;34m/\u001b[0m\u001b[0mpython_examples\u001b[0m\u001b[0;34m/\u001b[0m\u001b[0msprite_sheets\u001b[0m\u001b[0;34m/\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 19\u001b[0m \"\"\"\n\u001b[0;32m---> 20\u001b[0;31m \u001b[0;32mimport\u001b[0m \u001b[0mpygame\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 21\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 22\u001b[0m \u001b[0mBLACK\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mModuleNotFoundError\u001b[0m: No module named 'pygame'", "", "\u001b[0;31m---------------------------------------------------------------------------\u001b[0;32m\nNOTE: If your import is failing due to a missing package, you can\nmanually install dependencies using either !pip or !apt.\n\nTo view examples of installing some common dependencies, click the\n\"Open Examples\" button below.\n\u001b[0;31m---------------------------------------------------------------------------\u001b[0m\n" ] } ] }, { "cell_type": "code", "metadata": { "id": "oY8lfP5WNFBI", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 375 }, "outputId": "05e858ba-3959-4043-9c13-a9c92cebdec9" }, "source": [ "# Author: William\n", "# Description: This is a maze solving algorithm. This is an implementation of the Wall Follower Algorithm. \n", "# It uses the \"left hand\" of the robot as a means to solve the maze.\n", "# Date: April 23, 2018\n", "\n", "import sys, pygame\n", "from pygame.locals import *\n", "\n", "size_x = 32\n", "size_y = 32 \n", "\n", "change_x = 32\n", "change_y = 32\n", "\n", "Size = 32\n", "\n", "SPEED = 32\n", "timer = 375\n", "\n", "DAY9YELLOW = (255, 167, 26)\n", "GOAL = (245, 163, 183)\n", "BLACK = (0, 0, 0)\n", "WHITE = (255, 255, 255)\n", "GREY = (200, 200, 200)\n", "BLUE = (50, 50, 255)\n", "\n", "m = 21\n", "n = 21\n", "\n", "goal_x = 640\n", "goal_y = 576\n", "\n", "# List to hold all the sprites\n", "all_sprite_list = pygame.sprite.Group()\n", "clock = pygame.time.Clock()\n", "\n", " # x--->\n", " # 0 ------------------> 21\n", "maze = [ [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], # 0 y\n", " [1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 1 |\n", " [1,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 2 \\ | / \n", " [1,0,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,1,1,1], # 3 \\ /\n", " [1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 4 `\n", " [1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 5\n", " [1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 6\n", " [1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 7\n", " [1,1,1,1,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1], # 8\n", " [1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1], # 9\n", " [1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1], # 10\n", " [1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1], # 11\n", " [1,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1], # 12\n", " [1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1], # 13\n", " [1,0,0,0,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1], # 14\n", " [1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1], # 15\n", " [1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1], # 16\n", " [1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1], # 17\n", " [1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1], # 18\n", " [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1], # 19\n", " [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1], # 20\n", " [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1] ] # 21\n", "\n", "class Robot(pygame.sprite.Sprite):\n", "\n", " def __init__(self, x, y): \n", " # Call the parent's constructor\n", " super().__init__()\n", "\n", " # Set height, width\n", " self.image = pygame.Surface([Size, Size])\n", " self.image.fill(DAY9YELLOW)\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", " \n", " self.face = 5\n", " self.lhs = 4\n", " \n", " # Set speed vector\n", " self.change_x = 0\n", " self.change_y = 0\n", "\n", " self.walls = None\n", " self.goals = None\n", " self.space = None\n", " \n", " def update(self):\n", " \"\"\" Update the robot position. \"\"\"\n", " # Move left/right=====\n", " self.rect.x += self.change_x\n", "\n", " if((self.change_x<0) & (maze[int(self.rect.x/32)][int(self.rect.y/32)+1] != 1)):\n", " print (\"Going West, Turning Left\")\n", " self.face = (self.face - 1) % 4\n", " self.lhs = (self.lhs - 1) % 4\n", " \n", "\n", " if((self.change_x>0) & (maze[int(self.rect.x/32)][int(self.rect.y/32)-1] != 1)):\n", " print (\"Going East, Turning Left\")\n", " self.face = (self.face - 1) % 4\n", " self.lhs = (self.lhs - 1) % 4\n", " \n", "\n", " block_hit_list = pygame.sprite.spritecollide(self, self.walls, False)\n", " for block in block_hit_list:\n", " \n", " # Wall to the east\n", " if ((self.change_x > 0) & (self.face %4 == 1)): \n", " if((maze[int(self.rect.x/32)][int(self.rect.y/32)] == 0)):\n", " print(\"what\")\n", " self.rect.x -= self.change_x\n", " print (\"You've hit a wall at the East\")\n", " self.rect.right = block.rect.left\n", " print (\"Turning Right\")\n", " self.face = (1 + self.face ) % 4\n", " self.lhs = (1 + self.lhs) % 4\n", "\n", " # Wall to the west\n", " elif ((self.change_x < 0) & (self.face %4 ==3)): \n", " self.rect.x -= self.change_x\n", " print (\"You've hit a wall at the West!\")\n", " self.rect.left = block.rect.right\n", " print (\"Turning Right\")\n", " self.face = (self.face + 1) % 4\n", " self.lhs = (1 + self.lhs) % 4\n", "\n", "\n", " self.rect.y += self.change_y\n", "\n", " if((self.change_y>0) & (maze[int(self.rect.x/32)+1][int(self.rect.y/32)] != 1)):\n", " print (\"Going South, Turning Left\")\n", " self.face = (self.face - 1) % 4\n", " self.lhs = (self.lhs - 1) % 4\n", " \n", "\n", " if((self.change_y<0) & (maze[int(self.rect.x/32)-1][int(self.rect.y/32)] != 1)):\n", " print (\"Going North, Turning Left\")\n", " self.face = (self.face - 1) % 4\n", " self.lhs = (self.lhs - 1) % 4\n", " \n", " \n", " \n", " block_hit_list = pygame.sprite.spritecollide(self, self.walls, False)\n", " for block in block_hit_list:\n", " \n", " # Wall to the South\n", " if ((self.change_y > 0) & (self.face %4 == 2)): \n", " self.rect.y -= self.change_y\n", " print (\"You've hit a wall at the South!\")\n", " self.rect.bottom = block.rect.top\n", " print (\"Turning Right\")\n", " self.face = (1 + self.face ) % 4\n", " self.lhs = (1 + self.lhs) % 4\n", "\n", " # Wall to the North\n", " elif ((self.change_y < 0) & (self.face %4 == 0)):\n", " self.rect.y -= self.change_y\n", " print (\"You've hit a wall at the North!\")\n", " self.rect.top = block.rect.bottom\n", " print (\"Turning Right\")\n", " self.face = (self.face + 1) % 4\n", " self.lhs = (1 + self.lhs) % 4\n", "\n", " if(self.rect.x == goal_x) & (self.rect.y == goal_y):\n", " print(\"You've solved the maze! Hooray!!!\")\n", " pygame.quit()\n", " sys.exit(0)\n", " \n", " self.change_x = 0\n", " self.change_y = 0\n", " \n", " \n", "class Wall(pygame.sprite.Sprite):\n", " \"\"\" Wall the robot can run into. \"\"\"\n", " def __init__(self, x, y, width, height):\n", " \"\"\" Constructor for the wall that the robot can run into. \"\"\"\n", " super().__init__()\n", " \n", " # Make a black wall, of the size specified in the parameters\n", " self.image = pygame.Surface([width, height])\n", " self.image.fill(BLACK)\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", "\n", "class Space(pygame.sprite.Sprite):\n", " \"\"\" Wall the robot can run into. \"\"\"\n", " def __init__(self, x, y, width, height):\n", " \"\"\" Constructor for the wall that the robot can run into. \"\"\"\n", " super().__init__()\n", " \n", " # Make a transparent wall, of the size specified in the parameters\n", " self.image = pygame.Surface([width, height], pygame.SRCALPHA, 32)\n", " self.image = self.image.convert_alpha()\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", " \n", "class Goal(pygame.sprite.Sprite):\n", " \"\"\" Wall the robot can run into. \"\"\"\n", " def __init__(self, x, y, width, height):\n", " \"\"\" Constructor for the wall that the robot can run into. \"\"\"\n", " # Call the parent's constructor\n", " super().__init__()\n", " \n", " # Make the goal, of the size specified in the parameters\n", " self.image = pygame.Surface([width, height])\n", " self.image.fill(GOAL)\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", "\t\t \n", " \n", "# Left-Hand Rule wall following algorithm\n", "def LHRwallFollowing(robot, screen):\n", " face = robot.face # 0 is north, 1 is east, 2 is south, 3 is west\n", " LHS = robot.lhs\n", " position = robot\n", " \n", " #lhs is north\n", " if(LHS%4 == 0):\n", " print(\"Current Position: (\", int((robot.rect.x/32)+2),\", \", int((robot.rect.y/32)-1), \") --Going East\")\n", " robot.change_x += SPEED\n", " \n", " #lhs is east\n", " if(LHS%4 == 1):\n", " print(\"Current Position: (\", int((robot.rect.x/32)+2),\", \", int((robot.rect.y/32)-1), \") --Going South\")\n", " robot.change_y += SPEED\n", "\n", " #lhs is south\n", " if(LHS%4 == 2):\n", " print(\"Current Position: (\", int((robot.rect.x/32)+2),\", \", int((robot.rect.y/32)-1), \") --Going West\")\n", " robot.change_x += -SPEED\n", "\n", " #lhs is west\n", " if(LHS%4 == 3):\n", " print(\"Current Position: (\", int((robot.rect.x/32)+2), \", \", int((robot.rect.y/32)-1), \") --Going North\")\n", " robot.change_y += -SPEED\n", "\n", "\n", "def main():\n", " pygame.init()\n", " size = width, height = 640, 640\n", " screen = pygame.display.set_mode(size)\n", " pygame.display.set_caption('Maze Solving Project by William Z.')\n", "\n", " background = pygame.Surface(screen.get_size())\n", " background = background.convert()\n", " background.fill(WHITE)\n", " \n", " # Make the walls. (x_pos, y_pos, width, height)\n", " wall_list = pygame.sprite.Group()\n", " \n", " # Make the goal. (x_pos, y_pos, width, height)\n", " goal_list = pygame.sprite.Group()\n", " \n", " # Make the space. (x_pos, y_pos, width, height)\n", " space_list = pygame.sprite.Group()\n", " \n", " for j in range(0, n):\n", " for i in range(0, m):\n", " if(maze[i][j] == 1):\n", " wall = Wall(i*32, j*32, Size, Size)\n", " wall_list.add(wall)\n", " all_sprite_list.add(wall)\n", " if(maze[i][j] == 2):\n", " goal = Goal(i*32, j*32, Size, Size)\n", " goal_list.add(wall)\n", " all_sprite_list.add(goal)\n", " if(maze[i][j] == 0):\n", " space = Space(i*32, j*32, Size, Size)\n", " space_list.add(space)\n", " all_sprite_list.add(space)\n", "\n", " robot = Robot(-64, 32)\n", " robot.face = 1\n", " robot.lhs = 0\n", " robot.walls = wall_list\n", " robot.goals = goal_list\n", " robot.space = space_list\n", "\n", " all_sprite_list.add(robot)\n", "\n", " clock = pygame.time.Clock()\n", "\n", " done = False\n", " \n", " while not done:\n", " \n", " for event in pygame.event.get():\n", " if event.type == pygame.QUIT:\n", " done = True\n", "\n", " LHRwallFollowing(robot, screen)\n", " \n", " all_sprite_list.update()\n", " \n", " screen.fill(GREY)\n", " \n", " all_sprite_list.draw(screen)\n", " \n", " pygame.display.flip()\n", " \n", " clock.tick(60)\n", " pygame.time.wait(timer)\n", " \n", " pygame.quit()\n", " \n", "if __name__ == '__main__': \n", " main()" ], "execution_count": 11, "outputs": [ { "output_type": "error", "ename": "ModuleNotFoundError", "evalue": "ignored", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mModuleNotFoundError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32mimport\u001b[0m \u001b[0msys\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpygame\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mpygame\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlocals\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0msize_x\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m32\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mModuleNotFoundError\u001b[0m: No module named 'pygame'", "", "\u001b[0;31m---------------------------------------------------------------------------\u001b[0;32m\nNOTE: If your import is failing due to a missing package, you can\nmanually install dependencies using either !pip or !apt.\n\nTo view examples of installing some common dependencies, click the\n\"Open Examples\" button below.\n\u001b[0;31m---------------------------------------------------------------------------\u001b[0m\n" ] } ] }, { "cell_type": "code", "metadata": { "id": "Atl6SUNnNFBK", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 375 }, "outputId": "f33a3286-a405-4f3c-96f4-af4bf6184182" }, "source": [ "# Author: William\n", "# Description: This is a maze solving algorithm. This is an implementation of the Wall Follower Algorithm. \n", "# It uses the \"left hand\" of the robot as a means to solve the maze.\n", "# Date: April 23, 2018\n", "\n", "import sys, pygame\n", "from pygame.locals import *\n", "\n", "size_x = 32\n", "size_y = 32 \n", "\n", "change_x = 32\n", "change_y = 32\n", "\n", "Size = 32\n", "\n", "SPEED = 32\n", "timer = 375\n", "\n", "DAY9YELLOW = (255, 167, 26)\n", "GOAL = (245, 163, 183)\n", "BLACK = (0, 0, 0)\n", "WHITE = (255, 255, 255)\n", "GREY = (200, 200, 200)\n", "BLUE = (50, 50, 255)\n", "\n", "m = 21\n", "n = 21\n", "\n", "goal_x = 640\n", "goal_y = 576\n", "\n", "# List to hold all the sprites\n", "all_sprite_list = pygame.sprite.Group()\n", "clock = pygame.time.Clock()\n", "\n", " # x--->\n", " # 0 ------------------> 21\n", "maze = [ [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], # 0 y\n", " [1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 1 |\n", " [1,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 2 \\ | / \n", " [1,0,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,1,1,1], # 3 \\ /\n", " [1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 4 `\n", " [1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 5\n", " [1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 6\n", " [1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1], # 7\n", " [1,1,1,1,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1], # 8\n", " [1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1], # 9\n", " [1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1], # 10\n", " [1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1], # 11\n", " [1,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1], # 12\n", " [1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1], # 13\n", " [1,0,0,0,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1], # 14\n", " [1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1], # 15\n", " [1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1], # 16\n", " [1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1], # 17\n", " [1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1], # 18\n", " [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1], # 19\n", " [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1], # 20\n", " [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1] ] # 21\n", "\n", "class Robot(pygame.sprite.Sprite):\n", "\n", " def __init__(self, x, y): \n", " # Call the parent's constructor\n", " super().__init__()\n", "\n", " # Set height, width\n", " self.image = pygame.Surface([Size, Size])\n", " self.image.fill(DAY9YELLOW)\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", " \n", " self.face = 5\n", " self.lhs = 4\n", " \n", " # Set speed vector\n", " self.change_x = 0\n", " self.change_y = 0\n", "\n", " self.walls = None\n", " self.goals = None\n", " self.space = None\n", " \n", " def update(self):\n", " \"\"\" Update the robot position. \"\"\"\n", " # Move left/right=====\n", " self.rect.x += self.change_x\n", "\n", " if((self.change_x<0) & (maze[int(self.rect.x/32)][int(self.rect.y/32)+1] != 1)):\n", " print (\"Going West, Turning Left\")\n", " self.face = (self.face - 1) % 4\n", " self.lhs = (self.lhs - 1) % 4\n", " \n", "\n", " if((self.change_x>0) & (maze[int(self.rect.x/32)][int(self.rect.y/32)-1] != 1)):\n", " print (\"Going East, Turning Left\")\n", " self.face = (self.face - 1) % 4\n", " self.lhs = (self.lhs - 1) % 4\n", " \n", "\n", " block_hit_list = pygame.sprite.spritecollide(self, self.walls, False)\n", " for block in block_hit_list:\n", " \n", " # Wall to the east\n", " if ((self.change_x > 0) & (self.face %4 == 1)): \n", " if((maze[int(self.rect.x/32)][int(self.rect.y/32)] == 0)):\n", " print(\"what\")\n", " self.rect.x -= self.change_x\n", " print (\"You've hit a wall at the East\")\n", " self.rect.right = block.rect.left\n", " print (\"Turning Right\")\n", " self.face = (1 + self.face ) % 4\n", " self.lhs = (1 + self.lhs) % 4\n", "\n", " # Wall to the west\n", " elif ((self.change_x < 0) & (self.face %4 ==3)): \n", " self.rect.x -= self.change_x\n", " print (\"You've hit a wall at the West!\")\n", " self.rect.left = block.rect.right\n", " print (\"Turning Right\")\n", " self.face = (self.face + 1) % 4\n", " self.lhs = (1 + self.lhs) % 4\n", "\n", "\n", " self.rect.y += self.change_y\n", "\n", " if((self.change_y>0) & (maze[int(self.rect.x/32)+1][int(self.rect.y/32)] != 1)):\n", " print (\"Going South, Turning Left\")\n", " self.face = (self.face - 1) % 4\n", " self.lhs = (self.lhs - 1) % 4\n", " \n", "\n", " if((self.change_y<0) & (maze[int(self.rect.x/32)-1][int(self.rect.y/32)] != 1)):\n", " print (\"Going North, Turning Left\")\n", " self.face = (self.face - 1) % 4\n", " self.lhs = (self.lhs - 1) % 4\n", " \n", " \n", " \n", " block_hit_list = pygame.sprite.spritecollide(self, self.walls, False)\n", " for block in block_hit_list:\n", " \n", " # Wall to the South\n", " if ((self.change_y > 0) & (self.face %4 == 2)): \n", " self.rect.y -= self.change_y\n", " print (\"You've hit a wall at the South!\")\n", " self.rect.bottom = block.rect.top\n", " print (\"Turning Right\")\n", " self.face = (1 + self.face ) % 4\n", " self.lhs = (1 + self.lhs) % 4\n", "\n", " # Wall to the North\n", " elif ((self.change_y < 0) & (self.face %4 == 0)):\n", " self.rect.y -= self.change_y\n", " print (\"You've hit a wall at the North!\")\n", " self.rect.top = block.rect.bottom\n", " print (\"Turning Right\")\n", " self.face = (self.face + 1) % 4\n", " self.lhs = (1 + self.lhs) % 4\n", "\n", " if(self.rect.x == goal_x) & (self.rect.y == goal_y):\n", " print(\"You've solved the maze! Hooray!!!\")\n", " pygame.quit()\n", " sys.exit(0)\n", " \n", " self.change_x = 0\n", " self.change_y = 0\n", " \n", " \n", "class Wall(pygame.sprite.Sprite):\n", " \"\"\" Wall the robot can run into. \"\"\"\n", " def __init__(self, x, y, width, height):\n", " \"\"\" Constructor for the wall that the robot can run into. \"\"\"\n", " super().__init__()\n", " \n", " # Make a black wall, of the size specified in the parameters\n", " self.image = pygame.Surface([width, height])\n", " self.image.fill(BLACK)\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", "\n", "class Space(pygame.sprite.Sprite):\n", " \"\"\" Wall the robot can run into. \"\"\"\n", " def __init__(self, x, y, width, height):\n", " \"\"\" Constructor for the wall that the robot can run into. \"\"\"\n", " super().__init__()\n", " \n", " # Make a transparent wall, of the size specified in the parameters\n", " self.image = pygame.Surface([width, height], pygame.SRCALPHA, 32)\n", " self.image = self.image.convert_alpha()\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", " \n", "class Goal(pygame.sprite.Sprite):\n", " \"\"\" Wall the robot can run into. \"\"\"\n", " def __init__(self, x, y, width, height):\n", " \"\"\" Constructor for the wall that the robot can run into. \"\"\"\n", " # Call the parent's constructor\n", " super().__init__()\n", " \n", " # Make the goal, of the size specified in the parameters\n", " self.image = pygame.Surface([width, height])\n", " self.image.fill(GOAL)\n", " \n", " # Make our top-left corner the passed-in location.\n", " self.rect = self.image.get_rect()\n", " self.rect.y = y\n", " self.rect.x = x\n", "\t\t \n", " \n", "# Left-Hand Rule wall following algorithm\n", "def LHRwallFollowing(robot, screen):\n", " face = robot.face # 0 is north, 1 is east, 2 is south, 3 is west\n", " LHS = robot.lhs\n", " position = robot\n", " \n", " #lhs is north\n", " if(LHS%4 == 0):\n", " print(\"Current Position: (\", int((robot.rect.x/32)+2),\", \", int((robot.rect.y/32)-1), \") --Going East\")\n", " robot.change_x += SPEED\n", " \n", " #lhs is east\n", " if(LHS%4 == 1):\n", " print(\"Current Position: (\", int((robot.rect.x/32)+2),\", \", int((robot.rect.y/32)-1), \") --Going South\")\n", " robot.change_y += SPEED\n", "\n", " #lhs is south\n", " if(LHS%4 == 2):\n", " print(\"Current Position: (\", int((robot.rect.x/32)+2),\", \", int((robot.rect.y/32)-1), \") --Going West\")\n", " robot.change_x += -SPEED\n", "\n", " #lhs is west\n", " if(LHS%4 == 3):\n", " print(\"Current Position: (\", int((robot.rect.x/32)+2), \", \", int((robot.rect.y/32)-1), \") --Going North\")\n", " robot.change_y += -SPEED\n", "\n", "\n", "def main():\n", " pygame.init()\n", " size = width, height = 640, 640\n", " screen = pygame.display.set_mode(size)\n", " pygame.display.set_caption('Maze Solving Project by William Z.')\n", "\n", " background = pygame.Surface(screen.get_size())\n", " background = background.convert()\n", " background.fill(WHITE)\n", " \n", " # Make the walls. (x_pos, y_pos, width, height)\n", " wall_list = pygame.sprite.Group()\n", " \n", " # Make the goal. (x_pos, y_pos, width, height)\n", " goal_list = pygame.sprite.Group()\n", " \n", " # Make the space. (x_pos, y_pos, width, height)\n", " space_list = pygame.sprite.Group()\n", " \n", " for j in range(0, n):\n", " for i in range(0, m):\n", " if(maze[i][j] == 1):\n", " wall = Wall(i*32, j*32, Size, Size)\n", " wall_list.add(wall)\n", " all_sprite_list.add(wall)\n", " if(maze[i][j] == 2):\n", " goal = Goal(i*32, j*32, Size, Size)\n", " goal_list.add(wall)\n", " all_sprite_list.add(goal)\n", " if(maze[i][j] == 0):\n", " space = Space(i*32, j*32, Size, Size)\n", " space_list.add(space)\n", " all_sprite_list.add(space)\n", "\n", " robot = Robot(-64, 32)\n", " robot.face = 1\n", " robot.lhs = 0\n", " robot.walls = wall_list\n", " robot.goals = goal_list\n", " robot.space = space_list\n", "\n", " all_sprite_list.add(robot)\n", "\n", " clock = pygame.time.Clock()\n", "\n", " done = False\n", " \n", " while not done:\n", " \n", " for event in pygame.event.get():\n", " if event.type == pygame.QUIT:\n", " done = True\n", "\n", " LHRwallFollowing(robot, screen)\n", " \n", " all_sprite_list.update()\n", " \n", " screen.fill(GREY)\n", " \n", " all_sprite_list.draw(screen)\n", " \n", " pygame.display.flip()\n", " \n", " clock.tick(60)\n", " pygame.time.wait(timer)\n", " \n", " pygame.quit()\n", " \n", "if __name__ == '__main__': \n", " main()" ], "execution_count": 12, "outputs": [ { "output_type": "error", "ename": "ModuleNotFoundError", "evalue": "ignored", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mModuleNotFoundError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32mimport\u001b[0m \u001b[0msys\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpygame\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mpygame\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlocals\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0msize_x\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m32\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mModuleNotFoundError\u001b[0m: No module named 'pygame'", "", "\u001b[0;31m---------------------------------------------------------------------------\u001b[0;32m\nNOTE: If your import is failing due to a missing package, you can\nmanually install dependencies using either !pip or !apt.\n\nTo view examples of installing some common dependencies, click the\n\"Open Examples\" button below.\n\u001b[0;31m---------------------------------------------------------------------------\u001b[0m\n" ] } ] }, { "cell_type": "code", "metadata": { "id": "eIZAIVSFNFBM", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 375 }, "outputId": "1fb3afd6-20a4-4361-d8d2-a07cd3da65f7" }, "source": [ "import os\n", "import pygame\n", "import random\n", "pygame.init()\n", "white = (255,255,255)\n", "black = (0,0,0)\n", "red = (255,0,0)\n", "green = (0,155,0)\n", "brown = (205,133,63)\n", "blue = (135,206,250)\n", "FPS = 60\n", "#the dimension of the game\n", "display_width = 680\n", "display_height = 440\n", "# Class for the player\n", "class Player(object):\n", " def __init__(self):\n", " self.rect = pygame.Rect(40, 40, 30, 30)\n", " def move(self, dx, dy):\n", " # Move each axis separately. Note that this checks for collisions both times.\n", " if dx != 0:\n", " self.move_single_axis(dx, 0)\n", " if dy != 0:\n", " self.move_single_axis(0, dy)\n", " def move_single_axis(self, dx, dy):\n", " # Move the rect\n", " self.rect.x += dx\n", " self.rect.y += dy\n", " # If you collide with a wall, move out based on velocity\n", " for wall in walls:\n", " if self.rect.colliderect(wall.rect):\n", " if dx > 0: # Moving right, Hit the left side of the wall\n", " self.rect.right = wall.rect.left\n", " if dx < 0: # Moving left, Hit the right side of the wall\n", " self.rect.left = wall.rect.right\n", " if dy > 0: # Moving down, Hit the top side of the wall\n", " self.rect.bottom = wall.rect.top\n", " if dy < 0: # Moving up, Hit the bottom side of the wall\n", " self.rect.top = wall.rect.bottom\n", "# Class to hold a wall rect\n", "class Wall(object):\n", " def __init__(self, pos):\n", " walls.append(self)\n", " self.rect = pygame.Rect(pos[0], pos[1], 40, 40)\n", "font = pygame.font.SysFont(None, 50)\n", "def message_to_screen(msg,color):\n", " screen_text = font.render(msg, True, color)\n", " gameDisplay.blit(screen_text, [680/2, display_height/2])\n", "# Initialise pygame\n", "os.environ[\"Time to play\"] = \"1\"\n", "# Set up the display\n", "pygame.display.set_caption(\"Wrath of the gods\")\n", "gameDisplay = pygame.display.set_mode((display_width,display_height))\n", "clock = pygame.time.Clock()\n", "walls = [] # List to hold the walls\n", "player = Player() # Create the player\n", "# Holds the level layout in a list of strings.\n", "level = [\n", "\"WWWWWWWWWWWWWWWWW\",\n", "\"W W W W\",\n", "\"W WW W WW WWW W\",\n", "\"W W W W W W W W\",\n", "\"W WWWWW WWW W W W\",\n", "\"W W W W W W\",\n", "\"WW W WW WWWWWWW W\",\n", "\"W W W W\",\n", "\"W WWWW W WWWWW WW\",\n", "\"W W\",\n", "\"WWWWWWWWWWWWWWWEW\",\n", "]\n", "# W = wall, E = exit\n", "x = y = 0\n", "for row in level:\n", " for col in row:\n", " if col == \"W\":\n", " Wall((x, y))\n", " if col == \"E\":\n", " end_rect = pygame.Rect(x, y, 40, 40)\n", " x += 40\n", " y += 40\n", " x = 0\n", "running = True\n", "while running:\n", " clock.tick(FPS)\n", " for e in pygame.event.get():\n", " if e.type == pygame.QUIT:\n", " running = False\n", " if e.type == pygame.KEYDOWN and e.key == pygame.K_ESCAPE:\n", " running = False\n", " # Move the player\n", " key = pygame.key.get_pressed()\n", " if key[pygame.K_LEFT]:\n", " player.move(-2, 0)\n", " if key[pygame.K_RIGHT]:\n", " player.move(2, 0)\n", " if key[pygame.K_UP]:\n", " player.move(0, -2)\n", " if key[pygame.K_DOWN]:\n", " player.move(0, 2)\n", " if player.rect.colliderect(end_rect):\n", " raise SystemExit\n", " # Draw the scene\n", " gameDisplay.fill((brown))\n", " for wall in walls:\n", " pygame.draw.rect(gameDisplay, green, wall.rect)\n", " pygame.draw.rect(gameDisplay, red, end_rect)\n", " pygame.draw.rect(gameDisplay, white, player.rect)\n", " pygame.display.flip()\n", "pygame.quit()\n", "quit()" ], "execution_count": 13, "outputs": [ { "output_type": "error", "ename": "ModuleNotFoundError", "evalue": "ignored", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mModuleNotFoundError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mos\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32mimport\u001b[0m \u001b[0mpygame\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mrandom\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0mpygame\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0mwhite\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m255\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m255\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m255\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mModuleNotFoundError\u001b[0m: No module named 'pygame'", "", "\u001b[0;31m---------------------------------------------------------------------------\u001b[0;32m\nNOTE: If your import is failing due to a missing package, you can\nmanually install dependencies using either !pip or !apt.\n\nTo view examples of installing some common dependencies, click the\n\"Open Examples\" button below.\n\u001b[0;31m---------------------------------------------------------------------------\u001b[0m\n" ] } ] }, { "cell_type": "code", "metadata": { "id": "WGzUls-VNFBN", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 375 }, "outputId": "3242d808-29d6-4864-fbc4-0ad08e3102a0" }, "source": [ "import numpy\n", "from numpy.random import random_integers as rand\n", "import matplotlib.pyplot as pyplot\n", "\n", "class Cell:\n", " def __init__(self, x, y):\n", " self.x = x\n", " self.y = y\n", " self.backtrack = [0,0,0,0] #N,E,S,W\n", " self.solution = [0,0,0,0]\n", " self.walls = [1,1,1,1]\n", " self.border = [0,0,0,0]\n", " self.visited = False\n", " \n", " def drawCell(self):\n", " if self.walls[0] == 1:\n", " pyplot.hlines(y=self.y, xmin=self.x, xmax=self.x+1, linewidth=1, color='b')\n", " if self.walls[1] == 1:\n", " pyplot.vlines(x=self.x+1, ymin=self.y, ymax=self.y+1, linewidth=1, color='b')\n", " if self.walls[2] == 1:\n", " pyplot.hlines(y=self.y+1, xmin=self.x, xmax=self.x+1, linewidth=1, color='b') \n", " if self.walls[3] == 1:\n", " pyplot.vlines(x=self.x, ymin=self.y, ymax=self.y+1, linewidth=1, color='b')\n", " \n", " def setupBorder(self,xmax,ymax):\n", " if self.y == 0: #N borders\n", " self.border[0] = 1\n", " if self.x == xmax: #E borders\n", " self.border[1] = 1\n", " if self.y == ymax: #S borders\n", " self.border[2] = 1\n", " if self.x == 0: #W borders\n", " self.border[3] = 1\n", " \n", " \n", "def maze(width=16, height=12):\n", " # Build cells' fill\n", " shape = (height, width)\n", " Z = numpy.zeros(shape, dtype=bool)\n", " \n", " # Initialize 2D cell arrray\n", " cells = [[0 for y in xrange(0,height)] for x in xrange(0,width)] \n", " # Initialize all walls (all present)\n", " for y in xrange(0,height):\n", " for x in xrange(0,width):\n", " c = Cell(x,y)\n", " c.setupBorder(width-1, height-1)\n", " cells[x][y] = c\n", " \n", " # Setup Cell Stack\n", " stack = []\n", " num_total = width*height\n", " num_visited = 0 #keep track of total no. of cells visited\n", " # Get random starting cell\n", " rand_x = rand(0,width-1)\n", " rand_y = rand(0,height-1)\n", " #Z[rand_y,rand_x] = 1\n", " print ('Starting cell:(',rand_x,',' ,rand_y, ')')\n", " current_cell = cells[rand_x][rand_y]\n", " num_visited += 1\n", " \n", " # DFS Algo\n", " while num_visited < num_total:\n", " neighbours_with_all_walls = checkNeighbours(cells, current_cell, current_cell.x, current_cell.y)\n", " n = len(neighbours_with_all_walls)\n", " if n > 0:\n", " index = rand(0,n-1)\n", " rand_neighbour = neighbours_with_all_walls[index]\n", " # knock down the wall btw current cell and chosen neighbour\n", " knockdownWallBtw(current_cell, rand_neighbour)\n", " stack.append(current_cell)\n", " current_cell = rand_neighbour\n", " num_visited += 1\n", " else:\n", " cell = stack.pop()\n", " current_cell = cell\n", " \n", " # Final Drawing\n", " for y in xrange(0,height):\n", " for x in xrange(0,width):\n", " c = cells[x][y]\n", " c.drawCell()\n", " \n", " # Route (given by end stack result)\n", " #for c in stack:\n", " # pyplot.plot(c.x+0.5, c.y+0.5, linestyle='None', marker=\"s\", color=\"y\")\n", " \n", " # Get Solution for given start/end point\n", " calcSolution(cells, 0, 0, width-1, height-1)\n", " \n", " return Z\n", "\n", "def checkNeighbours(cells, current_cell, x, y):\n", " neighbours = []\n", " if current_cell.border[0] == 0: #top\n", " nt = cells[x][y-1]\n", " if nt.walls == [1,1,1,1]:\n", " neighbours.append(nt)\n", " if current_cell.border[1] == 0: #right\n", " nr = cells[x+1][y]\n", " if nr.walls == [1,1,1,1]:\n", " neighbours.append(nr)\n", " if current_cell.border[2] == 0: #bottom\n", " nb = cells[x][y+1]\n", " if nb.walls == [1,1,1,1]:\n", " neighbours.append(nb)\n", " if current_cell.border[3] == 0: #left\n", " nl = cells[x-1][y]\n", " if nl.walls == [1,1,1,1]:\n", " neighbours.append(nl)\n", " return neighbours\n", "\n", "def knockdownWallBtw(cell, nbr):\n", " #compare N,E,S,W direction to discern wall direction\n", " if nbr.y == cell.y-1:\n", " cell.walls[0] = 0\n", " nbr.walls[2] = 0 \n", " return\n", " if nbr.x == cell.x+1:\n", " cell.walls[1] = 0\n", " nbr.walls[3] = 0\n", " return\n", " if nbr.y == cell.y+1:\n", " cell.walls[2] = 0\n", " nbr.walls[0] = 0\n", " return\n", " if nbr.x == cell.x-1:\n", " cell.walls[3] = 0\n", " nbr.walls[1] = 0\n", " return\n", "\n", "# Gets the maze solution route for any given start/end point\n", "def calcSolution(cells, startx, starty, endx, endy):\n", " start_cell = cells[startx][starty]\n", " end_cell = cells[endx][endy]\n", " \n", " # DFS again...\n", " stack = []\n", " current_cell = start_cell\n", " current_cell.visited = True\n", " while current_cell != end_cell:\n", " # get random possible neighbour\n", " neighbours = getAllNeighboursNotYetVisited(cells, current_cell)\n", " n = len(neighbours)\n", " if n > 0:\n", " index = rand(0,n-1)\n", " rand_neighbour = neighbours[index]\n", " rand_neighbour.visited = True\n", " stack.append(current_cell)\n", " current_cell = rand_neighbour\n", " else: # dead end, backtrack\n", " cell = stack.pop()\n", " current_cell = cell\n", " \n", " # Plot solution\n", " for c in stack:\n", " pyplot.plot(c.x+0.5, c.y+0.5, linestyle='None', marker=\"s\", color=\"g\")\n", " pyplot.plot(start_cell.x+0.5, start_cell.y+0.5, linestyle='None', marker=\"*\", color=\"y\", markersize=20)\n", " pyplot.plot(end_cell.x+0.5, end_cell.y+0.5, linestyle='None', marker=\"*\", color=\"r\", markersize=20)\n", " \n", "def getAllNeighboursNotYetVisited(cells, c):\n", " neighbours = []\n", " if c.border[0] == 0 and c.walls[0] == 0:\n", " n = cells[c.x][c.y-1]\n", " if not n.visited:\n", " neighbours.append(n)\n", " if c.border[1] == 0 and c.walls[1] == 0:\n", " n = cells[c.x+1][c.y]\n", " if not n.visited:\n", " neighbours.append(n)\n", " if c.border[2] == 0 and c.walls[2] == 0:\n", " n = cells[c.x][c.y+1]\n", " if not n.visited:\n", " neighbours.append(n)\n", " if c.border[3] == 0 and c.walls[3] == 0:\n", " n = cells[c.x-1][c.y]\n", " if not n.visited:\n", " neighbours.append(n)\n", " return neighbours\n", " \n", "pyplot.figure(figsize=(10, 5))\n", "pyplot.imshow(maze(16, 12), cmap=pyplot.cm.binary, interpolation='nearest')\n", "#pyplot.xticks([]), pyplot.yticks([])\n", "pyplot.axis([0,16,12,0])\n", "pyplot.show()" ], "execution_count": 14, "outputs": [ { "output_type": "error", "ename": "NameError", "evalue": "ignored", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 180\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 181\u001b[0m \u001b[0mpyplot\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfigure\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfigsize\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m10\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 182\u001b[0;31m \u001b[0mpyplot\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mimshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmaze\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m16\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m12\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcmap\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mpyplot\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbinary\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minterpolation\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m'nearest'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 183\u001b[0m \u001b[0;31m#pyplot.xticks([]), pyplot.yticks([])\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 184\u001b[0m \u001b[0mpyplot\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0maxis\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m16\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m12\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mmaze\u001b[0;34m(width, height)\u001b[0m\n\u001b[1;32m 40\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 41\u001b[0m \u001b[0;31m# Initialize 2D cell arrray\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 42\u001b[0;31m \u001b[0mcells\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0my\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mxrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mheight\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mxrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mwidth\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 43\u001b[0m \u001b[0;31m# Initialize all walls (all present)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 44\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0my\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mxrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mheight\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mNameError\u001b[0m: name 'xrange' is not defined" ] }, { "output_type": "display_data", "data": { "text/plain": [ "
" ] }, "metadata": { "tags": [] } } ] }, { "cell_type": "code", "metadata": { "id": "bBbzArHnNFBP", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 413 }, "outputId": "5a829e83-8b31-43f0-c636-b2bd0a46f538" }, "source": [ "# from http://en.wikipedia.org/wiki/Maze_generation_algorithm\n", "# from http://en.wikipedia.org/wiki/Maze_generation_algorithm\n", "import numpy\n", "from numpy.random import random_integers as rand\n", "import matplotlib.pyplot as pyplot\n", " \n", "def maze(width=81, height=51, complexity=.75, density=.75):\n", " # Only odd shapes\n", " shape = ((height // 2) * 2 + 1, (width // 2) * 2 + 1)\n", " # Adjust complexity and density relative to maze size\n", " complexity = int(complexity * (5 * (shape[0] + shape[1])))\n", " density = int(density * (shape[0] // 2 * shape[1] // 2))\n", " # Build actual maze\n", " Z = numpy.zeros(shape, dtype=bool)\n", " # Fill borders\n", " Z[0, :] = Z[-1, :] = 1\n", " Z[:, 0] = Z[:, -1] = 1\n", " # Make aisles\n", " for i in range(density):\n", " x, y = rand(0, shape[1] // 2) * 2, rand(0, shape[0] // 2) * 2\n", " Z[y, x] = 1\n", " for j in range(complexity):\n", " neighbours = []\n", " if x > 1: neighbours.append((y, x - 2))\n", " if x < shape[1] - 2: neighbours.append((y, x + 2))\n", " if y > 1: neighbours.append((y - 2, x))\n", " if y < shape[0] - 2: neighbours.append((y + 2, x))\n", " if len(neighbours):\n", " y_,x_ = neighbours[rand(0, len(neighbours) - 1)]\n", " if Z[y_, x_] == 0:\n", " Z[y_, x_] = 1\n", " Z[y_ + (y - y_) // 2, x_ + (x - x_) // 2] = 1\n", " x, y = x_, y_\n", " return Z\n", " \n", "pyplot.figure(figsize=(10, 5))\n", "pyplot.imshow(maze(80, 40), cmap=pyplot.cm.binary, interpolation='nearest')\n", "pyplot.xticks([]), pyplot.yticks([])\n", "pyplot.show()" ], "execution_count": 15, "outputs": [ { "output_type": "stream", "text": [ "/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:18: DeprecationWarning: This function is deprecated. Please call randint(0, 40 + 1) instead\n", "/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:18: DeprecationWarning: This function is deprecated. Please call randint(0, 20 + 1) instead\n", "/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:27: DeprecationWarning: This function is deprecated. Please call randint(0, 3 + 1) instead\n", "/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:27: DeprecationWarning: This function is deprecated. Please call randint(0, 2 + 1) instead\n", "/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:27: DeprecationWarning: This function is deprecated. Please call randint(0, 1 + 1) instead\n" ], "name": "stderr" }, { "output_type": "display_data", "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAioAAAEhCAYAAABRH4vtAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0\ndHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAALtUlEQVR4nO3dMbLbyBWFYT6Xcy/B+9+B9+LI+USz\nATlQ5hIwVlfzvr/B7wtVJbLRAKhTGJy5Xz9+/HgBABT97bsXAABwRVABALIEFQAgS1ABALIEFQAg\n67eCytfX17/etRAA4HNdZYyv36knf3196TIDAO/w548fP/7xv3/oP/0AAAX//tUfCioAQJagAgBk\nCSoAQJagAgBk/X3XBxWGG359ff3yzwtrA37t6r59ve7vXfc7fK+Ve/fu71zxRAUAyBJUAIAsQQUA\nyBJUAIAsQQUAyNrW+rmy8obvnZU3+lfXsPLW8kpLYcXU96yqr69u5xvzFVNtnMk9+rTztNK0KuzF\n1DFN7kPh35opnqgAAFmCCgCQJagAAFmCCgCQJagAAFmCCgCQ9fZ68p3d9arJ6vJOlUrbdyuv7R2m\nrvFJhWrwbvXzNDUY7u7zvvuzTjdVc6/XyK94ogIAZAkqAECWoAIAZAkqAECWoAIAZAkqAEDWt9aT\nV5QrVJN270N9X0+u6Z1am79zajV4al8L19CqJ/6vIVShz+aJCgCQJagAAFmCCgCQJagAAFmCCgCQ\n9fbWz+rb1t7S/qmwD4U13Dl1oNfupsTu8zTVyqhcX1Pr2P09K5+3uobygMZ6U25F5d64MrU+T1QA\ngCxBBQDIElQAgCxBBQDIElQAgCxBBQDIens9+YmVsd1OHs61c+31Kt6qQnV55/fsVv+NmFzfVKV+\nd829fg6nPHFY7Ooadv62eKICAGQJKgBAlqACAGQJKgBAlqACAGS9vfVzp9A4WDH5FvTVdxUG5K1+\nXmF9u9VbOoX2wIqV62jyWikMMjy5NbhTfR8mh6ROfd7UnnuiAgBkCSoAQJagAgBkCSoAQJagAgBk\nCSoAQNa31pPvFOqU5QF+k2soVBJP3bvXq19dnjJ1Duvnqe6Jx7Ti5H142rBYT1QAgCxBBQDIElQA\ngCxBBQDIElQAgCxBBQDIytaTrxSqUrudPAWzcD4K+7db4Zim/s6qwuTigsK1UnDyb9huT6vae6IC\nAGQJKgBAlqACAGQJKgBAlqACAGQd1/q5U35redXuYyoPyNt9rHefd7e+8nVUXhv/n1Ovvdersb7C\nb9ipv8un8kQFAMgSVACALEEFAMgSVACALEEFAMgSVACArEfVk68YOvW+z5uqLhcU1l1YA3+tUF+d\ntHt9k78r5f/9Qv28T/FEBQDIElQAgCxBBQDIElQAgCxBBQDIElQAgKyPqCc/ccrk6jFd1d0m9+jU\n6mb9OqpP5V259goTbCenehc+r169LVzLhXNYv9938kQFAMgSVACALEEFAMgSVACALEEFAMh6VOvn\niQOcPukN/Mpb7OXraHfba/W7Cu2xK7uvo8nrodDg2f159T3fqTCc8c6p++qJCgCQJagAAFmCCgCQ\nJagAAFmCCgCQJagAAFmPqicXqpErJmu5p+7RpMKwu6ka6CTr66gfa2F9k/dgoTZcrkJ7ogIAZAkq\nAECWoAIAZAkqAECWoAIAZD2q9XNlclDU1NvbhbfEV9X3qNy42T088tShde9w8j21U30fplp0K2u4\nc+pwxsKwWE9UAIAsQQUAyBJUAIAsQQUAyBJUAIAsQQUAyDqunnzykL6p76rUPaecWg3+7s+a/q5T\nq8uFNRSuvXd83pTd1eDCb/mp99MKT1QAgCxBBQDIElQAgCxBBQDIElQAgCxBBQDIytaT61MjT/ye\n6e861ROnnBY+77u/5x3fNTmZfcUTz+HuNZx6v9+pr+93eaICAGQJKgBAlqACAGQJKgBAlqACAGRl\nWz/l4UmFQVGVIWU7TQ4Bqw/0qq9vSv2auFI/FycPK7w6T582sPNO/fr7XZ6oAABZggoAkCWoAABZ\nggoAkCWoAABZggoAkJWtJ1952rCl12t/BbO+R1PHtFrRm9q/J57bFZNVz0Jtsz4YsXCN1eu/K99T\nuN8L53aFJyoAQJagAgBkCSoAQJagAgBkCSoAQJagAgBkHVdPLtQL61amO9frgCdPRt2psraV68hE\n6J8Kk4bv7K7RFs5hYQ13Cusr/xvgiQoAkCWoAABZggoAkCWoAABZggoAkJVt/RQGwxkI9VP9jf7C\nwLEpk2uYOrerx1S49q7Uz9MTr+XCMd2pXxNXCr//nqgAAFmCCgCQJagAAFmCCgCQJagAAFmCCgCQ\n9a315CfWHwtVrjuFNVzZvbZPG2RYr2cW9mi3J/6GFZy67lVTw2JP5YkKAJAlqAAAWYIKAJAlqAAA\nWYIKAJAlqAAAWW+vJ9cnRq6sb3dlbHKPdtfgVtZeqNEW9nzFyXXFwnlf8cTfsJOt/IYV9si5XeeJ\nCgCQJagAAFmCCgCQJagAAFmCCgCQ9fbWT70hs/tN8ZMH660orG/qmqgMt9z5PZPqA/yuFH7D6ud2\nZRhrpdGyc2+feO0VeKICAGQJKgBAlqACAGQJKgBAlqACAGQJKgBA1tvryXdWKm2Ta9j5d3bbvYb6\n59XXMFU5LezrqkJ1s36d189vuSb9aedi97+f5eP1RAUAyBJUAIAsQQUAyBJUAIAsQQUAyPrW1s+K\n+tC/qSbT5Nv3nzZE7crqMRUaQYXhZvXhjDtbD/Xr/079fp/6rsnmTPmYCjxRAQCyBBUAIEtQAQCy\nBBUAIEtQAQCyBBUAICtbTy4MSLpaQ6HquVuh0rlb/ZgKNdCTB5sV9u/K7ppqYaDjO9ax83vujqmw\nf/V7o8wTFQAgS1ABALIEFQAgS1ABALIEFQAgS1ABALK+tZ5crwpOMQn5p9WqbPmYVj3xmn1i3b9w\nHRXuDZO737OGO1N7Pvm7fMUTFQAgS1ABALIEFQAgS1ABALIEFQAg6+2tn3p7YcXuYyq8Xf7EpkR9\nMNyklbUX2lSTbZKVNZxq972x+7vqv2Er3E/rPFEBALIEFQAgS1ABALIEFQAgS1ABALIEFQAg6+31\n5NWhRSsV0d210kJFbqoytvs8TXriGurXUb0KuqJwHV2p/4ZN/laWa+mrayvfT4X7whMVACBLUAEA\nsgQVACBLUAEAsgQVACBLUAEAst5eT647tYJWqQxP1erK9b2/crX2Qu1v93VUP09T61ut+6+o/4bV\nq/HlCvek8r3riQoAkCWoAABZggoAkCWoAABZggoAkPURrZ+T33Av2P1W/Kl7VH4rvqJ+bgsNlCfu\nUWEfJptWuwfg7lzD7s9b/S3fuReeqAAAWYIKAJAlqAAAWYIKAJAlqAAAWYIKAJD1qHpyoT5aWMNu\nnzZ48InD+Arqe/Rp1/mUTzvenep7N7U+T1QAgCxBBQDIElQAgCxBBQDIElQAgCxBBQDI+tZ68uT0\nzBVTEzdX1Kd0lvfuHXZPET35eHd+1uTeFfa8sIa6qd++yXMxNaH+1N9lT1QAgCxBBQDIElQAgCxB\nBQDIElQAgKy3t34KQ5VW3o6etHt9K3teOE93nri+Jx7TpPL6Vn9Xysc0afJ3uTyMsvDv06qr4105\nJk9UAIAsQQUAyBJUAIAsQQUAyBJUAIAsQQUAyHp7PXl14FihllVYw4rJ4YxTe3TquXi99tb0Vr7n\nzu4abX2Q225TQ94K9+Bu9cGqK+rnqbCGFZ6oAABZggoAkCWoAABZggoAkCWoAABZb2/97Lb7TfHJ\nN88LA8cKDZRC22W3+jEVBqLVj6nQZNrt1HujPuTzifdGmScqAECWoAIAZAkqAECWoAIAZAkqAECW\noAIAZB1XTz65Kniq+uDBwsCx3Z54nT/xPK1Y2Yfde1eo1z7xGl9lL+55ogIAZAkqAECWoAIAZAkq\nAECWoAIAZAkqAEBWtp5crxiW1SePOrc/PXEf6sc0dW/U9+GOSb7vYR/WeaICAGQJKgBAlqACAGQJ\nKgBAlqACAGRta/0UBm1Bkeuck7heqfFEBQDIElQAgCxBBQDIElQAgCxBBQDIElQAgKzfrSf/8Xq9\n/vOOhQAAH+2fv/rDLxMdAYAq/+kHAMgSVACALEEFAMgSVACALEEFAMgSVACALEEFAMgSVACALEEF\nAMj6L7L3OZaOptDLAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "tags": [] } } ] }, { "cell_type": "code", "metadata": { "id": "1Jr--UvdNFBR", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "outputId": "fdfbd576-6dfd-4ed6-9284-fc2be6483c9c" }, "source": [ "#!/usr/bin/env python\n", "from PIL import Image, ImageDraw\n", "import random\n", "import os\n", "import glob\n", "import imageio\n", "import shutil\n", "\n", "\n", "class Cell:\n", " \"\"\"Create grid cell.\"\"\"\n", " def __init__(self, row_index, column_index, rows, columns):\n", " \"\"\"\n", " Initialize grid cell.\n", " row_index: cell row index.\n", " column_index: cell column index.\n", " rows: number of rows in grid.\n", " columns: number of columns in grid.\n", " \"\"\"\n", " if row_index >= rows or row_index < 0:\n", " raise ValueError(f'Expected a row index in range(0, {rows}) exclusive, got {row_index}')\n", " if column_index >= columns or column_index < 0:\n", " raise ValueError(f'Expected a column index in range(0, {columns} exclusive, got {column_index}')\n", " self.row = row_index\n", " self.column = column_index\n", " self.rows = rows\n", " self.columns = columns\n", " self.linked_cells = []\n", "\n", " def neighbors(self, grid):\n", " \"\"\"Return North, South, East, West neighbor cells.\"\"\"\n", " neighbors = []\n", " north = self.row - 1, self.column\n", " if north[0] < 0:\n", " north = 0\n", " neighbors.append(0)\n", " if north:\n", " neighbors.append(grid[north[0]][north[1]])\n", " south = self.row + 1, self.column\n", " if south[0] >= self.rows:\n", " south = 0\n", " neighbors.append(0)\n", " if south:\n", " neighbors.append(grid[south[0]][south[1]])\n", " east = self.row, self.column + 1\n", " if east[1] >= self.columns:\n", " east = 0\n", " neighbors.append(0)\n", " if east:\n", " neighbors.append(grid[east[0]][east[1]])\n", " west = self.row, self.column - 1\n", " if west[1] < 0:\n", " west = 0\n", " neighbors.append(0)\n", " if west:\n", " neighbors.append(grid[west[0]][west[1]])\n", " return neighbors\n", "\n", " def link(self, other, grid):\n", " \"\"\"Link 2 unconnected cells.\"\"\"\n", " if self in other.linked_cells or other in self.linked_cells:\n", " raise ValueError(f'{self} and {other} are already connected.')\n", " if self.columns != other.columns or self.rows != other.rows:\n", " raise ValueError('Cannot connect cells in different grids.')\n", " if self not in other.neighbors(grid) or other not in self.neighbors(grid):\n", " raise ValueError(f'{self} and {other} are not neighbors and cannot be connected.')\n", " if not isinstance(other, Cell):\n", " raise TypeError(f'Cannot link Cell to {type(other)}.')\n", " self.linked_cells.append(other)\n", " other.linked_cells.append(self)\n", "\n", " def unlink(self, other):\n", " \"\"\"Unlink 2 connected cells.\"\"\"\n", " if self not in other.linked_cells or other not in self.linked_cells:\n", " raise ValueError(f'{self} and {other} are not connected.')\n", " self.linked_cells.remove(other)\n", " other.linked_cells.remove(self)\n", "\n", " def coordinates(self):\n", " \"\"\"Return cell (row, column).\"\"\"\n", " return self.row, self.column\n", "\n", " def __str__(self):\n", " \"\"\"Cell display.\"\"\"\n", " return f'Cell{self.coordinates()}'\n", "\n", "\n", "class Maze:\n", " \"\"\"\n", " Generate a maze using different algorithms:\n", " - Binary Tree algorithm.\n", " \"\"\"\n", " def __init__(self, rows, columns, width, height, line_width=5, line_color='black', background_color='white'):\n", " \"\"\"\n", " Initialize maze variables:\n", " rows: number of rows in initial grid.\n", " columns: number of columns in initial grid.\n", " width: width of the frame(s).\n", " height: height of the frame(s).\n", " line_width: width of grid/maze lines.\n", " line_color: color of grid/maze lines.\n", " background_color: color of the grid/maze background (cells/path)\n", " \"\"\"\n", " if width % columns != 0:\n", " raise ValueError(f'Width: {width} not divisible by number of columns: {columns}.')\n", " if height % rows != 0:\n", " raise ValueError(f'Height: {height} not divisible by number of {rows}.')\n", " self.rows = rows\n", " self.columns = columns\n", " self.width = width\n", " self.height = height\n", " self.line_width = line_width\n", " self.line_color = line_color\n", " self.background_color = background_color\n", " self.cell_width = width // columns\n", " self.cell_height = height // rows\n", " self.drawing_constant = line_width // 2\n", " self.path = input('Enter path to folder to save maze creation GIF: ').rstrip()\n", "\n", " def _make_grid_image(self):\n", " \"\"\"Initiate maze initial grid image.\"\"\"\n", " grid = Image.new('RGB', (self.width, self.height), self.background_color)\n", " for x in range(0, self.width, self.cell_width):\n", " x0, y0, x1, y1 = x, 0, x, self.height\n", " column = (x0, y0), (x1, y1)\n", " ImageDraw.Draw(grid).line(column, self.line_color, self.line_width)\n", " for y in range(0, self.width, self.cell_height):\n", " x0, y0, x1, y1 = 0, y, self.width, y\n", " row = (x0, y0), (x1, y1)\n", " ImageDraw.Draw(grid).line(row, self.line_color, self.line_width)\n", " x_end = (0, self.height - self.drawing_constant),\\\n", " (self.width - self.drawing_constant, self.height - self.drawing_constant)\n", " y_end = (self.width - self.drawing_constant, 0), (self.width - self.drawing_constant, self.height)\n", " ImageDraw.Draw(grid).line(x_end, self.line_color, self.line_width)\n", " ImageDraw.Draw(grid).line(y_end, self.line_color, self.line_width)\n", " return grid\n", "\n", " def _create_maze_cells(self):\n", " \"\"\"Return maze cells.\"\"\"\n", " return [[Cell(row, column, self.rows, self.columns) for column in range(self.columns)]\n", " for row in range(self.rows)]\n", "\n", " def _binary_tree_configuration(self):\n", " \"\"\"Return binary tree maze configuration.\"\"\"\n", " cells = self._create_maze_cells()\n", " for row in range(self.rows):\n", " for column in range(self.columns):\n", " current_cell = cells[row][column]\n", " north, south, east, west = current_cell.neighbors(cells)\n", " to_link = random.choice('nw')\n", " if not north and not west:\n", " continue\n", " if to_link == 'n' and north:\n", " current_cell.link(north, cells)\n", " if to_link == 'w' and west:\n", " current_cell.link(west, cells)\n", " if to_link == 'n' and not north:\n", " current_cell.link(west, cells)\n", " if to_link == 'w' and not west:\n", " current_cell.link(north, cells)\n", " return cells\n", "\n", " def make_binary_tree_maze_image(self):\n", " \"\"\"Produce a maze image using binary tree algorithm.\"\"\"\n", " maze = self._make_grid_image()\n", " cells = self._binary_tree_configuration()\n", " linked_cells = {cell.coordinates(): [linked.coordinates() for linked in cell.linked_cells]\n", " for row in cells for cell in row}\n", " for row in range(self.rows):\n", " for column in range(self.columns):\n", " current_cell_coordinates = (row, column)\n", " if (row, column + 1) in linked_cells[current_cell_coordinates]:\n", " x0 = (column + 1) * self.cell_width\n", " y0 = (row * self.cell_height) + (self.line_width - 2)\n", " x1 = x0\n", " y1 = y0 + self.cell_height - (self.line_width + 1)\n", " wall = (x0, y0), (x1, y1)\n", " ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)\n", " if (row + 1, column) in linked_cells[current_cell_coordinates]:\n", " x0 = column * self.cell_width + self.line_width - 2\n", " y0 = (row + 1) * self.cell_height\n", " x1 = x0 + self.cell_width - (self.line_width + 1)\n", " y1 = y0\n", " wall = (x0, y0), (x1, y1)\n", " ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)\n", " x_end = (0, self.height - self.drawing_constant),\\\n", " (self.width - self.drawing_constant, self.height - self.drawing_constant)\n", " y_end = (self.width - self.drawing_constant, 0), (self.width - self.drawing_constant, self.height)\n", " ImageDraw.Draw(maze).line(x_end, self.line_color, self.line_width)\n", " ImageDraw.Draw(maze).line(y_end, self.line_color, self.line_width)\n", " return maze\n", "\n", " def make_binary_tree_maze_visualization(self, frame_speed):\n", " \"\"\"\n", " ** NOTE: Works on Unix systems only.\n", " Create a GIF for maze being created by a binary tree algorithm.\n", " frame_speed: speed in ms.\n", " \"\"\"\n", " print('GIF creation started ...')\n", " os.chdir(self.path)\n", " maze = self._make_grid_image()\n", " cells = self._binary_tree_configuration()\n", " linked_cells = {cell.coordinates(): [linked.coordinates() for linked in cell.linked_cells]\n", " for row in cells for cell in row}\n", " count = 0\n", " for row in range(self.rows):\n", " for column in range(self.columns):\n", " current_cell_coordinates = (row, column)\n", " # Remove vertical walls\n", " if (row, column + 1) in linked_cells[current_cell_coordinates]:\n", " x0 = (column + 1) * self.cell_width\n", " y0 = (row * self.cell_height) + (self.line_width - 2)\n", " x1 = x0\n", " y1 = y0 + self.cell_height - (self.line_width + 1)\n", " wall = (x0, y0), (x1, y1)\n", " ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)\n", " y_end = (self.width - self.drawing_constant, 0), (self.width - self.drawing_constant, self.height)\n", " ImageDraw.Draw(maze).line(y_end, self.line_color, self.line_width)\n", " maze.save(self.path + str(count) + '.png', 'png')\n", " count += 1\n", " # Remove horizontal walls\n", " if (row + 1, column) in linked_cells[current_cell_coordinates]:\n", " x0 = column * self.cell_width + self.line_width - 2\n", " y0 = (row + 1) * self.cell_height\n", " x1 = x0 + self.cell_width - (self.line_width + 1)\n", " y1 = y0\n", " wall = (x0, y0), (x1, y1)\n", " ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)\n", " x_end = (0, self.height - self.drawing_constant), \\\n", " (self.width - self.drawing_constant, self.height - self.drawing_constant)\n", " ImageDraw.Draw(maze).line(x_end, self.line_color, self.line_width)\n", " maze.save(self.path + str(count) + '.png', 'png')\n", " count += 1\n", " rand_name = 'maze' + str(random.randint(10 ** 6, 10 ** 8))\n", " os.mkdir(rand_name)\n", " for file in os.listdir(self.path):\n", " if file.endswith('.png'):\n", " shutil.move(file, rand_name)\n", " os.chdir(rand_name)\n", " frames = glob.glob('*.png')\n", " frames.sort(key=lambda x: int(x.split('.')[0]))\n", " frames = [imageio.imread(frame) for frame in frames]\n", " imageio.mimsave(self.path + str(rand_name) + '.gif', frames, 'GIF', duration=frame_speed)\n", " print(f'Creation of {count} frames GIF successful.')\n", "\n", "\n", "## if __name__ == '__main__':\n", "maze_test = Maze(50, 50, 500, 500)\n", "maze_test.make_binary_tree_maze_image().show()" ], "execution_count": 16, "outputs": [ { "output_type": "stream", "text": [ "Enter path to folder to save maze creation GIF: \n" ], "name": "stdout" } ] }, { "cell_type": "code", "metadata": { "id": "fRTZmvdsNFBT", "colab_type": "code", "colab": {} }, "source": [ "" ], "execution_count": 0, "outputs": [] } ] }