# 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
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 133.6/133.6 KB 6.3 MB/s eta 0:00:00
Collecting pyfastnoisesimd
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 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
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 2.0/2.0 MB 87.2 MB/s eta 0:00:00
Collecting trimesh
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 642.6/642.6 KB 59.2 MB/s eta 0:00:00
Collecting loguru
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 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
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 772.1/772.1 KB 84.1 MB/s eta 0:00:00
Preparing metadata (setup.py) ... - \ | / - done
Collecting scikit-fmm
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 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
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 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
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
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 136.1/136.1 KB 36.9 MB/s eta 0:00:00
Collecting partd>=0.3.10
Collecting cloudpickle>=1.1.1
Collecting toolz>=0.8.2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 55.8/55.8 KB 17.0 MB/s eta 0:00:00
Collecting pyyaml>=5.3.1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 701.2/701.2 KB 83.5 MB/s eta 0:00:00
Collecting wrapt<2,>=1.10
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 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
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
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
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


[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");


## 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)


## 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'


[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


## 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'


[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