Blad podczas wyswietlania tablicy 2D

0

Witam. Mam problem z wyświetlaniem tablicy 2D. Mój program ładuje plik .txt w formacie:

1 1 1 1 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1

Moim celem jest to aby program wyświetlił "." w miejscu "1" i "X" w miejscu "0". Niestety, wynik jest zupełnie inny niz tego oczekuje (puste miejsca, oraz matryca odwrócona o 90 stopni). Jakies sugestie? Oto mój kod:

#include <iostream>
#include <fstream>
#include <iomanip>
#include <queue>
#include <string>
#include <math.h>
#include <ctime>


using namespace std;

void loadMap();

const int n = 5;
const int m = 7;
static int map[n][m];

int main()
{
	loadMap();

    
        // display the map
        for(int y=0;y<n;y++)
        {
            for(int x=0;x<m;x++)
                if(map[x][y]==0)
                    cout<<"X"; //obstacle
                else if(map[x][y]==1)
                    cout<<"."; //walkable area
                
            cout<<endl;
        }
    

getchar();
return 0;

}

void loadMap ()
{
//load the map from .txt file
ifstream file;
file.open("testmap.txt");

if(file.good()==true)
{
    for(int i=0;i<n;i++)
    {
       for(int j=0;j<m;j++)
       {
          file>>map[i][j];
       }
    }
    file.close();
}
else
{
    cout<<"Cannot open the file";
}
}
 
1

To jest kara za nadawanie zmiennym nazw od czapy.
Tu poprawione: http://ideone.com/A95QpN

0

Dzieki za odpowiedz, ale gdy probuje Twojego kodu to nic na konsoli mi sie nie wyswietla...

1

zamień:
istream &file=cin;
na:
ifstream file("testmap.txt");

oraz przed:
return 0;
wstaw:
cin.get();

0

Dzieki, wlasnie tak zrobilem i dziala. Tylko jedno pytanie. Co mam zrobic aby poprawnie wyswietlic tablice, gdy ma ona przypisane rozne wartosci, tzn. wyglada mniej wiecej tak:

S 1 1 1 1 1 1
1 R 1 0 1 1 1
1 1 R 0 1 1 1
1 1 R 0 1 1 1
1 1 1 F 1 1 1

Probowalem zrobic cos takiego, ale w ogole nie dziala...:

// display the map with the route
        for(int y=0;y<n;y++)
        {
            for(int x=0;x<m;x++)
                if(map[x][y]==0)
                    cout<<"X"; //obstacle
                else if(map[x][y]==1)
                    cout<<"."; //walkable area
                else if(map[x][y]==2)
                    cout<<"S"; //start
                else if(map[x][y]==3)
                    cout<<"R"; //route
                else if(map[x][y]==4)
                    cout<<"F"; //finish
            cout<<endl;
        } 
0

Bardzo chetnie bym sie nauczyl :) czy mozesz mi wytlumaczyc na czym polega moj blad?

0
#include <iostream>
#include <fstream>
using namespace std;
 
const size_t Ysize=5;
const size_t Xsize=7;
int map[Ysize][Xsize];
 
bool loadMap(const char *map)
  {
   ifstream file(map);
   if(!file) return false;
   for(size_t y=0;y<Ysize;++y) for(size_t x=0;x<Xsize;++x) file>>map[y][x];
   return true;
  }
 
int main()
  {
   if(!loadMap("testmap.txt"))
     {
      cerr<<"Cannot open the file"<<endl;
      return 1;
     }
   for(size_t y=0;y<Ysize;++y,cout<<endl) for(size_t x=0;x<Xsize;++x) cout<<"X.SRF"[map[y][x]];
   cin.get();
   return 0;
  }
0

Zaadaptowalem kod wedlug w/w wskazowek, ale teraz zamiast blednie wyswietlanej tablicy mam puste okno konsoli...

#include <iostream>
#include <fstream>
#include <iomanip>
#include <queue>
#include <string>
#include <math.h>
#include <ctime>
#include"node.h"

