Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

C++ - SFML - 2D - A*Algorithmus - Problem bei der Umsetzung

Werbeanzeige

denniro

Treue Seele

  • »denniro« ist der Autor dieses Themas

Beiträge: 275

  • Private Nachricht senden

1

02.06.2012, 12:33

C++ - SFML - 2D - A*Algorithmus - Problem bei der Umsetzung

Heyho liebe Community!
Ich habe mir vorgenommen ein kleines Projekt zu programmieren, das mir den kürzesten Weg, von Punkt A nach B zeigt.
Ich habe mich entschlossen den bekannten A*Algorithmus dafür zu nutzen, da er hier auch auf der Wiki vorhanden ist.
Nun harpert's leider bei der Umsetzung...Er markiert einfach den falschen Weg..
Hier die MAP-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
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
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279

#include "Map.h"

//Map initialisieren
void CMap::Init(int amountX, int amountY)
{
    this->amountX = amountX;
    this->amountY = amountY;
    TileMap.resize(amountX);
    for(int i=0;i < amountX; i++)
    {
        TileMap.at(i).resize(amountY);
    }
    LoadContent();
    LoadStandard();

    found = false;

    TargetX = TargetY = StartX = StartY = -100;
}

//Inhalt laden
void CMap::LoadContent()
{
    Sheet.LoadFromFile("Data/Tile.png");
}

//Standardmap laden
void CMap::LoadStandard()
{
    for(int i=0;i < amountX; i++)
    {
        for(int j=0;j < amountY; j++)
        {
            TileMap[i][j].Init((float)(i*tileWidth), (float)(j*tileHeight), Sheet);
        }
    }
}

//Map zeichnen
void CMap::Draw(sf::RenderWindow &Window)
{
    for(int i=0;i < amountX; i++)
    {
        for(int j=0;j < amountY; j++)
        {
            TileMap[i][j].Draw(Window);
        }
    }
        if(StartX >= 0 && StartX <= tileWidth*mapWidth && StartY >= 0 && StartY <= tileHeight*mapHeight)
        {
            //std::cout << "Start existiert!" << std::endl;
            if(TargetX >= 0 && TargetX <= tileWidth*mapWidth && TargetY >= 0 && TargetY <= tileHeight*mapHeight)
            {
                //std::cout << "Ziel existiert!" << std::endl;
                if(!found)
                {
                    //std::cout << "Noch nicht gefunden!" << std::endl;
                    LowestFCost();
                }
            }
        }       
}

//Ziel setzen
void CMap::setTarget(int MouseX, int MouseY)
{
    if(TargetX >= 0 && TargetY >= 0)
    {
        for(int i=0;i < amountX; ++i)
        {
            for(int j=0;j < amountY; ++j)
            {
                if(TileMap[i][j].GetTileX() == 1 && TileMap[i][j].GetTileY() == 0)
                    TileMap[i][j].SetTile(0, 0);
            }
        }
    }
    for(int i=0;i < amountX; i++)
    {
        for(int j=0;j < amountY; j++)
        {
            if(MouseX > TileMap[i][j].GetPosX() && MouseX < TileMap[i][j].GetPosX() + tileWidth && MouseY > TileMap[i][j].GetPosY() && MouseY < TileMap[i][j].GetPosY() + tileHeight)
            {
                if(TileMap[i][j].GetTileX() != 2 && TileMap[i][j].GetTileY() == 0)
                {
                    TileMap[i][j].SetTile(1, 0);
                    clearList(1);
                    clearList(2);
                    TargetX = TileMap[i][j].GetPosX();
                    TargetY = TileMap[i][j].GetPosY();
                    std::cout << "TargetX = " << TileMap[i][j].GetPosX() << std::endl;
                    std::cout << "TargetY = " << TileMap[i][j].GetPosY() << std::endl;
                }
            }
        }
    }
}

