maze generation

mazegen.ipynb

{
 "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
}