[c,c++] algorytm A*
Logowanie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zapomniałem hasła
» Forum » Programowanie » [C, C++] Szukam pomocy

[c,c++] algorytm A*

Ostatnio zmodyfikowano 2017-03-01 16:04
Autor Wiadomość
aaadam
Temat założony przez niniejszego użytkownika
[c,c++] algorytm A*
» 2017-02-10 16:37:56
Witaj, próbuję napisać algorytm A*, czytam sobię ten artykuł : http://www.policyalmanac.org/games/aStarTutorial_pl.htm, mam pytanie co do tego:     'Szukamy wszystkich osiągalnych pól oznaczonych jako MOŻNA, przyległych do pola startowego (pkt. A), ignorując te z murami, wodą lub inne oznaczone jako NIE-MOŻNA. Dodajemy je do Listy Otwartych. Dla każdego z tych pól zachowujemy pkt. A jako "pole rodzica". To działanie jest ważne ze względu na możliwość podążania po wyznaczonej ścieżce, co zostanie wyjaśnione później.'
nie za bardzo wiem jak to zaimplementować żeby każdy element pamiętał swojego poprzednika, jak tak będę dodawał i dodawał nowych potomków to zrobi mi się mnustwo list, nie wiem jak ma być zrobione te zapamiętywanie potomków. Może ktoś poradzić jak to powinno być zaimplementowane?
Pozdrawiam
to kawałek mojego kodu na którym stanąłem
ten wektor Vector2i  to poprostu pojemnik na zmienną x oraz y wzięte z smfl
C/C++
class tile
{
    enum states { notAvailable = 0, available = 1 };
public:
    Vector2i parent;
    tile( int x, int y, int state )
    {
        this->x = x;
        this->y = y;
        this->state = state;
    }
    tile( int x, int y, int state, Vector2i parent )
    {
        this->parent = parent;
        this->x = x;
        this->y = y;
        this->state = state;
    }
    int x, y;
    int state;
};




int findPath( Vector2i start, Vector2i end )
{
    if( start == end )
    {
        cout << "path found 'start' and 'end' are equal";
        return 0;
    }
   
    list < tile > open_list;
   
   
    open_list.push_back( tile( start.x, start.y, 0, start ) );
   
   
   
   
   
   
    cout << "path not found";
    return - 1;
}
//to moja mapa :
vector < vector < tile >> map1;
void Loadmap1( const char * fileName )
{
   
    fstream openfile( fileName );
   
    tempmap.clear();
    map1.clear();
   
   
    if( openfile.is_open() )
    {
        string value;
        int i = 0;
        while( getline( openfile, value ) )
        {
           
            for( int j = 0; j < value.length(); j++ )
            {
                if( isdigit( value[ j ] ) )
                {
                    tempmap.push_back( tile( i, j, value[ j ] - 48 ) ); // czytam z pliku txt i musze przekonwertować znaki asci dlatego -48
                }
            }
            value.clear();
            map1.push_back( tempmap );
            tempmap.clear();
            i++;
        }
    }
    openfile.close();
}
P-157576
Nazgul
» 2017-02-10 17:51:56
Nie jestem pewien, nie znam tego algorytmu
Ale tam nie ma wpisanego, że pole rodzica idzie do listy 'zamkniętych pól'? to by znaczyło, że wszystkie pola ('węzły') mają jedną i tę samą listę

Można chyba zamienić kolejnością i wtedy nie będzie tego problemu:

1 Dodajemy do listy otwartych wszystkie pola wokół A pamiętając A jako rodzica
2 Usuwamy A z otwartych, dodajemy do zamkniętych

tak jakbyśmy zamienili powyższy proces na

1 Usuwamy A z otwartych, dodajemy do zamkniętych
2 Dodajemy do listy otwartych wszystkie pola wokół A JUŻ NIE TRZEBA PAMIĘTAĆ 'A' JAKO RODZICA, JUŻ JEST OZNACZONE JAKO POLE KTÓREGO SIĘ NIE SPRAWDZA

możliwe jednak że w samej implementacji ta zamiana jest niemożliwa/niezoptymalizowana/cokolwiek i dlatego bardziej opłaca się wpisać tam tego rodzica

