Maze Solver#

In this notebook, we write a maze solver by solving the Poisson equation with two Dirichlet boundary conditions imposed on the two faces that correspond to the start and end of the maze, respectively.

The logic is pretty simple: once we have the solution, we just need to start off from one face and follow the gradient. Since the gradient in the deadends is almost close to 0, following the nonzero gradient should guide us toward the other side of the maze.

We implement two different approaches:

  1. Direct numerical simulation Here, we first convert the image into a Cubic network, trim the pores that correspond to the walls, and finally run a basic OhmicConduction (or FickianDiffusion) on the resulting trimmed network.

  2. Network extraction Here, we first use the SNOW algorithm to extract the equivalent network of the maze. Note that the nodes in the equivalent network will not exactly give us the corners of the maze, but at least it gives us a rough idea, enough for solving the maze! Then, like the first approach, we run a basic OhmicConduction on the extracted network. The advantage of this approach is that it’s way faster due to much fewer unknowns.

Note: Inspired by this post by Jeremy Theler https://www.linkedin.com/posts/jeremytheler_how-to-solve-a-maze-without-ai-use-laplaces-activity-6831291311832760320-x9d5

[1]:

# Install the required pmeal packages in the current Jupyter kernel
import sys
try:
    import openpnm as op
except:
    !{sys.executable} -m pip install openpnm
    import openpnm as op
try:
    import porespy as ps
except:
    !{sys.executable} -m pip install porespy
    import porespy as ps

Collecting porespy
  Downloading porespy-2.1-py3-none-any.whl (133 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 133.6/133.6 KB 6.3 MB/s eta 0:00:00
Collecting pyfastnoisesimd
  Downloading pyfastnoisesimd-0.4.2-cp38-cp38-manylinux2010_x86_64.whl (3.5 MB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 3.5/3.5 MB 59.4 MB/s eta 0:00:00
Requirement already satisfied: pandas in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from porespy) (1.4.2)
Requirement already satisfied: tqdm in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from porespy) (4.64.0)
Requirement already satisfied: numpy in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from porespy) (1.21.6)
Collecting edt
  Downloading edt-2.1.3-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (2.0 MB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 2.0/2.0 MB 87.2 MB/s eta 0:00:00
Collecting trimesh
  Downloading trimesh-3.10.8-py3-none-any.whl (642 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 642.6/642.6 KB 59.2 MB/s eta 0:00:00
Collecting loguru
  Downloading loguru-0.6.0-py3-none-any.whl (58 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 58.3/58.3 KB 17.9 MB/s eta 0:00:00
Requirement already satisfied: imageio in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from porespy) (2.17.0)
Requirement already satisfied: numba in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from porespy) (0.55.1)
Requirement already satisfied: psutil in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from porespy) (5.9.0)
Requirement already satisfied: matplotlib in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from porespy) (3.5.1)
Collecting numpy-stl
  Downloading numpy-stl-2.16.3.tar.gz (772 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 772.1/772.1 KB 84.1 MB/s eta 0:00:00
  Preparing metadata (setup.py) ... - \ | / - done
Collecting scikit-fmm
  Downloading scikit-fmm-2022.3.26.tar.gz (432 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 432.3/432.3 KB 43.4 MB/s eta 0:00:00
  Installing build dependencies ... - \ | / - \ | done
  Getting requirements to build wheel ... - \ done
  Preparing metadata (pyproject.toml) ... - \ | done
Collecting pyevtk
  Downloading pyevtk-1.5.0-py3-none-any.whl (20 kB)
Collecting dask
  Downloading dask-2022.4.1-py3-none-any.whl (1.1 MB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 1.1/1.1 MB 90.8 MB/s eta 0:00:00
Requirement already satisfied: scikit-image in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from porespy) (0.19.2)
Requirement already satisfied: openpnm in /home/runner/work/OpenPNM/OpenPNM (from porespy) (2.8.2.dev1116)
Collecting deprecated
  Downloading Deprecated-1.2.13-py2.py3-none-any.whl (9.6 kB)
Requirement already satisfied: scipy in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from porespy) (1.8.0)
Collecting fsspec>=0.6.0
  Downloading fsspec-2022.3.0-py3-none-any.whl (136 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 136.1/136.1 KB 36.9 MB/s eta 0:00:00
Collecting partd>=0.3.10
  Downloading partd-1.2.0-py3-none-any.whl (19 kB)
Requirement already satisfied: packaging>=20.0 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from dask->porespy) (21.3)
Collecting cloudpickle>=1.1.1
  Downloading cloudpickle-2.0.0-py3-none-any.whl (25 kB)
Collecting toolz>=0.8.2
  Downloading toolz-0.11.2-py3-none-any.whl (55 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 55.8/55.8 KB 17.0 MB/s eta 0:00:00
Collecting pyyaml>=5.3.1
  Downloading PyYAML-6.0-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl (701 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 701.2/701.2 KB 83.5 MB/s eta 0:00:00
Collecting wrapt<2,>=1.10
  Downloading wrapt-1.14.0-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (80 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 81.0/81.0 KB 22.0 MB/s eta 0:00:00
Requirement already satisfied: pillow>=8.3.2 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from imageio->porespy) (9.1.0)
Requirement already satisfied: fonttools>=4.22.0 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from matplotlib->porespy) (4.32.0)
Requirement already satisfied: kiwisolver>=1.0.1 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from matplotlib->porespy) (1.4.2)
Requirement already satisfied: python-dateutil>=2.7 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from matplotlib->porespy) (2.8.2)
Requirement already satisfied: pyparsing>=2.2.1 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from matplotlib->porespy) (3.0.8)
Requirement already satisfied: cycler>=0.10 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from matplotlib->porespy) (0.11.0)
Requirement already satisfied: llvmlite<0.39,>=0.38.0rc1 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from numba->porespy) (0.38.0)
Requirement already satisfied: setuptools in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from numba->porespy) (62.1.0)
Collecting python-utils>=1.6.2
  Downloading python_utils-3.1.0-py2.py3-none-any.whl (19 kB)
