Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Algorytm szukania drogi

Ostatnio zmodyfikowano 2024-05-14 20:08
Autor Wiadomość
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

C/C++
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;
}
P-181080
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

C/C++
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;
}
P-181081
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)
C/C++
#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 ) { // HERE EDITED
           
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 { }; // No path found
}
P-181082
1 « 2 »
Poprzednia strona Strona 2 z 2