//Start setzen
void CMap::setStart(int MouseX, int MouseY)
{
    if(StartX >= 0 && StartY >= 0)
    {
        for(int i=0;i < amountX; ++i)
        {
            for(int j=0;j < amountY; ++j)
            {
                if(TileMap[i][j].GetTileX() == 2 && TileMap[i][j].GetTileY() == 0)
                {
                    TileMap[i][j].SetTile(0, 0);
                }
            }
        }
    }
    for(int i=0;i < amountX; i++)
    {
        for(int j=0;j < amountY; j++)
        {
            if(MouseX > TileMap[i][j].GetPosX() && MouseX < TileMap[i][j].GetPosX() + tileWidth && MouseY > TileMap[i][j].GetPosY() && MouseY < TileMap[i][j].GetPosY() + tileHeight)
            {
                if(TileMap[i][j].GetTileX() != 1 && TileMap[i][j].GetTileY() == 0)
                {
                    TileMap[i][j].SetTile(2, 0);
                    StartX = TileMap[i][j].GetPosX();
                    StartY = TileMap[i][j].GetPosY();
                    clearList(1);
                    clearList(2);
                    TileMap[i][j].Reset();
                    TileMap[i][j].setIsKnown(true); 
                    OpenList.push_back(&TileMap[i][j]);
                    std::cout << "StartX = " << TileMap[i][j].GetPosX() << std::endl;
                    std::cout << "StartY = " << TileMap[i][j].GetPosY() << std::endl;
                }
            }
        }
    }
}

//Liste leeren
void CMap::clearList(int ID)
{
    switch(ID)
    {
    case 2:
        {
            std::list<CTile*>::iterator ItClosedTile = ClosedList.begin();
            while(ItClosedTile != ClosedList.end())
            {
                (*ItClosedTile)->Reset();
                (*ItClosedTile)->SetTile(0, 0);
                ItClosedTile++;
                found = false;
            }
            ClosedList.clear();
        }break;
    default:
        {
            std::list<CTile*>::iterator ItOpenTile = OpenList.begin();
            while(ItOpenTile != OpenList.end())
            {
                (*ItOpenTile)->Reset();
                (*ItOpenTile)->SetTile(0, 0);
                ItOpenTile++;
                found = false;
            }
            OpenList.clear();
        }break;
    }
}

//Sucht nach dem Tile, mit den niedrigsten F-Kosten
void CMap::LowestFCost()
{
    int x = -100;
    int y = -100;
    int F_Cost = 500;

    std::list<CTile*>::iterator ItOpenTile = OpenList.begin();
    std::list<CTile*>::iterator ItClosedTile = ClosedList.begin();

    while(ItOpenTile != OpenList.end())
    {
        if(F_Cost>(*ItOpenTile)->GetFCost())
        {
            x = (int)(*ItOpenTile)->GetPosX();
            y = (int)(*ItOpenTile)->GetPosY();
            F_Cost = (*ItOpenTile)->GetFCost();
            std::cout << "F_Cost: " << (*ItOpenTile)->GetFCost() << std::endl;
        }
        ItOpenTile++;
    }

    if(x!=TargetX && y!=TargetY)
    {
        ItOpenTile = OpenList.begin();
        while(ItOpenTile != OpenList.end())
        {
            if(x == (*ItOpenTile)->GetPosX() && y == (*ItOpenTile)->GetPosY() && F_Cost == (*ItOpenTile)->GetFCost())
            {
                (*ItOpenTile)->setIsKnown(false);
                (*ItOpenTile)->setClosed(true);
                ClosedList.push_back(*ItOpenTile);
                OpenList.erase(ItOpenTile);
                std::cout << "Tile wurde der geschlossenen Liste hinzugefuegt!" << std::endl;
                break;
            }
            ItOpenTile++;
        }

        ItClosedTile = ClosedList.begin();
        while(ItClosedTile != ClosedList.end())
        {
            if(x == (*ItClosedTile)->GetPosX() && y == (*ItClosedTile)->GetPosY() && F_Cost == (*ItClosedTile)->GetFCost())
            {
                for(int i=0; i<amountX; i++)
                {
                    for(int j=0; j<amountY; j++)
                    {
                        if(x==TileMap[i][j].GetPosX() && y-tileHeight==TileMap[i][j].GetPosY() && TileMap[i][j].getWalkable() && !TileMap[i][j].getIsKnown() && !TileMap[i][j].getClosed())
                        {
                            TileMap[i][j].setIsKnown(true);
                            TileMap[i][j].setComeFrom(x, y);
                            TileMap[i][j].setPath(TargetX, TargetY, (*ItClosedTile)->GetGCost()+10);
                            OpenList.push_back(&TileMap[i][j]);
                            std::cout << "Tile wurde der offenen Liste hinzugefuegt!" << std::endl;
                        }else if(x-tileWidth==TileMap[i][j].GetPosX() && y==TileMap[i][j].GetPosY() && TileMap[i][j].getWalkable() && !TileMap[i][j].getIsKnown() && !TileMap[i][j].getClosed())
                        {
                            TileMap[i][j].setIsKnown(true);
                            TileMap[i][j].setComeFrom(x, y);
                            TileMap[i][j].setPath(TargetX, TargetY, (*ItClosedTile)->GetGCost()+10);
                            OpenList.push_back(&TileMap[i][j]);
                            std::cout << "Tile wurde der offenen Liste hinzugefuegt!" << std::endl;
                        }else if(x+tileWidth==TileMap[i][j].GetPosX() && y==TileMap[i][j].GetPosY() && TileMap[i][j].getWalkable() && !TileMap[i][j].getIsKnown() && !TileMap[i][j].getClosed())
                        {
                            TileMap[i][j].setIsKnown(true);
                            TileMap[i][j].setComeFrom(x, y);
                            TileMap[i][j].setPath(TargetX, TargetY, (*ItClosedTile)->GetGCost()+10);
                            OpenList.push_back(&TileMap[i][j]);
                            std::cout << "Tile wurde der offenen Liste hinzugefuegt!" << std::endl;
                        }else if(x==TileMap[i][j].GetPosX() && y+tileHeight==TileMap[i][j].GetPosY() && TileMap[i][j].getWalkable() && !TileMap[i][j].getIsKnown() && !TileMap[i][j].getClosed())
                        {
                            TileMap[i][j].setIsKnown(true);
                            TileMap[i][j].setComeFrom(x, y);
                            TileMap[i][j].setPath(TargetX, TargetY, (*ItClosedTile)->GetGCost()+10);
                            OpenList.push_back(&TileMap[i][j]);
                            std::cout << "Tile wurde der offenen Liste hinzugefuegt!" << std::endl;
                        }
                    }
                }
                std::cout << "OpenList: " << OpenList.size() << std::endl;
                break;
            }
            ItClosedTile++;
        }
    }else
    {
        found = true;
        std::cout << "Ziel wurde gefunden!" << std::endl;
        ColorPath();
    }
}