Zaznaczam, że mogę się mylić
P-157578
michal11
» 2017-02-11 00:10:41
Nie wiem do końca czy ci to pomoże, ale wkleję swoją implementację tego algorytmu (niestety nie pamiętam skąd brałem opis do tego)
C/C++
bool canFind( const Board & board, const sf::Vector2i & StartPosition )
{
    makeCopy( board );
    mValueParameter = - 1;
   
    sf::Vector2i chosenFieldPosition( FieldManager::getInstance().getChosenFieldPosition() );
    mWorkingBoard[ chosenFieldPosition.x ][ chosenFieldPosition.y ] = 9;
   
    mWorkingBoard[ StartPosition.x ][ StartPosition.y ] = mValueParameter;
    --mValueParameter;
   
    std::queue < sf::Vector2u > pointsList;
   
    pointsList.push( actualPosition );
   
    unsigned int pointsListSize = 0;
   
    while( pointsList.size() != 0 )
    {
        pointsListSize = pointsList.size();
       
        for( unsigned int i = 0; i < pointsListSize; ++i )
        {
            actualPosition = pointsList.front();
            pointsList.pop();
           
            if( mWorkingBoard[ actualPosition.x + 1 ][ actualPosition.y ] == 2 ) // found exit on right field
            {
                return true;
            }
            else if( mWorkingBoard[ actualPosition.x + 1 ][ actualPosition.y ] == 0 ) // right field
            {
                mWorkingBoard[ actualPosition.x + 1 ][ actualPosition.y ] = mValueParameter;
                pointsList.push( sf::Vector2u( actualPosition.x + 1, actualPosition.y ) );
            }
           
            if( mWorkingBoard[ actualPosition.x ][ actualPosition.y + 1 ] == 0 ) // down field
            {
                mWorkingBoard[ actualPosition.x ][ actualPosition.y + 1 ] = mValueParameter;
                pointsList.push( sf::Vector2u( actualPosition.x, actualPosition.y + 1 ) );
            }
           
            if( mWorkingBoard[ actualPosition.x ][ actualPosition.y - 1 ] == 0 ) // up field
            {
                mWorkingBoard[ actualPosition.x ][ actualPosition.y - 1 ] = mValueParameter;
                pointsList.push( sf::Vector2u( actualPosition.x, actualPosition.y - 1 ) );
            }
           
            if( actualPosition.x > 1 )
            {
                if( mWorkingBoard[ actualPosition.x - 1 ][ actualPosition.y ] == 0 ) // left field
                {
                    mWorkingBoard[ actualPosition.x - 1 ][ actualPosition.y ] = mValueParameter;
                    pointsList.push( sf::Vector2u( actualPosition.x - 1, actualPosition.y ) );
                }
            }
        }
        --mValueParameter;
    }
   
    return false;
}

z tym, że ja nie operowałem na enumach a na intach i założenie było takie, że pole 0 na boardzie jest wolne, 1 to ściana, 2 to exit a 9 to chyba początek.

makeCopy( board );
 po prostu robi sobie kopię roboczą tak aby później wyciągnąć listę kroków.
FieldManager::getInstance().getChosenFieldPosition()
 zwracało pozycje którą chcemy zablokować (ponieważ funkcja sprawdza czy można znaleźć ścieżkę od startu do końca blokując dany punkt).
Jeszcze jedna istotna sprawa to założenie było takie, że labirynt początek ma na lewej krawędzi a koniec na prawej i od początku musi istnieć ścieżka od początku do końca.

reszta funkcji jest chyba jasna, wkleję jeszcze algorytm do zbierania listy kroków jak już znaleziono ścieżkę
C/C++
void fillStepsList( std::stack < sf::Vector2i >& StepsList, int index )
{
    //empty steps list
    while( !StepsList.empty() )
    {
        StepsList.pop();
    }
   
    StepsList.push( mExitPosition );
    ++mValueParameter;
   
    sf::Vector2i actualPosition( mExitPosition );
   
    while( mValueParameter != - 1 )
    {
        if( mWorkingBoard[ actualPosition.x - 1 ][ actualPosition.y ] == mValueParameter ) //left
        {
            actualPosition.x -= 1;
            StepsList.push( actualPosition );
        }
        else if( mWorkingBoard[ actualPosition.x + 1 ][ actualPosition.y ] == mValueParameter ) //right
        {
            actualPosition.x += 1;
            StepsList.push( actualPosition );
        }
        else if( mWorkingBoard[ actualPosition.x ][ actualPosition.y - 1 ] == mValueParameter ) //up
        {
            actualPosition.y -= 1;
            StepsList.push( actualPosition );
        }
        else if( mWorkingBoard[ actualPosition.x ][ actualPosition.y + 1 ] == mValueParameter ) //down
        {
            actualPosition.y += 1;
            StepsList.push( actualPosition );
        }
        ++mValueParameter;
    }
}

mExitPosition
 było cachowane na kopiowaniu całej mapy, reszta powinna być jasna.
P-157595
aaadam
Temat założony przez niniejszego użytkownika
» 2017-02-21 15:11:44
hej, mam już dużą część tego algorytmu, mam teraz Problem z tym :
"
·       Jeśli pole (Xn) było już na Liście Otwartych, sprawdzamy czy aktualna ścieżka do tego pola (Xn) (prowadząca przez Z) jest lepsza (krótsza), poprzez porównanie jego (Xn) wartości G dla starej i aktualnej ścieżki. Mniejsza wartość G oznacza, że ścieżka jest krótsza. Jeśli tak, zmieniamy przypisanie “pole rodzica” na aktualne pole (Z) i przeliczamy wartości G i F dla pola (Xn). Jeśli wasza Lista Otwartych jest posortowana pod kątem wartości F, trzeba ją ponownie przesortować po wprowadzonej zmianie.
"

