MazeDynamic.cpp

/*----------------------------------------------------------------------
Pac-Man Evolution - Roberto Prieto
Copyright (C) 2018-2024 MegaStorm Systems
contact@megastormsystems.com - http://www.megastormsystems.com
 
This software is provided 'as-is', without any express or implied
warranty.  In no event will the authors be held liable for any damages
arising from the use of this software.
 
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
 
1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
 
------------------------------------------------------------------------
 
MazeGenerator class
 
 Based on Shaun LeBron code (https://github.com/shaunlebron/pacman-mazegen) using "tetris" variant.
 
------------------------------------------------------------------------ */
 
#include "MazeDynamic.h"
#include <algorithm>
#include <map>
#include <math.h>
 
#define UP  0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
 
#ifdef DEBUG_GENERATOR
static double aRandsSequence[] = {0.5129719235575136, 0.34348663304017557, 0.6661675989013662, 0.8596401856537104, 0.7144370682013301, 0.6571361789295214, 0.34061865256273527, 0.26202101108360587, 0.8688143512246322, 0.28898641980463524, 0.5304491684794037, 0.5554456481914671, 0.885355280505715, 0.8190719526946917, 0.6974568050485852, 0.8828828341655219, 0.276211699397634, 0.5462919073561716, 0.4671018356657537, 0.9350492706174056, 0.4779938422203398, 0.14721994418484585, 0.07612282547423832, 0.08780624670671422, 0.5943574517779637, 0.5221223829803883, 0.950987812197468, 0.2515330680939367, 0.14530868975510303, 0.2141918743985214, 0.74386825375617, 0.04525929141234375, 0.5753222964802585, 0.09554464411922603, 0.3460382031154865, 0.5435667417622243, 0.5786996323071909, 0.7541216428297157, 0.815797431679153, 0.6148391444621712, 0.013622973716154396, 0.26998664508467574, 0.3755701627468324, 0.7366815337453705, 0.8647608188233733, 0.13491547393494874, 0.2651724843447003, 0.6839982200395627, 0.670120029478374, 0.4513346589990226, 0.148727134762499, 0.47898349686439845, 0.352502337478225, 0.013382332037334077, 0.4780248626694803, 0.11471872347846479, 0.772679046209471, 0.08110571353164886, 0.9184054717229515, 0.15836324769915255, 0.2670807865518203, 0.43575980318532426, 0.19995378915659767, 0.8578353258248839, 0.023989304783126553, 0.39804897722056665, 0.4524796211277611, 0.18039796942653386, 0.04254758763279742, 0.2051481413629721, 0.5348289162359152, 0.3487847843118419, 0.7850501537804806, 0.9191684131753015, 0.8660164189740158, 0.9956579431789447, 0.6957477848968698, 0.03147128686622458, 0.9029694124616181, 0.4411391854837914, 0.52393126757956, 0.6292688283103802, 0.5824683335701215, 0.0279643412305417, 0.7908692161361748, 0.7254442799010183, 0.8205915580620644 };
static Sint32 iRandsSequenceSize = 87;
#endif
 
Maze::Maze(Sint32 iR, Sint32 iC)
{
    rows = iR;
    cols = iC;
    memset(tallRows, 0, sizeof(tallRows));
    memset(narrowCols, 0, sizeof(narrowCols));    
    iNumRands = 0;
 
    // Always the same seed -> deterministic mazes        
    randState = 0;
    Main::Instance().ITool().randSeedWELL(29031978, randSeed);
};
 
Maze::~Maze()
{
    vCells.clear();
}
 
// Create a new maze (internal format)
Sint32 Maze::createMaze(vector<Uint8>& vTiles)
{
    // try to generate a valid map, and keep count of tries.
    Sint32 genCount = 0;
    while(true)
    {
        reset();
        generate();        
        genCount++;        
        if(!isDesirable()) continue;        
        setUpScaleCoords();        
        joinWalls();
        
        if(!createTunnels()) continue;        
        break;
    }
    generateTiles(vTiles);
#ifdef DEBUG_GENERATOR
    for(Sint32 i = 0; i < tileCells.size(); ++i) tileCells[i].info(); // Debug information
#endif
    return genCount;
}
 
Maze::stCell::stCell()
{
    x = -1;
    y = -1;
    filled = false;
    connect[0] = false;
    connect[1] = false;
    connect[2] = false;
    connect[3] = false;
    next[0] = nullptr;
    next[1] = nullptr;
    next[2] = nullptr;
    next[3] = nullptr;
    no = -1;
    group = -1;
    final_x = final_w = final_y = final_h = 0;
    isRaiseHeightCandidate = false;
    isShrinkWidthCandidate = false;
    shrinkWidth = false;
    raiseHeight = false;
    isJoinCandidate = false;
    topTunnel = false;
    singleDeadEndDir = false;
    isEdgeTunnelCandidate = false;
    isVoidTunnelCandidate = false;
    isSingleDeadEndCandidate = false;
    isDoubleDeadEndCandidate = false;
}
 
#ifdef DEBUG_GENERATOR
void Maze::stCell::info()
{
    if(x == -1) return;
    Main& mC64 = Main::Instance();
    Log& mLog = *mC64.ILogMgr().get();
    mLog.msg(LML_NORMAL, "(%d,%d)-%s-", x, y, (filled == true) ? "true" : "false"); 
    mLog.msg(LML_NORMAL, "%s.%s.%s.%s-",
        (connect[0] == true) ? "true" : "false", (connect[1] == true) ? "true" : "false", (connect[2] == true) ? "true" : "false", (connect[3] == true) ? "true" : "false");
    mLog.msg(LML_NORMAL, "%s.%s.%s.%s-",
        (next[0] == nullptr) ? "null" : "defined", (next[1] == nullptr) ? "null" : "defined", (next[2] == nullptr) ? "null" : "defined", (next[3] == nullptr) ? "null" : "defined");
    mLog.msg(LML_NORMAL, "%d-%d-", no, group);
    mLog.msg(LML_NORMAL, "%d.%d.%d.%d-", final_x, final_w, final_y, final_h);
    mLog.msg(LML_NORMAL, "%s.%s.%s.%s.%s.%s\n",
        (isRaiseHeightCandidate) ? "isRaiseHeightCandidate" : "", 
        (isShrinkWidthCandidate) ? "isShrinkWidthCandidate" : "",
        (shrinkWidth) ? "shrinkWidth" : "", 
        (raiseHeight) ? "raiseHeight" : "",
        (isJoinCandidate) ? "isJoinCandidate" : "",
        (topTunnel) ? "topTunnel" : ""
    );
}
#endif
 