Requirement already satisfied: chemicals in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (1.0.20)
Requirement already satisfied: docrep>=0.3 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (0.3.2)
Requirement already satisfied: flatdict in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (4.0.1)
Requirement already satisfied: h5py in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (3.6.0)
Requirement already satisfied: jsonschema in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (4.4.0)
Requirement already satisfied: json-tricks in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (3.15.5)
Requirement already satisfied: networkx in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (2.8)
Requirement already satisfied: pypardiso in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (0.4.1)
Requirement already satisfied: sympy in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (1.10.1)
Requirement already satisfied: terminaltables in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (3.1.10)
Requirement already satisfied: traits in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (6.3.2)
Requirement already satisfied: transforms3d in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from openpnm->porespy) (0.3.1)
Requirement already satisfied: pytz>=2020.1 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from pandas->porespy) (2022.1)
Requirement already satisfied: PyWavelets>=1.1.1 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from scikit-image->porespy) (1.3.0)
Requirement already satisfied: tifffile>=2019.7.26 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from scikit-image->porespy) (2022.4.8)
Requirement already satisfied: six in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from docrep>=0.3->openpnm->porespy) (1.16.0)
Collecting locket
  Downloading locket-0.2.1-py2.py3-none-any.whl (4.1 kB)
Requirement already satisfied: fluids>=1.0.12 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from chemicals->openpnm->porespy) (1.0.21)
Requirement already satisfied: attrs>=17.4.0 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from jsonschema->openpnm->porespy) (21.4.0)
Requirement already satisfied: pyrsistent!=0.17.0,!=0.17.1,!=0.17.2,>=0.14.0 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from jsonschema->openpnm->porespy) (0.18.1)
Requirement already satisfied: importlib-resources>=1.4.0 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from jsonschema->openpnm->porespy) (5.7.1)
Requirement already satisfied: mkl in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from pypardiso->openpnm->porespy) (2022.0.2)
Requirement already satisfied: mpmath>=0.19 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from sympy->openpnm->porespy) (1.2.1)
Requirement already satisfied: zipp>=3.1.0 in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from importlib-resources>=1.4.0->jsonschema->openpnm->porespy) (3.8.0)
Requirement already satisfied: tbb==2021.* in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from mkl->pypardiso->openpnm->porespy) (2021.5.1)
Requirement already satisfied: intel-openmp==2022.* in /usr/share/miniconda3/envs/test/lib/python3.8/site-packages (from mkl->pypardiso->openpnm->porespy) (2022.0.2)
Building wheels for collected packages: numpy-stl, scikit-fmm
  Building wheel for numpy-stl (setup.py) ... - \ | / - \ | / done
  Created wheel for numpy-stl: filename=numpy_stl-2.16.3-py3-none-any.whl size=18677 sha256=4e00e0a1355fb694185bd2bd88944c2a5dc13f77276fafeadc15b4a1ee28e8dc
  Stored in directory: /home/runner/.cache/pip/wheels/3a/81/67/18f4cc12b926f6a5eb1c39df40b2cb6ad19e1c7686eec73574
  Building wheel for scikit-fmm (pyproject.toml) ... - \ | / - \ | / - \ | done
  Created wheel for scikit-fmm: filename=scikit_fmm-2022.3.26-cp38-cp38-linux_x86_64.whl size=58534 sha256=ced49b752eff266b3667aa7f6b9e5ec7ef6cbda22532ef14cba73201a43c59f5
  Stored in directory: /home/runner/.cache/pip/wheels/23/15/cf/ebbb283bbfae514442037733e0fd4b5c71482c6432f3e2f82e
