To jest potega forum! Serdeczne dzieki za odpowiedzi. MSM - dzieki za kod. Na pewno sprobuje go wykozystac gdy bede pisal moj kod od nowa (to jest chyba nieuniknione:)).
Popoprawialem moj kod zgodnie ze wczesniejszymi wskazowkami, ale teraz dzieje sie cos zupelnie niespodziewanego. Teraz program rysuje droge na konsoli, ale w "komorce" poprzedzajacej punkt koncowy wyswietla mi sie losowy znak za kazdym razem gdy odpale program (puste pole, znak "&", potem jakas nutka, nastepnym razem kolor "pik" z tali kart) - totalnie zglupialem :) moze mi cos podpowiecie... oto moj kod:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <queue>
#include <string>
#include <math.h>
#include <ctime>
#include "node.h"
using namespace std;
bool loadMap();
string pathFind( const int & xStart, const int & yStart, const int & xFinish, const int & yFinish );
//Map size
const size_t sizeN = 5; //number of rows
const size_t sizeM = 7; //number of columns
//Start and finish locations
const int sY=0;
const int sX=0;
const int fY=2;
const int fX=5;
//Node maps
static int closedNodes[sizeN][sizeM]; //the set of nodes alreadirX evaluated
static int openNodes[sizeN][sizeM]; // the set of nodes to be evaluated; initialy only containing start node
static int map[sizeN][sizeM]; //work map
//Directions
static int dirY[node::dir]={0, 1, 1, 1, 0, -1, -1, -1};
static int dirX[node::dir]={1, 1, 0, -1, -1, -1, 0, 1};
static int dir_map[sizeN][sizeM]; //map of directions (contains parents-children connection)
bool operator<(const node & a, const node & b)
{
return a.getPriority() > b.getPriority();
}
int main()
{
loadMap();
string route = pathFind(sY, sX, fY, fX);
// follow the route on the map and display it
if(route.length()>0)
{
int j;
char c; //current route cell
int y=sY;
int x=sX;
map[y][x]=2;
for(int i=0;i<route.length();i++)
{
c =route.at(i);
j=atoi(&c);
y=y+dirY[j];
x=x+dirX[j];
map[y][x]=3;
}
map[y][x]=4;
// display the map with the route
for(size_t y=0;y<sizeN;++y,cout<<endl) for(size_t x=0;x<sizeM;++x) cout<<"X.SRF"[map[y][x]];
}
getchar(); // wait for a (Enter) keypress
getchar();
return 0;
}
//load the map from .txt file
bool loadMap()
{
ifstream file("testmap.txt");
if(!file) return false;
for(size_t y=0;y<sizeN;++y)
for(size_t x=0;x<sizeM;++x)
file>>map[y][x];
return true;
}
// A-star algorithm.
// The route returned is a string of direction digits.
string pathFind( const int & xStart, const int & yStart,
const int & xFinish, const int & yFinish )
{
static priority_queue<node> pq[2]; // list of open (not-yet-tried) nodes
static int pqi; // pq index
static node* n0;
static node* m0;
static int i, j, x, y, xdx, ydy;
static char c;
pqi=0;
// reset the node maps
for(y=0;y<sizeN;y++)
{
for(x=0;x<sizeM;x++)
{
closedNodes[y][x]=0;
openNodes[y][x]=0;
}
}
// create the start node and push into list of open nodes
n0=new node(xStart, yStart, 0, 0);
n0->updatePriority(xFinish, yFinish);
pq[pqi].push(*n0);
openNodes[x][y]=n0->getPriority(); // mark it on the open nodes map
// A* search
while(!pq[pqi].empty())
{
// get the current node w/ the highest priority
// from the list of open nodes
n0=new node( pq[pqi].top().getXpos(), pq[pqi].top().getYpos(),
pq[pqi].top().getDistance(), pq[pqi].top().getPriority());
x=n0->getXpos(); y=n0->getYpos();
pq[pqi].pop(); // remove the node from the open list
openNodes[y][x]=0;
// mark it on the closed nodes map
closedNodes[y][x]=1;
// quit searching when the goal state is reached
//if((*n0).estimate(xFinish, yFinish) == 0)
if(x==xFinish && y==yFinish)
{
// generate the path from finish to start
// by following the directions
string path="";
while(!(x==xStart && y==yStart))
{
j=dir_map[x][y];
c='0'+(j+node::dir/2)%node::dir;
path=c+path;
x+=dirY[j];
y+=dirX[j];
}
// garbage collection
delete n0;
// empty the leftover nodes
while(!pq[pqi].empty()) pq[pqi].pop();
return path;
}
// generate moves (child nodes) in all possible directions
for(i=0;i<node::dir;i++)
{
xdx=x+dirY[i]; ydy=y+dirX[i];
if(!(xdx<0 || xdx>sizeN-1 || ydy<0 || ydy>sizeM-1 || map[xdx][ydy]==0
|| closedNodes[xdx][ydy]==1))
{
// generate a child node
m0=new node( xdx, ydy, n0->getDistance(),
n0->getPriority());
m0->updateDistance(i);
m0->updatePriority(xFinish, yFinish);
// if it is not in the open list then add into that
if(openNodes[xdx][ydy]==0)
{
openNodes[xdx][ydy]=m0->getPriority();
pq[pqi].push(*m0);
// mark its parent node direction
dir_map[xdx][ydy]=(i+node::dir/2)%node::dir;
}
else if(openNodes[xdx][ydy]>m0->getPriority())
{
// update the priority info
openNodes[xdx][ydy]=m0->getPriority();
// update the parent direction info
dir_map[xdx][ydy]=(i+node::dir/2)%node::dir;
// replace the node
// by emptying one pq to the other one
// except the node to be replaced will be ignored
// and the new node will be pushed in instead
while(!(pq[pqi].top().getXpos()==xdx &&
pq[pqi].top().getYpos()==ydy))
{
pq[1-pqi].push(pq[pqi].top());
pq[pqi].pop();
}
pq[pqi].pop(); // remove the wanted node
// empty the larger size pq to the smaller one
if(pq[pqi].size()>pq[1-pqi].size()) pqi=1-pqi;
while(!pq[pqi].empty())
{
pq[1-pqi].push(pq[pqi].top());
pq[pqi].pop();
}
pqi=1-pqi;
pq[pqi].push(*m0); // add the better node instead
}
else delete m0; // garbage collection
}
}
delete n0; // garbage collection
}
return ""; // no route found
}