zastanawiam się jak to zaimplementować i jakoś nie mogę wpaść na optymalne rozwiązanie.
Jeżeli ktoś ma czas i chęć to proszę o przeanalizowanie kodu i podpowiedz co można było zrobić lepiej.

standardowa mapa wygląda tak (wczytywana z pliku ):
9 to punkt koncowy 8 początkowy
11111111
10000001
10001001
18001901
10001001
11000011
10000011
11111111

do wyswietlania mapy stworzylem prosty obrazek o szerokosciach 160 na 80, jeden kafelek ma rozmiar 40 px
wciśnięcie klawisza l wywołuje kolejny krok algorytmu
a o to kod :
C/C++
#include <SFML/Graphics.hpp>
#include <string>
#include <iostream>
#include <fstream>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <list>
using namespace sf;
using namespace std;
enum waga { horizontal = 10, oblique = 14 };
enum states { available = 0, notAvailable = 1, veryfied = 11 };
class tile
{
   
public:
    Vector2i parent;
    tile() { }
    tile( int x, int y )
    {
        this->x = x;
        this->y = y;
       
    }
    tile( int x, int y, int state )
    {
        this->x = x;
        this->y = y;
        this->state = state;
       
    }
    tile( int x, int y, int state, Vector2i parent, int hyst )
    {
        this->parent = parent;
        this->x = x;
        this->y = y;
        this->state = state;
        this->hysteresys = hyst;
       
    }
    int x, y, hysteresys;
   
    int state;
    bool operator ==( const tile & temp )
    {
        return( temp.x == this->x && temp.y == this->y );
    }
   
   
};
bool b_exit = false;
list < tile > open_list;
list < tile > close_list;
vector < tile > tempmap;
Texture tileTexture;
Sprite tiles;
vector < vector < tile >> map1;
void Loadmap1( const char * fileName )
{
    string tileLocation;
    tileLocation = "tiles.png";
    tileTexture.loadFromFile( tileLocation );
    tiles.setTexture( tileTexture );
    fstream openfile( fileName );
    tempmap.clear();
    map1.clear();
    if( openfile.is_open() )
    {
        string value;
        int i = 0;
        while( getline( openfile, value ) )
        {
           
            for( unsigned j = 0; j < value.length(); j++ )
            {
                if( isdigit( value[ j ] ) )
                {
                    tempmap.push_back( tile( i, j, value[ j ] - 48 ) );
                }
            }
            value.clear();
            map1.push_back( tempmap );
            tempmap.clear();
            i++;
        }
    }
    openfile.close();
}

bool check_if_exist_in_closedList( tile node )
{
    for( list < tile >::iterator iter = close_list.begin(); iter != close_list.end(); iter++ )
    {
        if( iter->x == node.x && iter->y == node.y )
             return true;
       
    }
    return false;
}
bool check_if_exist_in_openedList( tile node )
{
    for( list < tile >::iterator iter = open_list.begin(); iter != open_list.end(); iter++ )
    {
        if( iter->x == node.x && iter->y == node.y )
             return true;
       
    }
    return false;
}
void verify_adjacent_nodes( tile node )
{
    //if (node.x == 6 && node.y == 7)
    //cout << "znalazles";
    Vector2i parent;
    tile tmpNode;
    if( map1[ node.x - 1 ][ node.y - 1 ].state == available )
    {
        parent.x = node.x;
        parent.y = node.y;
       
        tmpNode.x = node.x - 1;
        tmpNode.y = node.y - 1;
        if( !check_if_exist_in_openedList( tmpNode ) )
        {
            open_list.push_back( tile( node.x - 1, node.y - 1, available, parent, map1[ node.x - 1 ][ node.y - 1 ].hysteresys + oblique ) );
        }
        //else
        // {
        // int t;
        // t=check_if_exist_in_closedList(tmpNode);
        // }
       
    }
    if( map1[ node.x - 1 ][ node.y ].state == available )
    {
        parent.x = node.x;
        parent.y = node.y;
       
        tmpNode.x = node.x - 1;
        tmpNode.y = node.y;
        if( !check_if_exist_in_openedList( tmpNode ) )
             open_list.push_back( tile( node.x - 1, node.y, available, parent, map1[ node.x - 1 ][ node.y ].hysteresys + horizontal ) );
       
    }
    if( map1[ node.x + 1 ][ node.y - 1 ].state == available )
    {
        parent.x = node.x;
        parent.y = node.y;
       
        tmpNode.x = node.x + 1;
        tmpNode.y = node.y - 1;
        if( !check_if_exist_in_openedList( tmpNode ) )
             open_list.push_back( tile( node.x + 1, node.y - 1, available, parent, map1[ node.x + 1 ][ node.y - 1 ].hysteresys + oblique ) );
       
    }
    if( map1[ node.x ][ node.y - 1 ].state == available )
    {
        parent.x = node.x;
        parent.y = node.y;
        tmpNode.x = node.x;
        tmpNode.y = node.y - 1;
        if( !check_if_exist_in_openedList( tmpNode ) )
             open_list.push_back( tile( node.x, node.y - 1, available, parent, map1[ node.x ][ node.y - 1 ].hysteresys + horizontal ) );
       
    }
    if( map1[ node.x ][ node.y + 1 ].state == available )
    {
        parent.x = node.x;
        parent.y = node.y;
       
        tmpNode.x = node.x;
        tmpNode.y = node.y + 1;
        if( !check_if_exist_in_openedList( tmpNode ) )
             open_list.push_back( tile( node.x, node.y + 1, available, parent, map1[ node.x ][ node.y + 1 ].hysteresys + horizontal ) );
       
    }
    if( map1[ node.x + 1 ][ node.y + 1 ].state == available )
    {
        parent.x = node.x;
        parent.y = node.y;
       
        tmpNode.x = node.x + 1;
        tmpNode.y = node.y + 1;
        if( !check_if_exist_in_openedList( tmpNode ) )
             open_list.push_back( tile( node.x + 1, node.y + 1, available, parent, map1[ node.x + 1 ][ node.y + 1 ].hysteresys + oblique ) );
        //else
        // node.if_was_at_opened_list = true;
    }
    if( map1[ node.x - 1 ][ node.y + 1 ].state == available )
    {
        parent.x = node.x;
        parent.y = node.y;
       
        tmpNode.x = node.x - 1;
        tmpNode.y = node.y + 1;
        if( !check_if_exist_in_openedList( tmpNode ) )
             open_list.push_back( tile( node.x - 1, node.y + 1, available, parent, map1[ node.x - 1 ][ node.y + 1 ].hysteresys + oblique ) );
       
    }
    if( map1[ node.x + 1 ][ node.y ].state == available )
    {
        parent.x = node.x;
        parent.y = node.y;
       
        tmpNode.x = node.x + 1;
        tmpNode.y = node.y;
        if( !check_if_exist_in_openedList( tmpNode ) )
             open_list.push_back( tile( node.x + 1, node.y, available, parent, map1[ node.x + 1 ][ node.y ].hysteresys + horizontal ) );
       
    }
    open_list.remove( node );
   
    if( !check_if_exist_in_closedList( node ) )
         close_list.push_back( node );
   
}

