I can create simple but interesting mazes using cellular automata. I am looking for a quick way to check them for connectivity. In other words, making sure that all walkways are accessible from any starting point within the maze. There are no ways in or out and dead ends are acceptable. In the example below there is at least two interconnected areas (can you spot them?).
There isn't going to be a very quick or easy method for testing a maze after it has been generated.
You're going to be better off using a different algorithm, that will guarantee to generate "perfect" mazes to begin with.
I was going to comment that it's best not to put the cart before the horse... Seems to me it would be easier to have a program that built a maze path, then filled in the area around it with dead-end branches and whatnot. Building maze bits and then trying to create a contiguous path from start to finish seems like more hard work and trouble than it's worth.
Thanks for the links. The maze classification page I had come across before. Both 'Sparseness' and 'Weave' are similar in construction but not in quite the same style as my example maze. Something to go on I suppose.
Otherwise, I'd use an algorithm that generates a perfect maze, and then to get all the extra loops and branching that you have in your maze, you could just add a load of extra path squares at random positions afterwards.
You beat me to it - flood fill! I'd probably want to jazz up the mazes in PaintShop Pro 7 anyway. While I'm there, all I will need to do, is make a selection using the magic wand and then fill with another colour - hey presto! Then just add a square here and there so that everything joins up. I will take a look at the Dungeon Object extension though. Thanks Sketchy.
By the way can you see our mazes have different properties. Mine is more irregular looking (non grid format).
Ah, well if you're pre-generating the mazes (rather than randomizing them within the game) that does make it easier. I suppose even within a game, you could probably copy the map into a surface object somehow, and use the flood-fill function there...
And yes, I can see that your maze isn't aligned to a grid. Personally, I think it looks less pleasing when you have diagonally adjacent squares that aren't connected (plus it can potentially cause problems with other things, like line-of-sight).
It all just depends on what you plan to do with your mazes, once you have them.
Advertisement
Post Reply
Edited by Dave S.