Maze Generation Algorithms

Add to your list(s) Download to your calendar using vCal

• Michael French, St Catharine's College
• Wednesday 10 February 2016, 19:00-19:40
• Wolfson Hall, Churchill College.

If you have a question about this talk, please contact Matthew Ireland.

I shall talk on a selection of methods for generating random 2D mazes, exploring and comparing the complexities and traits of various algorithms, including Aldous-Broder’s, Recursive Subdivision, Recursive Backtracking, Kruskal’s and more. I shall comment on how to adapt these algorithms for producing mazes with specific textures, and briefly touch on some solving methods. During this exploration, I shall also look at possible applications of the algorithms outside of maze generation. I shall lastly look at how generation algorithms might be extended into higher dimensions, such as a 3D maze (easily pictured as a cube, or a series of 2D ‘floors’), or 4D or higher (less easy to picture, but can still be represented); and whether such generalisations come at an infeasible complexity cost.

This talk is part of the Churchill CompSci Talks series.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science

Note that ex-directory lists are not shown.