using namespace std;

bool loadMap();
void displayMap();
string pathFind( const int & xStart, const int & yStart, const int & xFinish, const int & yFinish );

//Map size
const size_t Ysize=5;
const size_t Xsize=7;

//Start and finish locations
const int sX=0;
const int sY=0;

const int fX=2;
const int fY=5;

//Node maps
static int closedNodes[Ysize][Xsize]; //the set of nodes alreadirY evaluated
static int openNodes[Ysize][Xsize]; // the set of nodes to be evaluated; initialy only containing start node
static int map[Ysize][Xsize];	//work map

//Directions

static int dirX[node::dir]={0, 1, 1, 1, 0, -1, -1, -1};
static int dirY[node::dir]={1, 1, 0, -1, -1, -1, 0, 1};
static int dir_map[Ysize][Xsize]; //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(sX, sY, fX, fY);

	// follow the route on the map and display it 
    if(route.length()>0)
    {
        int j; char c;
        int x=sX;
        int y=sY;
        map[x][y]=2;
        for(int i=0;i<route.length();i++)
        {
            c =route.at(i);
            j=atoi(&c); 
            x=x+dirX[j];
            y=y+dirY[j];
            map[x][y]=3;
        }
        map[x][y]=4;
    
        // display the map with the route
       for(size_t y=0;y<Ysize;++y,cout<<endl) for(size_t x=0;x<Xsize;++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<Ysize;++y) 
	   for(size_t x=0;x<Xsize;++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<Ysize;y++)
    {
        for(x=0;x<Xsize;x++)
        {
            closedNodes[x][y]=0;
            openNodes[x][y]=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[x][y]=0;
        // mark it on the closed nodes map
        closedNodes[x][y]=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+=dirX[j];
                y+=dirY[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+dirX[i]; ydy=y+dirY[i];

            if(!(xdx<0 || xdx>Ysize-1 || ydy<0 || ydy>Xsize-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
}
0

Wciąż nazewnictwo od czapy się mści:

closedNodes[Ysize][Xsize];
closedNodes[x][y]=0;

openNodes[Ysize][Xsize];
openNodes[x][y]=0;

Ale widać dopiero teraz.

0

Moja daaaaawna implementacja (jedyne co zmieniłem to zmieniłem nawiasy z takich jak Twoje (jak kiedyś pisałem) na fajniejsze (jakie są teraz) ;) ). Pisana na podstawia artykułu z wikipedii - teraz widzę że pseudokod tam się mocno zmienił.
Jest pisana na dość wysokim poziomie abstrakcji (parametryzowana czterema typami itp) i ogólnie mogła by być lepsza (teraz bym kilka rzeczy inaczej napisał), ale powinna działać (w każdym razie, kiedyś działała jak ją testowałem ;) ) i jest chyba dość czytelna (w każdym razie, czyta się ją trochę jak specyfikację, a o to chodzi w końcu).

Raczej nie da się jej bezpośrednio wykorzystać, ale może Ci w czymś pomoże.

template <class GraphT, class NodeT, int (*HeuristicEstimate) (NodeT, NodeT), class NodeComparer>
bool astar_alg::astar(const GraphT &graph, NodeT start, NodeT goal, vector<NodeT> &result) {
    set<NodeT, NodeComparer> closedSet, openSet;
    map<NodeT, NodeT, NodeComparer> cameFrom;
    map<NodeT, int, NodeComparer> gScore, hScore, fScore;
    
    openSet.insert(start);
    gScore[start] = 0;
    hScore[start] = fScore[start] = HeuristicEstimate(start, goal);
    
    while(!openSet.empty()) {
        NodeT x = *openSet.begin();
        if (x == goal) { 
            reconstructPath(cameFrom, cameFrom[goal], result);
            return true; 
        }
        
        openSet.erase(openSet.begin());
        closedSet.insert(x);
        vector<NodeT> neighs = graph.getNeighs(x);
        for(vector<NodeT>::const_iterator it = neighs.begin(); it != neighs.end(); ++it) {
            NodeT y = *it;
            if (closedSet.find(y) != closedSet.end()) { continue; }
            
            int tentactiveG = gScore[x] + graph.distanceBetween(x, y);
            if (openSet.find(y) == openSet.end()) {
                openSet.insert(y);
                hScore[y] = HeuristicEstimate(y, goal);
            } else if (tentactiveG >= gScore[y]) { continue; }
            
            cameFrom[y] = x;
            gScore[y] = tentactiveG;
            fScore[y] = gScore[y] + hScore[y];
        }
    } return false;
}

edit:

Jak juz pisalem... jestem laikiem. Moze za pare lat kodowania po 8 godzin dziennie bede wstanie to napisac w 50 linijkach :) - jaspernorth 2 minuty temu

Masz w 36 linijkach ;)

Oczywiście nie ma tu kodu np. HeuristicEstimate, graph.distanceBetween(x, y), ale i tak by było lepiej gdybyś u siebie te zadania wydzielił do osobnych funkcji (bo nie sa związane z samym algorytmem).

0

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
} 
0

