FIT ČVUT Course Pages
BI-ZUM — Základy umělé inteligence
Jdi na navigaci předmětu

Tutorial "Hraduch v bludišti"

Autor: Mgr. Ing. Ladislava Smítková Janků, Ph.D.

V tomto tutorialu budeme implementovat zobrazení pohybu hradního ducha (zkráceně hraducha :-)) v bludišti. Je zde popsán postup, jak implementovat grafické zobrazení bludiště a zobrazení agenta, který reaguje na pokyny z klávesnice a pohybuje se v bludišti pole toho, jak uživatel mačká klávesy šipek. V bludišti je označena počáteční poloha agenta (Start). Dále je označena cílová poloha (End), která však konkrétně v tomto tutorialu není významná (využijeme jí v dalších tutorialech).

bludiste

Zadání

Načtěte bludiště ze souboru a vykreslete ho v okně programu s využitím Qt. Do bludiště umístěte agenta a implementujte jeho pohyb pomocí šipek na klávesnici (= čtěte vstup z klávesnice a zohledněte ve vykreslování změnu polohy v závislosti na vstupu z klávesnice).

Prerekvizity

  • Nainstalované knihovny Qt
  • Nainstalované vývojové prostředí QtCreator
  • funkční překladač gcc a g++

Formát bludiště a souřadnicový systém (= jak je bludiště zadáno v souboru a jak uvádíme souřadnice x,y)

  • Soubor s bludištěm je tvořen řádky obsahujícmi znaky: X (= stěna), 'mezera'(= volné pole, na které může vstoupit agent), S (= Start, agent může vstoupit na S), E (= End, agent může vstoupit na E).
  • Řádky v souboru jsou zakončeny znakem konce řádky, typicky \n. Předokládáme bludiště ve tvaru obdélníku, takže všechny řádky musí být stejně dlouhé.
  • Počátek souřadného systému je vlevo nahoře, kde je bode se souřadnicemi 0,0.
  • Osa x směřuje zleva doprava.
  • Osa y směřuje shora dolů.
  • Rozměr bludiště v ose y tedy odpovídá POČTU ŘÁDKů v souboru.
  • Rozměr bludiště v ose x odpovídá DÉLCE (každého) ŘÁDKU v souboru.

Příklad textového souboru s bludištěm a odpovídající vykreslený grafický výstup:

zum bludiste

Architektura programu

V programu musíme:

  • vyřešit načtení bludiště ze souboru do vhodné datové struktury,
  • vyřešit zobrazení bludiště z datové struktury do okna programu,
  • vyřešit vnitřní reprezentaci agenta a zobrazení agenta v okně programu,
  • vyřešit obsluhu klávesnice a odpovídající reakci na vstup.

Vnitřní datová reprezentace bludiště

Bludiště může být vnitřně uchováváno různými způsoby. V tomto příkladu budeme bludiště uchovávat ve formě dvourozměrného pole znaků, přesněji jako pole, kde každým prvkem pole je string (řetězec).

Bludiště je uchováváno v proměnné bludisteStr

QStringList bludisteStr;    // seznam řádek (stringů) s bludištěm

kde QStringList je seznam stringů v prostředí Qt. V čistém C++ by se toto napsalo jako:

vector<string> bludisteStr;

V jazyce C by se to napsalo takto:

char*(*bludisteStr)[];

Dále budeme potřebovat proměnné, ve kterých budou uchovávány rozměry bludiště, souřadnice startu a souřadnice cíle.

int X, Y;                   // rozměry bludiště
int Sx, Sy;                 // souřadnice startu
int Ex, Ey;                 // souřadnice cíle

Dále zavedeme proměnnou image, ve které je uchováván obrázek s bludištěm. K jeho sestavení slouží privátní metody s prefixem draw_.

QImage *image;              // generovaný obrázek

V C++ implementujeme třídu popisující celé bludiště.

#include <QtCore>
#include <QPainter>

#define PSIZE   40    // velikost jednoho místa v bludišti v pixelech

class TBludiste
{
public:
    TBludiste( QString fileName);
    int getX() const;
    int getY() const;
    int getSx() const;
    int getSy() const;
    int getEx() const;
    int getEy() const;
    const QImage *getImage() const;
    bool wall( int x, int y) const;

private:
    int X, Y;                   // rozměry bludiště
    int Sx, Sy;                 // souřadnice startu
    int Ex, Ey;                 // souřadnice cíle