Sint32 Maze::reset()
{
    Sint32 i;
    stCell sCell, *pCell;
 
    // Clean all cells
    vCells.clear();
 
    // initialize cells
    for(i = 0; i < rows * cols; i++)
    {
        sCell.x = i % cols;
        sCell.y = (Sint32)floor(i / cols);
        vCells.push_back(sCell);
    }
 
    // allow each cell to refer to surround cells by direction
    for(i = 0; i < rows * cols; i++)
    {
        pCell = &vCells[i];
        if(pCell->x > 0) pCell->next[LEFT] = &vCells[i - 1];
        if(pCell->x < cols - 1) pCell->next[RIGHT] = &vCells[i + 1];
        if(pCell->y > 0) pCell->next[UP] = &vCells[i - cols];
        if(pCell->y < rows - 1) pCell->next[DOWN] = &vCells[i + cols];
    }
 
    // define the ghost home square
    i = 3 * cols;
    pCell = &vCells[i];
    pCell->filled = true;
    pCell->connect[LEFT] = pCell->connect[RIGHT] = pCell->connect[DOWN] = true;
 
    i++;
    pCell = &vCells[i];
    pCell->filled = true;
    pCell->connect[LEFT] = pCell->connect[DOWN] = true;
 
    i += cols - 1;
    pCell = &vCells[i];
    pCell->filled = true;
    pCell->connect[LEFT] = pCell->connect[UP] = pCell->connect[RIGHT] = true;
 
    i++;
    pCell = &vCells[i];
    pCell->filled = true;
    pCell->connect[UP] = pCell->connect[LEFT] = true;
 
    numFilled = numGroups = iNumRands = 0;
    return 0;
}
 
#ifdef DEBUG_GENERATOR
// Fixed sequence for debugging
Sint32 Maze::getRandomInt(Sint32 min, Sint32 max)
{
    Sint32 iRet;
    double iRnd;
    iRnd = aRandsSequence[iNumRands % iRandsSequenceSize];
    iRet = (Sint32)floor(iRnd * (max - min + 1)) + min;
    iNumRands++;
    return iRet;
}
 
// Fixed sequence for debugging
double Maze::getRandomReal()
{
    double iRnd = aRandsSequence[iNumRands % iRandsSequenceSize];
    iNumRands++;
    return iRnd;
}
#else
 
// Random generator
Sint32 Maze::getRandomInt(Sint32 min, Sint32 max)
{
    ++iNumRands;
    return (Sint32)floor(Main::Instance().ITool().randRealWELL(&randState, randSeed) * (max - min + 1)) + min;
};
 
// Random generator
double Maze::getRandomReal()
{
    ++iNumRands;
    return Main::Instance().ITool().randRealWELL(&randState, randSeed);
}
#endif
 
Maze::stCell* Maze::randomElement(vector<stCell*>& vList)
{
    if(vList.size() > 0)
    {
        return vList[getRandomInt(0, (Sint32)vList.size() - 1)];
    }
    return nullptr;
}
 
Sint32 Maze::suffle(vector<stCell*>& vSuffle)
{
    Sint32 iLen = (Sint32)vSuffle.size();
    Sint32 i, j;
    stCell* pCell;
 
    for(i = 0; i < iLen; i++)
    {
        j = getRandomInt(0, iLen - 1);
        pCell = vSuffle[i];
        vSuffle[i] = vSuffle[j];
        vSuffle[j] = pCell;
    }
    return 0;
}
 
void Maze::getOpenCells(stCell& cell, Sint32 prevDir, Sint32 size, vector<Sint32>& openCells)
{
    Sint32 i;
    openCells.clear();
 
    for(i = 0; i < 4; i++)
    {
        if(isOpenCell(cell, i, prevDir, size))
        {
            openCells.push_back(i);
        }
    }
}
 
Sint32 Maze::getLeftMostEmptyCells(vector<stCell*>& leftCells)
{
    Sint32 x, y;
    stCell* pCell;
    leftCells.clear();
 
    for(x = 0; x < cols; x++)
    {
        for(y = 0; y < rows; y++)
        {
            pCell = &vCells[x + y * cols];
            if(!pCell->filled) leftCells.push_back(pCell);
        }
 
        if(leftCells.size() > 0) break;
    }
    return 0;
}
 
bool Maze::isOpenCell(stCell& cell, Sint32 i, Sint32 prevDir, Sint32 size)
{
    // prevent wall from going through starting position
    if(cell.y == 6 && cell.x == 0 && i == DOWN || cell.y == 7 && cell.x == 0 && i == UP) return false;
 
    // prevent long straight pieces of length 3
    if(size == 2 && (i == prevDir || (i + 2) % 4 == prevDir)) return false;
 
    // examine an adjacent empty cell
    if(cell.next[i] && !cell.next[i]->filled)
    {
        // only open if the cell to the left of it is filled
        if(cell.next[i]->next[LEFT] && !cell.next[i]->next[LEFT]->filled) {} // RPP out of range pointer?
        else return true;
    }
    return false;
}
 
void Maze::connectCell(stCell& cell, Sint32 dir)
{
    cell.connect[dir] = true;
    cell.next[dir]->connect[(dir + 2) % 4] = true;
    if(cell.x == 0 && dir == RIGHT) cell.connect[LEFT] = true;
}
 