_13th_Dragon - teraz nazewnictwo powinno byc OK. sizeN to maksymalny rozmiar y. Oto najnowszy 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, ySize, xSize, ydy, xdx;
    static char c;
    pqi=0;

    // reset the node maps
    for(ySize=0;ySize<sizeN;ySize++)
    {
        for(xSize=0;xSize<sizeM;xSize++)
        {
            closedNodes[ySize][xSize]=0;
            openNodes[ySize][xSize]=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[ySize][xSize]=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());

        ySize=n0->getXpos(); xSize=n0->getYpos();

        pq[pqi].pop(); // remove the node from the open list
        openNodes[ySize][xSize]=0;
        // mark it on the closed nodes map
        closedNodes[ySize][xSize]=1;

        // quit searching when the goal state is reached
        //if((*n0).estimate(xFinish, yFinish) == 0)
        if(ySize==xFinish && xSize==yFinish) 
        {
            // generate the path from finish to start
            // by following the directions
            string path="";
            while(!(ySize==xStart && xSize==yStart))
            {
                j=dir_map[ySize][xSize];
                c='0'+(j+node::dir/2)%node::dir;
                path=c+path;
                ySize+=dirY[j];
                xSize+=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++)
        {
            ydy=ySize+dirY[i]; xdx=xSize+dirX[i];

            if(!(ydy<0 || ydy>sizeN-1 || xdx<0 || xdx>sizeM-1 || map[ydy][xdx]==0 
                || closedNodes[ydy][xdx]==1))
            {
                // generate a child node
                m0=new node( ydy, xdx, 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[ydy][xdx]==0)
                {
                    openNodes[ydy][xdx]=m0->getPriority();
                    pq[pqi].push(*m0);
                    // mark its parent node direction
                    dir_map[ydy][xdx]=(i+node::dir/2)%node::dir;
                }
                else if(openNodes[ydy][xdx]>m0->getPriority())
                {
                    // update the priority info
                    openNodes[ydy][xdx]=m0->getPriority();
                    // update the parent direction info
                    dir_map[ydy][xdx]=(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()==ydy && 
                           pq[pqi].top().getYpos()==xdx))
                    {                
                        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
}
0

openNodes[ySize][xSize]=n0->getPriority(); // mark it on the open nodes map jakie wartości maja ySize,xSize ?

0

ySize = 0; xSize = 0;

1

Po zmianie struktury danych i kilku optymalizacjach:

#include <iostream>
#include <fstream>
using namespace std;

const size_t Ysize=5;
const size_t Xsize=7;
const size_t Msize=Ysize*Xsize;
const size_t MARK=(size_t)-1;

struct Node
  {
   size_t qu, // zamiast kolejki priorytetowej
          to, // zamiast dirX i dirY - gdzie idziemy
          map; // element mapy
  };

bool loadMap(Node map[],const char *fileName)
  {
   ifstream file(fileName);
   if(!file) return false;
   for(size_t m=0;m<Msize;++m) file>>map[m].map;
   return file;
  }

void show(Node map[])
  {
   for(size_t m=0;m<Msize;cout<<endl) for(size_t x=0;x<Xsize;++x,++m) cout<<"X.abcdefghijklmnopqrstuvwxyz"[map[m].map];
   cout<<endl;
  }

size_t toId(size_t y,size_t x) { return y*Xsize+x; } // z Y,X do pozycji w tablice
size_t toX(size_t pos) { return pos%Xsize; } // z pozycji w tablice na X
size_t toY(size_t pos) { return pos/Xsize; } // z pozycji w tablice na Y

bool pathFind(Node map[],size_t sid,size_t fid)
  {
   for(size_t m=0;m<Msize;++m) map[m].qu=map[m].to=Msize;
   size_t first=fid,last=fid; // zaczynamy od końca
   map[fid].map=MARK; // zaznaczamy że odwiedzony
   while(first<Msize)
     {
      size_t curr=first; // pierwszy z kolejki
      first=map[first].qu; // usuwamy z kolejki
      if(first>=Msize) last=Msize; // brak pierwszego => brak ostatniego
      for(size_t dy=0;dy<=2;++dy)
        {
         for(size_t dx=0;dx<=2;++dx)
           {
            size_t y=toY(curr)+dy-1,x=toX(curr)+dx-1,m=toId(y,x); // w okolicach curr
            if((y<Ysize)&&(x<Xsize)&&(map[m].map==1)) // jeżeli możemy tam wstać
              {
               map[m].map=MARK; // zaznaczamy że odwiedzony
               map[m].to=curr; // zaznaczamy że dokąd trafimy z tej pozycji
               last=(last<Msize?map[last].qu:first)=m; // dodajemy do kolejki
              }
           }
        }
      if(map[sid].map!=1) // jeżeli znaleziono drogę
        {
         for(size_t m=0;m<Msize;++m) if(map[m].map==MARK) map[m].map=1; // usuwamy zaznaczenia
         return true;
        }
     }
   return false; // nie znaleziono drogi
  }

int main()
  {
   Node map[Msize];
   if(!loadMap(map,"testmap.txt"))
     {
      cerr<<"Bad file data"<<endl;
      return 1;
     }
   size_t sid=toId(0,0);
   pathFind(map,sid,toId(2,5));
   show(map);
   for(size_t m=sid;m<Msize;m=map[m].to) cout<<toY(m)<<','<<toX(m)<<' ';
   cout<<endl<<endl;
   for(size_t m=sid,x=1;m<Msize;m=map[m].to) map[m].map=++x; // mark steps
   show(map);
   cin.get();
   return 0;
  }

Proszę zauważyć że nie ma żadnych kolejek priorytetowych, żadnych dodatkowych tablic a nawet żadnych tablic dwuwymiarowych.

0

Witam ponownie. Probuje wprowadzic do mojego kodu zroznicowany koszt poruszania sie po mapie. Zmienilem format pliku .txt z ktorym pracuje na:

1 1 2 2 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1

Zalozmy ze 2 reprezentuje "bagna" gdzie koszt ruchu jest np. podwojony. Chodzi mi o to aby algorytm bral to po uwage i dalej przeliczal najlepsza trase, uwzgledniajac dodatkowy teren. Probowalem to zrobic, zwiekszajac wartosc "Distance" podczas generowania ruchu, ale nie przynioslo to pozadanego efektu. Moze bedziecie w stanie mi pomoc. Oto moj kod:

#include <iostream>
#include <fstream>
#include <iomanip>
#include <queue>
#include <string>
#include <math.h>
#include <ctime>
#include "node.h"

using namespace std;

//function declaration
bool loadMap();
void displayMap();
string pathFind( const int & xStart, const int & yStart, const int & xFinish, const int & yFinish );

//map size
const int sizeN = 5;			//number of rows
const int sizeM = 7;			//number of columns

//start and finish locations
const int sY=4;
const int sX=0;

const int fY=0;
const int fX=6;

//node maps
static int closedNodes[sizeN][sizeM];	//the set of nodes already evaluated
static int openNodes[sizeN][sizeM];		//the set of nodes to be evaluated, initialy only start node
static int map[sizeN][sizeM];			//work map

//directions
static int dirY[node::dir]={0, 1, 1, 1, 0, -1, -1, -1};		//horizontal movement
static int dirX[node::dir]={1, 1, 0, -1, -1, -1, 0, 1};		//vertical movement
static int dir_map[sizeN][sizeM];							//map of directions


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;	//mark start point
        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;	//mark route on the map
        }
        map[y][x]=4;		//mark finnish point
    
     //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
return 0;
}


//load the map from .txt file
bool loadMap()
  {
   ifstream file("testmap.txt");
   if(!file) return false;
   for(int y=0;y<sizeN;++y) 
	   for(int x=0;x<sizeM;++x) 
		   file>>map[y][x];
   return true;
  }

void displayMap()
{
	  //display the map
     for(size_t y=0;y<sizeN;++y,cout<<endl)
		 for(size_t x=0;x<sizeM;++x) cout<<"X."[map[y][x]];
}

//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=0;		//priority queue index
    static node* n0;		//start node
    static node* m0;		//child node
    static int i;
	static int j;
	static int ySize;		//vertical size
	static int xSize;		//horizontal size
	static int ydy;			//vertical movement
	static int xdx;			//horizontal movement
    static char c;			//route step

    //reset the node maps
    for(ySize=0;ySize<sizeN;ySize++)
    {
        for(xSize=0;xSize<sizeM;xSize++)
        {
            closedNodes[ySize][xSize]=0;
            openNodes[ySize][xSize]=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[ySize][xSize]=n0->getPriority(); //mark it on the open nodes map

    //A* search
    while(!pq[pqi].empty())
    {
        //get the current node with 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());

        ySize=n0->getXpos();
		xSize=n0->getYpos();

        pq[pqi].pop(); //remove the node from the open list
        openNodes[ySize][xSize]=0;

        //mark it on the closed nodes map
        closedNodes[ySize][xSize]=1;

        //quit searching when the goal state is reached
        if(ySize==xFinish && xSize==yFinish) 
        {
            //generate the path from finish to start by following the directions digits
            string path="";
            while(!(ySize==xStart && xSize==yStart))
            {
                j=dir_map[ySize][xSize];
                c='0'+(j+node::dir/2)%node::dir;
                path=c+path;
                ySize+=dirY[j];
                xSize+=dirX[j];
            }

            //free the memory
            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++)
        {
            ydy=ySize+dirY[i]; xdx=xSize+dirX[i];

            if(!(ydy<0 || ydy>sizeN-1 || xdx<0 || xdx>sizeM-1 || map[ydy][xdx]==0 
                || closedNodes[ydy][xdx]==1))
            {
				//generate a child node
                m0=new node( ydy, xdx, 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[ydy][xdx]==0)
                {
                    openNodes[ydy][xdx]=m0->getPriority();
                    pq[pqi].push(*m0);

                    //mark its parent node direction
                    dir_map[ydy][xdx]=(i+node::dir/2)%node::dir;
                }
                else if(openNodes[ydy][xdx]>m0->getPriority())
                {
                    //update the priority
                    openNodes[ydy][xdx]=m0->getPriority();

                    //update the parent direction
                    dir_map[ydy][xdx]=(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()==ydy && 
                           pq[pqi].top().getYpos()==xdx))
                    {                
                        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; //free the memory
            }
        }
        delete n0; //free the memory
    }
    return ""; //no route found
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1