    QStringList bludisteStr;    // seznam řádek (stringů) s bludištěm
    QImage *image;              // generovaný obrázek

    void draw_pixel( QByteArray &bytes, int index, int r, int g, int b);
    void draw_wall( QByteArray &bytes, int x, int y);
    void draw_space( QByteArray &bytes, int x, int y);
    void draw_start( QPainter &p);
    void draw_end( QPainter &p);
    void draw_text( QPainter &p, int x, int y, QString text);
    void draw_node( QPainter &p, int x, int y);
};

Všechny proměnné ponecháme jako privátní. To zajistí, že přístup k nim zvenku (mimo tuto třídu) bude pouze pro čtení. Tent způsob zavedení proměnných snižuje riziko vzniku nechtěných chyb.

Public metody pro čtení hodnot privátních proměnných

Metody, které vrací rozměry bludiště X, Y, souřadnice Sx, Sy a Ex, Ey:

int getX() const;
int getY() const;
int getSx() const;
int getSy() const;
int getEx() const;
int getEy() const;

Metoda, která vrací vygenerovaný obrázek:

const QImage *getImage() const;

Komentář ke klíčovým slovům const: První const předchází nechtěnému poškození obsahu obrázku zvnějšku třídy. Uživatel tedy může nakládat s obrázkem pouze v režimu read-only. Druhý const informuje, že metodu je bezpečné volat kdykoliv bez hrozby modifikace vnitřních proměnných. Ani jeden const v tomto příkladu vlastně není vyloženě nutný, jedná se však o zavedený způsob prevence proti chybám programátora.

Metoda, která vrací informaci, zda se na daném poli nachází zeď:

bool wall( int x, int y) const;

Konstruktoru se budeme věnovat v kapitole "Načtení bludiště ze souboru".

Načtení bludiště ze souboru a vykreslení bludiště (popis konstruktoru)

Nejprve si stanovíme, co všechno bude konstruktor třídy TBludiste zajišťovat:

  • načtení bludiště ze souboru do proměnné bludisteStr
  • uložení rozměrů bludiště do proměnných X, Y
  • kontrolu, že jsou všechny řádky stejně dlouhé a obsahují pouze povolené znaky
  • kontrolu, že v bludišti je pouze jeden Start a pouze jeden cíl (End)
  • uložení souřadnic Startu do proměnných Sx, Sy
  • uložení souřadnic cíle (End) do proměnných Ex, Ey
  • vygenerování obrázku s bludištěm (background).

Při vytváření objektu se volá konstruktor s parametrem fileName. Parametr fileName obsahuje název souboru s bludištěm. V tomto příkladu pro jednoduchost není implementován destruktor třídy TBludiste.

Teď si postupně projdeme jednotlivé body.

Načtení bludiště ze souboru do proměnné bludisteStr

Otevře se soubor a načtou se postupně všechny řádky do seznamu řádků v proměnné bludisteStr.

 QFile textFile( fileName);
    if (!textFile.open( QIODevice::ReadOnly))
        throw QString("Soubor s bludištěm nelze otevřít.");

    // bludiště se načte do seznamu stringů
    QTextStream textStream(&textFile);
    while (true)
    {
        // načtení řádky ze souboru
        QString line = textStream.readLine();

        if (line.isNull()) break;
        bludisteStr.append( line);
    }
Načtení rozměrů bludiště
// načtení rozměrů bludiště
    Y = bludisteStr.count();
    if (Y == 0)
        throw QString("Soubor s bludištěm je prázdný.");

    X = bludisteStr[0].length();
    if (X == 0)
        throw QString("Bludiště je prázdné.");
Kontrola, že jsou všechny řádky stejně dlouhé a obsahují pouze povolené znaky
// kontrola bludiště
    for (auto &l: bludisteStr) {
        if (l.length() != X)
            throw QString("Všechny řádky bludiště musí být stejně dlouhé.");
        for (auto &c: l) {

            if ((c != ' ') && (c != 'X') && (c != 'E') && (c != 'S'))
                throw QString("V bludišti se vyskytuje neznámý znak '%1'.").arg(c);
        }
    }
Kontrola, že v bludišti je pouze jeden Start a pouze jeden cíl (End)

