tBane Temat założony przez niniejszego użytkownika |
» 2024-05-14 18:49:21 Coś słabo mi to zrozumienie idzie :-/ Przepisałem funkcję po swojemu i nie działa std::vector < Point > getNeighbors( const Point & p, const std::vector < std::vector < bool >> & map ) { std::vector < Point > neighbors; if( p.y - 1 >= 0 ) { if( p.x - 1 >= 0 && map[ p.x - 1 ][ p.y - 1 ] ) neighbors.push_back( Point( p.x - 1, p.y - 1 ) ); if( p.x + 1 < map.size() && map[ p.x + 1 ][ p.y - 1 ] ) neighbors.push_back( Point( p.x + 1, p.y - 1 ) ); } if( p.y + 1 < map.size() ) { if( p.x - 1 >= 0 && map[ p.x - 1 ][ p.y + 1 ] ) neighbors.push_back( Point( p.x - 1, p.y + 1 ) ); if( p.x + 1 < map.size() && map[ p.x + 1 ][ p.y + 1 ] ) neighbors.push_back( Point( p.x + 1, p.y + 1 ) ); } return neighbors; }
|
|
tBane Temat założony przez niniejszego użytkownika |
» 2024-05-14 19:35:24 Generalnie to chcę tak zmodyfikować kod, żeby kroki były w odstępach 100 jednostek std::vector < Point > getNeighbors( const Point & p ) { std::vector < Point > neighbors; neighbors.emplace_back( p.x - 100, p.y ); neighbors.emplace_back( p.x + 100, p.y ); neighbors.emplace_back( p.x, p.y - 100 ); neighbors.emplace_back( p.x, p.y + 100 ); return neighbors; }
|
|
tBane Temat założony przez niniejszego użytkownika |
» 2024-05-14 20:08:25 No więc udało mi się zmienić algorytm - teraz szuka drogi z jednego punktu do drugiego, krok co 100 jednostek. Wydaje się poprawny :-) cursor at 119 571 Path: (400, 400) (300, 400) (200, 400) (200, 500) (119, 571) #include <iostream> #include <vector> #include <queue> #include <unordered_map> #include <algorithm>
float stepsize = 100.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( 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 ); return neighbors; } std::vector < Point > aStar( const Point & start, const Point & goal ) { 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( abs( current.x - goal.x ) < stepsize && abs( 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( 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 { }; }
|
|
1 « 2 » |