void Maze::setResizeCandidates()
{
    Sint32 i;
    Sint32 x, y;
    bool* q;
    bool* q2;
 
    for(i = 0; i < rows * cols; i++)
    {
        stCell& c = vCells[i];
        x = i % cols;
        y = (Sint32)floor(i / cols);
 
        // determine if it has flexible height
        // |_|
        //
        // or
        //  _
        // | |
        q = c.connect;
        if((c.x == 0 || !q[LEFT]) && (c.x == cols - 1 || !q[RIGHT]) && q[UP] != q[DOWN]) c.isRaiseHeightCandidate = true;
 
        //  _ _
        // |_ _|
        //
        stCell* c2 = c.next[RIGHT];
        if(c2 != nullptr)
        {
            q2 = c2->connect;
            if(((c.x == 0 || !q[LEFT]) && !q[UP] && !q[DOWN]) && ((c2->x == cols - 1 || !q2[RIGHT]) && !q2[UP] && !q2[DOWN])) c.isRaiseHeightCandidate = c2->isRaiseHeightCandidate = true;
        }
 
        // determine if it has flexible width
        // if cell is on the right edge with an opening to the right
        if(c.x == cols - 1 && q[RIGHT]) c.isShrinkWidthCandidate = true;
 
        //  _
        // |_
        // 
        // or
        //  _
        //  _|
        //
        if((c.y == 0 || !q[UP]) && (c.y == rows - 1 || !q[DOWN]) && q[LEFT] != q[RIGHT]) c.isShrinkWidthCandidate = true;
    }
}
 
// Identify if a cell is the center of a cross.
bool Maze::cellIsCrossCenter(stCell& c)
{
    return c.connect[UP] && c.connect[RIGHT] && c.connect[DOWN] && c.connect[LEFT];
}
 
bool Maze::canShrinkWidth(Sint32 x, Sint32 y)
{
    Sint32 i;
    Sint32 numCandidates = 0;
    stCell* c2;
    vector<stCell*> pCandidates;
 
    // Can cause no more tight turns.
    if(y == rows - 1)  return true;
 
    // get the right-hand-side bound
    for(i = x; i < cols; i++)
    {
        stCell& c = vCells[i + y * cols];
        c2 = c.next[DOWN]; // RPP lacks of ;
        if((!c.connect[RIGHT] || cellIsCrossCenter(c)) && (!c2->connect[RIGHT] || cellIsCrossCenter(*c2))) break;
    }
 
    // build candidate list
    for(; c2; c2 = c2->next[LEFT])
    {
        if(c2->isShrinkWidthCandidate)
        {
            pCandidates.push_back(c2);
            numCandidates++;
        }
 
        // cannot proceed further without causing irreconcilable tight turns
        if((!c2->connect[LEFT] || cellIsCrossCenter(*c2)) && (!c2->next[UP]->connect[LEFT] || cellIsCrossCenter(*c2->next[UP]))) break;
    }
 
    // Shuffle the candidates
    suffle(pCandidates);
 
    for(i = 0; i < numCandidates; i++)
    {
        c2 = pCandidates[i];
        if(canShrinkWidth(c2->x, c2->y))
        {
            c2->shrinkWidth = true;
            narrowCols[c2->y] = c2->x;
            return true;
        }
    }
    return false;
}
 
bool Maze::chooseNarrowCols()
{
    Sint32 x;
 
    for(x = cols - 1; x >= 0; x--)
    {
        stCell& c = vCells[x];
        if(c.isShrinkWidthCandidate && canShrinkWidth(x, 0))
        {
            c.shrinkWidth = true;
            narrowCols[c.y] = c.x;
            return true;
        }
    }
    return false;
}
 
bool Maze::canRaiseHeight(Sint32 x, Sint32 y)
{
    Sint32 i;
    Sint32 numCandidates = 0;
    stCell* c2;
    vector<stCell*> pCandidates;
 
    // Can cause no more tight turns.
    if(x == cols - 1) return true;
 
    // find the first cell below that will create too tight a turn on the right
    for(i = y; i >= 0; i--)
    {
        stCell& c = vCells[x + i * cols];
        c2 = c.next[RIGHT]; // RPP lacks of ;
        if((!c.connect[UP] || cellIsCrossCenter(c)) && (!c2->connect[UP] || cellIsCrossCenter(*c2))) break;
    }
 
    // Proceed from the right cell upwards, looking for a cell that can be raised.
    for(; c2; c2 = c2->next[DOWN])
    {
        if(c2->isRaiseHeightCandidate)
        {
            pCandidates.push_back(c2);
            numCandidates++;
        }
 
        // cannot proceed further without causing irreconcilable tight turns
        if((!c2->connect[DOWN] || cellIsCrossCenter(*c2)) && (!c2->next[LEFT]->connect[DOWN] || cellIsCrossCenter(*c2->next[LEFT]))) break;
    }
 
    // Shuffle the candidates
    suffle(pCandidates);
 
    for(i = 0; i < numCandidates; i++)
    {
        c2 = pCandidates[i];
        if(canRaiseHeight(c2->x, c2->y))
        {
            c2->raiseHeight = true;
            tallRows[c2->x] = c2->y;
            return true;
        }
    }
 
    return false;
}
 
bool Maze::chooseTallRows()
{
    // From the top left, examine cells below until hitting top of ghost house.
    // A raisable cell must be found before the ghost house.
    Sint32 y;
    for(y = 0; y < 3; y++)
    {
        stCell& c = vCells[y*cols];
        if(c.isRaiseHeightCandidate && canRaiseHeight(0, y))
        {
            c.raiseHeight = true;
            tallRows[c.x] = c.y;
            return true;
        }
    }
    return false;
}
 
// ensure there are no two stacked/side-by-side 2-cell pieces.
bool Maze::isHori(Sint32 x, Sint32 y)
{
    bool* q1 = vCells[x + y * cols].connect;
    bool* q2 = vCells[x + 1 + y * cols].connect;
    return !q1[UP] && !q1[DOWN] && (x == 0 || !q1[LEFT]) && q1[RIGHT] && !q2[UP] && !q2[DOWN] && q2[LEFT] && !q2[RIGHT];
}
 