//Weg markieren
void CMap::ColorPath()
{
    std::list<CTile*>::iterator ItClosedTile = ClosedList.begin();
    while(ItClosedTile != ClosedList.end())
        {
            if((*ItClosedTile)->GetPosX() != StartX || (*ItClosedTile)->GetPosY() != StartY)
            {
                if((*ItClosedTile)->GetPosX() != TargetX || (*ItClosedTile)->GetPosY() != TargetY)
                {
                    (*ItClosedTile)->SetTile(3, 0);
                }
            }
            ItClosedTile++;
        }
    std::cout << "Weg wurde markiert!(" << ClosedList.size() << " Tiles)" << std::endl;
}


Was habe ich falsch gemacht? ;o

Lg. denniro
Only God can judge me.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »denniro« (02.06.2012, 17:10)

Koschi

Alter Hase

Beiträge: 657

  • Private Nachricht senden

2

06.06.2012, 21:52

Also wenn ich das richtig durchschaut habe kommt der Ziel Knoten nicht in die ClosedList, dann kann ich bei deinem Weg MarkioerFunktion nicht erkennen das du dich vom Zielknoten entlang der ComeFrom hangelst. Du zählst die liste nur von vorne nach hinten durch der Richtige weg wird damit aber nicht durchlaufen. Wie gesagt vom Zielknoten zu dessen Comefrom von diesem wieder zu dessen ComeFrom usw. bis zum Startknoten.

Gruß Koschi
Wer aufhört besser werden zu wollen hört auf gut zu sein!

aktuelles Projekt:Rickety Racquet

denniro

Treue Seele

  • »denniro« ist der Autor dieses Themas

Beiträge: 275

  • Private Nachricht senden

3

07.06.2012, 12:57

Okey vielen Dank erstmal für deine Antwort! Sobald ich den Code gefixxt habe und er weiterhin nicht funktionieren wird, werde ich ihn erneut posten ;)
lg. denniro
Only God can judge me.

Werbeanzeige

Ähnliche Themen