void calculate_histeresys_for_all_nodes( tile end )
{
    cout << end.x << " " << end.y;
    for( unsigned i = 0; i < map1.size(); i++ )
    {
        for( unsigned j = 0; j < map1[ i ].size(); j++ )
        {
            map1[ i ][ j ].hysteresys =( abs( end.x - map1[ i ][ j ].x ) + abs( end.y - map1[ i ][ j ].y ) ) * 10;
        }
    }
}

int findPath( tile start, tile end )
{ //docelowa funkcja jeszcze nie do konca ukonczona
    calculate_histeresys_for_all_nodes( end );
    if( start == end )
    {
        cout << "path found 'start' and 'end' are equal";
        return 0;
    }
    open_list.push_back( start );
    verify_adjacent_nodes( start );
    cout << "path not found";
    return - 1;
}
tile select_node_with_lowest_histeresys()
{
    tile tmp;
    list < tile >::iterator iter = open_list.begin();
    tmp.hysteresys = iter->hysteresys;
    tmp.x = iter->x;
    tmp.y = iter->y;
    tmp.state = iter->state;
    for(; iter != open_list.end(); ++iter )
    {
        if( iter->hysteresys < tmp.hysteresys )
        {
            tmp.hysteresys = iter->hysteresys;
            tmp.x = iter->x;
            tmp.y = iter->y;
            tmp.state = iter->state;
            tmp.parent = iter->parent;
        }
    }
    return tmp;
}
int main()
{
    Loadmap1( "mapfile.txt" );
    Vector2i screenDimensions( 800, 800 );
    RenderWindow window( VideoMode( 800, 600, 32 ), "SFML works!" );
    window.setKeyRepeatEnabled( false );
    for( unsigned i = 0; i < map1.size(); i++ )
    {
        for( unsigned j = 0; j < map1[ i ].size(); j++ )
        {
            cout << map1[ i ][ j ].state;
        }
        cout << endl;
    }
    for( unsigned i = 0; i < map1.size(); i++ )
    {
        for( unsigned j = 0; j < map1[ i ].size(); j++ )
        {
            cout << "xy(" << map1[ i ][ j ].x << ",";
            cout << map1[ i ][ j ].y << "," << map1[ i ][ j ].state << ") ";
        }
        cout << endl;
    }
    findPath( tile( 3, 1, 0, Vector2i( 0, 0 ), map1[ 3 ][ 1 ].hysteresys ), tile( 3, 5, 0, Vector2i( 3, 5 ), map1[ 3 ][ 5 ].hysteresys ) ); //
    cout << endl;
    for( unsigned i = 0; i < map1.size(); i++ )
    {
        for( unsigned j = 0; j < map1[ i ].size(); j++ )
        {
            //map1[i][j].h = abs(map1[i][j].x - end.x) + abs(map1[i][j].y - end.y);
            cout << " [" << i << "][" << j << "] " << map1[ i ][ j ].hysteresys;
        }
        cout << endl;
    }
    for( list < tile >::iterator iter = open_list.begin(); iter != open_list.end(); iter++ )
    {
       
        for( unsigned i = 0; i < map1.size(); i++ )
        {
            for( unsigned j = 0; j < map1[ i ].size(); j++ )
            {
                if(( iter->x == map1[ i ][ j ].x ) &&( iter->y == map1[ i ][ j ].y ) )
                {
                    map1[ i ][ j ].state = 4;
                }
            }
            cout << endl;
        }
       
    }
    for( list < tile >::iterator iter = close_list.begin(); iter != close_list.end(); iter++ )
    {
       
        for( unsigned i = 0; i < map1.size(); i++ )
        {
            for( unsigned j = 0; j < map1[ i ].size(); j++ )
            {
                if(( iter->x == map1[ i ][ j ].x ) &&( iter->y == map1[ i ][ j ].y ) )
                {
                    map1[ i ][ j ].state = 5;
                }
            }
            cout << endl;
        }
       
    }
    while( window.isOpen() )
    {
        Event event;
        while( window.pollEvent( event ) )
        {
            switch( event.type )
            {
            case Event::Closed:
                window.close();
                break;
            case Event::KeyPressed:
                if( event.key.code == Keyboard::L ) //wcisniecie przycisku l wywoluje kolejny krok algorytmu
                {
                    if( open_list.size() > 0 || b_exit )
                    {
                        tile tmpNode = select_node_with_lowest_histeresys();
                        verify_adjacent_nodes( tmpNode );
                        for( list < tile >::iterator iter = open_list.begin(); iter != open_list.end(); iter++ )
                        {
                            for( unsigned i = 0; i < map1.size(); i++ )
                            {
                                for( unsigned j = 0; j < map1[ i ].size(); j++ )
                                {
                                    if(( iter->x == map1[ i ][ j ].x ) &&( iter->y == map1[ i ][ j ].y ) )
                                    {
                                        map1[ i ][ j ].state = 4; //zmiana stanu dla renderingu
                                    }
                                }
                            }
                        }
                        for( list < tile >::iterator iter = close_list.begin(); iter != close_list.end(); iter++ )
                        {
                            for( unsigned i = 0; i < map1.size(); i++ )
                            {
                                for( unsigned j = 0; j < map1[ i ].size(); j++ )
                                {
                                    if(( iter->x == map1[ i ][ j ].x ) &&( iter->y == map1[ i ][ j ].y ) )
                                    {
                                        map1[ i ][ j ].state = 5;
                                    }
                                }
                            }
                        }
                    }
                    else
                    {
                        cout << "path found";
                    }
                }
                cout << "opensize " << open_list.size() << "closedsize " << close_list.size() << endl;
                break;
                default:
                break;
            }
        }
        window.clear( Color( 50, 50, 50 ) );
        for( unsigned i = 0; i < map1.size(); i++ )
        {
            for( unsigned j = 0; j < map1[ i ].size(); j++ )
            {
                tiles.setPosition( j * 40, i * 40 );
                if( map1[ i ][ j ].state == 0 )
                     tiles.setTextureRect( IntRect( 40, 40, 40, 40 ) );
                else if( map1[ i ][ j ].state == 2 )
                     tiles.setTextureRect( IntRect( 0, 0, 40, 40 ) );
                else if( map1[ i ][ j ].state == 3 )
                     tiles.setTextureRect( IntRect( 40, 0, 40, 40 ) );
                else if( map1[ i ][ j ].state == 4 )
                     tiles.setTextureRect( IntRect( 80, 0, 40, 40 ) );
                else if( map1[ i ][ j ].state == 5 )
                     tiles.setTextureRect( IntRect( 80, 40, 40, 40 ) );
                else if( map1[ i ][ j ].state == 9 )
                     tiles.setTextureRect( IntRect( 40, 00, 40, 40 ) );
                else
                     tiles.setTextureRect( IntRect( 0, 40, 40, 40 ) );
               
                window.draw( tiles );
            }
        }
        window.display();
    }
    return 0;
}
P-158106
DejaVu
» 2017-02-22 17:14:36
Prosta rada: nie wykonuj optymalizacji przedwcześnie. Zadbaj o to, aby algorytm działał poprawnie przy wykonywaniu algorytmu A*.