bool Maze::isVert(Sint32 x, Sint32 y)
{
    bool* q1 = vCells[x + y * cols].connect;
    bool* q2 = vCells[x + (y + 1)*cols].connect;
    if(x == cols - 1)
    {
        // special case (we can consider two single cells as vertical at the right edge)
        return !q1[LEFT] && !q1[UP] && !q1[DOWN] && !q2[LEFT] && !q2[UP] && !q2[DOWN];
    }
    return !q1[LEFT] && !q1[RIGHT] && !q1[UP] && q1[DOWN] && !q2[LEFT] && !q2[RIGHT] && q2[UP] && !q2[DOWN];
}
 
// This is a function to detect impurities in the map that have no heuristic implemented to avoid it yet in gen().
bool Maze::isDesirable()
{
    Sint32 x, y, g;
 
    // ensure a solid top right corner
    stCell& rCTR = vCells[4];
    if(rCTR.connect[UP] || rCTR.connect[RIGHT]) return false;
 
    // ensure a solid bottom right corner
    stCell& rCBR = vCells[rows*cols - 1];
    if(rCBR.connect[DOWN] || rCBR.connect[RIGHT]) return false;
 
    for(y = 0; y < rows - 1; y++)
    {
        for(x = 0; x < cols - 1; x++)
        {
            if(isHori(x, y) && isHori(x, y + 1) || isVert(x, y) && isVert(x + 1, y))
            {
                // don't allow them in the middle because they'll be two large when reflected.
                if(x == 0) return false;
 
                // Join the four cells to create a square.
                vCells[x + y * cols].connect[DOWN] = true;
                vCells[x + y * cols].connect[RIGHT] = true;
                g = vCells[x + y * cols].group;
 
                vCells[x + 1 + y * cols].connect[DOWN] = true;
                vCells[x + 1 + y * cols].connect[LEFT] = true;
                vCells[x + 1 + y * cols].group = g;
 
                vCells[x + (y + 1)*cols].connect[UP] = true;
                vCells[x + (y + 1)*cols].connect[RIGHT] = true;
                vCells[x + (y + 1)*cols].group = g;
 
                vCells[x + 1 + (y + 1)*cols].connect[UP] = true;
                vCells[x + 1 + (y + 1)*cols].connect[LEFT] = true;
                vCells[x + 1 + (y + 1)*cols].group = g;
            }
        }
    }
 
    if(!chooseTallRows()) return false;
 
    if(!chooseNarrowCols()) return false;
 
    return true;
}
 
// set the final position and size of each cell when upscaling the simple model to actual size
void Maze::setUpScaleCoords()
{
    Sint32 i;
    for(i = 0; i < rows * cols; i++)
    {
        stCell& c = vCells[i];
        c.final_x = c.x * 3;
        if(narrowCols[c.y] < c.x) c.final_x--;
        c.final_y = c.y * 3;
        if(tallRows[c.x] < c.y) c.final_y++;
        c.final_w = c.shrinkWidth ? 2 : 3;
        c.final_h = c.raiseHeight ? 4 : 3;
    }
}
 
// randomly join wall pieces to the boundary to increase difficulty
void Maze::joinWalls()
{
    Sint32 x, y;
 
    // join cells to the top boundary
    for(x = 0; x < cols; x++)
    {
        stCell& c = vCells[x];
        if(!c.connect[LEFT] && !c.connect[RIGHT] && !c.connect[UP] && (!c.connect[DOWN] || !c.next[DOWN]->connect[DOWN])) // RPP out of range pointer?
        {
            // ensure it will not create a dead-end
            if((!c.next[LEFT] || !c.next[LEFT]->connect[UP]) && (c.next[RIGHT] && !c.next[RIGHT]->connect[UP])) // RPP out of range pointer?
            {
                // prevent connecting very large piece
                if(!(c.next[DOWN] && c.next[DOWN]->connect[RIGHT] && c.next[DOWN]->next[RIGHT]->connect[RIGHT]))
                {
                    c.isJoinCandidate = true;
                    if(getRandomReal() <= 0.25) c.connect[UP] = true;
                }
            }
        }
    }
 
    // join cells to the bottom boundary
    for(x = 0; x < cols; x++)
    {
        stCell& c = vCells[x + (rows - 1)*cols];
        if(!c.connect[LEFT] && !c.connect[RIGHT] && !c.connect[DOWN] && (!c.connect[UP] || !c.next[UP]->connect[UP]))
        {
            // ensure it will not creat a dead-end
            if((!c.next[LEFT] || !c.next[LEFT]->connect[DOWN]) && (c.next[RIGHT] && !c.next[RIGHT]->connect[DOWN]))
            {
                // prevent connecting very large piece
                if(!(c.next[UP] && c.next[UP]->connect[RIGHT] && c.next[UP]->next[RIGHT]->connect[RIGHT]))
                {
                    c.isJoinCandidate = true;
                    if(getRandomReal() <= 0.25) c.connect[DOWN] = true;
                }
            }
        }
    }
 
    // join cells to the right boundary
    for(y = 1; y < rows - 1; y++)
    {
        stCell& c = vCells[cols - 1 + y * cols];
        if(c.raiseHeight) continue;
        if(!c.connect[RIGHT] && !c.connect[UP] && !c.connect[DOWN] && !c.next[UP]->connect[RIGHT] && !c.next[DOWN]->connect[RIGHT])
        {
            if(c.connect[LEFT])
            {
                stCell* c2 = c.next[LEFT];
                if(!c2->connect[UP] && !c2->connect[DOWN] && !c2->connect[LEFT])
                {
                    c.isJoinCandidate = true;
                    if(getRandomReal() <= 0.5) c.connect[RIGHT] = true;
                }
            }
        }
    }
}
 
void Maze::fillCell(stCell& cell)
{
    cell.filled = true;
    cell.no = numFilled++;
    cell.group = numGroups;
}
 
