![\"Open](\"https://colab.research.google.com/assets/colab-badge.svg\"){kind=icon}
"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "L6PPJugj5kly",
"colab_type": "text"
},
"source": [
" \n",
" ![](\"https://raw.githubusercontent.com/klajosw/python/master/kl_mie_python_logo_250.jpg\"){kind=logo}
\n",
" \n",
"
\n", "\n", "# Labirintus generálás és megoldás pythonnal.\n", "\n", "https://klajosw.blogspot.com/\n", "\n", "https://github.com/klajosw/\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": { "id": "BthzIA015klz", "colab_type": "text" }, "source": [ "--- \n", "\n", "A két fő megszorítás az, hogy legyen egy út a bejárattól a kijáratig, és szórakoztatónak kell lennie, ha a labirintust ceruzával, papírral és az agyi erővel oldja meg, nem túl könnyű, de nem is lehetetlen.\n", "\n", "Ahogy egy számítógépes labirintus modellezésére gondolok, úgy tűnik, hogy a grafikon lesz a megfelelő modell:\n", "a grafikon a rács négyzete, a grafikon szélei pedig a szomszédos négyzetek közötti nyílások. \n", "\n", "Tehát a grafikon milyen tulajdonságai eredményeznek jó labirintust\n", "\n", "\n", "- A bejárattól a kijáratig vezető útnak kell lennie.\n", "- Nem lehet túl sok ilyen út; talán a legjobb, ha csak egy van.\n", "- Valószínűleg a gráfot külön-külön össze kell kapcsolni, nem lehetnek olyan négyzet-szigetek, amelyek a kezdetektől elérhetetlenek. Valójában talán pontosan egy utat akarunk a két négyzet között.\n", "- Az útnak sok csavarral kell rendelkeznie; túl könnyű lenne, ha többnyire egyenes.\n", "\n", "Tudom, hogy a fa ezen tulajdonságokkal rendelkezik az utolsó kivételével. \n", "\n", "Tehát a célom így módosult: Helyezzünk a fát egy rácsra, amely minden négyzetet lefed, és ellenőrizzük, hogy az ösvények csavarodnak-e. \n", "\n", "Így tegyem meg:\n", "\n", "- Indítsa el a szélek nélküli rácsot (minden négyzetet mindkét oldalán falak vesznek körül).\n", "- A bal felső sarokban és a jobb alsó sarokban adja hozzá a széleket (azaz le kell falakat) a bejárathoz.\n", "- Helyezze a fa gyökerét valamilyen négyzetre.\n", "- Ezután ismételje meg, amíg a fa nem fedezi az egész rácsot:\n", " * Válasszon ki egy csomópontot a fában.\n", " * Véletlenszerűen válassza ki a szomszédot, amelyet még nem adtak hozzá a fához.\n", " * Adjon hozzá egy szélt (leüt a falon) a csomóponttól a szomszédhoz.\n", " \n", "\n", "Az alábbi példában az A gyökér a bal felső sarokban van, és két ága van, Az \"A-B-C-D\" és az \"A-b-c-d\" véletlenszerűen választottak (nos, valójában nem véletlenszerűen; ugyanazt a labirintust kezdenek létrehozni):\n", "\n", " o o--o--o--o--o--o--o--o--o--o\n", " | A b c| | | | | | | |\n", " o o--o o--o--o--o--o--o--o--o\n", " | B| | d| | | | | | | |\n", " o o--o--o--o--o--o--o--o--o--o\n", " | C D| | | | | | | | |\n", " o--o--o--o--o--o--o--o--o--o--o\n", " | | | | | | | | | | |\n", " o--o--o--o--o--o--o--o--o--o--o\n", " | | | | | | | | | | |\n", " o--o--o--o--o--o--o--o--o--o o\n", "\n", "\n", "---\n", " \n", "Ezután kiválasztom a \"d\" csomópontot, és kiterjesztem az \"e\" -re \n", "(ezen a ponton nincsenek elérhető szomszédok, tehát az \"e\" -et a jövőben nem választjuk meg), \n", "\n", "majd a \"D\" -et választom, és onnan kiterjesztem az összes az \"N\" módhoz, minden lépésben kiválasztva az éppen hozzáadott csomópontot:\n", "\n", " o o--o--o--o--o--o--o--o--o--o\n", " | A b c| | | | | | | |\n", " o o--o o--o--o--o--o--o--o--o\n", " | B| e d| | N| | | | | |\n", " o o--o--o--o o--o--o--o--o--o\n", " | C D| | | M| | | | | |\n", " o--o o--o--o o--o--o--o--o--o\n", " | F E| | K L| | | | | |\n", " o o--o--o o--o--o--o--o--o--o\n", " | G H I J| | | | | | |\n", " o--o--o--o--o--o--o--o--o--o o\n", " \n", "Folytassa így, amíg a rács minden négyzetét hozzáadja a fához. Ezen a ponton lesz egy út a kezdetektől a célokig. Néhány falak megmaradnak; néhányat leütönek.\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "CQsTvX-j5kl0", "colab_type": "text" }, "source": [ "---\n", "\n", "# Véletlenszerű fák készítése\n", "\n", "A következő végrehajtási döntéseket hozom:\n", "\n", "- A fa élek halmaza.\n", "- Az „él” egy csomópont két csomópontból. Az élek kétirányúak, így a félreértés elkerülése érdekében mindig a rendezett sorrendben fogjuk megkapni: mindig `(A, B)`, soha `(B, A)`. A „szél” kivitelező ezt kényszeríti.\n", "- A fában lévő csomópont bármi lehet: szám, betű, ... Ebben a jegyzetfüzetben fákat készítünk, ahol a csomópontok négyzet alakban vannak egy rácsban, de a \"random_tree\" függvény bármilyen típusú csomópontot elfogad.\n", "- A \"random_tree (csomópontok, szomszédok, pop)\" algoritmus a következőképpen működik:\n", " * Az érvek:\n", " - \"csomópontok\": csomópontok gyűjteménye.\n", " - \"szomszédok\": olyan funkció, hogy a \"szomszédok (csomópont)\" egy csomópontkészletet ad vissza.\n", " - \"pop\": olyan funkció, hogy a \"pop (frontier)\" eltávolítja és visszatér egy elemet a \"határról\".\n", " * A funkció három gyűjteményt nyomon követi:\n", " - \"fa\": a fa éleinek halmaza.\n", " - \"csomópontok\": azon csomópontok halmaza, amelyeket még nem adtak hozzá a fához, de lesznek.\n", " - \"határ\": a fában lévő csomópontok sora, amelyek jogosultak egy él hozzáadásához.\n", " * Minden iteráción:\n", " - A „pop” gombbal válasszon ki egy „csomópontot” a határról, és keresse meg azokat a szomszédokat, akik még nem vannak a fában.\n", " - Ha vannak szomszédok, véletlenszerűen válasszon egyet (`nbr`), adjon hozzá` él (csomópont, nbr) `-t a` fához `, távolítsa el a\n", " szomszédját a \"csomópontokból\", és tartsa a csomópontot és a szomszédot a határon. Ha nincsenek szomszédok,\n", " dobja el a csomópontot a határról.\n", " * Ha nincsenek \"csomópontok\", tegyük vissza a \"fát\".\n", "\n", "\n", "\n", "---" ] }, { "cell_type": "code", "metadata": { "id": "7EzyC9Q-5kl0", "colab_type": "code", "colab": {} }, "source": [ "import random\n", "from collections import deque, namedtuple\n", "\n", "Edge = tuple\n", "Tree = set\n", "\n", "def edge(A, B) -> Edge: return Edge(sorted([A, B]))\n", "\n", "def random_tree(nodes, neighbors, pop=deque.pop) -> Tree:\n", " \"\"\"Repeat: pop a node and add edge(node, nbr) until all nodes have been added to tree.\"\"\"\n", " tree = Tree()\n", " nodes = set(nodes)\n", " root = nodes.pop()\n", " frontier = deque([root])\n", " while nodes:\n", " node = pop(frontier)\n", " nbrs = neighbors(node) & nodes\n", " if nbrs:\n", " nbr = random.choice(list(nbrs))\n", " tree.add(edge(node, nbr))\n", " nodes.remove(nbr)\n", " frontier.extend([node, nbr])\n", " return tree" ], "execution_count": 0, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "WrwLF8aR5kl4", "colab_type": "text" }, "source": [ "---\n", "\n", "# Véletlenszerű labirintus készítése\n", "\n", "Most használjuk a `random_tree` funkciót a `random_maze` megvalósításához. \n", "\n", "Alapvetően csak `(x, y)` négyzetek gyűjteményét készítjük, ezeket átvisszük a `random_tree` -re, és hagyjuk, hogy a munka megtörténjen. \n", "\n", "Vegye figyelembe, hogy:\n", "\n", "A labirintus egy elnevezett tuple, amely három mezővel rendelkezik: a rács szélessége és magassága, valamint a négyzetek közötti élek.\n", " \n", "A négyzetet egész koordináták (x, y) együttese jelöli.\n", "\n", "A szomszédok 4 (négyzet) függvény adja a négy környező négyzetet.\n", "\n", "---" ] }, { "cell_type": "code", "metadata": { "id": "VCSJv0Ub5kl4", "colab_type": "code", "colab": {} }, "source": [ "Maze = namedtuple('Maze', 'width, height, edges')\n", "\n", "Square = tuple\n", "\n", "def neighbors4(square) -> {Square}:\n", " \"\"\"The 4 neighbors of an (x, y) square.\"\"\"\n", " (x, y) = square\n", " return {(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)}\n", "\n", "def grid(width, height) -> {Square}: \n", " \"\"\"All squares in a grid of these dimensions.\"\"\"\n", " return {(x, y) for x in range(width) for y in range(height)}\n", "\n", "def random_maze(width, height, pop=deque.pop) -> Maze:\n", " \"\"\"Generate a random maze, using random_tree.\"\"\"\n", " tree = random_tree(grid(width, height), neighbors4, pop)\n", " return Maze(width, height, tree)" ], "execution_count": 0, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "23_W7Xt45kl7", "colab_type": "text" }, "source": [ "### Készítsünk egy 10x5-es labirintust:" ] }, { "cell_type": "code", "metadata": { "id": "eOCjVJ595kl8", "colab_type": "code", "colab": { "base_uri": "https://localhost:8080/", "height": 54 }, "outputId": "d87e2fbc-920c-4a7b-e632-32f939aedf4a" }, "source": [ "random_maze(10, 5)" ], "execution_count": 3, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "Maze(width=10, height=5, edges={((6, 2), (6, 3)), ((8, 0), (8, 1)), ((6, 4), (7, 4)), ((8, 3), (9, 3)), ((2, 2), (3, 2)), ((8, 4), (9, 4)), ((4, 0), (5, 0)), ((1, 0), (2, 0)), ((1, 1), (2, 1)), ((4, 1), (5, 1)), ((4, 2), (4, 3)), ((2, 1), (2, 2)), ((0, 2), (0, 3)), ((7, 4), (8, 4)), ((6, 0), (7, 0)), ((3, 1), (3, 2)), ((3, 0), (3, 1)), ((2, 3), (2, 4)), ((7, 1), (7, 2)), ((0, 4), (1, 4)), ((3, 3), (4, 3)), ((9, 0), (9, 1)), ((1, 2), (1, 3)), ((8, 1), (9, 1)), ((7, 0), (8, 0)), ((9, 1), (9, 2)), ((7, 3), (8, 3)), ((4, 0), (4, 1)), ((4, 2), (5, 2)), ((2, 4), (3, 4)), ((6, 1), (7, 1)), ((0, 1), (0, 2)), ((1, 1), (1, 2)), ((6, 3), (6, 4)), ((6, 2), (7, 2)), ((3, 3), (3, 4)), ((0, 0), (1, 0)), ((5, 1), (5, 2)), ((2, 0), (3, 0)), ((5, 0), (6, 0)), ((3, 4), (4, 4)), ((0, 0), (0, 1)), ((0, 3), (0, 4)), ((4, 4), (5, 4)), ((1, 3), (2, 3)), ((9, 3), (9, 4)), ((5, 3), (5, 4)), ((6, 0), (6, 1)), ((8, 2), (9, 2))})" ] }, "metadata": { "tags": [] }, "execution_count": 3 } ] }, { "cell_type": "markdown", "metadata": { "id": "OnUc_mSR5kl_", "colab_type": "text" }, "source": [ "---\n", "\n", "Ez így nem nagyon szép. Szükség lesz egy módszerre a labirintus megjelenítésére.\n", "\n", "\n", "# Labirintus megjelenítése\n", "\n", "\n", "\n", "\n", "\n", "A `matplotlib` -t használom a labirintus falainak ábrázolására. Alig várom, mikor lesz * megoldási út *, és megengedjük ennek ábrázolását is.\n", "\n", "\n", "---" ] }, { "cell_type": "code", "metadata": { "id": "XKHPkXvX5kmA", "colab_type": "code", "colab": {} }, "source": [ "%matplotlib inline\n", "import matplotlib.pyplot as plt\n", "\n", "def plot_maze(maze, figsize=None, path=None):\n", " \"\"\"Plot a maze by drawing lines between adjacent squares, except for pairs in maze.edges\"\"\"\n", " w, h = maze.width, maze.height\n", " plt.figure(figsize=figsize or (w/5, h/5))\n", " plt.axis('off')\n", " plt.gca().invert_yaxis()\n", " exits = {edge((0, 0), (0, -1)), edge((w-1, h-1), (w-1, h))}\n", " edges = maze.edges | exits\n", " for sq in grid(w, h):\n", " for nbr in neighbors4(sq):\n", " if edge(sq, nbr) not in edges:\n", " plot_wall(sq, nbr)\n", " if path: # Plot the solution (or any path) as a green line through the maze\n", " X, Y = transpose((x + 0.5, y + 0.5) for (x, y) in path)\n", " plt.plot(X, Y, 'g-', linewidth=2)\n", " \n", "def transpose(matrix): return list(zip(*matrix))\n", "\n", "def plot_wall(s1, s2):\n", " \"\"\"Plot a wall: a blue line between squares s1 and s2.\"\"\"\n", " (x1, y1), (x2, y2) = s1, s2\n", " if x1 == x2: # horizontal wall\n", " y = max(y1, y2)\n", " X, Y = [x1, x1+1], [y, y]\n", " else: # vertical wall\n", " x = max(x1, x2)\n", " X, Y = [x, x], [y1, y1+1]\n", " plt.plot(X, Y, 'b-', linewidth=2)" ], "execution_count": 0, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "c6tvFDJL5kmC", "colab_type": "text" }, "source": [ "### Nézzük meg, hogy néz ki:" ] }, { "cell_type": "code", "metadata": { "id": "XzWTU5qs5kmD", "colab_type": "code", "colab": {}, "outputId": "99321fc3-6a54-4fc1-836a-387c2a02b521" }, "source": [ "M = random_maze(10, 5)\n", "plot_maze(M, figsize=(5, 2.5)) " ], "execution_count": 0, "outputs": [ { "output_type": "display_data", "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAASUAAACWCAYAAACYTp4YAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAACwUlEQVR4nO3dQY4TMRBAUTfi/ldutggQYqRu57t47wCZ9Dj5rqzquu97AVR8+/QbAPiZKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKR8f/LFrmvda6113+t68nX/9DeAlqe+9yYlIOXRSWmHN6cw2nZM4nzd079eTEpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpx61Ysoyy7fT1RxM/X6ediUkJSDluUjqt+v+LHRPGzrP3OfsckxKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpBy3DaTiXu5dti1nWPK+Ux5jrXO28xiUgJSjpuUdt/4p90yv9p945/+/5rk1GnPpASkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpDyyoqlHatdJqzymbLGaZdTVwb9jbP/nUkJSHllUnqz/hNvyzdNuol3PIvp9fNMSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmvrFjiayatjZqyiHTSmZzGpASkHDcpTVoSOOlZpnE2n2NSAlJECUgRJSBFlIAUUQJSRAlIESUgRZSAFFECUkQJSBElIEWUgBRRAlJECUgRJSBFlIAUUQJSRAlIESUgRZSAFFECUkQJSHllxdKkRX6TnoV/N+ncT1sXZVICUq77HnMhAAOYlIAUUQJSRAlIESUgRZSAFFECUkQJSBElIEWUgBRRAlJECUj5AZ35UzmPSBlLAAAAAElFTkSuQmCC\n", "text/plain": [ "