-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfs_algorithm.cpp
121 lines (99 loc) · 2.89 KB
/
bfs_algorithm.cpp
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include "bfs_algorithm.h"
#include <QtDebug>
BFS_Algorithm::BFS_Algorithm(Map *map)
: map(map)
{
}
QVector<GridElement *> BFS_Algorithm::getPath(QPointF source, QPoint destination)
{
path.clear();
currentChecking.append(map->getGridElement(qRound(source.x()/10), qRound(source.y()/10)));
iterateThroughMapUntilDestinationFound(destination);
while (distanceFromSource != 0)
checkNeighbours();
for (auto it = path.begin(); it != path.end(); ++it)
{
(*it)->setX((*it)->x()*10);
(*it)->setY((*it)->y()*10);
}
reset();
return path;
}
void BFS_Algorithm::iterateThroughMapUntilDestinationFound(QPoint &destination)
{
for (it = currentChecking.begin(); it != currentChecking.end();)
{
if (!(*it)->isTaken() && (*it)->getPosition() == -1)
{
(*it)->setPosition(distanceFromSource);
checked << *it;
if (checkIfPointEqualsDestination(destination))
break;
if ((*it)->x() - 1 >= 0)
checkLater.append(map->getGridElement((*it)->x() - 1, (*it)->y()));
if ((*it)->x() + 1 <= 248)
checkLater.append(map->getGridElement((*it)->x() + 1, (*it)->y()));
if ((*it)->y() - 1 >= 0)
checkLater.append(map->getGridElement((*it)->x(), (*it)->y() - 1));
if ((*it)->y() + 1 <= 248)
checkLater.append(map->getGridElement((*it)->x(), (*it)->y() + 1));
}
checkIfLastElement();
}
}
bool BFS_Algorithm::checkIfPointEqualsDestination(QPoint &destination)
{
if ((*it)->x() == destination.x()/10 && (*it)->y() == destination.y()/10)
{
pointEqualsDestination();
return true;
}
return false;
}
void BFS_Algorithm::pointEqualsDestination()
{
path << *it;
distanceFromSource--;
}
void BFS_Algorithm::checkIfLastElement()
{
if (currentChecking.end() - it == 1)
lastElement();
else
++it;
}
void BFS_Algorithm::lastElement()
{
currentChecking = checkLater;
it = currentChecking.begin();
checkLater.clear();
distanceFromSource++;
}
void BFS_Algorithm::checkNeighbours()
{
if (path.last()->x() - 1 >= 0)
neighbour(-1, 0);
if (path.last()->x() + 1 <= 248)
neighbour(1, 0);
if (path.last()->y() - 1 >= 0)
neighbour(0, -1);
if (path.last()->y() + 1 <= 248)
neighbour(0, 1);
}
void BFS_Algorithm::neighbour(int x, int y)
{
if (map->getGridElement(path.last()->x() + x, path.last()->y() + y)->getPosition() == distanceFromSource)
{
distanceFromSource--;
path.append(map->getGridElement(path.last()->x() + x, path.last()->y() + y));
}
}
void BFS_Algorithm::reset()
{
distanceFromSource = 0;
for (auto it = checked.begin(); it != checked.end(); ++it)
(*it)->setPosition(-1);
checked.clear();
currentChecking.clear();
checkLater.clear();
}