void Maze::selectSingleDeadEnd(stCell* c)
{
    c->connect[RIGHT] = true;
    if(c->singleDeadEndDir == UP) 
    {
        c->topTunnel = true;
    }
    else 
    {
        c->next[DOWN]->topTunnel = true;
    }
};
 
void Maze::replaceGroup(Sint32 oldg, Sint32 newg) 
{
    Sint32 i;
    
    for(i = 0; i < rows*cols; i++) 
    {
        stCell& c = vCells[i];
        if(c.group == oldg) c.group = newg;
    }
}
 
bool Maze::createTunnels()
{
    // declare candidates
    vector<stCell*> edgeTunnelCells;
    vector<stCell*> topEdgeTunnelCells;
    vector<stCell*> botEdgeTunnelCells;
    vector<stCell*> voidTunnelCells;
    vector<stCell*> topVoidTunnelCells;
    vector<stCell*> botVoidTunnelCells;
    vector<stCell*> singleDeadEndCells;
    vector<stCell*> topSingleDeadEndCells;
    vector<stCell*> botSingleDeadEndCells;
    vector<stCell*> doubleDeadEndCells;
    
    Sint32 numTunnelsCreated = 0;
    Sint32 y;
    bool upDead, downDead;
    stCell* pCell;
 
    // prepare candidates
    for(y = 0; y < rows; y++) 
    {
        stCell& c = vCells[cols - 1 + y * cols];
        if(c.connect[UP]) 
        {
            continue;
        }
        if(c.y > 1 && c.y < rows - 2) 
        {
            c.isEdgeTunnelCandidate = true;
            edgeTunnelCells.push_back(&c);
            if(c.y <= 2) 
            {
                topEdgeTunnelCells.push_back(&c);
            }
            else if(c.y >= 5) 
            {
                botEdgeTunnelCells.push_back(&c);
            }
        }
        upDead = (!c.next[UP] || c.next[UP]->connect[RIGHT]);
        downDead = (!c.next[DOWN] || c.next[DOWN]->connect[RIGHT]);
        if(c.connect[RIGHT]) 
        {
            if(upDead) 
            {
                c.isVoidTunnelCandidate = true;
                voidTunnelCells.push_back(&c);
                if(c.y <= 2) 
                {
                    topVoidTunnelCells.push_back(&c);
                }
                else if(c.y >= 6) 
                {
                    botVoidTunnelCells.push_back(&c);
                }
            }
        }
        else 
        {
            if(c.connect[DOWN]) 
            {
                continue;
            }
            if(upDead != downDead) 
            {
                if(!c.raiseHeight && y < rows - 1 && !c.next[LEFT]->connect[LEFT]) 
                {
                    singleDeadEndCells.push_back(&c);
                    c.isSingleDeadEndCandidate = true;
                    c.singleDeadEndDir = upDead ? UP : DOWN;
                    Sint32 offset = upDead ? 1 : 0;
                    if(c.y <= 1 + offset) 
                    {
                        topSingleDeadEndCells.push_back(&c);
                    }
                    else if(c.y >= 5 + offset) 
                    {
                        botSingleDeadEndCells.push_back(&c);
                    }
                }
            }
            else if(upDead && downDead) 
            {
                if(y > 0 && y < rows - 1) 
                {
                    if(c.next[LEFT]->connect[UP] && c.next[LEFT]->connect[DOWN]) 
                    {
                        c.isDoubleDeadEndCandidate = true;
                        if(c.y >= 2 && c.y <= 5) 
                        {
                            doubleDeadEndCells.push_back(&c);
                        }
                    }
                }
            }
        }
    }
 
    // choose tunnels from candidates
    Sint32 numTunnelsDesired = getRandomReal() <= 0.45 ? 2 : 1;
    if(numTunnelsDesired == 1) 
    {
        if(pCell = randomElement(voidTunnelCells)) 
        {
            pCell->topTunnel = true;
        }
        else if(pCell = randomElement(singleDeadEndCells)) 
        {
            selectSingleDeadEnd(pCell);
        }
        else if(pCell = randomElement(edgeTunnelCells)) 
        {
            pCell->topTunnel = true;
        }
        else 
        {
            return false;
        }
    }
    else if(numTunnelsDesired == 2) 
    {
        if(pCell = randomElement(doubleDeadEndCells)) 
        {
            pCell->connect[RIGHT] = true;
            pCell->topTunnel = true;
            pCell->next[DOWN]->topTunnel = true;
        }
        else 
        {
            numTunnelsCreated = 1;
            if(pCell = randomElement(topVoidTunnelCells))
            {
                pCell->topTunnel = true;
            }
            else if(pCell = randomElement(topSingleDeadEndCells))
            {
                selectSingleDeadEnd(pCell);
            }
            else if(pCell = randomElement(topEdgeTunnelCells))
            {
                pCell->topTunnel = true;
            }
            else 
            {
                // could not find a top tunnel opening
                numTunnelsCreated = 0;
            }
 
            if(pCell = randomElement(botVoidTunnelCells))
            {
                pCell->topTunnel = true;
            }
            else if(pCell = randomElement(botSingleDeadEndCells))
            {
                selectSingleDeadEnd(pCell);
            }
            else if(pCell = randomElement(botEdgeTunnelCells))
            {
                pCell->topTunnel = true;
            }
            else 
            {
                // could not find a bottom tunnel opening
                if(numTunnelsCreated == 0) 
                {
                    return false;
                }
            }
        }
    }
 
    // don't allow a horizontal path to cut straight through a map (through tunnels)
    bool exit;
    Sint32 topy;
    for(y = 0; y < rows; y++) 
    {
        pCell = &vCells[cols - 1 + y * cols];
        if(pCell->topTunnel)
        {
            exit = true;
            topy = pCell->final_y;
            while(pCell->next[LEFT])
            {
                pCell = pCell->next[LEFT];
                if(!pCell->connect[UP] && pCell->final_y == topy) 
                {
                    continue;
                }
                else 
                {
                    exit = false;
                    break;
                }
            }
            if(exit) 
            {
                return false;
            }
        }
    }
 
    // clear unused void tunnels (dead ends)
    Sint32 len = (Sint32)voidTunnelCells.size();
    Sint32 i;    
    for(i = 0; i < len; i++) 
    {
        pCell = voidTunnelCells[i];
        if(!pCell->topTunnel)
        {
            replaceGroup(pCell->group, pCell->next[UP]->group);
            pCell->connect[UP] = true;
            pCell->next[UP]->connect[DOWN] = true;
        }
    }
 
    return true;
}
 
// generate a maze (internal format)
void Maze::generate()
{
    vector<stCell*> openCells; // list of open cells around the center cell
    Sint32 numOpenCells; // size of openCells // RPP remove this and use .size()
    vector<Sint32> nearCells;
    stCell* newCell = nullptr;   // most recent cell filled
 
    Sint32 dir = -1; // the most recent direction of growth relative to the center cell
    Sint32 i;   // loop control variable used for iterating directions
 
    Sint32 size; // current number of cells in the current group
    double probStopGrowingAtSize[] = {  // probability of stopping growth at sizes...
            0,     // size 0
            0,     // size 1
            0.10,  // size 2
            0.5,   // size 3
            0.75,  // size 4
            1 };   // size 5
 
    // A single cell group of size 1 is allowed at each row at y=0 and y=rows-1,
    // so keep count of those created.
    std::map<Sint32, Sint32> singleCount;
    singleCount.insert(std::pair<Sint32, Sint32>(0, 0));
    singleCount.insert(std::pair<Sint32, Sint32>(rows - 1, 0));
    double probTopAndBotSingleCellJoin = 0.35;
 
    // A count and limit of the number long pieces (i.e. an "L" of size 4 or "T" of size 5)
    Sint32 longPieces = 0;
    Sint32 maxLongPieces = 1;
    Sint32 probExtendAtSize2 = 1;
    double probExtendAtSize3or4 = 0.5;
 
    for(numGroups = 0; ; numGroups++)
    {
        // find all the leftmost empty cells
        getLeftMostEmptyCells(openCells);
 
        // stop add pieces if there are no more empty cells.
        numOpenCells = (Sint32)openCells.size();
        if(numOpenCells == 0) break;
 
        // choose the center cell to be a random open cell, and fill it.
        stCell* firstCell = openCells[getRandomInt(0, numOpenCells - 1)];  // cell at the center of growth (open cells are chosen around this cell)        
        stCell* pCell = firstCell; // the starting cell of the current group
 
        fillCell(*pCell);
 
        // randomly allow one single-cell piece on the top or bottom of the map.
        if(pCell->x < cols - 1 && (singleCount.count(pCell->y)) && getRandomReal() <= probTopAndBotSingleCellJoin)
        {
            if(singleCount[pCell->y] == 0)
            {
                pCell->connect[pCell->y == 0 ? UP : DOWN] = true;
                singleCount[pCell->y]++;
                continue;
            }
        }
 
        // number of cells in this contiguous group
        size = 1;
 
        if(pCell->x == cols - 1)
        {
            // if the first cell is at the right edge, then don't grow it.
            pCell->connect[RIGHT] = true;
            pCell->isRaiseHeightCandidate = true;
        }
        else
        {
            // only allow the piece to grow to 5 cells at most.
            while(size < 5)
            {
                bool stop = false;
                if(size == 2)
                {
                    // With a horizontal 2-cell group, try to turn it into a 4-cell "L" group.
                    // This is done here because this case cannot be reached when a piece has already grown to size 3.
                    stCell& c = *firstCell;
                    if(c.x > 0 && c.connect[RIGHT] && c.next[RIGHT] && c.next[RIGHT]->next[RIGHT])
                    {
                        if(longPieces < maxLongPieces && getRandomReal() <= probExtendAtSize2)
                        {
                            stCell* pC = c.next[RIGHT]->next[RIGHT];
                            std::map<Sint32, bool> dirs;
                            if(isOpenCell(*pC, UP)) dirs[UP] = true;
                            if(isOpenCell(*pC, DOWN)) dirs[DOWN] = true;
                            if(dirs[UP] && dirs[DOWN]) i = (getRandomInt(0, 1) == 0 ? UP : DOWN);
                            else if(dirs[UP]) i = UP;
                            else if(dirs[DOWN]) i = DOWN;
                            else i = -1;
 
                            if(i != -1)
                            {
                                connectCell(*pC, LEFT);
                                fillCell(*pC);
                                connectCell(*pC, i);
                                fillCell(*pC->next[i]);
                                longPieces++;
                                size += 2;
                                stop = true;
                            }
                        }
                    }
                }
 
                if(!stop)
                {
                    // find available open adjacent cells.
                    getOpenCells(*pCell, dir, size, nearCells);
                    numOpenCells = (Sint32)nearCells.size();
 
                    // if no open cells found from center point, then use the last cell as the new center
                    // but only do this if we are of length 2 to prevent numerous short pieces.
                    // then recalculate the open adjacent cells.
                    if(nearCells.size() == 0 && size == 2)
                    {
                        pCell = newCell;
                        getOpenCells(*pCell, dir, size, nearCells);
                        numOpenCells = (Sint32)nearCells.size();
                    }
 
                    // no more adjacent cells, so stop growing this piece.
                    if(numOpenCells == 0) stop = true;
                    else
                    {
                        // choose a random valid direction to grow.
                        dir = nearCells[getRandomInt(0, numOpenCells - 1)];
                        newCell = pCell->next[dir];
 
                        // connect the cell to the new cell.
                        connectCell(*pCell, dir);
 
                        // fill the cell
                        fillCell(*newCell);
 
                        // increase the size count of this piece.
                        size++;
 
                        // don't let center pieces grow past 3 cells
                        if(firstCell->x == 0 && size == 3) stop = true;
 
                        // Use a probability to determine when to stop growing the piece.
                        if(getRandomReal() <= probStopGrowingAtSize[size]) stop = true;
                    }
                }
 
                // Close the piece.
                if(stop)
                {
                    if(size == 1)
                    {
                        // This is probably impossible because this loop is never entered with size==1.
                    }
                    else if(size == 2)
                    {
                        // With a vertical 2-cell group, attach to the right wall if adjacent.
                        stCell& c = *firstCell;
                        if(c.x == cols - 1)
                        {
                            // select the top cell
                            if(c.connect[UP]) c = *c.next[UP];
                            c.connect[RIGHT] = c.next[DOWN]->connect[RIGHT] = true;
                        }
                    }
                    else if(size == 3 || size == 4)
                    {
                        // Try to extend group to have a long leg
                        if(longPieces < maxLongPieces && firstCell->x > 0 && getRandomReal() <= probExtendAtSize3or4)
                        {
                            vector<Sint32> dirs;
                            dirs.clear();
                            Sint32 dirsLength = 0;
                            for(i = 0; i < 4; i++)
                            {
                                if(pCell->connect[i] && isOpenCell(*pCell->next[i], i))
                                {
                                    dirs.push_back(i);
                                    dirsLength++;
                                }
                            }
                            if(dirsLength > 0)
                            {
                                i = dirs[getRandomInt(0, dirsLength - 1)];
                                stCell& c = *pCell->next[i];
                                connectCell(c, i);
                                fillCell(*c.next[i]);
                                longPieces++;
                            }
                        }
                    }
                    break;
                }
            }
        }
    }
    setResizeCandidates();
}
 
