Senior Project! Argg! Volume 2

Okay. So this past weekend I started really plugging away at maze/break. I knew the very first thing that needed to happen was I needed to get a random maze generator working. I realized early on that this would be a rough task to undertake, and that it's all my fault. Before I get to explaining why, here is a concept of the UI:

At first glance, it's easy to see that it's a maze, but it isn't easy to see what the issue is. The biggest issue arises from the fact that my walls and walkways are all cells in the grid. Most maze algorithms that I encountered during my research assumed that the maze is made of cell-walkways with walls surrounding each, which is what most people think of when they think of a maze.

Many of the algorithms followed a "breaking walls down" sort of approach, where you found a cell, chose a direction at random, and broke through the wall in that direction. I attempted to apply these algorithms to my maze structure without any luck whatsoever. I would have had to tweak the algorithms to the point that they'd be completely different. Regardless, there goes 5 hours of research.

Eventually I found an article by a developer who made a game for mobile using JavaME. In the article, Carol discusses her algorithm, and it really all just fell into place in my mind. Carol suggests thinking of a maze as a tree or graph that "grows" from a central point. This means that any single node or vertex will only be connected to another through a single path, which makes for a perfect maze. If you'd like to read up on her algorithm before I go on, check it out here: http://bittyjava.wordpress.com/2007/03/10/a-little-maze-algorithm/

The next step was to implement it. Because of the way Carol described her algorithm, I was a little unclear of how I wanted to go about implementing it in my project. Every single possible data structure offered by C# went through my head for this one. I thought about using stacks, hashtables, dictionaries, blah blah blah... and I realized that none of those would really suit my needs. I need to make a graph myself. Luckily, MSDN has written a fantastic article on building a graph class:

http://msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx#datastructures20_5_topic3

I'll be using this heavily whilst I build my maze generator. The other data structure I'll need is a simple dynamic array of points, each of which will represent the location of a different cell.

Goals for tonight/tomorrow morning:
-Finish the generation algorithm
-Find a way to display the maze and player piece
-Add keyboard-powered movement
-Timer possibly?

Time to write some code!