Backtracking-Labyrinth/Solver.cpp at master · Ritzga/Backtracking-Labyrinth · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "Solver.hpp"

Solver::Solver(const string &fileName, bool graphicalSolve)
        :graphicalSolve(graphicalSolve)
{
    Reader generator = Reader(fileName);
    if(!generator.isException())
    {
        map = generator.getMap();
        currentPosition = map.getStartPoint();
    }
    else
    {
        exception = true;
    }
}

const Coordinate &Solver::getCurrentPosition() const
{
    return currentPosition;
}

bool Solver::getIsSolved() const
{
    return isSolved;
}

bool Solver::isException() const
{
    return exception;
}

bool Solver::pathExists(unsigned int x, unsigned int y)
{
    //prüft ob es das Feld überhaupt gibt
    if (x > map.getWidth()-1)
    {
        return false;
    }
    else if (y > map.getHeight()-1)
    {
        return false;
    }
    return map.at(x, y).isWalkable() && !map.at(x, y).isUsedPath();
}

bool Solver::SolveProblem(Coordinate &position, string path)
{
    if(isSolved)
    {
        //verhindert, dass übrig bleibende Wege weiter verfolgt werden, wenn die Lösung ermittelt wurde
       return false;
    }
    try
    {
        unsigned int x = position.getX();
        unsigned int y = position.getY();
        //Setzt den Punkt als benutzt
        map.at(x, y).setUsedPath(true);
        if (map.getEndPoint() == position)
        {
            cout << "Das Labyrinth wurde gelöst!" << "\nDieser Weg ist möglich um durch " <<
                 "das Labyrinth zu kommen:\n" << path << "\n";
            isSolved = true;
            return true;
        }
        if(graphicalSolve)
        {
            cout << "Labyrinth\n" << map;
            cout << "\naktuelle Position: " << position;
            cout <<
                 "path at " << x << "," << y - 1 << " exists " << pathExists(x, y - 1) << "\n" <<
                 "path at " << x + 1 << "," << y << " exists " << pathExists(x + 1, y) << "\n" <<
                 "path at " << x << "," << y + 1 << " exists " << pathExists(x, y + 1) << "\n" <<
                 "path at " << x - 1 << "," << y << " exists " << pathExists(x - 1, y) << "\n";
            system("clear");
            system("sleep 0.6");
        }
        //Positionen werden auf Begehbarkeit abhängig von der Position geprüft
        return (pathExists(x, y - 1) && SolveProblem(map.at(x, y - 1), path+"O")) || //Norden
               (pathExists(x + 1, y) && SolveProblem(map.at(x + 1, y), path+"R")) || //Osten
               (pathExists(x, y + 1) && SolveProblem(map.at(x, y + 1), path+"U")) || //Süden
               (pathExists(x - 1, y) && SolveProblem(map.at(x - 1, y), path+"L"));   //westen
    }
    catch (const runtime_error& e)
    {
        cerr << e.what();
    }
    return false;
}