http://stackoverflow.com​/questions/2107601​/fastest-cross-platform-a-implementation


https://harablog.wordpress.com/

http://www.gdcvault.com/play​/1022094​/JPS-Over-100x-Faster-than
P-158133
aaadam
Temat założony przez niniejszego użytkownika
» 2017-03-01 12:08:10
witam, mam jeszcze jedno pytanie co do optymalizacji nie chodzi mi o zasade działania algorytmu ale o takie rzeczy jak np:
- zamiast przekazywania przez wartość to może zmienić przekazywanie przez wskaźnik (obiektu) ponoć to jest szybsze
- może zamiast wektorów używać czegoś innego lub w inny sposób
dalej nie mam pomysłów na razie

dla planszy 13x13 z kilkoma przeszkodami algorytm wykonuje się w około 5 ms dość szybko ale biorąc pod uwagę że chcę to wykożystać do napisania Zombie shootera i tych zombiaków  będzie sporo to może mieć znaczenie. Czy może ściągnąć jakąś gotową implementacje 'szybką'.
Algorytm działa już prawidłowo chociaż nie była optymalizowana zasada działania samego algorytmu puki co

kod poniżej,

przykładowa mapa w pliku txt :

11111111111111 
10000000000001
10000000000001
18000000000001
10000000000001
10011000000001
10011001101111
10000001111001
10000000190001
10000000111001
10000000000001
10000000000001
11111111111111

