Maze generation algorithm for specified parts

[ponjavic]

I am an undergraduate student studying mechanical engineering. We are doing a project called the labyrinth cutter, we're constructing a piece of artwork consisting of a a gantry connected to a cutter head. The cutter is supposed to cut out a labyrinth to a piece of music.

I decided to use the midi file of the music piece to create straight parts with certain lengths. At various beats the labyrinths changes direction.

I used Java with J-music to do this and came out with 400 pieces that now have to be placed in a certain order to create a labyrinth. The lenghts of the pieces depend on the frequency of the note being played and the time between pieces.

I wrote a program in c++ that uses recursive backtracking, simply trying to place piece after piece and see if it fits. Currently up to about 150 pieces is doable but after this the computation time gets way to heavy.

I am wondering if anybody has an idea of a certain algorithm that could be used to solve this or point me in the right direction a bit as I'm not quite sure what I can do right now except for reducing the amount of pieces.

Picture shows a solution with 150 pieces, obviously this won't fill the area.

http://img89.imageshack.us/my.php?image=labyyc7.jpg

Also if you have another idea of how to represent the labyrinths creation as being done to the piece of music please state your idea.

 

[Aaron Bex]

There are a few algorithms that could be used for this problem. One approach would be to use an evolutionary algorithm, where each generation of "labyrinths" is evaluated based on how closely they match the music, and the best ones from each generation are used to create the next generation. Another approach would be to use a simulated annealing approach, where new labyrinths are created by making small random changes to existing ones, and the changes are accepted or rejected based on how well the new labyrinth matches the music. Finally, you could also use a heuristic search algorithm like A*, which would try to find a path from the initial labyrinth to one that is close to the desired music.

 

[quicknote]

I find your project very interesting and creative. Using a midi file to generate a labyrinth is a unique approach and I commend you for that. However, I can understand your struggle with the computational complexity as the number of pieces increases.

One possible solution to reduce the computation time would be to use a heuristic algorithm. This type of algorithm uses a "best guess" approach to determine the next piece placement, rather than trying every possible combination. This can significantly reduce the number of computations needed and speed up the process. Some examples of heuristic algorithms that could be applied to your project are genetic algorithms or simulated annealing.

Another approach could be to divide the area into smaller sections and work on each section separately. This could help reduce the overall complexity and make the problem more manageable. You could also consider using a parallel processing approach to speed up the computation time.

In terms of representing the labyrinth creation as being done to the piece of music, one idea could be to incorporate the tempo and rhythm of the music into the placement of the pieces. For example, faster and more upbeat sections of the music could correspond to shorter and more frequent changes in direction in the labyrinth.

Overall, I think you have a unique and challenging project and I encourage you to continue exploring different algorithms and methods to solve it. Good luck!