Successfully built numpy-stl scikit-fmm
Installing collected packages: wrapt, trimesh, toolz, scikit-fmm, pyyaml, python-utils, pyfastnoisesimd, pyevtk, loguru, locket, fsspec, edt, cloudpickle, partd, numpy-stl, deprecated, dask, porespy
Successfully installed cloudpickle-2.0.0 dask-2022.4.1 deprecated-1.2.13 edt-2.1.3 fsspec-2022.3.0 locket-0.2.1 loguru-0.6.0 numpy-stl-2.16.3 partd-1.2.0 porespy-2.1 pyevtk-1.5.0 pyfastnoisesimd-0.4.2 python-utils-3.1.0 pyyaml-6.0 scikit-fmm-2022.3.26 toolz-0.11.2 trimesh-3.10.8 wrapt-1.14.0

[2]:

import requests
import numpy as np
from scipy import ndimage
import matplotlib.pyplot as plt
import porespy as ps
import openpnm as op
from openpnm.utils import tic, toc
from PIL import Image
from io import BytesIO
%config InlineBackend.figure_formats = ['svg']
ws = op.Workspace()
ws.settings["loglevel"] = 60

Load maze samples#

[3]:

im_size = 'medium'

if im_size == 'small':
    url = 'https://imgur.com/ZLbV4eh.png'
elif im_size == 'medium':
    url = 'https://imgur.com/A3Jx8SJ.png'
else:
    url = 'https://imgur.com/FLJ21e5.png'

[4]:

response = requests.get(url)
img = Image.open(BytesIO(response.content))
im = np.array(img.getdata()).reshape(img.size[0], img.size[1], 4)[:, :, 0]
im = im == 255

Nx, Ny, = im.shape

fig, ax = plt.subplots(figsize=(5, 5))
ax.imshow(im, cmap='Blues', interpolation="none")
ax.axis("off");
../../_images/examples_contrib_maze_solver_5_0.svg

Approach A: Direct numerical simulation#

Thicken the walls to reduce number of unknowns#

[5]:

# Structuring element for thickening walls
strel = np.array([[1, 1, 1],
                  [1, 1, 1],
                  [1, 1, 1]])

# Save some computation by thickening the walls
def thicken_wall(im):
    return ~ndimage.morphology.binary_dilation(~im, structure=strel)

for _ in range(5):
    im = thicken_wall(im)

/tmp/ipykernel_2933/1691655960.py:8: DeprecationWarning: Please use `binary_dilation` from the `scipy.ndimage` namespace, the `scipy.ndimage.morphology` namespace is deprecated.
  return ~ndimage.morphology.binary_dilation(~im, structure=strel)

[6]:

fig, ax = plt.subplots(figsize=(5, 5))
ax.imshow(im, cmap='Blues', interpolation="none")
ax.axis("off")

[6]:

(-0.5, 801.5, 801.5, -0.5)
../../_images/examples_contrib_maze_solver_9_1.svg

Convert the maze into a Cubic network#

[7]:

# Get top and bottom boundaries
BP_top = np.zeros_like(im)
BP_bot = np.zeros_like(im)
BP_top[0, :] = True
BP_bot[-1, :] = True
BP_top *= im
BP_bot *= im

# Make a cubis network with same dimensions as image and assign the props
net = op.network.Cubic(shape=[Nx, Ny, 1])
net['pore.index'] = np.arange(0, net.Np)
net['pore.BP_top'] = BP_top.flatten()
net['pore.BP_bot'] = BP_bot.flatten()

# Trim wall pores
op.topotools.trim(network=net, pores=~im.flatten())

Solve the Poisson equation (\(\nabla^2 \phi = 0\)) on the maze#