8 pozycja startowa
9 pozycja koncowa
 
Pozdro
C/C++
#include <SFML/Graphics.hpp>
#include <string>
#include <iostream>
#include <fstream>
#include <ctime>
#include <vector>
#include <sstream>
#include <list>
using namespace sf;
using namespace std;
enum waga { horizontal = 10, oblique = 14 };
enum states { available = 0, notAvailable = 1, exitNode = 9 };
class tile
{
public:
    Vector2i parent;
    tile() { }
    tile( int x, int y )
    {
        this->x = x;
        this->y = y;
        //this->was_checked = false;
    }
    tile( int x, int y, int state )
    {
        this->x = x;
        this->y = y;
        this->state = state;
        //this->was_checked = false;
    }
    tile( int x, int y, int state, Vector2i parent, int hyst )
    {
        this->parent = parent;
        this->x = x;
        this->y = y;
        this->state = state;
        this->hysteresys = hyst;
        //this->was_checked = false;
    }
   
    int x, y, hysteresys;
    //bool was_checked;
    int state;
    bool operator ==( const tile & temp )
    {
        return( temp.x == this->x && temp.y == this->y );
    }
   
};
bool b_exit = false;
vector < tile > open_list;
vector < tile > close_list;
vector < Vector2i > Path;
vector < Vector2i >::iterator it_Path;
vector < tile > tempmap;
Texture tileTexture;
Sprite tiles;
vector < vector < tile >> map1;
void Loadmap1( const char * fileName )
{
    string tileLocation;
    tileLocation = "tiles.png";
    tileTexture.loadFromFile( tileLocation );
    tiles.setTexture( tileTexture );
    fstream openfile( fileName );
    tempmap.clear();
    map1.clear();
    if( openfile.is_open() )
    {
        string value;
        int i = 0;
        while( getline( openfile, value ) )
        {
            for( unsigned j = 0; j < value.length(); j++ )
            {
                if( isdigit( value[ j ] ) )
                {
                    tempmap.push_back( tile( i, j, value[ j ] - 48 ) );
                }
            }
            value.clear();
            map1.push_back( tempmap );
            tempmap.clear();
            i++;
        }
    }
    openfile.close();
}
bool check_if_exist_in_closedList( tile node )
{
    for( vector < tile >::iterator iter = close_list.begin(); iter != close_list.end(); iter++ )
    {
        if( iter->x == node.x && iter->y == node.y )
             return true;
       
    }
    return false;
}
bool check_if_exist_in_openedList( tile node )
{
    for( vector < tile >::iterator iter = open_list.begin(); iter != open_list.end(); iter++ )
    {
        if( iter->x == node.x && iter->y == node.y )
             return true;
       
    }
    return false;
}
void calculate_histeresys_for_all_nodes( tile end )
{
    for( unsigned i = 0; i < map1.size(); i++ )
    {
        for( unsigned j = 0; j < map1[ i ].size(); j++ )
        {
            map1[ i ][ j ].hysteresys =( abs( end.x - map1[ i ][ j ].x ) + abs( end.y - map1[ i ][ j ].y ) ) * 10;
        }
    }
}
void verify_adjacent_nodes( tile node )
{
    if( !( node.x == 8 && node.y == 9 ) )
    {
        if( !check_if_exist_in_closedList( node ) )
        {
            map1[ node.x ][ node.y ].state = 5;
            close_list.push_back( node );
        }
        Vector2i parent;
        tile tmpNode;
        if( map1[ node.x - 1 ][ node.y - 1 ].state == available || map1[ node.x - 1 ][ node.y - 1 ].state == exitNode )
        {
            parent.x = node.x;
            parent.y = node.y;
            tmpNode.x = node.x - 1;
            tmpNode.y = node.y - 1;
            if( !check_if_exist_in_openedList( tmpNode ) )
            {
                open_list.push_back( tile( node.x - 1, node.y - 1, available, parent, map1[ node.x - 1 ][ node.y - 1 ].hysteresys + oblique ) );
                map1[ node.x - 1 ][ node.y - 1 ].state = 4;
            }
        }
        if( map1[ node.x - 1 ][ node.y ].state == available || map1[ node.x - 1 ][ node.y ].state == exitNode )
        {
            parent.x = node.x;
            parent.y = node.y;
            tmpNode.x = node.x - 1;
            tmpNode.y = node.y;
            if( !check_if_exist_in_openedList( tmpNode ) )
            {
                open_list.push_back( tile( node.x - 1, node.y, available, parent, map1[ node.x - 1 ][ node.y ].hysteresys + horizontal ) );
                map1[ node.x - 1 ][ node.y ].state = 4;
            }
        }
        if( map1[ node.x + 1 ][ node.y - 1 ].state == available || map1[ node.x + 1 ][ node.y - 1 ].state == exitNode )
        {
            parent.x = node.x;
            parent.y = node.y;
            tmpNode.x = node.x + 1;
            tmpNode.y = node.y - 1;
            if( !check_if_exist_in_openedList( tmpNode ) )
            {
                open_list.push_back( tile( node.x + 1, node.y - 1, available, parent, map1[ node.x + 1 ][ node.y - 1 ].hysteresys + oblique ) );
                map1[ node.x + 1 ][ node.y - 1 ].state = 4;
            }
        }
        if( map1[ node.x ][ node.y - 1 ].state == available || map1[ node.x ][ node.y - 1 ].state == exitNode )
        {
            parent.x = node.x;
            parent.y = node.y;
            tmpNode.x = node.x;
            tmpNode.y = node.y - 1;
            if( !check_if_exist_in_openedList( tmpNode ) )
            {
                open_list.push_back( tile( node.x, node.y - 1, available, parent, map1[ node.x ][ node.y - 1 ].hysteresys + horizontal ) );
                map1[ node.x ][ node.y - 1 ].state = 4;
            }
        }
        if( map1[ node.x ][ node.y + 1 ].state == available || map1[ node.x ][ node.y + 1 ].state == exitNode )
        {
            parent.x = node.x;
            parent.y = node.y;
            tmpNode.x = node.x;
            tmpNode.y = node.y + 1;
            if( !check_if_exist_in_openedList( tmpNode ) )
            {
                open_list.push_back( tile( node.x, node.y + 1, available, parent, map1[ node.x ][ node.y + 1 ].hysteresys + horizontal ) );
                map1[ node.x ][ node.y + 1 ].state = 4;
            }
        }
        if( map1[ node.x + 1 ][ node.y + 1 ].state == available || map1[ node.x + 1 ][ node.y + 1 ].state == exitNode )
        {
            parent.x = node.x;
            parent.y = node.y;
            tmpNode.x = node.x + 1;
            tmpNode.y = node.y + 1;
            if( !check_if_exist_in_openedList( tmpNode ) )
            {
                open_list.push_back( tile( node.x + 1, node.y + 1, available, parent, map1[ node.x + 1 ][ node.y + 1 ].hysteresys + oblique ) );
                map1[ node.x + 1 ][ node.y + 1 ].state = 4;
            }
        }
        if( map1[ node.x - 1 ][ node.y + 1 ].state == available || map1[ node.x - 1 ][ node.y + 1 ].state == exitNode )
        {
            parent.x = node.x;
            parent.y = node.y;
            tmpNode.x = node.x - 1;
            tmpNode.y = node.y + 1;
            if( !check_if_exist_in_openedList( tmpNode ) ) {
                open_list.push_back( tile( node.x - 1, node.y + 1, available, parent, map1[ node.x - 1 ][ node.y + 1 ].hysteresys + oblique ) );
                map1[ node.x - 1 ][ node.y + 1 ].state = 4;
            }
        }
        if( map1[ node.x + 1 ][ node.y ].state == available || map1[ node.x + 1 ][ node.y ].state == exitNode )
        {
            parent.x = node.x;
            parent.y = node.y;
            tmpNode.x = node.x + 1;
            tmpNode.y = node.y;
            if( !check_if_exist_in_openedList( tmpNode ) ) {
                open_list.push_back( tile( node.x + 1, node.y, available, parent, map1[ node.x + 1 ][ node.y ].hysteresys + horizontal ) );
                map1[ node.x + 1 ][ node.y ].state = 4;
            }
        }
        vector < tile >::iterator it = find( open_list.begin(), open_list.end(), node );
        open_list.erase( it );
    }
    else
    {
        if( !check_if_exist_in_closedList( node ) )
             close_list.push_back( node );
       
        if( !b_exit ) {
            Vector2i temp = Vector2i( close_list[ close_list.size() - 1 ].x, close_list[ close_list.size() - 1 ].y );
           
            for( int i = close_list.size(); i > 0; i-- )
            {
                if( close_list[ i - 1 ].x == temp.x && close_list[ i - 1 ].y == temp.y )
                {
                    Path.push_back( Vector2i( close_list[ i - 1 ].x, close_list[ i - 1 ].y ) );
                    temp.x = close_list[ i - 1 ].parent.x;
                    temp.y = close_list[ i - 1 ].parent.y;
                }
            }
        }
        b_exit = true;
    }
}


