Author: Nicolas Rougier (@rougier)
Submitted by: Nicolas Rougier (@rougier)
The snippet below creates a maze and solve it using ndimage.generic_filter. The "trick" is to use the generic_filer to diffuse a value (at the entrance) in the maze such as to reach the exit. Then, by descending the gradient from the entrance, you can reach the exit (shortest path). This is a simplified version of the Bellman-Ford algorithm.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
''' Maze solving using the Bellman-Ford algorithm '''
import numpy as np
import matplotlib.pyplot as plt
from scipy.ndimage import generic_filter
def maze(shape=(64,64), complexity=.75, density = 1):
# Only odd shapes
shape = ((shape[0]//2)*2+1, (shape[1]//2)*2+1)
# Adjust complexity and density relative to maze size
complexity = int(complexity*(5*(shape[0]+shape[1])))
density = int(density*(shape[0]//2*shape[1]//2))
# Build actual maze
Z = np.zeros(shape, dtype=bool)
# Fill borders
Z[0,:] = Z[-1,:] = 1
Z[:,0] = Z[:,-1] = 1
# Create islands
for i in range(density):
x = shape[1]*(0.5-min(max(np.random.normal(0,.5),-.5),.5))
y = shape[0]*(0.5-min(max(np.random.normal(0,.5),-.5),.5))
x, y = (x//2)*2, (y//2)*2
Z[y,x] = 1
for j in range(complexity):
neighbours = []
if x > 1: neighbours.append( (y,x-2) )
if x < shape[1]-2: neighbours.append( (y,x+2) )
if y > 1: neighbours.append( (y-2,x) )
if y < shape[0]-2: neighbours.append( (y+2,x) )
if len(neighbours):
y_,x_ = neighbours[np.random.random_integers(0,len(neighbours)-1)]
if Z[y_,x_] == 0:
Z[y_,x_] = 1
Z[y_+(y-y_)//2, x_+(x-x_)//2] = 1
x, y = x_, y_
Z[-2,-1] = 0 # Entrance
Z[ 0, 1] = 0 # Exit
return 1 - Z
n = 41
Z = maze((n,n))
# Diffusion
G = np.zeros((n,n))
G[-2,-1] = 1
def diffuse(Z):
N = 0.99*Z[0] # North
W = 0.99*Z[1] # West
V = Z[2] # Center
E = 0.99*Z[3] # East
S = 0.99*Z[4] # South
return max(max(max(max(V,E),W),N),S)
for i in xrange(5*(n+n)):
G = Z * generic_filter(G, diffuse, footprint= [[0, 1, 0],
[1, 1, 1],
[0, 1, 0]])
# Solution finding and drawing by ascending gradient
y,x = 0, 1
X,Y = [],[]
dirs = [(0,-1), (0,+1), (-1,0), (+1,0)]
S = Z.astype(float)
for i in range(5*(n+n)):
Y.append(y), X.append(x)
neighbours = -np.ones(4)
if x > 0: neighbours[0] = G[y,x-1]
if x < G.shape[1]-1: neighbours[1] = G[y,x+1]
if y > 0: neighbours[2] = G[y-1,x]
if y < G.shape[0]-1: neighbours[3] = G[y+1,x]
a = np.argmax(neighbours)
x,y = x + dirs[a][1], y + dirs[a][0]
# Visualization
plt.figure(figsize=(9,9))
plt.subplot(1, 1, 1, frameon=False)
plt.imshow(G, interpolation='nearest', cmap=plt.cm.hot, vmin=0, vmax=1)
plt.scatter(X, Y, s=40.0, lw=1, color='k', marker='o', edgecolors='k', facecolors='w')
plt.xticks([]), plt.yticks([])
plt.savefig("maze.png")
plt.show()
Author: Nicolas Rougier (@rougier) Submitted by: Nicolas Rougier (@rougier)
The snippet below creates a maze and solve it using ndimage.generic_filter. The "trick" is to use the generic_filer to diffuse a value (at the entrance) in the maze such as to reach the exit. Then, by descending the gradient from the entrance, you can reach the exit (shortest path). This is a simplified version of the Bellman-Ford algorithm.