Hallo zusammen,
ich habe mich dazu entschlossen den Code nun trotzdem zu posten. Ich denke aber, dass ich da noch einen Fehler drin habe. Vielleicht könnt ihr mir ja helfen diesen zu finden.
Bitte macht auch Anmerkungen zu meinem Programmierstil im Allgemeinen, von Beruf her programmiere ich leider kein C++. Wäre mal nett zu hören was die Pros hier so sagen, ich denke hier kann ich auch noch
optimieren. OK los gehts.
Ich habe das ganze nach der folgenden Erklärung programmiert.
http://www.policyalmanac.org/games/aStarTutorial_de.html
Ich fange mit der Main an, ist eine simple Consolen Anwendung. Mein Motto war hier so leicht wie es geht, damit man den Algorithmus erstmal schnallt.
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
|
#include "AStar.h"
int main() {
AStar *star = new AStar();
star->findPath();
star->print();
delete star;
cin.get();
return 0;
}
|
Nun folgt der Header von der AStar Klasse. Für die offene Liste habe ich ein simples multiset benutzt.
Ich denke hier kann man schon optimieren, aber da es erstmal nichts mit dem eigentlichen AStar zu tun hat
habe ich es mir hier besonders einfach gemacht.
|
C-/C++-Quelltext
|
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
|
#ifndef ASTAR_H
#define ASTAR_H
#include "NodeMap.h"
#include <iostream>
#include <set>
#include <list>
using namespace std;
struct ANodePtrComp{
bool operator()(const Node* n1, const Node* n2) const { return n1->getF() < n2->getF(); }
};
class AStar
{
public:
AStar();
~AStar();
void print();
void findPath();
private:
void addNodeToOpenList(Node* node);
Node* getLastNodeFromOpenList();
void eraseNodeFromOpenList(Node* node);
void print(Node* node);
void updateNode(int i, float g, Node* n);
private:
NodeMap* nodeMap;
multiset<Node*, ANodePtrComp> openList; //easy way!
};
#endif
|
Hier die Klasse dazu. Hier sind noch einige
hard coded values drin, die fliegen natürlich später raus.
|
C-/C++-Quelltext
|
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
|
#include "AStar.h"
AStar::AStar(){
nodeMap = new NodeMap(9,5);
nodeMap->initialize();
nodeMap->setStartPoint(0,0);
nodeMap->setEndPoint(8,4);
}
AStar::~AStar(){
delete nodeMap;
nodeMap = 0;
}
void AStar::print(){
print(nodeMap->getCurrentEndPoint());
cout << "\nFinal way." << endl;
nodeMap->print();
cin.get();
}
void AStar::print(Node* node){
cout << "x: "
<< node->getPosition().x << " "
<< "y: "
<< node->getPosition().y << endl;
if(!node->isStartNode() && node->getParentNode() != 0){
node->setAsFinalWaypoint();
print(node->getParentNode());
}
}
void AStar::findPath(){
bool found = 0;
Node* startNode = nodeMap->getCurrentStartPoint();
Node* endNode = nodeMap->getCurrentEndPoint();
//1. add start node to open list
addNodeToOpenList(startNode);
do{
nodeMap->print();
//2. remove start node from open list and close it
Node *currentNode = getLastNodeFromOpenList();
currentNode->setIsClosed();
//3. analyse all neighbors
for(int i=0;i<8; i++){
Node *node = nodeMap->getNeighborFromNode(currentNode->getPosition(),static_cast<NodeMap::Neighbors>(i));
if(node == 0 || node->isClosed() || !node->isWalkable()) continue;
float g = currentNode->getG() + nodeMap->calculateDistance(currentNode->getPosition(),node->getPosition());
float h = nodeMap->calculateDistance(node->getPosition(), endNode->getPosition());
if(!node->isOpen()){
node->setParentNode(currentNode);
node->setG(g);
} else if (g < node->getG()){
eraseNodeFromOpenList(node);
node->setParentNode(currentNode);
node->setG(g);
}
node->setH(h);
node->calculateF();
addNodeToOpenList(node);
if(currentNode->isEndNode()){ //strike
found = true;
}
}
}
while (found != true && openList.size() != 0);
}
void AStar::addNodeToOpenList(Node* node){
node->setIsOpen();
openList.insert(node);
}
void AStar::eraseNodeFromOpenList(Node* node){
set<Node*>::iterator it;
it=openList.find(node);
openList.erase(it);
}
Node* AStar::getLastNodeFromOpenList(){
set<Node*>::iterator it;
Node* n;
//get the first node from open list
it=openList.begin();
n = *it;
//remove it
openList.erase(it);
return n;
}
|
Hier nun die eigentlich Node, ok man kann das auch alles in einem struct halten, ich habe jedoch die normale Klasse gewählt.
|
C-/C++-Quelltext
|
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
|
#ifndef NODE_H
#define NODE_H
struct Position{
int x;
int y;
};
class Node {
public:
/*-- mothods --*/
void calculateF();
/*-- constructor and destructor --*/
Node(float g, float h, bool start, bool end, Node* parentNode, Position position, bool walkable);
virtual ~Node();
Node(const Node& other);
Node& operator=(const Node& other);
/*-- get and set methods --*/
void setParentNode(Node* node);
Node* getParentNode();
void setG(const float& g);
void setH(const float& h);
float const& getG() const;
float const& getH() const;
float const& getF() const;
void setIsStartNode(const bool& start);
void setIsEndNode(const bool& end);
void setIsWalkable(const bool& walkable);
void setIsOpen();
void setIsClosed();
bool const& isStartNode() const;
bool const& isEndNode() const;
bool const& isWalkable() const;
bool const& isOpen() const;
bool const& isClosed() const;
bool const& isFinal() const;
void setPosition(const struct Position& position);
Position const& getPosition() const;
void setSign(char* sign);
char* getSign() const;
void setAsFinalWaypoint();
protected:
private:
bool isFinalWayNode;
char* sign;
float g;
float h;
float f;
bool start;
bool end;
bool walkable;
bool open;
bool closed;
Node* parentNode;
Position position;
};
#endif // NODE_H
|
Hier die Implementierung der Klasse.
|
C-/C++-Quelltext
|
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
122
123
124
125
|
#include "Node.h"
/*-- mothods --*/
void Node::calculateF() {
f = g + h;
}
/*-- constructor and destructor --*/
Node::Node(float g, float h, bool start, bool end, Node* parentNode, Position position, bool walkable):g(g),h(h),start(start), end(end),parentNode(parentNode), position(position), walkable(walkable) {
open = 0;
closed = 0;
sign = ".";
isFinalWayNode=false;
}
Node::~Node() {
}
Node::Node(const Node& other) {
//copy ctor
}
Node& Node::operator=(const Node& rhs) {
if (this == &rhs) return *this; // handle self assignment
//assignment operator
return *this;
}
/*-- get and set methods --*/
void Node::setParentNode(Node* node) {
this->parentNode = node;
}
void Node::setAsFinalWaypoint(){
isFinalWayNode = true;
}
bool const& Node::isFinal() const {
return isFinalWayNode;
}
Node* Node::getParentNode(){
return this->parentNode;
}
float const& Node::getG() const {
return g;
}
float const& Node::getH() const {
return h;
}
float const& Node::getF() const {
return f;
}
void Node::setG(const float& g) {
this->g = g;
}
void Node::setH(const float& h) {
this->h = h;
}
void Node::setIsStartNode(const bool& start) {
this->start=start;
}
void Node::setIsEndNode(const bool& end) {
this->end = end;
}
bool const& Node::isStartNode() const {
return start;
}
bool const& Node::isEndNode() const {
return end;
}
void Node::setIsWalkable(const bool& walkable) {
this->walkable = walkable;
}
bool const& Node::isWalkable() const {
return walkable;
}
void Node::setPosition(const struct Position& position) {
this->position = position;
}
Position const& Node::getPosition() const {
return position;
}
void Node::setIsOpen() {
this->closed = 0;
this->open = 1;
}
void Node::setIsClosed() {
this->open = 0;
this->closed = 1;
}
bool const& Node::isOpen() const {
return open;
}
bool const& Node::isClosed() const {
return closed;
}
void Node::setSign(char* sign){
this->sign = sign;
}
char* Node::getSign() const{
return sign;
}
|
Die Nodes werden innerhalb einer NodeMap gehalten.
|
C-/C++-Quelltext
|
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
|
#ifndef NODEMAP_H
#define NODEMAP_H
#include "Node.h"
class NodeMap {
public:
enum Neighbors{
bottom,
left,
right,
above,
bottom_left,
bottom_right,
above_left,
above_right
};
NodeMap(int width, int height);
~NodeMap();
void initialize();
void shutdown();
void print();
void setStartPoint(int x, int y);
void setEndPoint(int x, int y);
void setWalkable(int x, int y, bool able);
Node* getNeighborFromNode(Position const& position,Neighbors neighbor);
Node* getCurrentStartPoint();
Node* getCurrentEndPoint();
float calculateDistance(Position const& p1, Position const& p2);
private:
Node* getNodeFromMap(int const &x, int const &y);
int height;
int width;
int size;
Node** nodes;
Node* currentStartPoint;
Node* currentEndPoint;
};
#endif
|
Hier noch die Implementierung dazu.
|
C-/C++-Quelltext
|
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
#include <iostream>
#include <vector>
#include <math.h>
#include "NodeMap.h"
using namespace std;
NodeMap::NodeMap(int width, int height){
this->height=height;
this->width=width;
this->size = width * height;
}
NodeMap::~NodeMap(){
shutdown();
}
/*
* This method creates a map like this.
* .........
* ....#....
* ..O.#.X..
* ....#....
* .........
*/
void NodeMap::initialize(){
nodes = new Node*[size];
//fill
for(int i=0; i<height; i++) {
for(int j=0; j<width; j++) {
Position position;
position.x = j;
position.y = i;
float g = 0;
float h = 0.0f;
nodes[width * i + j] = new Node(g, h, false, false, 0, position, true);
}
}
//create wall
for(int i=0; i<=3; i++){
setWalkable(1,i,false);
}
for(int i=1; i<=4; i++){
setWalkable(3,i,false);
}
}
void NodeMap::shutdown(){
//clean
for(int i=0; i<size; i++) {
delete nodes[i];
}
delete[] nodes;
}
void NodeMap::print(){
for(int i=0; i<height; i++) {
for(int j=0; j<width; j++) {
if(j % width == 0){
cout << endl;
}
if(nodes[width * i + j]->isStartNode()){
cout << "O";
}
else if(nodes[width * i + j]->isEndNode()){
cout << "X";
}
else if(!nodes[width * i + j]->isWalkable()){
cout << "#";
}
else if(nodes[width * i + j]->isOpen())
{
cout << "+";
}
else if(nodes[width * i + j]->isFinal() && !nodes[width * i + j]->isEndNode())
{
cout << "w";
}
else if(nodes[width * i + j]->isClosed() && !nodes[width * i + j]->isEndNode())
{
cout << "-";
}
else{
cout << nodes[width * i + j]->getSign();
}
}
}
cout << "\n" << endl;
}
/*
* This method return the neighbor from a specific node.
* In the case that a node is not walkable null will be returned as result.
*/
Node* NodeMap::getNeighborFromNode(Position const& position,Neighbors neighbor){
const int *x;
const int *y;
x = &position.x;
y = &position.y;
switch(neighbor){
/********
* +++
* +X+
* +?+
*********/
case bottom:
return getNodeFromMap(*x, *y - 1);
break;
/********
* +++
* +X+
* ?++
********/
case bottom_left:
return getNodeFromMap(*x - 1, *y - 1);
break;
/********
* +++
* +X+
* ++?
********/
case bottom_right:
return getNodeFromMap(*x + 1, *y - 1);
break;
/********
* +++
* ?X+
* +++
********/
case left:
return getNodeFromMap(*x - 1, *y);
break;
/********
* +++
* +X?
* +++
********/
case right:
return getNodeFromMap(*x + 1, *y);
break;
/********
* +?+
* +X+
* +++
********/
case above:
return getNodeFromMap(*x, *y + 1);
break;
/********
* ?++
* +X+
* +++
********/
case above_left:
return getNodeFromMap(*x - 1, *y + 1);
break;
/********
* ++?
* +X+
* +++
********/
case above_right:
return getNodeFromMap(*x + 1, *y + 1);
break;
default :
return 0;
break;
};
return 0;
}
Node* NodeMap::getNodeFromMap(int const &x, int const &y){
if(x < 0 || y < 0 || x > width - 1 || y > height - 1){
return 0;
}
return nodes[width * y + x];
}
float NodeMap::calculateDistance(Position const& p1, Position const& p2){
//return 10 * (abs(p1.x - p2.x) + abs(p1.y - p2.y));
float px = float(p2.x - p1.x);
float py = float(p2.y - p1.y);
return sqrt(px * px + py * py);
}
void NodeMap::setStartPoint(int x, int y){
currentStartPoint = nodes[width * y + x];
currentStartPoint->setIsStartNode(true);
}
void NodeMap::setEndPoint(int x, int y){
currentEndPoint = nodes[width * y + x];
currentEndPoint->setIsEndNode(true);
}
void NodeMap::setWalkable(int x, int y, bool able){
nodes[width * y + x]->setIsWalkable(able);
}
Node* NodeMap::getCurrentStartPoint(){
return currentStartPoint;
}
Node* NodeMap::getCurrentEndPoint(){
return currentEndPoint;
}
|
Hier dann der Weg, der ausgerechnet wurde.
|
Quellcode
|
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
O#.......
.#.#.....
.#.#.....
.#.#.....
...#....X
O#.......
+#.#.....
.#.#.....
.#.#.....
...#....X
O#.......
-#.#.....
+#.#.....
.#.#.....
...#....X
O#.......
-#.#.....
-#.#.....
+#.#.....
...#....X
O#.......
-#.#.....
-#.#.....
-#.#.....
++.#....X
O#.......
-#.#.....
-#.#.....
-#+#.....
+-+#....X
O#.......
-#.#.....
-#.#.....
-#+#.....
+--#....X
O#.......
-#.#.....
-#+#.....
-#-#.....
+--#....X
O#.......
-#.#.....
-#+#.....
-#-#.....
+--#....X
O#.......
-#.#.....
-#+#.....
-#-#.....
---#....X
O#.......
-#.#.....
-#+#.....
-#-#.....
---#....X
O#.......
-#+#.....
-#-#.....
-#-#.....
---#....X
O#.......
-#+#.....
-#-#.....
-#-#.....
---#....X
O#++.....
-#-#.....
-#-#.....
-#-#.....
---#....X
O#++.....
-#-#.....
-#-#.....
-#-#.....
---#....X
O#+-+....
-#-#+....
-#-#.....
-#-#.....
---#....X
O#+-+....
-#-#+....
-#-#.....
-#-#.....
---#....X
O#+-++...
-#-#-+...
-#-#++...
-#-#.....
---#....X
O#+-++...
-#-#-+...
-#-#++...
-#-#.....
---#....X
O#+-++...
-#-#-++..
-#-#+-+..
-#-#+++..
---#....X
O#+-++...
-#-#-++..
-#-#+-+..
-#-#+++..
---#....X
O#+-++...
-#-#-++..
-#-#+-++.
-#-#++-+.
---#.+++X
O#+-++...
-#-#-++..
-#-#+-++.
-#-#++-+.
---#.+++X
O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.+++X
O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.++-X
O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.++-X
O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.++-X
O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.++-X
x: 8 y: 4
x: 7 y: 3
x: 6 y: 3
x: 5 y: 2
x: 4 y: 1
x: 3 y: 0
x: 2 y: 1
x: 2 y: 2
x: 2 y: 3
x: 1 y: 4
x: 0 y: 3
x: 0 y: 2
x: 0 y: 1
x: 0 y: 0
Final way.
O#+w++...
w#w#w++..
w#w#+w+++
w#w#++ww+
-w-#.++-X
|
w = Final Node
+ = Node in der Open List
- = Node in der Closed List
Das Problem welches ich hier habe ist, dass meine Lösung nicht den optimalen Weg berechnet hat. Durch den Manhattan Algorithmus geht es erst einmal auf direkten Wege zum Zielpunkt, erst wenn der Algorithmus auf das Hindernis stößt wandert er an dem Hindernis vorbei. Danach geht es auf direktem Wege zum Ziel. Im Spiel würde die Figur erstmal gegen die Wand rennen und dann in Richtung Norden an dem Hindernis vorbei.
Kann man das noch verbessern?
Schöne Grüße
Fb