Second: I spent my free time over the past couple days trying to speed up my maze generator. I failed, and I sort of understand why, but I'm still a little confused. When I started, I noticed that when I was randomly selecting a wall to break down, if the wall I was breaking down had a visited room on the other side, I grabbed another number ad nauseum until the next wall led to a new room. I figured that the wasteful looping could be optimized out. Well, my "solutions" inevitably involved generating a list of "good" walls each iteration, or removing the entries for the "bad" walls from the surrounding rooms. Not only did it actually slow down the generation (by about 100+ ticks, according to a GetTickCount() delta), most of the time it didn't even work! So, I'm just going to leave it, no matter how much I want to speed it up. At least it works.
Well, that said, I do want to explain how it works. Maybe one of you will see something that can be sped up that I missed. Here's the source code for MazeGen::Generate(), with comments explaining what I'm doing.
struct cell_info{ cell_info* next[4]; cell_info* last_visited; bool visited : 1; bool top_wall : 1; bool left_wall : 1;};std::vector MazeGen::Generate(unsigned width, unsigned height) const{ // Wall #s // 0 // 1 2 // 3 // Allocate the cell grid. cell_info* cells = new cell_info[width*height]; // Initialize each cell. for (unsigned y = 0; y < height; ++y) { for (unsigned x = 0; x < width; ++x) { unsigned i = x+y*width; cells.last_visited = NULL; cells.visited = false; cells.top_wall = true; cells.left_wall = true; // I could probably make do with using the ModFloor function and // index arithmetic everywhere, and drop the 'next' array, but // I hate index arithmetic. May as well get it over with here. // Also: ModFloor aligns a value into a specific range, a bit // like how integer overflow loops back around to the other end. // It's how I sew the edges of my Map together. cells.next[0] = &cells[x+ModFloor(y-1, 0, height)*width]; cells.next[1] = &cells[ModFloor(x-1, 0, width)+y*width]; cells.next[2] = &cells[ModFloor(x+1, 0, width)+y*width]; cells.next[3] = &cells[x+ModFloor(y+1, 0, height)*width]; } } cell_info* current = &cells[0]; do { // No matter what, we've visited this cell and don't // want to return. current->visited = true; // Are we in a dead-end? if (current->next[0]->visited && current->next[1]->visited && current->next[2]->visited && current->next[3]->visited) { // If yes, we need to backtrack. current = current->last_visited; continue; } // This right here is what annoys me. I feel like it's // useless cycling, and a waste. But everything I try // to replace it either doesn't work or is slower. unsigned which_wall; do which_wall = rand()%4; while (current->next[which_wall]->visited); // This, at least, is straightforward. switch (which_wall) { case 0: // top current->top_wall = false; break; case 1: // left current->left_wall = false; break; case 2: // right current->next[which_wall]->left_wall = false; break; case 3: // bottom current->next[which_wall]->top_wall = false; break; } // Before we move, tell the next room that we're coming // from this one. current->next[which_wall]->last_visited = current; // Now move. current = current->next[which_wall]; // Only true when we've backtracked to the beginning // with nowhere else to go! } while (current->last_visited != NULL); // This code knocks out walls randomly. I kind of want // to incorporate it into the above somehow, but it's // simpler and cleaner to leave it here, I think. for (int i = 0; i < rand()%5+25; ++i) { // Knock out between 25 and 30 walls. unsigned which_wall = rand()%2; unsigned index = rand()%(width*height); // I hate index arithmetic. if (which_wall == 0) // top { if (cells[index].top_wall) cells[index].top_wall = false; else --i; } else // left { if (cells[index].left_wall) cells[index].left_wall = false; else --i; } } // This is where I create and position each of the walls. // It's also the only place in all of Cripes where I use Boost... std::vector walls; for (unsigned y = 0; y < height; ++y) { for (unsigned x = 0; x < width; ++x) { unsigned cornerflag = 0; // Bitwise mask identifying a corner. unsigned i = x+y*width; // Index arithmetic. Hate. if (cells.left_wall) { Entity wall = loader->Construct("VertWall"); wall.X = x*8; // I'll get around to un-hardcoding wall.Y = 1+y*6; // these later. walls.push_back(wall); cornerflag += 8; } if (cells.top_wall) { Entity wall = loader->Construct("HorizWall"); wall.X = 1+x*8; wall.Y = y*6; walls.push_back(wall); cornerflag += 2; } if (cells.next[0]->left_wall) cornerflag += 4; if (cells.next[1]->top_wall) cornerflag += 1; if (cornerflag != 0) { std::string cornerID = "Corner"; // Corners! This is the only place I use Boost. // lexical_cast is great. cornerID += boost::lexical_cast(cornerflag); Entity corner = loader->Construct(cornerID); corner.X = x*8; corner.Y = y*6; walls.push_back(corner); } } } delete[] cells; // I actually forgot this before I wrote this post! return walls; // I have a suspicion that returning the entire vector // is a little slow, especially when I'm also passing it // to the EntityMap (by reference!), but still...}