maze algorithms

hello all ,
I am making a maze game in bge using python scripting. I want the maze to generate itself,i.e,when the player finishes a level by reaching a goal, collecting all pickups,etc. the next maze will be generated by a maze gen. algorithm:p.so
how exactly do i do it?
i thought that maybe i should take a cube and extrude it around to make a boundary and use the recursive division algorithm on it but that doesn’t seem the best idea? what else can i do?
also, can anyone pls. give me a python implementation of any of these algorithms that will work in blender 2.57?:spin:
thanks in advance.

Here is a good bit of info on the theory of generating the maze pattern:

As far as generating the maze geometry, I think you could have some wall pieces and add them where you need them from python.

thanks alot RobCozzens i will try it out.
if you don’t mind, why maya for the animation?

It is easier to find animators who are trained in Maya. Because of smaller budgets we can’t afford to train anyone in different software. You end up with a cycle: everyone uses Maya because everyone else uses Maya.

oh… same goes for c++ everybody uses c++ because everybody else uses c++:no:even though the syntax is [email protected]#$%^substitute for swearing:o

Reading the article, the cell-based algorithms would be well within the realm of possibility in the BGE, you’d just have a network of cubes (perhaps named ‘cell’), pick a random cube from the list of objects that starts with cell and is on the edge, use rayCast() to generate a spidering network of rays to tag objects for deletion in a way that creates passages, then either delete a cube on the opposite end to create the exit or mark a cell somewhere in the maze as an exit.

The recursive division though might be a little tricky, but still possible using thin wall objects with their origin at the very end and a scale F-curve. Then with many instances of the same object, assign the F-curve position and rotate them according to their created position in the space (which would the origins of the created objects would either always be in a random position along the edge of an existing object or the edge of the space)

I wouldn’t implement that directly into the BGE. Better create an internal model (you can use the Python example from wikipedia). The internal model can be a list, dict, class or what ever.

When you have the internal model you can convert it into BGE structures, e.g. walls, floors etc…
You can remove the internal model after that. But you might want to keep it for pathfinding.

Algorithm -> internal model -> converter -> GameObjects

Advantages:

  • much more efficient algorithm
  • you can use existing implementations
  • easy replace with other algorithms
  • game independent (reusable)

I see. Monster raises a good point - rather than directly use the algorithm and code, you would use the code to return values that you use in games. That’s a good idea.

I don’t like algorithms! It is pretty hard to me, anyway!