[C++] Jak ulepszyć moją implementację algorytmu A*?

Nazwa użytkownika:

Hasło:

Nie masz jeszcze konta?

Zarejestruj się!

» Forum » Programowanie » [C, C++] Szukam pomocy

[C++] Jak ulepszyć moją implementację algorytmu A*?

Ostatnio zmodyfikowano 2018-04-05 01:10

twoxu

Temat założony przez niniejszego użytkownika

[C++] Jak ulepszyć moją implementację algorytmu A*?

» 2018-03-31 20:31:48

Witam. Na potrzeby mojej gry próbowałem napisać algorytm A*, i po wielu godzinach, piwach, próbach i skargach na hałas i butelki latające przez okno, udało mi się, ale nie pracuje on wydajnie.

Cała "mapa" do sprawdzania jest generowana z kwadratowego obrazka o rozmiarach w zakresie od 100x100 do 200x200, czyli sumarycznie wszystkich "Node" są dziesiątki tysięcy.

Mam tego ekstremalnie dosyć i skręca mnie od myślenia o A*, który śni mi się już po nocach, dlatego chciałbym i uprzejmie proszę, aby ktoś kto ma za dużo czasu może spojrzał i udzielił paru porad dla nowicjusza (co chyba widać po kodzie).

#include <SFML/Graphics.hpp>
#include <iostream>
#include <math.h>
#include <algorithm>

#include "other_definitions.h"
#include "actor_definitions.h"

using namespace std;

//A-Cost of moving from the destination
//B-Cost of moving from the beginning
//C-Combined cost (A+B) of moving from beginning
//X-Pos X
//Y-Pos Y

//Searching will occur from destination to beginning, to make path positions saved in vector<sf::Vector2i> to be in correct order.
sf::Image abDebug;

class Node
{
public:
int i; //Index in allNodes
float A;
float B;
int C = 1;
int X;
int Y;
int parent; //Index in allNodes of parent. equals to X*Y
bool used = false;
bool isOpen = false;
};

vector < Node > allNodes;
vector < Node > openNodes;

Node getNode( int x, int y, sf::Image col )
{
std::cout << "Trying to get a Node" << x << " " << y << " " << col.getSize().x << " " << col.getSize().y << std::endl;
for( int a = 0; a <= col.getSize().x * col.getSize().y; a++ )
{
if( allNodes[ a ].X == x && allNodes[ a ].Y == y )
{
std::cout << "Found a node!\n";
return allNodes[ a ];
}
}

std::cout << "Couldnt return a Node!\n";
}