Kontrolu provedeme tak, že spojíme všechny řádky bludiště do jednoho řetězce (stringu) a zkontrolujeme, že je v tomto řetězci právě jeden znak označující Start a právě jeden znak označující cíl (End).

Pro tuto kontrolu využijeme regulární výrazy.

QString spojeno = bludisteStr.join("");

    // kontrola, zda je start a cíl jen jeden
    QRegExp rS("^[ XE]*S[ XE]*$");
    if (rS.indexIn( spojeno) < 0)
        throw QString("V bludišti je více míst označených jako start.");
    QRegExp rE("^[ XS]*E[ XS]*$");
    if (rE.indexIn( spojeno) < 0)
        throw QString("V bludišti je více míst označených jako konec.");
Uložení souřadnic Startu do proměnných Sx, Sy

Souřadnici Sy vypočteme jako pozici znaku 'S' v řetězci spojeno, který obsahuje všechny řádky bludiště spojené do jednoho řetězce. Pokud tuto pozici vydělíme šířkou bludiště, dostaneme číslo řádku, kde se Start nachází, tedy souřadnici Sy. Zbytek po tomto dělení bude představovat hodnotu souřadnice x, tedy Sx.

    Sx = spojeno.indexOf('S');
    Sy = Sx / X;
    Sx = Sx % X;
Uložení souřadnic cíle (End) do proměnných Ex, Ey

Stejným způsobem jako v předchozím kroku vypočteme i hodnoty Ex a Ey.

    Ex = spojeno.indexOf('E');
    Ey = Ex / X;
    Ex = Ex % X;
Vygenerování obrázku

Obrázek bludiště bude uchováván v proměnné image, která je typu QImage. Abychom však vytvořili instanci třídy QImage, musíme mít nejdříve vytvořenou mapu pixelů tohoto obrázku. Pro obrázek zvolíme formát RGB s osmibitovou hloubkou barvy. Barva každého pixelu tedy bude definována trojicí bytů R, G a B. Mapa pixelů obsahuje trojice RGB pro všechny pixely obrázku, a to postupně po řádcích od levého horního rohu až po poslední pixel vpravo dole. Mapa pixelů je tedy velká X*Y*3 bytů.

Jednotlivá místa v bludišti však nemůžeme zobrazit jako jeden pixel - uživatel by nic neviděl. Je třeba zvolit velikost místa v bludišti (v pixelech). Tato velikost bude uložena v konstantě PSIZE (konstanta již byla definována u definice třídy TBludiste - viz výše). Nyní bude tedy mít každé místo v bludišti velikost PSIZE krát PSIZE pixelů. Mapa pixelů obrázku s bludištěm bude tedy zabírat v paměti velikost PSIZE*X*PSIZE*Y*3 bytů.

Pro mapování souřadnic bludiště do mapy pixelů můžeme nadefinovat následující makro:

#define BITMAPINDEX(x,y)    (((x)*PSIZE)*((y)*PSIZE)*3)     // mapování souřadnic bludiště do pixelů obrázku

Mapu pixelů vytvoříme voláním kontruktoru QByteArray(n,c), který vytvoří pole n znaků s hodnotou c:

    QByteArray bytes( BITMAPINDEX(X,Y), 0xaa);

Zde byla mapa vyplněna hodnotou 0xaa, což vede na šedivou plochu. Všechna místa budou později přepsána, takže tato barva by se v obrázku ve finále neměla vyskytovat. Můžeme začít hned teď, projdeme všechny řádky a na zadané místo v mapě pixelů vymalujeme zeď nebo prostor:

for (int y=0; y<Y; y++) {
        for (int x=0; x<X; x++) {
            if (bludisteStr[y][x] == 'X') draw_wall( bytes, x, y);
            else draw_space( bytes, x, y);
        }
    }

Nyní můžeme vytvořit objekt třídy QImage na základě naší mapy pixelů. Poté ještě do obrázku označíme start a cíl.

    image = new QImage( (const uchar*) bytes.constData(),
                                X*PSIZE, Y*PSIZE, X*PSIZE*3, QImage::Format_RGB888);

    QPainter p;
    if (!p.begin( image))
        throw QString("QPainter init error.");

    // ještě označení startu a cíle
    draw_start(p);
    draw_end(p);

    p.end();

Celý konstruktor pak bude vypadat takto:

