// A Star.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
int wymx = 20;
int wymy = 20;
struct pole// struktura dla danych każdego pola w gridzie
{
int x = 0;
int y = 0;
double g = 0;
double h = 0;
double f = g + h;
pole * rodzic = NULL;// rodzic - kratka z ktorej przyszlismy
int wartoscPola = 0;
};
//wczytanie z txt
void wczytajGrid(string nazwa, pole **G, int wym1, int wym2)
{
cout << "Wczytywanie danych z pliku\n";
string nazwap = nazwa;
cout << "\n\nNacisnij ENTER aby wczytac tablice o nazwie " << nazwap << endl;
getchar();
std::ifstream plik(nazwap.c_str());
for (int i = 1; i<wym2 + 1; i++)
{
for (int j = 1; j<wym1 + 1; j++)
{
plik >> G[i][j].wartoscPola;
}
}
plik.close();
cout << "\nWypisujemy na ekran\n\n";
for (int i = 1; i<wym2 + 1; i++)
{
for (int j = 1; j<wym1 + 1; j++)
{
cout << " " << G[i][j].wartoscPola;
}cout << "\n";
}
}
void WyznaczTrase(pole **G, vector <pole> zamkniete, pole kratka)
{
while(kratka.rodzic!=NULL)
{
G[kratka.x][kratka.y].wartoscPola=1;
kratka = *kratka.rodzic;
}
if(kratka.rodzic==NULL)
G[kratka.x][kratka.y].wartoscPola=1;
}
bool czyJestWKontenerze(vector <pole> kontener, pole kratka)
{
for (int i = 0; i < kontener.size(); i++)
{
if (kontener[i].x == kratka.x&&kontener[i].y == kratka.y)
return true;
}
return false;
}
int indeksNajtanszego(vector <pole> otwarte)
{
pole tmp = otwarte.front();
int indeks = 0;
for (int i = 0; i < otwarte.size(); ++i)
if (otwarte[i].f < tmp.f)
{
tmp = otwarte[i];
indeks = i;
}
return indeks;
}
void ZnajdzSasiadow(pole kratka, pole meta, pole ** siatka, vector <pole> zamkniete, vector <pole> &sasiedzi)
{
if (kratka.x + 1 <= 20 && siatka[kratka.x + 1][kratka.y].wartoscPola == 0)//dol
{
pole tmp = siatka[kratka.x + 1][kratka.y];
tmp.rodzic = &zamkniete.back();
tmp.g = tmp.rodzic->g + 1;
tmp.h = sqrt(pow((tmp.x - meta.x), 2) + pow(tmp.y - meta.y, 2));
tmp.f = tmp.g + tmp.h;
if (czyJestWKontenerze(zamkniete, tmp) == false)
sasiedzi.push_back(tmp);
}
if (kratka.y - 1 >= 1 && siatka[kratka.x][kratka.y - 1].wartoscPola == 0)//lewo
{
pole tmp = siatka[kratka.x][kratka.y - 1];
tmp.rodzic = &zamkniete.back();
tmp.g = tmp.rodzic->g + 1;
tmp.h = sqrt(pow((tmp.x - meta.x), 2) + pow(tmp.y - meta.y, 2));
tmp.f = tmp.g + tmp.h;
if (czyJestWKontenerze(zamkniete, tmp) == false)
sasiedzi.push_back(tmp);
}
if (kratka.x - 1 >= 1 && siatka[kratka.x - 1][kratka.y].wartoscPola == 0)//gora
{
pole tmp = siatka[kratka.x - 1][kratka.y];
tmp.rodzic = &zamkniete.back();
tmp.g = tmp.rodzic->g + 1;
tmp.h = sqrt(pow((tmp.x - meta.x), 2) + pow(tmp.y - meta.y, 2));
tmp.f = tmp.g + tmp.h;
if (czyJestWKontenerze(zamkniete, tmp) == false)
sasiedzi.push_back(tmp);
}
if (kratka.y + 1 <= 20 && siatka[kratka.x][kratka.y + 1].wartoscPola == 0)//prawo
{
pole tmp = siatka[kratka.x][kratka.y + 1];
tmp.rodzic = &zamkniete.back();
tmp.g = tmp.rodzic->g + 1;
tmp.h = sqrt(pow((tmp.x - meta.x), 2) + pow(tmp.y - meta.y, 2));
tmp.f = tmp.g + tmp.h;
if (czyJestWKontenerze(zamkniete, tmp) == false)
sasiedzi.push_back(tmp);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned int i, j;
vector <pole> otwarte;
vector <pole> zamkniete;
pole **siatka;
int rows = wymx + 1;
siatka = new pole *[rows];
while (rows--) siatka[rows] = new pole[wymy + 1];
for (i = 1; i < wymx + 1; ++i)
{
for (j = 1; j < wymx + 1; ++j)
{
siatka[i][j].x = i;
siatka[i][j].y = j;
}
}
string nazwaPliku = "grid.txt";
pole meta;
meta.x = 20;
meta.y = 20;
pole start;
start.x = 15;
start.y = 15;
start.g = 0;
start.h = sqrt(pow((start.x - meta.x), 2) + pow(start.y - meta.y, 2));
start.rodzic = NULL;
otwarte.push_back(start);
wczytajGrid(nazwaPliku, siatka, wymx, wymy);
cout << endl;
cout << endl;
cout << "Wyznaczanie trasy" << endl;
cout << endl;
cout << endl;
while (otwarte.size() != 0)
{
int indeks = indeksNajtanszego(otwarte);
pole tmp = otwarte[indeks];
vector <pole> sasiedzi;
zamkniete.push_back(tmp);
otwarte.erase(otwarte.begin() + indeks);
if ((zamkniete.back().x == 20 && zamkniete.back().y == 20))
break;
ZnajdzSasiadow(tmp, meta, siatka, zamkniete, sasiedzi);
for (int i = 0; i < sasiedzi.size(); i++)
{
if (czyJestWKontenerze(otwarte, sasiedzi[i]))
{
int j = 0;
for (j = 0; j < otwarte.size(); j++)
if (otwarte[j].x == sasiedzi[i].x&&otwarte[j].y == sasiedzi[i].y)
break;
if (sasiedzi[i].f < otwarte[j].f)
{
otwarte[j].rodzic = sasiedzi[i].rodzic;
otwarte[j].g = sasiedzi[i].g;
otwarte[j].f = sasiedzi[i].f;
}
}
else
otwarte.push_back(sasiedzi[i]);
}
}
if (zamkniete.back().x == meta.x && zamkniete.back().y == meta.y)
{
WyznaczTrase(siatka,zamkniete,zamkniete.back());
cout << "wyznaczona trasa:" << endl;
for (int i = 1; i < wymx + 1; i++)
{
for (int j = 1; j < wymy + 1; j++)
{
cout << " " << siatka[i][j].wartoscPola;
}
cout << "\n";
}
}
else
cout << "NIE MA TRASY!" << endl;
//na koniec czyścimy pamięć po naszej tablicy
for (i = 0; i < wymx + 1; i++)
{
delete[] siatka[i];
}//czyscimy wiersze
delete[] siatka;//zwalniamy tablice
return 0;
}
Witajcie, staram się zaimplementować algorytm a*, jednak mam jakiś problem z pamięcią, przyznam, jeżeli chodzi o tematyke alokacji pamięci, wskaźników itp to się gubię, nie będę już się rozwodził na temat samego algorytmu(a raczej jego uproszczonej wersji), bo nie o to w tym chodzi, mam jednak następujący problem:
Program wywala się przy
void WyznaczTrase(pole **G, vector <pole> zamkniete, pole kratka)
z błędem
Access violation reading location(...)
w debugerze widzę, że pole kratka ma jakies randomowe dane po wywołaniu funkcji i to chyba jest problem, nie wiem jednak dlaczego tak się dzieje. Z góry dzięki za pomoc :)