vector < Node > getSurroundingNodes( Node & n, sf::Image col )
{
vector < Node > surroundingNodes;
if( !n.used )
for( int a = 0; a < col.getSize().x * col.getSize().y; a++ )
if( allNodes[ a ].X >= n.X - 1 && allNodes[ a ].X <= n.X + 1 && allNodes[ a ].Y >= n.Y - 1 && allNodes[ a ].Y <= n.Y + 1 ) // && allNodes[a].X !=n.X && allNodes[a].Y != n.Y)
{
if( col.getPixel( allNodes[ a ].X, allNodes[ a ].Y ) != sf::Color( 0, 0, 255, 255 ) ) //&&!allNodes[a].used)
{
Node sr;
sr = allNodes[ a ];
sr.i = allNodes[ a ].i;
sr.parent = n.i;
surroundingNodes.push_back( sr );
n.used = true;
}
}
return surroundingNodes;
}
void viewPath( vector < sf::Vector2i > path, sf::Image & output )
{
for( int i = 0; i < path.size(); i++ )
{
output.setPixel( path[ i ].x, path[ i ].y, sf::Color( 255, 0, 255, 255 ) );
}
output.saveToFile( "debug.png" );
}
bool compC( const Node & n1, const Node & n2 )
{
return allNodes[ n1.i ].C < allNodes[ n2.i ].C;
}
vector < sf::Vector2i > Pathfind( int bx, int by, int dx, int dy ) //bx,by - beginning x and y coords || dx,dy - destination x and y coords
{
std::cout << "Started Pathfinding" << std::endl;
vector < sf::Vector2i > foundPath;
sf::Image col;
//Firstly, assign all nodes to a Vector.
col = maps[ currentMap ].colImage;
for( int z = 0; z < col.getSize().x; z++ )
{
for( int q = 0; q < col.getSize().y; q++ )
{
Node n;
n.X = z;
n.Y = q;
n.i = allNodes.size();
allNodes.push_back( n );
}
}
std::cout << "Nodes assigned to Vector" << std::endl;
//Now, calculate A and B values for all nodes.
for( int l = 0; l < allNodes.size(); l++ )
{
allNodes[ l ].A = abs( dx - allNodes[ l ].X ) + abs( by - allNodes[ l ].Y );
allNodes[ l ].B = abs( bx - allNodes[ l ].X ) + abs( by - allNodes[ l ].Y );
}

std::cout << "A and B values for all vectors calculated" << std::endl;
sf::Image abDebug;
abDebug.create( col.getSize().x, col.getSize().y, sf::Color::Black );
for( int k = 0; k < allNodes.size(); k++ )
{
abDebug.setPixel( allNodes[ k ].X, allNodes[ k ].Y, sf::Color( allNodes[ k ].X, allNodes[ k ].Y, 0, 255 ) );
if( col.getPixel( allNodes[ k ].X, allNodes[ k ].Y ) == sf::Color( 0, 0, 255, 255 ) )
abDebug.setPixel( allNodes[ k ].X, allNodes[ k ].Y, sf::Color::White );

}
abDebug.saveToFile( "debug.png" );
std::cout << "Collisions have been applied to Vector" << std::endl;
//Create pointers to beginning and destination nodes
Node * beginningNode;
Node b = getNode( bx, by, col );
Node * destinationNode;
Node d = getNode( dx, dy, col );
beginningNode = & b;
destinationNode = & d;
std::cout << "Assigned beg and dest nodes." << std::endl;
//Now, start checking from the destination.
Node * currentNode;
destinationNode->C = destinationNode->A + destinationNode->B;
currentNode = destinationNode;
Node * previousNode;
int currentLowestCost = currentNode->A + currentNode->B + 1;
currentNode->isOpen = true;
openNodes.push_back( * currentNode );
cout << "--" << openNodes.size() << endl;
cout << currentNode->C << endl;
while( !openNodes.empty() )
{
sort( openNodes.begin(), openNodes.end(), compC );
* currentNode = openNodes[ 0 ];
openNodes.erase( openNodes.begin() + 0 );
vector < Node > surroundingNodes;
surroundingNodes = getSurroundingNodes( * currentNode, col );
if( !surroundingNodes.empty() )
{
for( int a = 0; a < surroundingNodes.size(); a++ )
{
allNodes[ surroundingNodes[ a ].i ].C = allNodes[ surroundingNodes[ a ].i ].A + allNodes[ surroundingNodes[ a ].i ].B;
if( surroundingNodes[ a ].X == beginningNode->X && surroundingNodes[ a ].Y == beginningNode->Y )
{
cout << "Path has been found!!Nodes:" << foundPath.size() << endl;
abDebug.saveToFile( "debug.png" );
foundPath.push_back( sf::Vector2i( allNodes[ surroundingNodes[ a ].i ].X, allNodes[ surroundingNodes[ a ].i ].Y ) );
viewPath( foundPath, abDebug );
return foundPath;
}
if( !allNodes[ surroundingNodes[ a ].i ].isOpen )
{
abDebug.setPixel( surroundingNodes[ a ].X, surroundingNodes[ a ].Y, sf::Color::Cyan );
allNodes[ surroundingNodes[ a ].i ].isOpen = true;
allNodes[ surroundingNodes[ a ].i ].parent = currentNode->i;
openNodes.push_back( allNodes[ surroundingNodes[ a ].i ] );
}
}
}
}
abDebug.saveToFile( "debug.png" );
}

Warto zaznaczyć, że kod ten nie jest jeszcze sfinalizowany (nie generuje foundPath) ponieważ najpierw chciałbym naprawić problemy takie jak ten

Nie chce mnie sie już na to patrzeć kurła.

Nie chce mnie sie już na to patrzeć kurła.

Biały kolor oznacza przeszkodę, cyjan natomiast ścieżkę, którą sprawdzał algorytm. Jak widać u góry, ścieżka nie jest do końca optymalna i to chciałbym naprawić zanim napiszę kod odpowiedzialny za wypełnienie foundPath.

Z góry dzięki za wyjaśnienia.

P-170396

DejaVu

» 2018-03-31 23:25:12

Jest omówiony algorytm A* i optymalizacje na przykładach Starcraft. W necie znajdziesz 'wykład' na ten temat po angielsku.

P-170403

pekfos

» 2018-03-31 23:31:54

Jeśli cyan to pola które były odwiedzone, ale niekoniecznie należą do ścieżki, to wygląda to poprawnie. Nie wiem jakich cudów się tu spodziewasz. Jeśli A* jest za wolny, to powinieneś użyć lepszego algorytmu.
https://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than
Tu może znajdziesz trochę inspiracji.

P-170404

twoxu

