Step by step perfect maze generation with php

Read all posts about "" game

This is a project I made for teaching purpose.
First of all, let’s see what is a perfect maze.
From Maze Works: A perfect maze is defined as a maze which has one and only one path from any point in the maze to any other point. This means that the maze has no inaccessible sections, no circular paths, no open areas.

This is a perfect maze
Perfect maze

This is not a perfect maze
Not a perfect maze

With the script I provide, you can generate perfect mazes with a given length and height, and the cute thing is that the script will “think loud” its actions in order to explain how does it work.
It uses backtracking.

The program, like most maze generators, starts off by building a maze with all the walls between the cells intact.
Then chooses a random cell where to start and mark the current cell as ‘Visited’;

If the current cell has any neighbour cells which have not been visited

  • Randomly choose one of these cells
  • Knock down the wall between current and choosen cells
  • Make the chosen cell the current cell
  • Mark the new current cell as visited

else

  • Go to your previoulsy visited cell

Until all cells are visited

So, you can use it both for generating perfect mazes, and to show how would you generated a perfect maze.

In the example, the script executed with a 5×5 maze.

Later I will explain the code, meanwhile here it is:

";

$maze[$pos]{0} = 1;
$visited ++;

// determine possible directions
while($visited<$cell_count){
	$possible = "";	
	if((floor($pos/$dim_x)==floor(($pos-1)/$dim_x)) and ($maze[$pos-1]{0}==0)){
		$possible .= "W";
	}
	if((floor($pos/$dim_x)==floor(($pos+1)/$dim_x)) and ($maze[$pos+1]{0}==0)){
		$possible .= "E";
	}
	if((($pos+$dim_x)<$cell_count) and ($maze[$pos+$dim_x]{0}==0)){
		$possible .= "S";
	}
	if((($pos-$dim_x)>=0) and ($maze[$pos-$dim_x]{0}==0)){
		$possible .= "N";
	}
	$html .= "I am in $pos and I can go to: $possible
"; if($possible){ $visited ++; array_push($moves,$pos); $direction = $possible{rand(0,strlen($possible)-1)}; $html .= "I randomly choose to go $direction"; switch($direction){ case "N": $maze[$pos]{1} = 0; $maze[$pos-$dim_x]{2} = 0; $pos -= $dim_x; break; case "S": $maze[$pos]{2} = 0; $maze[$pos+$dim_x]{1} = 0; $pos += $dim_x; break; case "E": $maze[$pos]{3} = 0; $maze[$pos+1]{4} = 0; $pos ++; break; case "W": $maze[$pos]{4} = 0; $maze[$pos-1]{3} = 0; $pos --; break; } $maze[$pos]{0} = 1; } else{ $html .= "No possible moves, I have to perform a backtracking
"; $pos = array_pop($moves); } $html .= ""; for($x=0;$x<$cell_count;$x++){ if($x % $dim_x == 0){ $html .= ""; } $style = $maze[$x]{2}.$maze[$x]{3}; if($x!=$pos){ $html.= ""; } else{ $html .= ""; } if(($x % $dim_x) == ($dim_x-1)){ $html .= ""; } } $html .= "
$x$x
"; } $html.= "Hooray, that's the final maze"; ?>

Enjoy it and give me feedback.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers