Pathfinding Algorithms with Mazes

An implementation of a visual path-finder using Python3.

Notes:

Mazes are simple parameters, where a pixel denotes path(white), or wall(black). Unconventional mazes or RGB mazes can be retrofitted by specifiying within the state class

The start and end is considered to be the first open path on both the top and bottom of the maze respectively.

Modify the color transition of the solver by editing the RGB transition value in the ScanImage class.

Current Working Algorithms:

• A* optimised

  • As opposed to brute forcing each available path the program finds nodes

  • This can reduce total working area by a significant amount

  • 4k x 4k (16 million pixels) Mazes with multiple solutions can take under a minute to solve on basic hardware

  • It is not optimised to work with multiple threads

Special thanks to MikePound, I used a few of his mazes and ideas from Computerphile to get going!

Demonstration

Maze (41x41)

Finding nodes:

Solved:

Additional Solved mazes can be found in the solved folder

• Notes:
  • Larger mazes example
  • 4 million pixel width
  • 
  • Trimmed to nearly 600k (~85% reduction)
  • Node discovery is approx 75k/s (on an older laptop, yet to test on others)
  • Started at ~12.5k/s initally (500% increase)

Additonal mazes:

400x100

200x200

Computerphile