tBane Temat założony przez niniejszego użytkownika |
Pathfinding - Podążanie wyznaczoną ścieżką » 2024-09-05 19:35:06 Witam. Próbuję napisać algorytm podążania ścieżką, ale coś mi nie wychodzi. Nie wiem gdzie popełniłem błąd. Algorytm wyrzuca błąd: Expression: vector subscript out of rangevoid loadTheTarget() { target.x = base.x + rand() % 200 - 100; target.y = base.y + rand() % 200 - 100; cout << "Load the target: [" << target.x << "," << target.y << "]\n"; }
void loadThePath() { Point goal = Point( target.x, target.y ); path = aStar( this, goal ); cout << "monster: " << name << "\n"; cout << "position: [" << position.x << "," << position.y << "]\n"; cout << "path(" << path.size() << ") : "; for( auto & p: path ) cout << "[" << p.x << "," << p.y << "] "; cout << "\n"; }
void followThePath( float dt ) { float dist = 15.0f * 4.0f * dt; if( position.x == target.x && position.y == target.y ) { loadTheTarget(); loadThePath(); } else if( position.x != target.x && fabs( target.x - position.x ) < dist ) { position.x = target.x; } else if( position.y != target.y && fabs( target.y - position.y ) < dist ) { position.y = target.y; } else if( position.x == path[ 0 ].x && position.y == path[ 0 ].y ) { path.erase( path.begin() ); } else if( position.x != path[ 0 ].x && fabs( path[ 0 ].x - position.x ) < dist ) { position.x = path[ 0 ].x; } else if( position.y != path[ 0 ].y && fabs( path[ 0 ].y - position.y ) < dist ) { position.y = path[ 0 ].y; } else if( path[ 0 ].x < position.x ) { position.x -= dist; } else if( path[ 0 ].x > position.x ) { position.x += dist; } else if( path[ 0 ].y < position.y ) { position.y -= dist; } else if( path[ 0 ].y > position.y ) { position.y += dist; } }
|
|
tBane Temat założony przez niniejszego użytkownika |
» 2024-09-05 19:56:55 Wszystko już działa. Sorki za zaśmiecanie forum :-/ void followThePath( float dt ) { float dist = 15.0f * 4.0f * dt; if( position.x == target.x && position.y == target.y ) { loadTheTarget(); loadThePath(); } else if( position.x == path[ 0 ].x && position.y == path[ 0 ].y ) { path.erase( path.begin() ); } else if( position.x != path[ 0 ].x && fabs( path[ 0 ].x - position.x ) < dist ) { position.x = path[ 0 ].x; } else if( position.y != path[ 0 ].y && fabs( path[ 0 ].y - position.y ) < dist ) { position.y = path[ 0 ].y; } else if( path[ 0 ].x < position.x ) { position.x -= dist; } else if( path[ 0 ].x > position.x ) { position.x += dist; } else if( path[ 0 ].y < position.y ) { position.y -= dist; } else if( path[ 0 ].y > position.y ) { position.y += dist; } }
|
|
tBane Temat założony przez niniejszego użytkownika |
» 2024-09-05 20:18:34 Jednak nie działa. Potrzebowałbym, by ktoś bardziej doświadczony spojrzał na kod pathfindingu, gdyż ja tego kodu za bardzo nie rozumiem. Tylko dopisałem kolizje (collisionPrediction). Błąd objawia się tym, że algorytm pathfindingu pozwala na przechodzenie przez drzewa, a gdy dopiszę collisionPrediction do pathfindingu to zawiesza program. #ifndef Pathfinding_hpp #define Pathfinding_hpp
#include <iostream> #include <vector> #include <queue> #include <unordered_map> #include <algorithm>
float stepsize = 32.0f;
class Point { public: float x, y; Point() : x( 0 ) , y( 0 ) { } Point( float x, float y ) : x( x ) , y( y ) { } bool operator ==( const Point & other ) const { return x == other.x && y == other.y; } bool operator !=( const Point & other ) const { return x != other.x || y != other.y; } bool operator <( const Point & other ) const { return std::tie( x, y ) < std::tie( other.x, other.y ); } };
namespace std { template < > struct hash < Point > { size_t operator()( const Point & p ) const { return hash < float >()( p.x ) ^ hash < float >()( p.y ); } }; }
float heuristic( const Point & a, const Point & b ) { return abs( a.x - b.x ) + abs( a.y - b.y ); }
std::vector < Point > getNeighbors( GameObject * object, const Point & p ) { std::vector < Point > neighbors; neighbors.emplace_back( p.x - stepsize, p.y ); neighbors.emplace_back( p.x + stepsize, p.y ); neighbors.emplace_back( p.x, p.y - stepsize ); neighbors.emplace_back( p.x, p.y + stepsize ); neighbors.emplace_back( p.x - stepsize, p.y - stepsize ); neighbors.emplace_back( p.x - stepsize, p.y + stepsize ); neighbors.emplace_back( p.x + stepsize, p.y - stepsize ); neighbors.emplace_back( p.x + stepsize, p.y + stepsize ); return neighbors; }
std::vector < Point > aStar( GameObject * object, const Point & goal ) { const Point & start = Point( object->position.x, object->position.y ); std::priority_queue < std::pair < float, Point >, std::vector < std::pair < float, Point >>, std::greater < >> openSet; std::unordered_map < Point, Point > cameFrom; std::unordered_map < Point, int > costSoFar; openSet.emplace( 0, start ); cameFrom[ start ] = start; costSoFar[ start ] = 0; while( !openSet.empty() ) { Point current = openSet.top().second; openSet.pop(); if( current == goal ) { std::vector < Point > path; while( current != start ) { path.push_back( current ); current = cameFrom[ current ]; } path.push_back( start ); std::reverse( path.begin(), path.end() ); return path; } else if( fabs( current.x - goal.x ) < stepsize && fabs( current.y - goal.y ) < stepsize ) { Point next = Point( goal.x, goal.y ); float newCost = costSoFar[ current ] + 1; if( costSoFar.find( next ) == costSoFar.end() || newCost < costSoFar[ next ] ) { costSoFar[ next ] = newCost; float priority = newCost + heuristic( next, goal ); openSet.emplace( priority, next ); cameFrom[ next ] = current; } } else { for( const Point & next: getNeighbors( object, current ) ) { float newCost = costSoFar[ current ] + 1; if( costSoFar.find( next ) == costSoFar.end() || newCost < costSoFar[ next ] ) { costSoFar[ next ] = newCost; float priority = newCost + heuristic( next, goal ); openSet.emplace( priority, next ); cameFrom[ next ] = current; } } } } return { }; } #endif
Mam do dyspozycji funkcję sprawdzającą czy wystąpią kolizje dla danego obiektu po przesunięciu bool collisionPrediction(GameObject* object, float dx, float dy) |
|
pekfos |
» 2024-09-05 21:42:09 Nie wiem czym jest tu collisionPrediction, ale nie bardzo widzę mechanizm którym miałoby to się zawiesić. Zawsze gdy rozważasz pozycję na mapie, sprawdzasz kolizje dla jej 8-sądziedztwa i test kolizji pewnie leci po wszystkich obiektach, więc pewnie jest to po prostu bardzo wolne. Uzbrój się w cierpliwość i zmierz czas, potem zastanów się nad zoptymalizowaniem detekcji kolizji. |
|
tBane Temat założony przez niniejszego użytkownika |
» 2024-09-05 21:51:10 Po 61.6387s sekundach zrezygnowałem, to nie powinno tak powoli działać. Mnie się wydaje, że algorytm nie może w jakiś sposób dojść do targetu. Mogę rozwiązać ten problem w taki sposób, że generuje ścieżkę bez kolizji i gdy potwór idzie wyznaczoną ścieżką to sprawdza na bieżąco kolizje i gdy taką wykryje, wtedy szuka nowego targetu i nowej ścieżki. Ale to nie rozwiązuje problemu "szukania ścieżki z ominięciem drzew" |
|
pekfos |
» 2024-09-05 22:04:36 To daj limit 500 iteracji na potrzeby benchmarka. Zmierz czas z i bez kolizji. Algorytm ma skończoną liczbę iteracji, bo openSet się musi wyczerpać, bo dodajesz do niego tylko niesprawdzone pozycje, lub o nowym i lepszym wyniku. Nie możesz w nieskończoność poprawiać trasy, ani nie masz nieskończonej liczby możliwych pozycji. |
|
tBane Temat założony przez niniejszego użytkownika |
» 2024-09-05 22:30:36 Dodałem limit czasowy na generowanie ścieżki wynoszący 1 sekundę. Ale i tak wywala co jakiś czas z powodu: monster: monsters/dziobak Load the target: [1323,796] position: [1208,656] path(0) : time: 0.102018s Expression: vector subscript out of range monster: monsters/bies Load the target: [411,1303] position: [282,1330] path(0) : time: 0.117392s
monster: monsters/bies Load the target: [414,1300] position: [282,1330] path(0) : time: 0.141749s Expression: vector subscript out of range Tu kod jak napisałem ten limit: while( !openSet.empty() ) { Point current = openSet.top().second; openSet.pop(); if(( timeClock.getElapsedTime() - starttime ).asSeconds() > 1.0f ) { return { }; } if( current == goal ) { std::vector < Point > path; while( current != start ) { path.push_back( current ); current = cameFrom[ current ]; } path.push_back( start ); std::reverse( path.begin(), path.end() ); return path; } else if( fabs( current.x - goal.x ) < stepsize && fabs( current.y - goal.y ) < stepsize ) { Point next = Point( goal.x, goal.y ); float newCost = costSoFar[ current ] + 1; if( costSoFar.find( next ) == costSoFar.end() || newCost < costSoFar[ next ] ) { costSoFar[ next ] = newCost; float priority = newCost + heuristic( next, goal ); openSet.emplace( priority, next ); cameFrom[ next ] = current; } } else { for( const Point & next: getNeighbors( object, current ) ) { float newCost = costSoFar[ current ] + 1; if( costSoFar.find( next ) == costSoFar.end() || newCost < costSoFar[ next ] ) { costSoFar[ next ] = newCost; float priority = newCost + heuristic( next, goal ); openSet.emplace( priority, next ); cameFrom[ next ] = current; } } } }
return { }; }
Jak wyłączam kolizje to wtedy program sie nie wysypuje: std::vector < Point > getNeighbors( GameObject * object, const Point & p ) { std::vector < Point > neighbors; neighbors.emplace_back( p.x - stepsize, p.y ); neighbors.emplace_back( p.x + stepsize, p.y ); neighbors.emplace_back( p.x, p.y - stepsize ); neighbors.emplace_back( p.x, p.y + stepsize ); neighbors.emplace_back( p.x - stepsize, p.y - stepsize ); neighbors.emplace_back( p.x - stepsize, p.y + stepsize ); neighbors.emplace_back( p.x + stepsize, p.y - stepsize ); neighbors.emplace_back( p.x + stepsize, p.y + stepsize ); return neighbors; }
// edit - wtedy też się program wysypuje z powodu: Expression: vector subscript out of range |
|
pekfos |
» 2024-09-05 23:07:48 Dodałem limit czasowy na generowanie ścieżki wynoszący 1 sekundę. No i co niby chcesz tym osiągnąć? Nie to miałeś zrobić. Expression: vector subscript out of range Bo pewnie nie sprawdzasz czy dostałeś niepustą ścieżkę. Po co w ogóle o tym tu piszesz? Możesz to po prostu sprawdzić debuggerem. |
|
« 1 » 2 |