Created
January 14, 2021 16:31
-
-
Save paiv/2768ca80d09ea5f7f263666746b90189 to your computer and use it in GitHub Desktop.
maze generation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"screen_size = (120, 100)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 2, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"(19, 16)" | |
] | |
}, | |
"execution_count": 2, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"room_size = 6\n", | |
"maze_size = (screen_size[0] - 1) // room_size, (screen_size[1] - 1) // room_size\n", | |
"maze_size" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"import random\n", | |
"from collections import deque" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 4, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"random.seed(10)\n", | |
"grid = dict()\n", | |
"edges = list()\n", | |
"entry = (0, 1)\n", | |
"exit = (17, 15)\n", | |
"n = maze_size[0] * maze_size[1]\n", | |
"fringe = [entry, exit]\n", | |
"moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n", | |
"while fringe:\n", | |
" i = random.choice(range(len(fringe)))\n", | |
" pos = fringe.pop(i)\n", | |
" if pos in grid: continue\n", | |
" px, py = pos\n", | |
" neib = [(px + dx, py + dy) for dx, dy in moves if 0 <= px + dx < maze_size[0] if 0 <= py + dy < maze_size[1]]\n", | |
" mx = [p for p in neib if p in grid]\n", | |
" if mx:\n", | |
" s = random.choice(mx)\n", | |
" grid[pos] = grid[s]\n", | |
" edges.append((s, (px, py)))\n", | |
" else:\n", | |
" grid[pos] = 1 if pos == entry else 2\n", | |
" for pn in neib:\n", | |
" if pn not in grid:\n", | |
" fringe.append(pn)\n", | |
" \n", | |
"zs = [((x,y), n) for y in range(maze_size[1]) for x in range(maze_size[0]) for dx, dy in [(1,0), (0,1)] for n in [(x+dx, y+dy)] if n in grid if grid[(x,y)] != grid[n]]\n", | |
"edges.append(random.choice(zs))" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 5, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"import numpy as np\n", | |
"from PIL import Image" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 6, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"def render_image(px, image_size):\n", | |
" px = (1 - px) * 255\n", | |
" im = Image.fromarray(px, mode='L')\n", | |
" return im.resize((image_size[0]*4, image_size[1]*4), Image.NEAREST)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 7, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"(97, 115)\n" | |
] | |
}, | |
{ | |
"data": { | |
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAcwAAAGECAAAAACeu09bAAAF3UlEQVR4nO3dQVLkyBIAUfGN+195ZvV3nZpOWSQC570lCKlot+zaRAXXBQD8jY/ruq5/Ft/409cnH7zz3N2v7z73p/u4rut/b78I5ogZImaImCFihogZImaImCFihogZImaImCFihogZImaImCFihogZImbI5+4PfNx8bzWj84bd5771Oic5mSFihogZ8jE1Q/rW/OrUPO13e+6Tf08nM0TMEDFDxAwRM0TMEDFDxAwRM0TMEDFDxAwRM0TMEDFDxAwRM0TMEDFDPp/sqtvx5PqT87enf9+7556+j5MZImaImCHbnzVZzXKu/i+fnF3dudfUc3d/3yf32rn/3etxMkPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEz5HYG6Mkcyo6J+zyZxVn9zOmdsxNzUnc79ZzMEDFDxAxZvmeeno+dus/JnbLXtb/39e7anc+yPPm9nMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDFnOAJ3eK3t3nzf2wd7ZmdP5ir85vXo9TmaImCFihny7udknTr5HvflevbJ6PU5miJghYoaIGSJmiJghYoaIGSJmiJghYoaIGSJmiJghYoaIGSJmiJghYobczs1O7EF9Mkc6sQ/2zXnat+7vZIaIGSJmyO2O9jdM7Y+9m/ud2vt6cp7WvtlfTswQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUMezQBNzLXeXf/WDrvJv/986rl3v6+TGSJmiJgh2++ZU58b2d1nuzI1H7u61+7rf/L+uvsz9s3+AmKGiBkiZoiYIWKGiBkiZoiYIWKGiBkiZoiYIWKGiBkiZoiYIWKGiBmyPQM0Naf63e4z+YzTc1IrTmaImCFihmTnZk9fP/XZl6l/h+tyMlPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEz5NHc7M4+2P9/708m9rj+9H2zk6/fyQwRM0TMkEc72ned3K2+O9e6snv97r7Zyf20K05miJghYoaIGSJmiJghYoaIGSJmiJghYoaIGSJmiJghYoaIGSJmiJghYoZ8Xtf+PM5bu2Knrp/cV/e39/+KvbhOZoiYIWKGfF7X2Z2tu/Oid+8tJz+bMjl/u3Jyjve6nMwUMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDBEzRMwQMUPEDLmdm31jvnT3/lN/+/nJ9af35e52cTJDxAwRM2R7bnZqP+pX7EOf+L1Of0Zkal73upzMFDFDxAwRM0TMEDFDxAwRM0TMEDFDxAwRM0TMEDFDxAwRM0TMEDFDxAxZ/s3pu3nU3a/fPeNPpva1Tt3/5BzQ5HyvkxkiZoiYIcv3zElv7GvdvX5qXnd3v+6T567e853MEDFDxAwRM0TMEDFDxAwRM0TMEDFDxAwRM0TMEDFDxAwRM0TMEDFDxAy5nQFazeNMzJE+mVP9Tntxd2eVJq9fcTJDxAwRM2T5njm1B3V3XnRq9/ndM3aee/q9cfdanzX5JcQMETNEzBAxQ8QMETNEzBAxQ8QMETNEzBAxQ8QMETNEzBAxQ8QMETNke9/s3fUrO/tp/+tef3v/lcm9tbvXn96v62SGiBkiZsjovtk35l137zG1s3b3cy8rk5+fcTJDxAwRM0TMEDFDxAwRM0TMEDFDxAwRM0TMEDFDxAwRM0TMEDFDxAwRM+TRDNDOTOeT+djTe2Invr4yeZ9dTmaImCFihmy/Z57+fMjkvtmTTs8IP7m/kxkiZoiYIWKGiBkiZoiYIWKGiBkiZoiYIWKGiBkiZoiYIWKGiBkiZoiYIZ/XNbMf9c7UvtaViTnV3ed+xTzw7h5aJzNEzBAxQz6v6+yc6k+Zj/0p88B393cyQ8QMETNEzBAxQ8QMETNEzBAxQ8QMETNEzBAxQ8QMETNEzBAxQ8QMETNkarUrB5ib/cXEDBEz5F/ThblG0Yu1zQAAAABJRU5ErkJggg==\n", | |
"text/plain": [ | |
"<PIL.Image.Image image mode=L size=460x388 at 0x10BEF1C10>" | |
] | |
}, | |
"execution_count": 7, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"image_size = maze_size[0] * room_size + 1, maze_size[1] * room_size + 1\n", | |
"px = np.zeros((image_size[1], image_size[0]), dtype=np.uint8)\n", | |
"for y in range(maze_size[1]+1):\n", | |
" px[y*room_size,:] = 1\n", | |
"for x in range(maze_size[0]+1):\n", | |
" px[:,x*room_size] = 1\n", | |
"\n", | |
"for (ax, ay), (bx, by) in edges:\n", | |
" if ax == bx:\n", | |
" if by < ay:\n", | |
" ay, by = by, ay\n", | |
" if ay < by:\n", | |
" sy = (ay + 1) * room_size\n", | |
" sx = slice(ax * room_size + 1, (ax + 1) * room_size)\n", | |
" px[sy, sx] = 0\n", | |
" elif ay == by:\n", | |
" if bx < ax:\n", | |
" ax, bx = bx, ax\n", | |
" if ax < bx:\n", | |
" sx = (ax + 1) * room_size\n", | |
" sy = slice(ay * room_size + 1, (ay + 1) * room_size)\n", | |
" px[sy, sx] = 0\n", | |
"\n", | |
"px[entry[1]*room_size+1:(entry[1]+1)*room_size, entry[0]*room_size] = 0\n", | |
"px[(exit[1]+1)*room_size, exit[0]*room_size+1:(exit[0]+1)*room_size] = 0\n", | |
"print(px.shape)\n", | |
"render_image(px, image_size)" | |
] | |
} | |
], | |
"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.9.1" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 4 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment