Ciao,
in questi giorni mi sto riprendendo dal COVID, quindi niente video per un po’. Detto questo avevo un po’ di codice C++ in giro sviluppato settimane fa e quindi volevo postarlo qui.
Il contesto di riferimento è la generazione di labirinti. Ho scritto un piccolo programma in C++ con le librerie SFML + ImgGui per ottenere il seguente risultato
Nel menu è possibile scegliere il tipo di algoritmo da utilizzare per la generazione del labirinto. Per adesso le opzioni sono due:
stack basedrandom uniform
La stack based è la più interessante in quanto utilizza l’algoritmo di vista dei grafi noto con il nome di Depth First Search (DFS) per ottenere il labirinto finale. Dato che durante la generazione vengono effettuate delle scelte pseudo-randomiche, il risultato finale cambia ad ogni generazione.
È possibile quindi generare il labirinto in modo istantaneo, oppure di vedere una piccola animazione che visualizza il processo di generazione frame by frame. Segue una piccola gif che mostra quando descritto.
È poi possibile “risolvere” il labirinto, il che consiste nel trovare il cammino che collega la sorgente (il punto iniziale) ad una destinazione, che per adesso è hard-codata ad essere il punto più in basso a destra del labirinto. Anche la risoluzione può essere fatta in due modi diversi: se si clicca sulla flag live si può vedere una renderizzazione frame by frame del calcolo del percorso.
L’idea di base di questo tipo di generatori è molto semplice: si rappresenta il labirinto come un grafo, e abbiamo un muro tra due celle adiacenti solo quando queste non sono connesse da nessun arco.
Tramite una visita DFS siamo in grado di visitare le varie celle e durante questo processo di visita è possibile selezionare i muri da costruire.
La visita DFS fa utilizzo di una particolare strutture dati detta stack. Questa è una struttura dati di tipo LIFO (Last-In-First-Out), il che significa che gli elementi vengono tirati fuori nell’ordine inverso da quello di inserzione. Se prima aggiungo X e poi aggiungo Y, allora dopo l’elemento che estrarrò sarà Y, e poi X. Questo comportamento è simmetricalmente opposto a quello di una queue, un’altra struttura dati fondamentale che però lavora in modo FIFO (First-In-First-Out).
Il codice della visita è piuttosto semplice, ed è la parte più interessante, per questo la riporto a seguire
void Maze::initMazeStack() {
// check if this is the first frame we're being called
//
if (init && workingStack.empty()) {
// initialize board for maze generation
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
setAllWalls(y, x);
grid[y][x].state = CellState::NOT_REACHED;
}
}
workingStack.push(getPlayerPos());
}
do {
Cell *c = workingStack.top();
c->state = CellState::VISITED;
std::vector<Wall> directions = getAdjValidDirections(c->y, c->x, false);
if (directions.size() == 0) {
workingStack.pop();
if (init && workingStack.empty()) {
init = false;
return;
}
continue;
}
Wall direction = randomDirection(directions);
Cell *adj = getAdjCell(c->y, c->x, direction);
unsetWall(c->y, c->x, direction);
adj->state = CellState::REACHED;
workingStack.push(adj);
} while (!liveInit && !workingStack.empty());
}
Da notare come la flag liveInit determina se abbiamo una visualizzazione frame by frame, oppure una generazione immediata del labirinto.
E niente, questo è un contesto in cui semplici e utili concetti ripresi dall’informatica più teorica (in particolare la teoria dei grafi, l’utilizzo di strutture dati fondamentali quali stack e queue, e gli algoritmi di visita), sono messi in pratica per ottenere delle divertenti applicazioni.
Segue il codice.
maze-solver.zip (761.3 KB)
Per eseguirlo bisogna scaricare la libreria SFML. Il setup è simile a quello mostrato nel seguente video:
