I have a structure called grid:
struct grid {
grid *parent;
int x, y;
float f, g, h;
};
I also create a vector of struct grid: vector<grid> open
Below is part of code for path-finding. I am trying to create a new grid called neighbor and in each iteration i add it to the open vector but since neighbor is changed every iteration, it is not getting added properly to the open vector. What is a more efficient way to do this? How to add to the open vector? Basically how to implement a linked vector of structure members instead of linked list?
while( !open.empty() )
{
grid current, neighbor;
current=//... minimum-value node in the open vector
for(vector<grid>::iterator it = open.begin(); it != open.end();++it )
if((it->x == current.x) &&(it->y == current.y))
it=open.erase(it);
for(i=0;i<4;i++)
{
neighbor.x=current.x+neighbor_primitves[i][0];
neighbor.y=current.y+neighbor_primitves[i][1];
if( (neighbor.x>=0) && (neighbor.x<=100) && (neighbor.y>=0) && (neighbor.y<=100))
{
neighbor.parent=new grid;
neighbor.parent->x=current.x;
neighbor.parent->y=current.y;
neighbor.g=current.g+1;
neighbor.h=heuristic(neighbor,goal);
neighbor.f=neighbor.g+neighbor.h;
if(isitinNless(neighbor,open))
for(vector<grid>::iterator it = open.begin(); it != open.end(); ++it)
{
if((it->x == neighbor.x) &&(it->y == neighbor.y))
it=open.erase(it);
}
if(!(isitin(neighbor,open)) )
open.push_back(neighbor);
}
}
closed.push_back(current);
}
EDIT:
grid* test=goal.parent;
cout<<test->x<<" "<<test->y;
When i add the following lines of codes at the end of while loop, I find that the parents were not updated outside the while loop, i.e. inside while loop i update the parents of each grid member but outside the scope of while loop those updates don't take place as if parents could not be assigned to any grid member. Entire code:
// A star
#include<iostream>
#include <vector>
#include <cmath>
using namespace std;
struct grid {
grid *parent;
int x, y;
float f, g, h;
};
float heuristic(grid one, grid two)
{
float norm= (one.x-two.x)*(one.x-two.x)+(one.y-two.y)*(one.y-two.y);
return (sqrt(norm));
}
bool isitin(grid &ref, vector<grid> &whole)
{
bool key=false;
if(whole.empty())
return key;
std::vector<grid>::iterator it;
for(it = whole.begin(); it != whole.end(); ++it)
{
if((it->x==ref.x) && (it->y==ref.y))
key=true;
}
return key;
}
bool isitinNless(grid &ref, vector<grid> &whole)
{
bool key=false;
if(whole.empty())
return key;
/*
node iter;
while(!whole.empty())
{
iter=whole.back();
if((iter.x==ref.x) && (iter.y==ref.y))
key=true;
whole.pop_back();
}*/
std::vector<grid>::iterator it;
for(it = whole.begin(); it != whole.end(); ++it)
if((it->x==ref.x) && (it->y==ref.y) && (ref.g < it->g))
key=true;
return key;
}
grid& findmin(vector<grid> &open)
{
int mini=2000000;
grid mininode;
/*
while(!open.empty())
{
iter=open.back();
if(iter.f<mini)
{
mini=iter.f;
}
open.pop_back();
}
*/
std::vector<grid>::iterator it;
for(it = open.begin(); it != open.end(); ++it) {
if(it->f<mini)
{
mini=it->f;
mininode=*it;
}
}
return mininode;
}
int main() {
/*
vector<node*> open;
vector<node*> closed;
node *start=new node;
start->x=50;
start->y=50;
start->f=0;
start->g=0;
start->h=0;// you can take it as zero. works instea of the actual distnace between goal and start.
node *goal=new node;
goal->x=53;
goal->y=50;
goal->f=-1;
goal->g=-1;
goal->h=0;
// put the starting node on the open list
open.push_back(start);
node *current=new node;
current=open.back();
cout<<current->x;
*/
vector<grid> open;
vector<grid> closed;
// neighbor generation scheme
int neighbor_primitves[4][2],i;
neighbor_primitves[0][0]=1; neighbor_primitves[0][1]=0;
neighbor_primitves[1][0]=0; neighbor_primitves[1][1]=1;
neighbor_primitves[2][0]=-1; neighbor_primitves[2][1]=0;
neighbor_primitves[3][0]=0; neighbor_primitves[3][1]=-1;
grid start;
start.parent=NULL;
start.x=50;
start.y=50;
start.f=0;
start.g=0;
start.h=0;// you can take it as zero. works instead of the actual distnace between goal and start.
grid goal;
goal.parent=&start; // just a cosmetic assignment.
goal.x=53;
goal.y=50;
goal.f=-1;
goal.g=-1;
goal.h=0;
// put the starting node on the open list
open.push_back(start);
/*if(isitin(start,open))
cout<<"YO!!!";
if(!open.empty())
cout<<"NO!!!";*/
/*
node current;
current=open.back();
cout<<current.x;
*/
while( !open.empty() )//&& !(findmin(open).x==goal.x) && !(findmin(open).y==goal.y) )
{
grid current, neighbor;
// find the node with the least f on the open list, call it "current"
current=findmin(open);
cout<<open.size();
if(current.x==goal.x && current.y==goal.y)
{
cout<<"Goal!!!\n";
break;
}
// pop current off the open list
for(vector<grid>::iterator it = open.begin(); it != open.end(); )
{
if((it->x == current.x) &&(it->y == current.y))
{
it=open.erase(it);
}
else
++it;
}
cout<<open.size();
// generate q's 8 successors and set their parents to current
for(i=0;i<4;i++)
{
neighbor.x=current.x+neighbor_primitves[i][0];
neighbor.y=current.y+neighbor_primitves[i][1];
if( (neighbor.x>=0) && (neighbor.x<=100) && (neighbor.y>=0) && (neighbor.y<=100))
{
neighbor.parent=new grid;
neighbor.parent->x=current.x;
neighbor.parent->y=current.y;
neighbor.g=current.g+1;
neighbor.h=heuristic(neighbor,goal);
neighbor.f=neighbor.g+neighbor.h;
//if(!(isitinNless(neighbor,open)) && !(isitinNless(neighbor,closed)))
// open.push_back(neighbor);
if(isitinNless(neighbor,open))
{
// pop neighbor off the open list
for(vector<grid>::iterator it = open.begin(); it != open.end(); )
{
if((it->x == neighbor.x) &&(it->y == neighbor.y))
{
it=open.erase(it);
}
else
++it;
}
}
if(isitinNless(neighbor,closed))
{
// pop neighbor off the closed list
for(vector<grid>::iterator it = closed.begin(); it != closed.end(); )
{
if((it->x == neighbor.x) &&(it->y == neighbor.y))
{
it=closed.erase(it);
}
else
++it;
}
}
if(!(isitin(neighbor,open)) && !(isitin(neighbor,closed)))
open.push_back(neighbor);
}
}
closed.push_back(current);
// cout<<open.size()<<"\n";
cout<<"\n";
for(vector<grid>::iterator it = open.begin(); it != open.end(); ++it)
cout<<it->x<<" "<<it->y<<" "<<it->parent->x<<" "<<it->parent->y<<"\n";
}
grid* test=goal.parent;
cout<<test->x<<" "<<test->y;
cin.get();
return 0;
}
Your problem is in findmin. You're expecting that to return a reference to an element of your vector but instead it is returning a reference to an invalid data location:
grid& findmin(vector<grid> &open)
{
int mini=2000000;
grid mininode; //locally allocated grid
std::vector<grid>::iterator it;
for(it = open.begin(); it != open.end(); ++it) {
if(it->f<mini)
{
mini=it->f;
mininode=*it; //assigns values in the grid pointed to by it to mininode
}
}
return mininode; //returns a reference to the locally scoped grid
} //destroys mininode
You can clearly see how this is a problem. A better solution would be replacing findmin with:
auto& current = *find_min(open.begin(), open.end(), [](const grid& first, const grid& smallest){return first->f < smallest->f;});