It has been over a year since I last updated CuteMaze. I have worked on it since then, but my other projects distracted me so much I didn’t think about it. A few months ago I added zooming support, but moving was pretty slow when zoomed out. I finally got around to looking at it a few days ago, and I discovered that I could noticeably speed up rendering by caching the background. I don’t know why I didn’t do that from the start, actually.

Once I had done that, I decided that it was time to polish up CuteMaze and make a release. I don’t want the new features to sit for too long without people getting to use them, and a year is pretty long! Along with zooming, I also added support for hints. Other than that it is mostly code cleanup. I had intended to rewrite the maze generation algorithms, but I lost interest in that and I have pushed that off to a future release.

For anybody who has made themes, this new release changes the format from being a collection of SVG files to being a single SVG file. You need to put a transparent rectangle behind smaller elements to make them render at the appropriate sizes. It is a fairly easy change to make, and you can look at the provided themes for examples.

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.