A week ago I wrote a simple maze solver for CuteMaze based on the principle of “dead end filling”, for the purpose of giving the player hints. Unfortunately, I had a pretty busy week and I was delayed in adding it. Some things were avoidable, some things were not, but suffice it to say that I’m glad that it’s done.

The cool thing about dead end filling is that it can solve any of CuteMaze’s mazes very quickly. It is actually a remarkably easy way to solve a maze. You start by iterating over every cell in the maze. Each time you find a dead end, you “fill” the maze from that point until you find a junction. If you treat the start and stop cells as junctions, you will end up with a maze entirely filled except for the path between the start and the stop cells. Once you are done filling in all of the dead ends, you track a fill from the start to the stop to find the cells for the solution.

I guess I’m trying to see just how many projects I can work on at the exact same time. I’m trying to recreate a reported issue with Kapow on the Mac. I’m still playing around with the interface of Simsu. I’m finishing up Peg-E so that it can be reviewed by the KDE developers. Plus, to top it off, I’m also working on adding themes and goals to FocusWriter. I should probably slow down and focus on one project at a time so that they get done faster, but that’s not as much fun!

Sometimes I look at old code and say, “What in the world was I thinking?” I had such an incident today. For an unrelated reason I found myself looking at the source code of CuteMaze. One piece of code in particular stood out: the placement of targets on the maze. This is the code in the current version:

// Add player
m_player.setX(rand() % (columns - 1));
m_player.setY(rand() % (rows - 1));
m_start = m_player;

// Add targets
QList locations;
if (columns * rows > m_total_targets * 2) {
	locations.append(m_start);
	QPoint target;
	for (int i = 0; i < m_total_targets; ++i) {
		do {
			target.setX(rand() % (columns - 1));
			target.setY(rand() % (rows - 1));
		} while (locations.contains(target));
		locations.append(target);
		m_targets.append(target);
	}
// Handle if targets cover half or more of the maze
} else {
	for (int c = 0; c < columns; ++c) {
		for (int r = 0; r < rows; ++r) {
			locations.append(QPoint(c, r));
		}
	}
	locations.removeAll(m_player);
	int pos;
	for (int i = 0; i < m_total_targets; ++i) {
		pos = rand() % locations.size();
		m_targets.append(locations.takeAt(pos));
		for (int y = 0; y < size; ++y) {
			for (int x = 0; x < size; ++x) {
				locations.append(QPoint(x,y));
			}
		}
	}
}

Now that is some pretty strange code. And its major flaw is that as the number of targets increases it gets a lot slower, which apparently I tried to paper over. I randomly selected a location and tried to place a target, unless the number of targets was over half of the maze, in which case I selected random locations from a list. Riiight. Instead, here’s the code that will be in the next version:

QList locations;
for (int y = 0; y < size; ++y) {
	for (int x = 0; x < size; ++x) {
		locations.append(QPoint(x,y));
	}
}
std::random_shuffle(locations.begin(), locations.end());
m_player = m_start = locations.first();
m_targets = locations.mid(1, m_total_targets);

Now I make a list of all locations in the maze, shuffle it, and use the first location for the player and the next group of locations for the targets. Simple, fast, and scales all of the way up to having targets in every single cell of a 10x10 maze (Whee! It’s Pac-Man! 😛).

Of course, changing the target placement code means that old save games won’t work. I seem to be on a roll of breaking compatibility lately. If I’m going to do that, I might as well see if any of the rest of the code makes me say, “What in the world?”.

While testing things yesterday, I discovered that none of my projects install the executables when compiled from source. Oops. I don’t usually try to install them, so I’m not surprised I missed it. I guess nobody else does either, otherwise I expect I would’ve heard about this already.

I am going to be making releases of Gottet, NovProg2, and Tetzle today. I am also planning on making a release of CuteMaze, but that is being delayed while I work out the last few details of porting it to Qtopia4—thanks go to Alessandro Briosi for porting CuteMaze and Gottet to Qtopia4.

Now that Trolltech has released a version of Qt 4 under the GPL version 3, I have decided to re-license CuteMaze as GPL 3 or later. As this is the only change between the 1.0 and 1.0.1 releases, it’s quite a minor update.

I’m amazed that nobody has reported any bugs after the 1.0 release. If you do encounter any bugs, please don’t hesitate to inform me. They won’t get fixed if I don’t know about them!

Update: In my zeal to upload the newest version of CuteMaze earlier today, I accidentally uploaded the wrong versions for most of the files—the only correct builds were the Linux ones. 🙂 I have replaced the incorrect files and updated their checksums.

I have not been doing much with CuteMaze recently. That’s probably due to the fact that I have almost completed the game. Today I uploaded a version that allows the player to install or uninstall themes, which should make sharing them easier. If you have a theme you would like for me to put on the website, please email it to me.

The one task I have left for CuteMaze is to port it to the Mac. This should be relatively easy, and the only thing holding me up is that I don’t have a Mac. However, I will have one in about a week, so that isn’t too big of an issue.