Ohjelma toimii seuraavasti:
- tarkistetaan mihin suuntiin on mahdollista liikkua ja liikutaan sinne minne pääsee
- jos vastaan tulee risteys, merkataan risteys siihen kohtaan
- jos joudutaan umpikujaan, palataan takaisin viimeksi merkittyyn risteykseen ja tutkitaan sen tutkimattomat suunnat
- jos risteyksestä kaikkiin suuntiin vievät tiet on tutkittu, palataan sitä ennen olleeseen risteykseen ja tutkitaan sen tutkimattomat suunnat
Päätin tehdä tästä koodivinkin, koska en ainakaan itse löytänyt muita labyrintinratkaisijoita täältä. Idea tämän itse ohjelman tekemiseen tuli siitä, kun keskustelussa puhuttiin putkan kilpailuista ja tekoäly sielä muutamaan kertaan mainittiin, niin päätinpä koittaa koodata jonkinlaisen tekoälyn itse.
PS. Tuossa esimerkkilabyrintissa pitää olla lopussa rivinvaihto, jotta se toimisi oikein.
ratkaisija.h
#include <iostream>
#include <vector>
#define MAXW 100 // labyrintin maksimileveys
#define MAXH 100 // labyrintin maksimikorkeus
using namespace std;
string lue(const string tiedosto_nimi, const int rivi) // tiedostosta lukemiseen
{
char teksti[MAXW] = { 0 };
int plus = 0;
FILE *tiedosto = fopen(tiedosto_nimi.c_str(), "r");
for (int i = 0; !feof(tiedosto); i++)
{
fgets(teksti, 100, tiedosto);
if (i == rivi)
break;
}
fclose(tiedosto);
return teksti;
}
class RISTEYS // ohjelma toimii risteyksien eri suuntia tutkimalla
{
private:
int x; // näihin koodrinaatteihin palataan,
int y; // jos yhdestä suunnasta ei löydy reittiä loppuun
public:
RISTEYS(const int xp, const int yp)
{
x = xp;
y = yp;
}
int X()
{
return x;
}
int Y()
{
return y;
}
};
class RATKAISIJA
{
private:
vector<RISTEYS> r; // risteykset
int xs; // sijainti x
int ys; // sijainti y
char seina; // seinä-merkki
char tyhja; // tyhjä-merkki
char kayty; // käyty reitti -merkki
char etsija; // kartalla näkyvä etsijä -merkki
char alku; // alku-merkki
char loppu; // loppu-merkki
char labyrintti[MAXW][MAXH]; // labyrintti
int w; // labyrintin leveys
int h; // labyrintin korkeus
int ax; // alku x
int ay; // alku y
int lx; // loppu x
int ly; // loppu y
public:
RATKAISIJA (const string tiedosto, const char alkup, const char loppup, const char seinap, const char tyhjap, const char kaytyp, const char etsijap)
{
seina = seinap;
tyhja = tyhjap;
kayty = kaytyp;
alku = alkup;
loppu = loppup;
etsija = etsijap;
bool aloytyy = false, lloytyy = false; // löytyykö alku ja loppu
int pisin = 0; // pisin merkkijono tiedostossa, labyrintin leveys
int tiedosto_pituus = 0;
char teksti[MAXW] = { 0 };
FILE *filu = fopen(tiedosto.c_str(), "r");
while (!feof(filu))
{
fgets(teksti, MAXW, filu);
for (int ind = 0; ind < strlen(teksti); ind++)
if (teksti[ind] == '\n' || teksti[ind] == '\r') tiedosto_pituus++;
}
tiedosto_pituus--;
fclose(filu);
cout<<"Ratkaistava labyrintti:"<<endl<<endl;
// tulostetaan labyrintti ja kerätään tarvittavat tiedot siitä
for (int y = 0; y < tiedosto_pituus; y++)
{
if (pisin < lue(tiedosto, y).length()-1) pisin = lue(tiedosto, y).length()-1;
for (int x = 0; x < lue(tiedosto, y).length()-1; x++)
{
labyrintti[x][y] = lue(tiedosto, y)[x];
if (labyrintti[x][y] == alku)
{
aloytyy = true;
ax = xs = x;
ay = ys = y;
}
if (labyrintti[x][y] == loppu)
{
lloytyy = true;
lx = x;
ly = y;
}
cout<<labyrintti[x][y];
}
cout<<endl;
}
w = pisin;
h = tiedosto_pituus;
if (!aloytyy || !lloytyy) cerr<<"ERROR: Alkua tai loppua ei löydy!"<<endl;
cout<<endl<<"Aloita labyrintin ratkaiseminen painamalla jotain näppäintä"<<endl;
getchar();
}
void AsetaRisteys(const int xp, const int yp) // merkitään kartalle risteys
{
for (int i = 0; i < r.size(); i++)
if (r[i].X() == xp && r[i].Y() == yp) // jos kartalta löytyy jo tästä kohdasta risteys,
return; // ei sitä merkitä kartalle
RISTEYS temp(xp, yp);
r.push_back(temp);
}
void PoistaRisteys() // poistetaan viimeisin risteys
{
if (r.size() > 1) // alkua ei voi poistaa
r.pop_back();
}
void PalaaRisteys() // palataan viimeisimpään risteykseen
{
xs = r[r.size()-1].X(); // viimeisimmän risteyksen x
ys = r[r.size()-1].Y(); // viimeisimmän risteyksen y
}
bool SeinaY() // onko ylhäällä seinä
{
return (labyrintti[xs][ys-1] == seina);
}
bool SeinaA() // onko alhaalla seinä
{
return (labyrintti[xs][ys+1] == seina);
}
bool SeinaV() // onko vasemmalla seinä
{
return (labyrintti[xs-1][ys] == seina);
}
bool SeinaO() // onko oikealla seinä
{
return (labyrintti[xs+1][ys] == seina);
}
bool LoppuLoytyyYmparilta() // löytyykö loppu
{
return (labyrintti[xs+1][ys] == loppu || // oikealta
labyrintti[xs-1][ys] == loppu || // vasemmalta
labyrintti[xs][ys+1] == loppu || // alhaalta
labyrintti[xs][ys-1] == loppu); // tai ylhäältä
}
bool JonnekinPaasee() // vielä on käymättömiä paikkoja
{ // jos etsijän ympäriltä löytyy tyhjää, niin jonnekin pääsee
if (labyrintti[xs+1][ys] == tyhja ||
labyrintti[xs-1][ys] == tyhja ||
labyrintti[xs][ys+1] == tyhja ||
labyrintti[xs][ys-1] == tyhja)
return true;
for (int i = 0; i < r.size(); i++)
{ // jos löytyy risteys, jonka ympärillä on tyhjää, niin jonnekin pääsee
if (labyrintti[r[i].X()+1][r[i].Y()] == tyhja ||
labyrintti[r[i].X()-1][r[i].Y()] == tyhja ||
labyrintti[r[i].X()][r[i].Y()+1] == tyhja ||
labyrintti[r[i].X()][r[i].Y()-1] == tyhja)
return true;
}
return false;
}
bool RatkaiseLabyrintti() // ratkaistaan labyrintti, jos mahdollista
{
AsetaRisteys(ax, ay); // alkuristeys
while (true)
{
system("cls"); // tulostetaan
cout<<"x: "<<xs<<endl; // tilanne
cout<<"y: "<<ys<<endl; // käyttäjälle
for (int y = 0; y < h; y++)
{
for (int x = 0; x < w; x++)
{
if (x == xs && y == ys)
cout<<etsija;
else
cout<<labyrintti[x][y];
}
cout<<endl;
}
labyrintti[xs][ys] = kayty;
if (LoppuLoytyyYmparilta()) // jos loppu löytyy,
return true; // lopetetaan ratkominen
if (!JonnekinPaasee()) // jos minnekään ei pääse,
return false; // lopetetaan ratkominen
if (SeinaY() && SeinaA() && SeinaV() && !SeinaO()) // vain oikealle pääsee
{
if (labyrintti[xs+1][ys] == kayty) // jos oikealla on käyty,
PalaaRisteys(); // niin palataan viimeisimpään risteykseen
else
xs++; // muutoin mennään oikealle
}
else if (SeinaY() && SeinaA() && !SeinaV() && SeinaO()) // vain vasemmalle pääsee
{
if (labyrintti[xs-1][ys] == kayty)
PalaaRisteys();
else
xs--;
}
else if (SeinaY() && !SeinaA() && SeinaV() && SeinaO()) // vain alas pääsee
{
if (labyrintti[xs][ys+1] == kayty)
PalaaRisteys();
else
ys++;
}
else if (!SeinaY() && SeinaA() && SeinaV() && SeinaO()) // vain ylös pääsee
{
if (labyrintti[xs][ys-1] == kayty)
PalaaRisteys();
else
ys--;
}
else if (SeinaY() && SeinaA() && !SeinaV() && !SeinaO()) // vain sivuille pääsee
{
if (labyrintti[xs+1][ys] != kayty)
xs++;
else if (labyrintti[xs-1][ys] != kayty)
xs--;
else
PalaaRisteys();
}
else if (!SeinaY() && SeinaA() && !SeinaV() && SeinaO()) // vain vasemmalle ja ylös pääsee
{
if (labyrintti[xs-1][ys] != kayty)
xs--;
else if (labyrintti[xs][ys-1] != kayty)
ys--;
else
PalaaRisteys();
}
else if (!SeinaY() && SeinaA() && SeinaV() && !SeinaO()) // vain oikealle ja ylös pääsee
{
if (labyrintti[xs+1][ys] != kayty)
xs++;
else if (labyrintti[xs][ys-1] != kayty)
ys--;
else
PalaaRisteys();
}
else if (SeinaY() && !SeinaA() && !SeinaV() && SeinaO()) // vain vasemmalle ja alas pääsee
{
if (labyrintti[xs-1][ys] != kayty)
xs--;
else if (labyrintti[xs][ys+1] != kayty)
ys++;
else
PalaaRisteys();
}
else if (SeinaY() && !SeinaA() && SeinaV() && !SeinaO()) // vain oikealle ja alas pääsee
{
if (labyrintti[xs+1][ys] != kayty)
xs++;
else if (labyrintti[xs][ys+1] != kayty)
ys++;
else
PalaaRisteys();
}
else if (!SeinaY() && !SeinaA() && SeinaV() && SeinaO()) // vain ylös ja alas pääsee
{
if (labyrintti[xs][ys+1] != kayty)
ys++;
else if (labyrintti[xs][ys-1] != kayty)
ys--;
else
PalaaRisteys();
}
// risteykset
else if (!SeinaY() && !SeinaA() && !SeinaV() && SeinaO()) // vain ylös, alas ja vasemmalle pääsee
{
if (labyrintti[xs-1][ys] != kayty)
{
AsetaRisteys(xs, ys);
xs--;
}
else if (labyrintti[xs][ys+1] != kayty)
{
AsetaRisteys(xs, ys);
ys++;
}
else if (labyrintti[xs][ys-1] != kayty)
{
AsetaRisteys(xs, ys);
ys--;
}
else
{
PoistaRisteys();
PalaaRisteys();
}
}
else if (!SeinaY() && !SeinaA() && SeinaV() && !SeinaO()) // vain ylös, alas ja oikealle pääsee
{
if (labyrintti[xs+1][ys] != kayty)
{
AsetaRisteys(xs, ys);
xs++;
}
else if (labyrintti[xs][ys+1] != kayty)
{
AsetaRisteys(xs, ys);
ys++;
}
else if (labyrintti[xs][ys-1] != kayty)
{
AsetaRisteys(xs, ys);
ys--;
}
else
{
PoistaRisteys();
PalaaRisteys();
}
}
else if (SeinaY() && !SeinaA() && !SeinaV() && !SeinaO()) // vain sivuille ja alas pääsee
{
if (labyrintti[xs+1][ys] != kayty)
{
AsetaRisteys(xs, ys);
xs++;
}
else if (labyrintti[xs-1][ys] != kayty)
{
AsetaRisteys(xs, ys);
xs--;
}
else if (labyrintti[xs][ys+1] != kayty)
{
AsetaRisteys(xs, ys);
ys++;
}
else
{
PoistaRisteys();
PalaaRisteys();
}
}
else if (!SeinaY() && SeinaA() && !SeinaV() && !SeinaO()) // vain sivuille ja ylös pääsee
{
if (labyrintti[xs+1][ys] != kayty)
{
AsetaRisteys(xs, ys);
xs++;
}
else if (labyrintti[xs-1][ys] != kayty)
{
AsetaRisteys(xs, ys);
xs--;
}
else if (labyrintti[xs][ys-1] != kayty)
{
AsetaRisteys(xs, ys);
ys--;
}
else
{
PoistaRisteys();
PalaaRisteys();
}
}
else if (!SeinaY() && !SeinaA() && !SeinaV() && !SeinaO()) // kaikkiin suuntiin pääsee
{
if (labyrintti[xs+1][ys] != kayty)
{
AsetaRisteys(xs, ys);
xs++;
}
else if (labyrintti[xs-1][ys] != kayty)
{
AsetaRisteys(xs, ys);
xs--;
}
else if (labyrintti[xs][ys-1] != kayty)
{
AsetaRisteys(xs, ys);
ys--;
}
else if (labyrintti[xs][ys+1] != kayty)
{
AsetaRisteys(xs, ys);
ys++;
}
else
{
PoistaRisteys();
PalaaRisteys();
}
}
}
}
};käyttö
#include "ratkaisija.h"
int main()
{
RATKAISIJA botti("labyrintti.txt", 'A', 'L', '#', ' ', '.', '@');
if (botti.RatkaiseLabyrintti())
cout<<endl<<"ONNISTUI! :-)"<<endl;
else
cout<<endl<<"EI ONNISTUNUT! :-("<<endl;
cout<<"# = seinä"<<endl;
cout<<"A = alku"<<endl;
cout<<"L = loppu"<<endl;
cout<<". = kuljettu reitti"<<endl;
cout<<"@ = labyrinttiseikkailija"<<endl;
getchar();
return 0;
}esimerkkilabyrintti
################ #L # # # ###### # ##### # # # # # # ### #### # # # # # # # # ###### # # # # # # # # # ###### # # ### # # # # ### ######## # # # A# # # ################
Aihe on jo aika vanha, joten et voi enää vastata siihen.