struct cell_info
{
    cell_info* next[4];
    cell_info* last_visited;
    bool visited : 1;
    bool top_wall : 1;
    bool left_wall : 1;
};

std::vector<Entity> 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[i].last_visited = NULL;
            cells[i].visited = false;
            cells[i].top_wall = true;
            cells[i].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[i].next[0] = &cells[x+ModFloor(y-1, 0, height)*width];
            cells[i].next[1] = &cells[ModFloor(x-1, 0, width)+y*width];
            cells[i].next[2] = &cells[ModFloor(x+1, 0, width)+y*width];
            cells[i].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<Entity> 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[i].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[i].top_wall)
            {
                Entity wall = loader->Construct("HorizWall");
                wall.X = 1+x*8;
                wall.Y = y*6;
                walls.push_back(wall);

                cornerflag += 2;
            }

            if (cells[i].next[0]->left_wall)
                cornerflag += 4;
            if (cells[i].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<std::string>(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...
}