// getter and setter for tiles (ensures vertical symmetry axis)
void Maze::setTile(Sint32 x, Sint32 y, Uint8 v, vector<Uint8>& tiles)
{
    if(x<0 || x>subcols - 1 || y<0 || y>subrows - 1) return;
    x -= 2;
    tiles[midcols + x + y * fullcols] = v;
    tiles[midcols - 1 - x + y * fullcols] = v;
}
 
Sint32 Maze::getTile(Sint32 x, Sint32 y, vector<Uint8>& tiles)
{
    if(x<0 || x>subcols - 1 || y<0 || y>subrows - 1) return -1;
    x -= 2;
    return tiles[midcols + x + y * fullcols];
}
 
// getter and setter for tile cells
void Maze::setTileCell(Sint32 x, Sint32 y, stCell& cell)
{
    if(x<0 || x>subcols - 1 || y<0 || y>subrows - 1) return;
    x -= 2;
    tileCells[x + y * subcols] = cell;
}
 
Maze::stCell* Maze::getTileCell(Sint32 x, Sint32 y)
{
    Sint32 i;
    if(x<0 || x>subcols - 1 || y<0 || y>subrows - 1) return nullptr;
    x -= 2;
    i = x + y * subcols;
    if(i < 0) return nullptr; // Out of bounds
    if(tileCells[i].x == -1) return nullptr; // Undefined elements
    return &tileCells[i];
}
 
bool Maze::getTopEnergizerRange(Sint32& miny, Sint32& maxy, vector<Uint8>& tiles)
{
    Sint32 x = subcols - 2;
    Sint32 y;
    maxy = subrows / 2;
 
    for(y = 2; y < maxy; y++)
    {
        if(getTile(x, y, tiles) == '.' && getTile(x, y + 1, tiles) == '.')
        {
            miny = y + 1;
            break;
        }
    }
    maxy = (std::min)(maxy, miny + 7); // VS: bypass min macro definition
    for(y = miny + 1; y < maxy; y++)
    {
        if(getTile(x - 1, y, tiles) == '.')
        {
            maxy = y - 1;
            break;
        }
    }
    return true;
}
 
bool Maze::getBotEnergizerRange(Sint32& miny, Sint32& maxy, vector<Uint8>& tiles)
{
    Sint32 x = subcols - 2;
    Sint32 y;
    miny = subrows / 2;
    for(y = subrows - 3; y >= miny; y--)
    {
        if(getTile(x, y, tiles) == '.' && getTile(x, y + 1, tiles) == '.')
        {
            maxy = y;
            break;
        }
    }
    miny = (std::max)(miny, maxy - 7); // VS: bypass max macro definition
    for(y = maxy - 1; y > miny; y--)
    {
        if(getTile(x - 1, y, tiles) == '.')
        {
            miny = y + 1;
            break;
        }
    }
    return true;
}
 
// erase pellets in the tunnels
void Maze::eraseUntilIntersection(Sint32 x, Sint32 y, vector<Uint8>& tiles)
{
    struct sAdj
    {
        Sint32 x, y;
    } sAdjust;
    vector<sAdj> vAdj;
 
    //var adj;
    while(true)
    {
        if(getTile(x - 1, y, tiles) == '.')
        {
            sAdjust.x = x - 1;
            sAdjust.y = y;
            vAdj.push_back(sAdjust);
        }
        if(getTile(x + 1, y, tiles) == '.')
        {
            sAdjust.x = x + 1;
            sAdjust.y = y;
            vAdj.push_back(sAdjust);
        }
        if(getTile(x, y - 1, tiles) == '.')
        {
            sAdjust.x = x;
            sAdjust.y = y - 1;
            vAdj.push_back(sAdjust);            
        }
        if(getTile(x, y + 1, tiles) == '.')
        {
            sAdjust.x = x;
            sAdjust.y = y + 1;
            vAdj.push_back(sAdjust);
        }
        if(vAdj.size() == 1)
        {
            setTile(x, y, ' ', tiles);
            x = vAdj[0].x;
            y = vAdj[0].y;
        }
        else
        {
            break;
        }
    }
}
 
#ifdef DEBUG_GENERATOR
// Debugging maze tiles...
#include <fstream>
#include <sstream>
#endif
 