Temat założony przez niniejszego użytkownika

» 2018-04-01 21:03:33

Poprawiłem już ten błąd widoczny na obrazku, jego przyczyną było

allNodes[ l ].A = abs( dx - allNodes[ l ].X ) + abs( ⟶ by ⟵ - allNodes[ l ].Y );
allNodes[ l ].B = abs( bx - allNodes[ l ].X ) + abs( by - allNodes[ l ].Y );

Ale gdy wstawiłem taki kod odpowiedzialny za wypełnienie foundPath

if( surroundingNodes[ a ].X == beginningNode->X && surroundingNodes[ a ].Y == beginningNode->Y )
{
cout << "Path has been found!!Nodes:" << foundPath.size() << endl;
abDebug.saveToFile( "debug.png" );
foundPath.push_back( sf::Vector2i( allNodes[ surroundingNodes[ a ].i ].X, allNodes[ surroundingNodes[ a ].i ].Y ) );

//NOW trace back the path and then return it.
currentNode = & allNodes[ surroundingNodes[ a ].i ];
while( currentNode != beginningNode )
{

//currentNode = &allNodes[currentNode->parent];
//cout << currentNode->parent;
foundPath.push_back( sf::Vector2i( currentNode->X, currentNode->Y ) ); //163 linia z błędem
currentNode = & allNodes[ currentNode->parent ];
}
viewPath( foundPath, abDebug );
return foundPath;

}

Debugger wywala mi SIGSEGV segmentation fault na linii 163 (zaznaczone komentarzem). Google twierdzą że oznacza to że odwołuję się do pamięci która nie jest przeznaczona dla mojego programu. Jakieś porady? Z góry dzięki.

P-170407

pekfos

» 2018-04-01 21:25:14

Jakieś porady?

Zrób z debuggera lepszy użytek niż tylko uruchomienie go. Dowiedziałeś się tyle co nic.

P-170408

twoxu

Temat założony przez niniejszego użytkownika

» 2018-04-01 22:06:33

Segmentation fault naprawiłem przydzielając od nowa wartość parent dla finalnego Node, bo nie miał jej przydzielonej.
Odpaliłem debuggera jeszcze raz i tym razem nie wywaliło (choć program się zaciął), a w Call stack znalazłem takie informacje:

#0 0x405df0 __cxa_throw () (??:??)
#1 0x404c26 operator new(unsigned int) () (??:??)
#2 0x488fd8 typeinfo for std::time_put<wchar_t, std::ostreambuf_iterator<wchar_t, std::char_traits<wchar_t> > > () (??:??)
#3 0x40bd20 std::bad_alloc::what() const () (??:??)
#4 0x767c8cd5 msvcrt!atan2() (C:\Windows\syswow64\msvcrt.dll:??)
#5 0x81f6442d ?? () (??:??)
#6 0xfffffffe ?? () (??:??)
#7 0x8000000 ?? () (??:??)
#8 0x4770bf allocate(this=0x28e624, __n=134217728) (D:/Pliki programow/Dev-Cpp/CodeBlocks/MinGW/lib/gcc/mingw32/4.9.2/include/c++/ext/new_allocator.h:104)
#9 ?? allocate (__a=..., __n=134217728) (D:/Pliki programow/Dev-Cpp/CodeBlocks/MinGW/lib/gcc/mingw32/4.9.2/include/c++/bits/alloc_traits.h:357)
#10 ?? _M_allocate (this=0x28e624, __n=134217728) (D:/Pliki programow/Dev-Cpp/CodeBlocks/MinGW/lib/gcc/mingw32/4.9.2/include/c++/bits/stl_vector.h:170)
#11 ?? std::vector<sf::Vector2<int>, std::allocator<sf::Vector2<int> > >::_M_emplace_back_aux<sf::Vector2<int> >(sf::Vector2<int>&&) (this=0x28e624) (D:/Pliki programow/Dev-Cpp/CodeBlocks/MinGW/lib/gcc/mingw32/4.9.2/include/c++/bits/vector.tcc:412)
#12 0x477072 std::vector<sf::Vector2<int>, std::allocator<sf::Vector2<int> > >::emplace_back<sf::Vector2<int> >(sf::Vector2<int>&&) (this=this@entry=0x28e624) (D:/Pliki programow/Dev-Cpp/CodeBlocks/MinGW/lib/gcc/mingw32/4.9.2/include/c++/bits/vector.tcc:101)
#13 0x4031c8 push_back(__x=<unknown type in --adres--bin\Debug\ProjektRPG.exe, CU 0x74303, DIE 0x93ff7>, this=<optimized out>) (D:/Pliki programow/Dev-Cpp/CodeBlocks/MinGW/lib/gcc/mingw32/4.9.2/include/c++/bits/stl_vector.h:932)
#14 ?? _fu21___ZN2sf5Color4CyanE () (--adres--pathfind.cpp:163)
#15 0x47fe54 _fu14___ZN2sf5Color11TransparentE() (--adres--main.cpp:91)

To pierwszy raz gdy korzystam z tego, wcześniej nie było potrzeby i nie wiem zbytnio co to jest.

P-170409

pekfos

» 2018-04-02 13:26:00

_{» Kurs C++ » Poziom X ♦}Debugowanie w Visual Studio 2017^lekcja Kurs debugowania w 5 minut, na przykładzie VS2017. Jak chcesz by ktoś stąd szukał błędu, podaj przynajmniej aktualny kod. Najlepiej na tyle kompletny, by dało się go przetestować.

P-170410

twoxu

Temat założony przez niniejszego użytkownika

» 2018-04-02 18:02:22

Już wiem mniej więcej o co chodzi, mianowicie niektóre Node mają wartość 'parent' wykraczającą poza zakres.
Nie wiem jak to się dzieje, ponieważ wszystkie Node obecne w surroundingNodes mają przydzieloną wartość 'parent' równą z i Node 'rodzica' jeszcze zanim zostaną do niej dodane (w funkcji getSurroundingNodes).

#include <SFML/Graphics.hpp>
#include <iostream>
#include <math.h>
#include <algorithm>

#include "other_definitions.h"
#include "actor_definitions.h"

using namespace std;

//A-Cost of moving from the destination
//B-Cost of moving from the beginning
//C-Combined cost (A+B) of moving from beginning
//X-Pos X
//Y-Pos Y

//Searching will occur from destination to beginning, to make path positions saved in vector<sf::Vector2i> to be in correct order.
sf::Image abDebug;

class Node
{
public:
int i; //Index in allNodes
float A;
float B;
int C = 1;
int X;
int Y;
int parent; //Index in allNodes of parent. equals to X*Y
bool used = false;
bool isOpen = false;
};

vector < Node > allNodes;
vector < Node > openNodes;

Node getNode( int x, int y, sf::Image col )
{
std::cout << "Trying to get a Node" << x << " " << y << " " << col.getSize().x << " " << col.getSize().y << std::endl;
for( int a = 0; a <= col.getSize().x * col.getSize().y; a++ )
{
if( allNodes[ a ].X == x && allNodes[ a ].Y == y )
{
std::cout << "Found a node!\n";
return allNodes[ a ];
}
}

std::cout << "Couldnt return a Node!\n";
}

vector < Node > getSurroundingNodes( Node & n, sf::Image col )
{
vector < Node > surroundingNodes;
if( !n.used )
for( int a = 0; a < col.getSize().x * col.getSize().y; a++ )
if( allNodes[ a ].X >= n.X - 1 && allNodes[ a ].X <= n.X + 1 && allNodes[ a ].Y >= n.Y - 1 && allNodes[ a ].Y <= n.Y + 1 ) // && allNodes[a].X !=n.X && allNodes[a].Y != n.Y)
{
if( col.getPixel( allNodes[ a ].X, allNodes[ a ].Y ) != sf::Color( 0, 0, 255, 255 ) ) //&&!allNodes[a].used)
{
Node sr;
sr = allNodes[ a ];
sr.i = allNodes[ a ].i;
sr.parent = n.i;
surroundingNodes.push_back( sr );
n.used = true;
}
}
return surroundingNodes;
}
void viewPath( vector < sf::Vector2i > path, sf::Image & output )
{
for( int i = 0; i < path.size(); i++ )
{
output.setPixel( path[ i ].x, path[ i ].y, sf::Color( 0, 255, 255, 255 ) );
}
output.saveToFile( "debug.png" );
}
bool compC( const Node & n1, const Node & n2 )
{
return allNodes[ n1.i ].C < allNodes[ n2.i ].C;
}
vector < sf::Vector2i > Pathfind( int bx, int by, int dx, int dy ) //bx,by - beginning x and y coords || dx,dy - destination x and y coords
{
std::cout << "Started Pathfinding" << std::endl;
vector < sf::Vector2i > foundPath;
sf::Image col;
//Firstly, assign all nodes to a Vector.
col = maps[ currentMap ].colImage;
for( int z = 0; z < col.getSize().x; z++ )
{
for( int q = 0; q < col.getSize().y; q++ )
{
Node n;
n.X = z;
n.Y = q;
n.i = allNodes.size();
allNodes.push_back( n );
}
}
std::cout << "Nodes assigned to Vector" << std::endl;
//Now, calculate A and B values for all nodes.
for( int l = 0; l < allNodes.size(); l++ )
{
//allNodes[l].A = abs(dx-allNodes[l].X) + abs(dy-allNodes[l].Y); //MANHATTAN METHOD
//allNodes[l].B = abs(bx-allNodes[l].X) + abs(by-allNodes[l].Y);
allNodes[ l ].A = sqrt( pow( dx - allNodes[ l ].X, 2 ) + pow( dy - allNodes[ l ].Y, 2 ) ); //EUCLIDEAN METHOD
allNodes[ l ].B = sqrt( pow( bx - allNodes[ l ].X, 2 ) + pow( by - allNodes[ l ].Y, 2 ) );
}

std::cout << "A and B values for all vectors calculated" << std::endl;
sf::Image abDebug;
abDebug.create( col.getSize().x, col.getSize().y, sf::Color::Black );
for( int k = 0; k < allNodes.size(); k++ )
{
abDebug.setPixel( allNodes[ k ].X, allNodes[ k ].Y, sf::Color( allNodes[ k ].A / 5, allNodes[ k ].B / 5, 0, 255 ) );
if( col.getPixel( allNodes[ k ].X, allNodes[ k ].Y ) == sf::Color( 0, 0, 255, 255 ) )
abDebug.setPixel( allNodes[ k ].X, allNodes[ k ].Y, sf::Color::White );

}
abDebug.saveToFile( "debug.png" );
std::cout << "Collisions have been applied to Vector" << std::endl;
//Create pointers to beginning and destination nodes
Node * beginningNode;
Node b = getNode( bx, by, col );
Node * destinationNode;
Node d = getNode( dx, dy, col );
beginningNode = & b;
destinationNode = & d;
std::cout << "Assigned beg and dest nodes." << std::endl;
//Now, start checking from the destination.
Node * currentNode;
destinationNode->C = destinationNode->A + destinationNode->B;
currentNode = destinationNode;
currentNode->isOpen = true;
openNodes.push_back( * currentNode );
cout << "--" << openNodes.size() << endl;
cout << currentNode->C << endl;
while( !openNodes.empty() )
{
sort( openNodes.begin(), openNodes.end(), compC );
* currentNode = openNodes[ 0 ];
openNodes.erase( openNodes.begin() + 0 );
vector < Node > surroundingNodes;
surroundingNodes = getSurroundingNodes( * currentNode, col );
if( !surroundingNodes.empty() )
{
for( int a = 0; a < surroundingNodes.size(); a++ )
{
allNodes[ surroundingNodes[ a ].i ].C = allNodes[ surroundingNodes[ a ].i ].B + allNodes[ surroundingNodes[ a ].i ].A;
if( surroundingNodes[ a ].X == beginningNode->X && surroundingNodes[ a ].Y == beginningNode->Y )
{
cout << "Path has been found!!Nodes:" << foundPath.size() << endl;
allNodes[ surroundingNodes[ a ].i ].parent = currentNode->i;
abDebug.saveToFile( "debug.png" );
foundPath.push_back( sf::Vector2i( allNodes[ surroundingNodes[ a ].i ].X, allNodes[ surroundingNodes[ a ].i ].Y ) );
//NOW trace back the path and then return it.
//*currentNode = allNodes[surroundingNodes[a].i];
* currentNode = allNodes[ surroundingNodes[ a ].i ];
while( currentNode != beginningNode )
{

//currentNode = &allNodes[currentNode->parent];
//cout << currentNode->parent;
sf::Vector2i n;
n.x = currentNode->X;
n.y = currentNode->Y;
foundPath.push_back( n );
* currentNode = allNodes[ currentNode->parent ]; //tutaj program się wywala
}
viewPath( foundPath, abDebug );
return foundPath;
}
if( !allNodes[ surroundingNodes[ a ].i ].isOpen )
{
allNodes[ surroundingNodes[ a ].i ].isOpen = true;
//allNodes[surroundingNodes[a].i].parent = currentNode->i;
abDebug.setPixel( surroundingNodes[ a ].X, surroundingNodes[ a ].Y, sf::Color::Cyan );
openNodes.push_back( allNodes[ surroundingNodes[ a ].i ] );
}
}
}
//abDebug.saveToFile("debug.png");
}
abDebug.saveToFile( "debug.png" );
}

P-170411

« 1 » 2 3

Strona 1 z 3

Następna strona

» Forum » Programowanie » [C, C++] Szukam pomocy

Regulamin

© Wszelkie prawa zastrzeżone 2005-2024