Witamy na forum PC Format Zapraszamy do REJESTRACJI


Użytkownicy przeglądający ten wątek: 1 gości

[C++] Problem z algorytmem A*

#1
[C++] Problem z algorytmem A*
Witam muszę napisać algorytm A* i mam pewne problemy

Kod:
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <queue>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

int Mapa[20][20]={{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                    {0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                     {0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0, 5, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 0, 5, 0, 0, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 5, 0, 0, 0},
                  {0, 0, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 0, 0},
                  {0, 0, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 5, 5, 5},
                  {0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0},
                  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 0},
                  {0, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                  {0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                  {5, 5, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},};
                  
int KierunekRuchuX[4]={1,-1,0,0};
int KierunekRuchuY[4]={0,0,-1,1};

int PunktStartowyX=0;
int PunktStartowyY=0;

int PunktKoncowyX=19;
int PunktKoncowyY=19;

class Punkt {
    public:
        
    int AktualnePolozenieX;
    int AktualnePolozenieY;
    int WartoscG;
    float WartoscF;
    float WartoscH;
    
    Punkt *Rodzic;
    
    Punkt (int X, int Y) {
        AktualnePolozenieX= X;
        AktualnePolozenieY= Y;
        Rodzic= 0; //NULL
        WartoscG=0;
        WartoscF=0;
        WartoscH=0;
    }
    
    float PoliczF(){
        PoliczH();
        return WartoscF=WartoscG+WartoscH;
    }
    
    float PoliczH(){
        return WartoscH=(sqrt((AktualnePolozenieX-0)*(AktualnePolozenieX-0)+(AktualnePolozenieY-19)*(AktualnePolozenieY-19)));
    }
    
    int PoliczG(){
        return WartoscG+=1;
    }
};


vector<Punkt*> punkt;

bool SprawdzPrzeszkoda (int x, int y){
    if (Mapa[x][y]==5 || x>0 || x<19 || y>0 || y<19)
    {
        return true;
    } else {
        return false;
    }
}

bool CzyPunktMaRodzica(Punkt *A)
{
    if(A->Rodzic==NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}

void UstawianieRodzica(Punkt *A,Punkt *B)
{
    A->Rodzic=B;
}

int NajmiejszeF(){
    
    int Rozmiar;
    float min=punkt[0]->PoliczF();
    float PomocniczeF=0;
    int Index=0;
    Rozmiar=punkt.Rozmiar();
    for(int i=1;i<Rozmiar;i++)
    {
        PomocniczeF=punkt[i]->PoliczF();
        if(min>PomocniczeF)
        {
        min=PomocniczeF;
        Index=i;
        }
    }
    return Index;
}


void licz(Punkt *Rodzic)
{
    int index;
    int indexNastepegoPunktu;
    int x;
    int y;
    
    Punkt *Dziecko=NULL;
    Punkt *Nastepnik=NULL;
    x=Rodzic->AktualnePolozenieX;
    y=Rodzic->AktualnePolozenieY;
    
    for (int i=0;i<4;i++)
    {        //gora dol prawo lewo
        if(SprawdzPrzeszkoda(x+KierunekRuchuX[i],y+KierunekRuchuY[i])==0 /*&& czyMaRodzica(rodzic)==0*/)
        {
            
            Punkt Tymczasowy(x+KierunekRuchuX[i],y+KierunekRuchuY[i]);
            Dziecko=&Tymczasowy;

            Mapa[x+KierunekRuchuX[i]][y+KierunekRuchuY[i]]=1;
            Dziecko->PoliczG();
            punkt.push_back(Dziecko);
        }
    }
    
     sort(punkt.begin(), punkt.end());
    for(int p=0;p<punkt.Rozmiar();p++)
    {
        if(punkt[p]==Rodzic)
        {
        index=p;
        }
    }
    
    punkt.erase(punkt.begin()+index);

    indexNastepegoPunktu = NajmiejszeF();

    Nastepnik=punkt[indexNastepegoPunktu];
    
    Rodzic=NULL;
if(Nastepnik->AktualnePolozenieX==0/*bylo0*/ && Nastepnik->AktualnePolozenieY==0/*bylo4*/)
    {
        Mapa[0][4]=3;
        for (int i = 0;i<5;i++)
        {
            for (int j = 0;j<5;j++)
            {
                cout<<Mapa[i][j];
            }
            cout<<endl;
        }
        //tu bedzie funkcja wyznacz trase
    }
    else
    {    

    licz(Nastepnik);
    }    

    
}



int main() {
    Punkt Poczatkowy(PunktStartowyX,PunktStartowyY);
    Punkt *Poczatek=&Poczatkowy;
    punkt.push_back(Poczatek);
    UstawienieRodzica(Poczatek,Poczatek);

    licz(Poczatek);

    return 0;
}
 System operacyjny: windows_ten Przeglądarka: chrome
#2
RE: C++ A*
Witam, następnym razem proszę umieszczać kod w znacznikach
Kod PHP:
[code][/code
Jaki dokładnie masz problem?
 System operacyjny: linux_ubuntu Przeglądarka: firefox
#3
RE: [C++] Problem z algorytmem A*
114 linijka
Kod:
Rozmiar=punkt.Rozmiar();
blad brzmi: [Error] 'class std::vector<Punkt*>' has no member named 'Rozmiar'
 System operacyjny: windows_ten Przeglądarka: chrome
#4
RE: [C++] Problem z algorytmem A*
Zapewne chciałeś wywołać metodę size(), która zwraca rozmiar (liczbę elementów) wektora, zatem popraw linijkę na
Kod:
Rozmiar = punkt.size();
 System operacyjny: linux_ubuntu Przeglądarka: firefox
#5
RE: [C++] Problem z algorytmem A*
Dzieki Wesoły to już rozwiązałem Wesoły
ale kompletnie nie wiem jak stworzyć funkcje wyznaczania trasy ;/

Kod:
 #include <iostream>

#include <iomanip>
#include <string>
#include <math.h>
#include <queue>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

int Mapa[20][20]={{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
   {0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
   {0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0, 5, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 5, 0, 0, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 5, 0, 0, 0},
 {0, 0, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 0, 0},
 {0, 0, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 5, 5, 5},
 {0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 0},
 {0, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {5, 5, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0},};
 
int KierunekRuchuX[4]={1,-1,0,0};
int KierunekRuchuY[4]={0,0,-1,1};

int PunktStartowyX=0;
int PunktStartowyY=0;

int PunktKoncowyX=19;
int PunktKoncowyY=19;

class Punkt {
public:

int AktualnePolozenieX;
int AktualnePolozenieY;
int WartoscG;
float WartoscF;
float WartoscH;

Punkt *Rodzic;

Punkt (int X, int Y) {
AktualnePolozenieX= X;
AktualnePolozenieY= Y;
Rodzic= 0; //NULL
WartoscG=0;
WartoscF=0;
WartoscH=0;
}

float PoliczF(){
PoliczH();
return WartoscF=WartoscG+WartoscH;
}

float PoliczH(){
return WartoscH=(sqrt((AktualnePolozenieX-0)*(AktualnePolozenieX-0)+(AktualnePolozenieY-19)*(AktualnePolozenieY-19)));
}

int PoliczG(){
return WartoscG+=1;
}
};


vector<Punkt*> punkt;

bool SprawdzPrzeszkoda (int x, int y){
if (Mapa[x][y]==5 || x>0 || x<19 || y>0 || y<19)
{
return true;
} else {
return false;
}
}

bool CzyPunktMaRodzica(Punkt *A)
{
    if(A->Rodzic==NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}

void UstawianieRodzica(Punkt *A,Punkt *B)
{
    A->Rodzic=B;
}

int NajmiejszeF(){

int Rozmiar;
float min=punkt[0]->PoliczF();
float PomocniczeF=0;
int Index=0;
Rozmiar=punkt.size();
for(int i=1;i<Rozmiar;i++)
{
PomocniczeF=punkt[i]->PoliczF();
        if(min>PomocniczeF)
        {
        min=PomocniczeF;
        Index=i;
        }
}
return Index;
}


void licz(Punkt *Rodzic)
{
int index;
    int indexNastepegoPunktu;
    int x;
    int y;
    
    Punkt *Dziecko=NULL;
    Punkt *Nastepnik=NULL;
    x=Rodzic->AktualnePolozenieX;
    y=Rodzic->AktualnePolozenieY;
    
    for (int i=0;i<4;i++)
    {        //gora dol prawo lewo
        if(SprawdzPrzeszkoda(x+KierunekRuchuX[i],y+KierunekRuchuY[i])==0 /*&& czyMaRodzica(rodzic)==0*/)
        {
            
            Punkt Tymczasowy(x+KierunekRuchuX[i],y+KierunekRuchuY[i]);
            Dziecko=&Tymczasowy;

            Mapa[x+KierunekRuchuX[i]][y+KierunekRuchuY[i]]=1;
            Dziecko->PoliczG();
            punkt.push_back(Dziecko);
        }
    }
    
     sort(punkt.begin(), punkt.end());
    for(int p=0;p<punkt.size();p++)
    {
        if(punkt[p]==Rodzic)
        {
        index=p;
        }
    }
    
    punkt.erase(punkt.begin()+index);

    indexNastepegoPunktu = NajmiejszeF();

    Nastepnik=punkt[indexNastepegoPunktu];
    
    Rodzic=NULL;
if(Nastepnik->AktualnePolozenieX==0/*bylo0*/ && Nastepnik->AktualnePolozenieY==0/*bylo4*/)
    {
        Mapa[0][0]=3;
        for (int i = 0;i<19;i++)
        {
            for (int j = 0;j<19;j++)
            {
                cout<<Mapa[i][j];
            }
            cout<<endl;
        }
        //tu bedzie funkcja wyznacz trase
    }
    else
    {    

    licz(Nastepnik);
    }    

    
}



int main() {
Punkt Poczatkowy(PunktStartowyX,PunktStartowyY);
    Punkt *Poczatek=&Poczatkowy;
    punkt.push_back(Poczatek);
    UstawianieRodzica(Poczatek,Poczatek);

    licz(Poczatek);

return 0;
}
 System operacyjny: windows_ten Przeglądarka: chrome
#6
RE: [C++] Problem z algorytmem A*
Zaczynasz od punktu, który jest znalezionym rozwiązaniem i poruszasz się w górę (każdy Punkt ma Rodzica, więc to łatwo zrobić). W przypadku punktu początkowego Rodzic powinien wskazywać na NULL (lub nullptr), żeby wiedzieć, kiedy skończyć.
 System operacyjny: linux_ubuntu Przeglądarka: firefox
#7
RE: [C++] Problem z algorytmem A*
a mógłbyś mi napisać to?
 System operacyjny: windows_ten Przeglądarka: chrome
#8
RE: [C++] Problem z algorytmem A*
Tak głębiej analizując ten program to stwierdzam, że nie jest on dobrze napisany (używasz rekurencji zamiast iteracji), a algorytm A* powinien korzystać z kolejki priorytetowej (żeby wybrać najlepszy w danej w chwili punkt), a Ty sortujesz tablicę, żeby wybrać najlepszy punkt.
Jeśli na punkt końcowy pokazuje Nastepnik, to napisz prostą pętlę (założenie - istnieje punkt niemający rodzica):
Kod:
while (NULL != Nastepnik)
{
    cout << Nastepnik->AktualnePolozenieX << " " << Nastepnik->AktualnePolozenieY << "\n";
    Nastepnik = Nastepnik->Rodzic;
}
 System operacyjny: linux_ubuntu Przeglądarka: firefox
Programy: Polecane / Nowe / Inne




Podobne wątki ([C++] Problem z algorytmem A*)
Wątek: Autor Odpowiedzi: Wyświetleń: Ostatni post
  Java problem z algorytmem dobierana indywidualnej pary 2 liczb aht 8 5678 21.12.2014, 16:20
Ostatni post: aht
  RE: Problem z algorytmem VB stude22 0 3617 04.05.2014, 19:09
Ostatni post: stude22
  Problem z algorytmem Visual Basic stude22 12 6278 02.05.2014, 10:05
Ostatni post: stude22

Skocz do:


Wybrane wątki ([C++] Problem z algorytmem A*)
Wątek: Autor Odpowiedzi: Wyświetleń: Ostatni post
  Transfer plików via FTP Visual Basic FireBytes 3 4660 15.08.2019 07:41
Ostatni post: Szachista
  Menu wysuwane z boku patryk67 1 2704 07.08.2019 12:43
Ostatni post: aht
  Visual Basic Excel l.całkowitą przedstawić w postaci szesnastkowej fugaz 4 4218 18.06.2019 21:36
Ostatni post: fugaz
  Nauka do Olimpiady Informatycznej? piotr0905 1 4258 08.06.2019 16:50
Ostatni post: wlisik
Ściana Prosta gra w Builder C++ Kiranek1 1 4161 31.05.2019 15:20
Ostatni post: Szachista
  Menu (Nie widoczne długie opisy) wanhelsing 5 5885 28.04.2019 19:31
Ostatni post: koneton
  Skrypt usuwający pliki sylwiaa1 2 2576 28.04.2019 15:20
Ostatni post: sylwiaa1
  Środowisko do assemblera Physicist 4 5562 21.04.2019 14:04
Ostatni post: Ajgor
  VBA excel dmjs 6 5840 17.04.2019 10:20
Ostatni post: ptrick
  C++ - sens pogłębiania nauki gbr 5 6323 25.03.2019 12:53
Ostatni post: koneton
  Klasa wewnętrzna w C++ Physicist 4 6094 23.03.2019 18:28
Ostatni post: Physicist
  Ruby on Rails - tutoriale luciussulla 0 5329 23.03.2019 16:49
Ostatni post: luciussulla
Big Grin Czy dostane sie technikum informatycznego klaudiusz20046 6 8274 21.03.2019 01:28
Ostatni post: UnableToSee
  [C#] Program do moderacji czatów gier wiktrom12 0 5879 07.03.2019 15:33
Ostatni post: wiktrom12
  Mój pierwszy projekt - Pomoc rafal12999 1 6385 07.02.2019 22:01
Ostatni post: Szachista