Sint32 Maze::generateTiles(vector<Uint8>& vTiles)
{
    Sint32 i, j, x, y, x0, y0;
    stCell* c;
    vTiles.clear(); // each is a character indicating a wall(|), path(.), or blank(_).
    tileCells.clear(); // maps each tile to a specific cell of our simple map
    subrows = rows * 3 + 1 + 3;
    subcols = cols * 3 - 1 + 2;
    midcols = subcols - 2;
    fullcols = (subcols - 2) * 2;
 
    // initialize tiles
    stCell cellContainer; // Todo: with a constructor it could be initiated
    for(i = 0; i < subrows*fullcols; i++) vTiles.push_back('_');
    for(i = 0; i < subrows*subcols; i++) tileCells.push_back(cellContainer);
 
    // set tile cells    
    for(i = 0; i < rows*cols; i++)
    {
        c = &vCells[i];
        for(x0 = 0; x0 < c->final_w; x0++)
        {
            for(y0 = 0; y0 < c->final_h; y0++)
            {
                setTileCell(c->final_x + x0, c->final_y + 1 + y0, *c);
            }
        }
    }
    
    // set path tiles
    stCell* cl; stCell* cu;
    for(y = 0; y < subrows; y++)
    {
        for(x = 0; x < subcols; x++)
        {
            c = getTileCell(x, y); // cell
            cl = getTileCell(x - 1, y); // left cell
            cu = getTileCell(x, y - 1); // up cell
 
            if(c)
            {
                // inside map
                if(cl && c->group != cl->group || // at vertical boundary
                    cu && c->group != cu->group || // at horizontal boundary
                    !cu && !c->connect[UP]) // at top boundary
                {
                    setTile(x, y, '.', vTiles);
                }
            }
            else
            {
                // outside map
                if(cl && (!cl->connect[RIGHT] || getTile(x - 1, y, vTiles) == '.') || // at right boundary
                    cu && (!cu->connect[DOWN] || getTile(x, y - 1, vTiles) == '.')) // at bottom boundary
                {
                    setTile(x, y, '.', vTiles);
                }
            }
 
            // at corner connecting two paths
            if(getTile(x - 1, y, vTiles) == '.' && getTile(x, y - 1, vTiles) == '.' && getTile(x - 1, y - 1, vTiles) == '_') setTile(x, y, '.', vTiles);
        }
    }
 
    #ifdef DEBUG_GENERATOR
    // Debugging maze tiles...
    std::ofstream vFile("DumpC-Tiles.txt");
    if(!vFile) return -1;
    for(i = 0; i < vTiles.size(); ++i)
    {
        vFile << vTiles[i] << std::endl;
    }
    vFile.close();
    #endif
 
    // extend tunnels
    for(c = &vCells[cols - 1]; c; c = c->next[DOWN])
    {
        if(c->topTunnel)
        {
            y = c->final_y + 1;
            setTile(subcols - 1, y, '.', vTiles);
            setTile(subcols - 2, y, '.', vTiles);
        }
    }
 
    // fill in walls
    for(y = 0; y < subrows; y++)
    {
        for(x = 0; x < subcols; x++)
        {
            // any blank tile that shares a vertex with a path tile should be a wall tile
            if(getTile(x, y, vTiles) != '.' && (getTile(x - 1, y, vTiles) == '.' || getTile(x, y - 1, vTiles) == '.' || getTile(x + 1, y, vTiles) == '.' || getTile(x, y + 1, vTiles) == '.' ||
                getTile(x - 1, y - 1, vTiles) == '.' || getTile(x + 1, y - 1, vTiles) == '.' || getTile(x + 1, y + 1, vTiles) == '.' || getTile(x - 1, y + 1, vTiles) == '.'))
            {
                setTile(x, y, '|', vTiles);
            }
        }
    }
 
    // create the ghost door
    setTile(2, 12, '-', vTiles);
 
    // set energizers       
    x = subcols - 2;
    Sint32 miny, maxy;
 
    if(getTopEnergizerRange(miny, maxy, vTiles))
    {
        y = getRandomInt(miny, maxy);
        setTile(x, y, 'o', vTiles);
    }
    if(getBotEnergizerRange(miny, maxy, vTiles))
    {
        y = getRandomInt(miny, maxy);
        setTile(x, y, 'o', vTiles);
    }
 
    x = subcols - 1;
    for(y = 0; y < subrows; y++)
    {
        if(getTile(x, y, vTiles) == '.')
        {
            eraseUntilIntersection(x, y, vTiles);
        }
    }
 
    // erase pellets on starting position
    setTile(1, subrows - 8, ' ', vTiles);
 
    // erase pellets around the ghost house
    for(i = 0; i < 7; i++)
    {
        // erase pellets from bottom of the ghost house proceeding down until
        // reaching a pellet tile that isn't surround by walls
        // on the left and right
        y = subrows - 14;
        setTile(i, y, ' ', vTiles);
        j = 1;
        while(getTile(i, y + j, vTiles) == '.' &&
            getTile(i - 1, y + j, vTiles) == '|' &&
            getTile(i + 1, y + j, vTiles) == '|')
        {
            setTile(i, y + j, ' ', vTiles);
            j++;
        }
 
        // erase pellets from top of the ghost house proceeding up until
        // reaching a pellet tile that isn't surround by walls
        // on the left and right
        y = subrows - 20;
        setTile(i, y, ' ', vTiles);
        j = 1;
        while(getTile(i, y - j, vTiles) == '.' &&
            getTile(i - 1, y - j, vTiles) == '|' &&
            getTile(i + 1, y - j, vTiles) == '|')
        {
            setTile(i, y - j, ' ', vTiles);
            j++;
        }
    }
    // erase pellets on the side of the ghost house
    for(i = 0; i < 7; i++)
    {
        // erase pellets from side of the ghost house proceeding right until
        // reaching a pellet tile that isn't surround by walls
        // on the top and bottom.
        x = 6;
        y = subrows - 14 - i;
        setTile(x, y, ' ', vTiles);
        j = 1;
        while(getTile(x + j, y, vTiles) == '.' &&
            getTile(x + j, y - 1, vTiles) == '|' &&
            getTile(x + j, y + 1, vTiles) == '|')
        {
            setTile(x + j, y, ' ', vTiles);
            j++;
        }
    }
    return 0;
}