[8]:

# Set up a dummy phase and apply uniform arbitrary conductance
phase = op.phases.GenericPhase(network=net)
phase['throat.electrical_conductance'] = 1.0

# Run algorithm
alg = op.algorithms.OhmicConduction(network=net, phase=phase)
alg.set_value_BC(pores=net.pores('BP_top'), values=0.0)
alg.set_value_BC(pores=net.pores('BP_bot'), values=1.0)
tic()
alg.run()
dt = toc(quiet=True);
print(f'Solve time: {dt:.3f} s')

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Input In [8], in <cell line: 2>()
      1 # Set up a dummy phase and apply uniform arbitrary conductance
----> 2 phase = op.phases.GenericPhase(network=net)
      3 phase['throat.electrical_conductance'] = 1.0
      5 # Run algorithm

AttributeError: module 'openpnm' has no attribute 'phases'

Follow the gradient!#

[9]:

# Calculate flux in throats and show in pores
# Note: No need to calculate pore.rate as it auto interpolates from throat values
phase['throat.rate'] = alg.rate(throats=net.Ts, mode='single')
rate_im = np.ones([Nx, Ny]).flatten() * np.nan
rate_im[net['pore.index']] = phase['pore.rate']
rate_im = rate_im.reshape([Nx, Ny])

# Plot the maze solution
fig, ax = plt.subplots(figsize=(5, 5))
ax.imshow(rate_im, cmap='jet', interpolation="none")
ax.axis("off");

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Input In [9], in <cell line: 3>()
      1 # Calculate flux in throats and show in pores
      2 # Note: No need to calculate pore.rate as it auto interpolates from throat values
----> 3 phase['throat.rate'] = alg.rate(throats=net.Ts, mode='single')
      4 rate_im = np.ones([Nx, Ny]).flatten() * np.nan
      5 rate_im[net['pore.index']] = phase['pore.rate']

NameError: name 'alg' is not defined

Approach B: Network extraction#

Network extraction using SNOW algorithm#

[10]:

# We need to pass image transpose since matrix xy coords is inverted
# i.e., row is x and col is y, whereas in Cartesian convention, it's the opposite.
out = ps.networks.snow2(im.T)
proj = op.io.PoreSpy.import_data(out.network)
net = proj.network

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Input In [10], in <cell line: 4>()
      1 # We need to pass image transpose since matrix xy coords is inverted
      2 # i.e., row is x and col is y, whereas in Cartesian convention, it's the opposite.
      3 out = ps.networks.snow2(im.T)
----> 4 proj = op.io.PoreSpy.import_data(out.network)
      5 net = proj.network

AttributeError: module 'openpnm.io' has no attribute 'PoreSpy'

Solve the Poisson equation (\(\nabla^2 \phi = 0\)) on the extracted network#

[11]:

# Set up a dummy phase and apply uniform arbitrary conductance
phase = op.phases.GenericPhase(network=net)
phase['throat.electrical_conductance'] = 1.0

# Run algorithm
alg = op.algorithms.OhmicConduction(network=net, phase=phase)
alg.set_value_BC(pores=net.pores('ymin'), values=0.0)
alg.set_value_BC(pores=net.pores('ymax'), values=1.0)
tic()
alg.run()
dt = toc(quiet=True);
print(f'Solve time: {dt:.3f} s')

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Input In [11], in <cell line: 2>()
      1 # Set up a dummy phase and apply uniform arbitrary conductance
----> 2 phase = op.phases.GenericPhase(network=net)
      3 phase['throat.electrical_conductance'] = 1.0
      5 # Run algorithm

AttributeError: module 'openpnm' has no attribute 'phases'

Follow the gradient!#

[12]:

# Get throat rate values
phase['throat.rate'] = alg.rate(throats=net.Ts, mode='single')

# Plot the maze solution (i.e., throat rates!)
fig, ax = plt.subplots(figsize=(5, 5))
op.topotools.plot_connections(net, ax=ax,
                              color_by=phase["throat.rate"],
                              linewidth=2, cmap="Wistia")
ax.imshow(im, interpolation="none", cmap='Blues');
ax.axis("off");

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Input In [12], in <cell line: 2>()
      1 # Get throat rate values
----> 2 phase['throat.rate'] = alg.rate(throats=net.Ts, mode='single')
      4 # Plot the maze solution (i.e., throat rates!)
      5 fig, ax = plt.subplots(figsize=(5, 5))

NameError: name 'alg' is not defined