#define BITMAPINDEX(x,y)    (((x)*PSIZE)*((y)*PSIZE)*3)     // mapování souřadnic bludiště do pixelů obrázku

TBludiste::TBludiste( QString fileName)
{
    QFile textFile( fileName);
    if (!textFile.open( QIODevice::ReadOnly))
        throw QString("Soubor s bludištěm nelze otevřít.");

    // bludiště se načte do seznamu stringů
    QTextStream textStream(&textFile);
    while (true)
    {
        // načtení řádky ze souboru
        QString line = textStream.readLine();

        if (line.isNull()) break;
        bludisteStr.append( line);
    }

    // načtení rozměrů bludiště
    Y = bludisteStr.count();
    if (Y == 0)
        throw QString("Soubor s bludištěm je prázdný.");

    X = bludisteStr[0].length();
    if (X == 0)
        throw QString("Bludiště je prázdné.");

    // kontrola bludiště
    for (auto &l: bludisteStr) {
        if (l.length() != X)
            throw QString("Všechny řádky bludiště musí být stejně dlouhé.");
        for (auto &c: l) {

            if ((c != ' ') && (c != 'X') && (c != 'E') && (c != 'S'))
                throw QString("V bludišti se vyskytuje neznámý znak '%1'.").arg(c);
        }
    }
    QString spojeno = bludisteStr.join("");

    // kontrola, zda je start a cíl jen jeden
    QRegExp rS("^[ XE]*S[ XE]*$");
    if (rS.indexIn( spojeno) < 0)
        throw QString("V bludišti je více míst označených jako start.");
    QRegExp rE("^[ XS]*E[ XS]*$");
    if (rE.indexIn( spojeno) < 0)
        throw QString("V bludišti je více míst označených jako konec.");

    // kde je start ?
    Sx = spojeno.indexOf('S');
    Sy = Sx / X;
    Sx = Sx % X;

    // kde je konec ?
    Ex = spojeno.indexOf('E');
    Ey = Ex / X;
    Ex = Ex % X;

    // ----------- vytvoř obrázek s bludištěm --------------

    QByteArray bytes( BITMAPINDEX(X,Y), 0xaa);

    // vytvoř mapu pixelů obrázku podle bludiště
    for (int y=0; y<Y; y++) {
        for (int x=0; x<X; x++) {
            if (bludisteStr[y][x] == 'X') draw_wall( bytes, x, y);
            else draw_space( bytes, x, y);
        }
    }

    // vytvoř obrázek, 3 byty na pixel, každá barva 1 byte (RGB)
    // rozměry obrázku budou X*PSIZE a Y*PSIZE
    // obrázek bude vytvořen podle mapy pixelů v poli bytů v proměnné bytes.
    image = new QImage( (const uchar*) bytes.constData(),
                                X*PSIZE, Y*PSIZE, X*PSIZE*3, QImage::Format_RGB888);

    QPainter p;
    if (!p.begin( image))
        throw QString("QPainter init error.");

    // ještě označení startu a cíle
    draw_start(p);
    draw_end(p);

    p.end();

}

Vykreslení bludiště z datové struktury do okna programu

Využijeme možností Qt a v okně programu (MainWindow) vytvoříme widget QLabel, který využijeme pro zobrazení obrázku. Okno programu se musí svými rozměry přizpůsobit velikosti obrázku s bludištěm. Widget s obrázkem pak musí vyplnit celé okno aplikace.

Návrh vnitřní reprezentace agenta a zobrazení agenta v okně programu

Nakreslíme si agenta jako obrázek ve formátu png. V tomto příkladu je obrázek uložen v souboru duch.png.

duch

V okně programu vytvoříme nový widget třídy QLabel a načteme do něj jako pozadí obrázek agenta. Přizpůsobíme rozměry widgetu. Widget umístíme na start (pozice PSIZE*Sx, PSIZE*Sy).

Obsluha klávesnice a odpovídající reakce na vstup

Pro čtení vstupu z klávesnice vytvoříme metodu keyPressEvent:

void MainWindow::keyPressEvent(QKeyEvent *event)

Tato metoda bude volána vždy po stisku klávesy z aplikační smyčky programu (event loop). Po detekci klávesy se šipkou upravíme souřadnice agenta a posuneme widget s agentem na nové místo. Překreslení bude provedeno automaticky po návratu do smyčky programu.