Esercizio - Navigazione di un robot in un labirinto (laboratorio 8)

In questa pagina 5

Testo.

Discussione (domande di ripasso sui capitoli di template e classi derivate): che cos'è un template? Come si rende astratta una classe? Che cos'è una funzione virtuale e in che cosa differisce da una non virtuale? Che cos'è una classe base? Che cosa rende derivata una classe? In che cosa una funzione virtuale pura differisce dalle altre funzioni virtuali? Che cosa significa overriding?

Esercizio. Programmare un robot che deve trovare l'uscita di un labirinto. Il labirinto è una matrice 9x9 che deve essere letta da file (con fstream; la lettura da file non è stata trattata a lezione). Codifica del file: gli asterischi sono posizioni dove il robot non può andare; E è un'uscita (ce ne possono essere più d'una); S è il punto di partenza (una sola per labirinto). Il robot ha due politiche di movimento:

RandomRobot: movimenti casuali tra le 8 caselle vicine alla posizione corrente;
WavefrontRobot: si muove seguendo il Wavefront Algorithm e deve quindi analizzare il labirinto prima della prima mossa.

Classi: Maze (rappresenta il labirinto, legge da file, fornisce funzioni per la navigazione: da progettare); Robot (implementa la funzione virtuale move che accetta un argomento Maze&, da valutare se const), con le derivate RandomRobot e WavefrontRobot; il main gestisce l'interazione tra robot e labirinto. Servono le operazioni essenziali viste a lezione. Il progetto va diviso in più file, con le include guard. L'interfaccia tra Robot e Maze è solo parzialmente specificata: si può definire a piacere. Domanda del testo: la funzione move di Robot deve essere virtuale pura?

Teoria: C++ - ereditarietà, funzioni virtuali e layout degli oggetti, C++ - polimorfismo, C++ - buona interfaccia e progetti su più file, STL - sequenze, iteratori e container (vector, list, string).

Esempi di labirinto del testo (i file maze1.txt e maze2.txt):

lab8/maze1.txt

*E*******
*       *
*   *** *
* * *   *
* * *** *
*   *   *
**  S * *
*       *
*********

lab8/maze2.txt

*E*******
*       *
*   *****
*   *   *
*   *****
*       *
**  S   *
*       *
*********

Discussione: le sette risposte

Template. Un modello di classe o di funzione parametrizzato su uno o più tipi (o valori): il compilatore genera la versione per i tipi usati (polimorfismo statico, C++ - template e programmazione generica).
Classe astratta. Dichiarando almeno una funzione membro virtuale pura (virtual void f() = 0;); in alternativa mettendo protetti i costruttori. Non si possono creare oggetti di una classe astratta.
Virtuale e non virtuale. Per una funzione virtuale la versione eseguita è scelta a run-time in base al tipo dell'oggetto (tramite puntatore o riferimento alla base); per una non virtuale è scelta a compile-time in base al tipo del puntatore o riferimento.
Classe base. La classe da cui altre ereditano membri e interfaccia comune.
Classe derivata. Quella dichiarata con : public Base (class RandomRobot : public Robot): eredita i membri della base e può ridefinirne le virtuali; è una specializzazione ("is a").
Virtuale pura. È dichiarata con = 0 e di norma non ha implementazione nella base; rende la classe astratta e obbliga le derivate a ridefinirla. Le altre virtuali hanno un comportamento predefinito che le derivate possono (non devono) cambiare.
Overriding. La ridefinizione, nella derivata, di una virtuale della base con stessa firma (nome, tipi dei parametri, const); la parola chiave override fa controllare l'intenzione al compilatore.

1. Progetto delle classi

Chi sa che cosa

classe	responsabilità	tiene
`Maze`	sapere com'è fatto il labirinto: lettura da file, controlli, "la cella è libera?", "è un'uscita?", partenza, elenco delle uscite	la griglia, la partenza, le uscite
`Robot` (astratta)	interfaccia comune: fare una mossa, dire dove si trova e quante mosse ha fatto	posizione e contatore
`RandomRobot`	politica casuale	il generatore pseudocasuale
`WavefrontRobot`	politica Wavefront	la mappa delle distanze
`main`	far interagire robot e labirinto: caricare, far muovere finché si è su un'uscita	niente

Il labirinto non conosce i robot e i robot non modificano il labirinto: la dipendenza va in una sola direzione.

`move` è virtuale pura? e `Maze&` è `const`?

Sì, virtuale pura: un robot "generico" non ha nessuna politica di movimento sensata, quindi Robot::move non ha un'implementazione di default da offrire. Dichiararla pura rende Robot astratta (non si può creare un Robot senza politica) e obbliga ogni derivata a scegliere come muoversi. Funziona anche come interfaccia: per aggiungere un nuovo tipo di robot basta derivare e fare override.
const Maze&: il robot legge il labirinto ma non lo cambia. Un parametro const lo dichiara nell'interfaccia e il compilatore lo garantisce; permette anche di passare un labirinto const. Un Maze& non const sarebbe una licenza a modificare i muri.

Operazioni essenziali

Robot è la base di una gerarchia: copia e assegnamento sono = delete (si evita lo slicing: C++ - ereditarietà, funzioni virtuali e layout degli oggetti) e il distruttore è virtuale, perché i robot si usano e si distruggono tramite Robot* (qui dentro uno unique_ptr<Robot>).
Maze possiede solo vector e string: le operazioni generate dal compilatore sono corrette (regola dello zero), non serve scriverne nessuna.
RandomRobot e WavefrontRobot non hanno risorse proprie da gestire: distruttore, copia e spostamento restano quelli impliciti (la copia è comunque disabilitata dalla base).

Come si legge da file: attenzione agli spazi

Il testo suggerisce fstream e l'operatore >>. Nel labirinto però gli spazi sono i passaggi, e operator>> salta gli spazi bianchi:

lab8_trappola/lettura.cppcpp

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main()
{
    // la stessa sorgente di testo si legge come un file: una riga di labirinto "*  *"
    string riga = "*  *\n*E *\n";

    istringstream a{riga};
    char c1, c2, c3;
    a >> c1 >> c2 >> c3;                               // operator>> SALTA gli spazi bianchi
    cout << "con >>:      '" << c1 << "' '" << c2 << "' '" << c3 << "'\n";   // legge * * * : spazi e a capo spariti

    istringstream b{riga};
    string l1, l2;
    getline(b, l1);                                    // getline legge la riga intera, spazi compresi
    getline(b, l2);
    cout << "con getline: '" << l1 << "' (" << l1.size() << " caratteri), '" << l2 << "'\n";

    istringstream c{riga};
    c >> noskipws >> c1 >> c2 >> c3;                   // alternativa: non saltare gli spazi
    cout << "noskipws:    '" << c1 << "' '" << c2 << "' '" << c3 << "'\n";
}

Uscita eseguita:

con >>:      '*' '*' '*'
con getline: '*  *' (4 caratteri), '*E *'
noskipws:    '*' ' ' ' '

Con >> i tre char letti sono *, *, *: gli spazi e il fine riga sono spariti e la riga * * diventa **. Con getline si ottiene la riga intera. Per questo Maze::read usa std::getline. (Alternativa: >> noskipws.)

Separare la lettura dalla sorgente

Maze::read(std::istream&) legge e controlla da un flusso qualsiasi; Maze::load(nome) si limita ad aprire il file e a chiamare read. Si guadagna la possibilità di provare read con uno istringstream o con la standard input, e un file maze_file.cpp minuscolo. Nel main il nome - significa "leggi dalla standard input" (./robot - 7 < maze1.txt).

Il controllo dei dati (nove righe di nove caratteri, solo *, spazio, E, S, una sola S, almeno una E) avviene prima di modificare l'oggetto: se qualcosa non va, read restituisce false con un messaggio e Maze resta com'era. Gli errori sono restituiti come valore (non eccezioni) perché è il modo più semplice in un main che deve solo stampare un messaggio e uscire.

Il Wavefront in breve

Il wavefront è una visita in ampiezza dalle uscite: le uscite hanno distanza 0; ogni cella libera confinante con una di distanza d (sui quattro lati) riceve d+1; si procede finché ci sono celle da raggiungere. Alla fine ogni cella ha la distanza minima da un'uscita (o -1 se non è raggiungibile). Il robot, a ogni mossa, passa alla cella vicina con distanza uno in meno: segue il gradiente e raggiunge l'uscita più vicina nel numero minimo di mosse. È l'analisi richiesta prima della prima mossa: il codice la fa nella prima chiamata a move.

Scelte di progetto:

il RandomRobot si muove tra le otto caselle vicine (incluse le diagonali, come chiede il testo) e, se la casella scelta è un muro o fuori dalla griglia, resta fermo (la mossa è sprecata ma conta);
il WavefrontRobot usa i quattro lati, come l'algoritmo originale (con le diagonali un robot passerebbe tra due muri che si toccano per un angolo);
il generatore è std::mt19937 con seme esplicito: le prove sono ripetibili; e rng_() % 8 non introduce distorsione perché 8 divide $2^{32}$ , quindi non serve una uniform_int_distribution (la cui implementazione varia da compilatore a compilatore).

2. Il codice

La struttura del progetto:

robot/
├── include/  maze.h  robot.h  random_robot.h  wavefront_robot.h
└── src/      maze.cpp  maze_file.cpp  random_robot.cpp  wavefront_robot.cpp  main.cpp

lab8/include/maze.hcpp

#ifndef MAZE_H
#define MAZE_H

#include <iosfwd>
#include <string>
#include <vector>

struct Position {
    int row;
    int col;
};
bool operator==(const Position& a, const Position& b);

// Labirinto kSize x kSize letto da file di testo.
// Codifica: '*' parete, ' ' passaggio, 'E' uscita (anche piu' di una), 'S' partenza (una sola).
// Invariante (dopo un load riuscito): griglia kSize x kSize, una sola 'S', almeno una 'E'.
class Maze {
public:
    static constexpr int kSize = 9;
    static constexpr char kWall = '*';
    static constexpr char kExit = 'E';
    static constexpr char kStart = 'S';

    Maze();                                                   // labirinto vuoto (non caricato)
    // legge e controlla il labirinto da un flusso qualsiasi; false + messaggio se non va bene
    bool read(std::istream& in, std::string& error);
    // apre il file e chiama read (definita a parte, in maze_file.cpp)
    bool load(const std::string& filename, std::string& error);

    bool loaded() const { return !grid_.empty(); }
    int rows() const { return kSize; }
    int cols() const { return kSize; }
    bool is_inside(Position p) const;
    bool is_free(Position p) const;                           // dentro la griglia e non parete
    bool is_exit(Position p) const;
    Position start() const { return start_; }
    const std::vector<Position>& exits() const { return exits_; }
    void print(std::ostream& os, Position robot) const;       // disegna il labirinto con il robot 'R'

private:
    std::vector<std::string> grid_;
    Position start_;
    std::vector<Position> exits_;
};

#endif // MAZE_H

lab8/src/maze.cppcpp

#include "maze.h"
#include <istream>
#include <ostream>

bool operator==(const Position& a, const Position& b)
{
    return a.row == b.row && a.col == b.col;
}

Maze::Maze() : grid_{}, start_{-1, -1}, exits_{} {}

bool Maze::read(std::istream& in, std::string& error)
{
    std::vector<std::string> grid;
    std::string line;
    while (static_cast<int>(grid.size()) < kSize && std::getline(in, line)) {
        if (!line.empty() && line.back() == '\r') line.pop_back();    // file creati su Windows
        grid.push_back(line);
    }
    // NOTA: si legge con getline e NON con operator>>, perche' >> salta gli spazi
    // e gli spazi sono i passaggi del labirinto.
    if (static_cast<int>(grid.size()) != kSize) {
        error = "servono " + std::to_string(kSize) + " righe, trovate " + std::to_string(grid.size());
        return false;
    }

    int starts = 0;
    std::vector<Position> exits;
    Position start{-1, -1};
    for (int r = 0; r < kSize; ++r) {
        if (static_cast<int>(grid[r].size()) != kSize) {
            error = "la riga " + std::to_string(r + 1) + " non ha " + std::to_string(kSize) + " caratteri";
            return false;
        }
        for (int c = 0; c < kSize; ++c) {
            char ch = grid[r][c];
            if (ch == kStart) { ++starts; start = Position{r, c}; }
            else if (ch == kExit) exits.push_back(Position{r, c});
            else if (ch != kWall && ch != ' ') {
                error = std::string("carattere non valido '") + ch + "' alla riga " + std::to_string(r + 1);
                return false;
            }
        }
    }
    if (starts != 1) { error = "deve esserci una sola 'S'"; return false; }
    if (exits.empty()) { error = "serve almeno una 'E'"; return false; }

    grid_ = grid;                                     // solo ora, a controlli superati, si modifica l'oggetto
    start_ = start;
    exits_ = exits;
    return true;
}

bool Maze::is_inside(Position p) const
{
    return p.row >= 0 && p.row < kSize && p.col >= 0 && p.col < kSize;
}

bool Maze::is_free(Position p) const
{
    return loaded() && is_inside(p) && grid_[p.row][p.col] != kWall;
}

bool Maze::is_exit(Position p) const
{
    return loaded() && is_inside(p) && grid_[p.row][p.col] == kExit;
}

void Maze::print(std::ostream& os, Position robot) const
{
    for (int r = 0; r < kSize; ++r) {
        for (int c = 0; c < kSize; ++c)
            os << (Position{r, c} == robot ? 'R' : (grid_[r][c] == kStart ? ' ' : grid_[r][c]));
        os << '\n';
    }
}

lab8/src/maze_file.cppcpp

#include <fstream>
#include "maze.h"

bool Maze::load(const std::string& filename, std::string& error)
{
    std::ifstream in{filename};                       // modalita' testuale (non binaria)
    if (!in) {
        error = "impossibile aprire il file " + filename;
        return false;
    }
    return read(in, error);
}

lab8/include/robot.hcpp

#ifndef ROBOT_H
#define ROBOT_H

#include <string>
#include "maze.h"

// Classe base astratta: stabilisce l'interfaccia comune a tutte le politiche di movimento.
class Robot {
public:
    explicit Robot(Position start) : pos_{start}, steps_{0} {}
    virtual ~Robot() {}                                  // distruttore virtuale: si usa tramite Robot*

    Robot(const Robot&) = delete;                        // classe di una gerarchia: niente copia (slicing)
    Robot& operator=(const Robot&) = delete;

    // Fa UNA mossa nel labirinto. Maze e' const: il robot lo legge ma non lo modifica.
    // Pura: un robot "generico" non sa come muoversi, quindi Robot e' astratta.
    virtual void move(const Maze& maze) = 0;
    virtual std::string name() const = 0;

    Position position() const { return pos_; }
    int steps() const { return steps_; }                 // mosse tentate

protected:
    void set_position(Position p) { pos_ = p; }
    void count_step() { ++steps_; }

private:
    Position pos_;
    int steps_;
};

#endif // ROBOT_H

lab8/include/random_robot.hcpp

#ifndef RANDOM_ROBOT_H
#define RANDOM_ROBOT_H

#include <random>
#include "robot.h"

// Si muove a caso tra le 8 caselle vicine; se la casella scelta e' una parete (o fuori) resta ferma.
class RandomRobot : public Robot {
public:
    RandomRobot(Position start, unsigned seed);
    void move(const Maze& maze) override;
    std::string name() const override { return "RandomRobot"; }

private:
    std::mt19937 rng_;                                   // generatore pseudocasuale con seme esplicito
};

#endif // RANDOM_ROBOT_H

lab8/src/random_robot.cppcpp

#include "random_robot.h"

namespace {
// le 8 direzioni: 4 lati e 4 diagonali (riga, colonna)
const int kDirections[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
}

RandomRobot::RandomRobot(Position start, unsigned seed) : Robot{start}, rng_{seed} {}

void RandomRobot::move(const Maze& maze)
{
    count_step();
    // rng_() ha 32 bit e 8 divide 2^32: il resto e' uniforme, senza bisogno di una distribuzione
    const int* d = kDirections[rng_() % 8];
    Position next{position().row + d[0], position().col + d[1]};
    if (maze.is_free(next)) set_position(next);          // altrimenti la mossa e' sprecata
}

lab8/include/wavefront_robot.hcpp

#ifndef WAVEFRONT_ROBOT_H
#define WAVEFRONT_ROBOT_H

#include <iosfwd>
#include <vector>
#include "robot.h"

// Wavefront: prima di muoversi analizza il labirinto assegnando a ogni cella la distanza (in mosse
// sui 4 lati) dall'uscita piu' vicina; poi a ogni mossa va nella cella vicina con distanza minore.
class WavefrontRobot : public Robot {
public:
    explicit WavefrontRobot(Position start) : Robot{start}, dist_{} {}
    void move(const Maze& maze) override;
    std::string name() const override { return "WavefrontRobot"; }

    bool analyzed() const { return !dist_.empty(); }
    int distance(Position p) const;                      // -1 se muro o non raggiungibile
    void print_wave(std::ostream& os) const;             // distanze (cifra delle unita'), per capire l'onda

private:
    void analyze(const Maze& maze);                      // la "onda": visita in ampiezza dalle uscite
    int rows_ = 0;
    int cols_ = 0;
    std::vector<int> dist_;                              // rows_ * cols_ valori, -1 = non visitata
};

#endif // WAVEFRONT_ROBOT_H

lab8/src/wavefront_robot.cppcpp

#include "wavefront_robot.h"
#include <ostream>
#include <queue>

namespace {
const int kSides[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};     // su, giu', sinistra, destra
}

int WavefrontRobot::distance(Position p) const
{
    if (!analyzed() || p.row < 0 || p.row >= rows_ || p.col < 0 || p.col >= cols_) return -1;
    return dist_[p.row * cols_ + p.col];
}

void WavefrontRobot::analyze(const Maze& maze)
{
    rows_ = maze.rows();
    cols_ = maze.cols();
    dist_.assign(rows_ * cols_, -1);

    std::queue<Position> frontier;                       // il "fronte d'onda"
    for (Position e : maze.exits()) {                    // tutte le uscite partono da distanza 0
        dist_[e.row * cols_ + e.col] = 0;
        frontier.push(e);
    }
    while (!frontier.empty()) {
        Position p = frontier.front();
        frontier.pop();
        int d = dist_[p.row * cols_ + p.col];
        for (const int* s : kSides) {
            Position n{p.row + s[0], p.col + s[1]};
            if (maze.is_free(n) && dist_[n.row * cols_ + n.col] == -1) {
                dist_[n.row * cols_ + n.col] = d + 1;    // l'onda avanza di un passo
                frontier.push(n);
            }
        }
    }
}

void WavefrontRobot::move(const Maze& maze)
{
    if (!analyzed()) analyze(maze);                      // l'analisi precede la prima mossa
    count_step();
    int here = distance(position());
    if (here <= 0) return;                               // sull'uscita (0) oppure intrappolato (-1)
    for (const int* s : kSides) {
        Position n{position().row + s[0], position().col + s[1]};
        if (distance(n) == here - 1) {                   // la cella vicina un passo piu' vicina all'uscita
            set_position(n);
            return;
        }
    }
}

void WavefrontRobot::print_wave(std::ostream& os) const
{
    for (int r = 0; r < rows_; ++r) {
        for (int c = 0; c < cols_; ++c) {
            int d = dist_[r * cols_ + c];
            os << (d < 0 ? '*' : static_cast<char>('0' + d % 10));
        }
        os << '\n';
    }
}

lab8/src/main.cppcpp

#include <cstdlib>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include "maze.h"
#include "random_robot.h"
#include "wavefront_robot.h"

namespace {
constexpr int kMaxSteps = 100000;                        // tetto: il robot casuale potrebbe non arrivare mai

// Fa muovere il robot finche' non e' su un'uscita; restituisce true se l'ha raggiunta.
bool run(Robot& robot, const Maze& maze)
{
    while (!maze.is_exit(robot.position())) {
        if (robot.steps() >= kMaxSteps) return false;
        robot.move(maze);                                // chiamata VIRTUALE: dipende dal tipo effettivo
    }
    return true;
}
}

int main(int argc, char** argv)
{
    if (argc < 2 || argc > 3) {
        std::cerr << "uso: " << argv[0] << " labirinto.txt [seme]\n";
        return 1;
    }
    unsigned seed = argc == 3 ? static_cast<unsigned>(std::strtoul(argv[2], nullptr, 10)) : 12345u;

    Maze maze;
    std::string error;
    bool ok = std::string{argv[1]} == "-" ? maze.read(std::cin, error)      // "-" = standard input
                                          : maze.load(argv[1], error);
    if (!ok) {
        std::cerr << "labirinto non valido: " << error << '\n';
        return 1;
    }
    std::cout << "Labirinto " << argv[1] << ", partenza (" << maze.start().row << ',' << maze.start().col << "):\n";
    maze.print(std::cout, maze.start());

    // una collezione di robot di tipo diverso, gestiti tramite la classe base
    std::vector<std::unique_ptr<Robot>> robots;
    robots.push_back(std::unique_ptr<Robot>(new RandomRobot{maze.start(), seed}));
    robots.push_back(std::unique_ptr<Robot>(new WavefrontRobot{maze.start()}));

    for (auto& r : robots) {
        bool found = run(*r, maze);
        std::cout << r->name() << ": " << (found ? "uscita raggiunta in (" : "NON ha trovato l'uscita, ferma in (")
                  << r->position().row << ',' << r->position().col << ") dopo " << r->steps() << " mosse\n";
    }

    // la dynamic_cast serve solo per mostrare l'analisi del Wavefront
    if (const WavefrontRobot* w = dynamic_cast<const WavefrontRobot*>(robots[1].get())) {
        std::cout << "Distanze calcolate dal WavefrontRobot (cifra delle unita'):\n";
        w->print_wave(std::cout);
    }
    return 0;
}

Punti da notare:

Il main tiene i robot in un vector<unique_ptr<Robot>> e chiama robot.move(maze) attraverso la classe base: è polimorfismo dinamico (la run accetta un Robot& e non sa quale politica si usa).
kMaxSteps impedisce un ciclo infinito: il robot casuale non ha garanzie di arrivare, e un WavefrontRobot chiuso in una zona senza uscite resta fermo (distanza -1).
La dynamic_cast nel main serve solo a stampare la mappa delle distanze (una funzione che esiste solo nella derivata): è uno dei casi in cui il downcasting si giustifica (C++ - polimorfismo).
Maze::kSize e i caratteri speciali sono costanti con nome (nessun magic number).
Compilazione (GNU): g++ -std=c++17 -Wall -Wextra -Iinclude src/*.cpp -o robot; esecuzione: ./robot maze1.txt 7.

3. Prova

Compilato per Linux con -Wall -Wextra senza avvisi. Eseguito in WebAssembly, che non ha <fstream>: il labirinto è stato passato dalla standard input (-) e maze_file.cpp è stato sostituito da una funzione che fallisce; la lettura da file vera è l'unica parte non eseguita. Con seme 7:

Labirinto -, partenza (6,4):
*E*******
*       *
*   *** *
* * *   *
* * *** *
*   *   *
**  R * *
*       *
*********
RandomRobot: uscita raggiunta in (0,1) dopo 116 mosse
WavefrontRobot: uscita raggiunta in (0,1) dopo 9 mosse
Distanze calcolate dal WavefrontRobot (cifra delle unita'):
*0*******
*1234567*
*234***8*
*3*5*109*
*4*6***0*
*567*121*
**7890*2*
*9890123*
*********

(R è il robot sulla partenza.) Il WavefrontRobot impiega 9 mosse: la distanza della partenza è la cifra in riga 6, colonna 4, cioè 9 (le distanze sono scritte modulo 10: la cifra 0 accanto è 10). Il RandomRobot impiega 116 mosse con questo seme. Sul secondo labirinto: RandomRobot 301 mosse (stesso seme), WavefrontRobot 9 mosse, con la mappa

*0*******
*1234567*
*234*****
*345*****
*456*****
*5678901*
**789012*
*9890123*
*********

Il numero di mosse del robot casuale cambia con il seme (e quindi non va confrontato tra esecuzioni diverse), quello del Wavefront no: è la lunghezza del cammino minimo.

Errori da evitare

Leggere il labirinto con >>: gli spazi spariscono (vedi sopra).
move non pura con un corpo vuoto: un Robot istanziabile che non fa niente nasconde i bug.
Dimenticare il distruttore virtuale in Robot: delete di un Robot* non distruggerebbe la parte derivata.
Maze& non const in move.
Includere i .cpp, header senza include guard, main dentro un header.
Numeri magici (9, 8, caratteri '*' sparsi).
Usare rand() senza seme controllabile o time come unico seme in una prova che si vuole ripetere.
Scelta della cella nel Wavefront sbagliata: scegliere la cella con distanza minore o uguale (può restare in cicli) invece che esattamente d-1.

Versione ripasso

Testo: robot in un labirinto 9x9 letto da file (* muro, spazio libero, E uscite, S partenza unica); RandomRobot (8 caselle vicine a caso) e WavefrontRobot (analisi prima della prima mossa). Classi Maze, Robot (virtuale move(Maze&)), le due derivate, main; più file con include guard. Teoria: C++ - ereditarietà, funzioni virtuali e layout degli oggetti, C++ - polimorfismo.
Discussione: template = modello parametrizzato sui tipi; classe astratta = almeno una virtuale pura (o costruttori protected); virtuale = scelta a run-time sul tipo dell'oggetto; base/derivata = : public Base; virtuale pura (= 0) obbliga le derivate; overriding = ridefinizione con stessa firma (override).
Progetto: Maze sa com'è il labirinto (griglia, partenza, uscite, is_free, is_exit); Robot astratta con virtual void move(const Maze&) = 0 (pura: nessuna politica generica; const: il robot legge, non modifica), distruttore virtuale, copia = delete; Maze con regola dello zero.
Lettura: operator>> salta gli spazi ("* *" diventa **): si usa std::getline. Maze::read(std::istream&) controlla (9 righe da 9, solo * ESE, una S, almeno una E) prima di modificare l'oggetto, Maze::load(nome) apre il file e chiama read.
RandomRobot: std::mt19937 con seme, rng_() % 8 (8 divide 2^32: nessuna distorsione), se la cella è muro resta ferma.
WavefrontRobot: visita in ampiezza dalle uscite (distanza 0, vicini a d+1, quattro lati); ogni mossa va nella cella vicina con distanza d-1; -1 = non raggiungibile.