tile select_node_with_lowest_histeresys()
{
    tile tmp;
    vector < tile >::iterator iter = open_list.begin();
    tmp.hysteresys = iter->hysteresys;
    tmp.x = iter->x;
    tmp.y = iter->y;
    tmp.state = iter->state;
    tmp.parent = iter->parent;
    for(; iter != open_list.end(); ++iter )
    {
        if( iter->hysteresys < tmp.hysteresys )
        {
            tmp.hysteresys = iter->hysteresys;
            tmp.x = iter->x;
            tmp.y = iter->y;
            tmp.state = iter->state;
            tmp.parent = iter->parent;
        }
    }
    return tmp;
}
int findPath( tile start, tile end )
{
    if( start == end )
    {
        return 0;
    }
    open_list.push_back( start );
    verify_adjacent_nodes( start );
    while( !b_exit )
    {
        if( open_list.size() > 0 || b_exit )
        {
            tile tmpNode = select_node_with_lowest_histeresys();
            verify_adjacent_nodes( tmpNode );
            if( open_list.size() == 0 )
                 break;
           
        }
    }
    return - 1;
}

int main()
{
    Loadmap1( "mapfile.txt" );
    Vector2i screenDimensions( 1200, 800 );
    RenderWindow window( VideoMode( 800, 600, 32 ), "SFML works!" );
    window.setKeyRepeatEnabled( false );
   
   
    ///start liczenia czasu
    tile start = tile( 3, 1, 0, Vector2i( 3, 1 ), map1[ 3 ][ 1 ].hysteresys );
    tile end = tile( 8, 9, 0, Vector2i( 8, 9 ), map1[ 8 ][ 9 ].hysteresys );
   
    calculate_histeresys_for_all_nodes( end );
    clock_t startT = clock();
    findPath( start, end ); // 6 6 bo liczymy od 0
    printf( "Czas wykonywania: %lu ms\n", clock() - startT );
   
   
    for( vector < tile >::iterator iter = open_list.begin(); iter != open_list.end(); iter++ )
    {
       
        for( unsigned i = 0; i < map1.size(); i++ )
        {
            for( unsigned j = 0; j < map1[ i ].size(); j++ )
            {
                if(( iter->x == map1[ i ][ j ].x ) &&( iter->y == map1[ i ][ j ].y ) )
                {
                    map1[ i ][ j ].state = 4;
                }
            }
            //cout << endl;
        }
       
    }
    for( vector < tile >::iterator iter = close_list.begin(); iter != close_list.end(); iter++ )
    {
       
        for( unsigned i = 0; i < map1.size(); i++ )
        {
            for( unsigned j = 0; j < map1[ i ].size(); j++ )
            {
                if(( iter->x == map1[ i ][ j ].x ) &&( iter->y == map1[ i ][ j ].y ) )
                {
                    map1[ i ][ j ].state = 5;
                }
            }
            //cout << endl;
        }
       
    }
    while( window.isOpen() )
    {
        Event event;
        while( window.pollEvent( event ) )
        {
            switch( event.type )
            {
            case Event::Closed:
                window.close();
                break;
            case Event::KeyPressed:
                if( event.key.code == Keyboard::L )
                {
                }
                break;
                default:
                break;
            }
        }
        window.clear( Color( 50, 50, 50 ) );
        for( unsigned i = 0; i < map1.size(); i++ )
        {
            for( unsigned j = 0; j < map1[ i ].size(); j++ )
            {
                tiles.setPosition( j * 40, i * 40 );
                if( map1[ i ][ j ].state == 0 )
                     tiles.setTextureRect( IntRect( 40, 40, 40, 40 ) );
                else if( map1[ i ][ j ].state == 2 )
                     tiles.setTextureRect( IntRect( 0, 0, 40, 40 ) );
                else if( map1[ i ][ j ].state == 3 )
                     tiles.setTextureRect( IntRect( 40, 0, 40, 40 ) );
                else if( map1[ i ][ j ].state == 4 )
                     tiles.setTextureRect( IntRect( 80, 0, 40, 40 ) );
                else if( map1[ i ][ j ].state == 5 )
                     tiles.setTextureRect( IntRect( 80, 40, 40, 40 ) );
                else if( map1[ i ][ j ].state == 9 )
                     tiles.setTextureRect( IntRect( 40, 00, 40, 40 ) );
                else
                     tiles.setTextureRect( IntRect( 0, 40, 40, 40 ) );
               
                window.draw( tiles );
            }
        }
        if( b_exit ) {
            for( unsigned j = 0; j < Path.size(); j++ )
            {
                tiles.setPosition( Path[ j ].y * 40, Path[ j ].x * 40 );
                tiles.setTextureRect( IntRect( 120, 40, 40, 40 ) );
                window.draw( tiles );
            }
        }
        window.display();
    }
    return 0;
}
P-158409
DejaVu
» 2017-03-01 16:04:23
Nie rób mikro optymalizacji. Dbaj o to, aby kod był czytelny, prosty i samo opisujący. Przez referencję przekazuj duże obiekty.
P-158413
« 1 »
  Strona 1 z 1  
» Forum » Programowanie » [C, C++] Szukam pomocy
© Wszelkie prawa zastrzeżone 2005-2024