0

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;
}
userzizzy
  • 159
  • 1
  • 2
  • 11
  • 2
    what do you mean by linked vector? – Géza Török Jan 26 '15 at 16:47
  • I know the term is incorrect. I meant a vector which has struct elements that are linked to each other. – userzizzy Jan 26 '15 at 16:50
  • 1
    at least your vector should contain `grid*`s. do you know why? – Géza Török Jan 26 '15 at 16:55
  • @userzizzy - `vector` It isn't a good idea to create a vector with a type that doesn't follow the "rule of 3". – PaulMcKenzie Jan 26 '15 at 17:01
  • @Walter there is no `node`. mistake. – userzizzy Jan 26 '15 at 17:04
  • @GézaTörök Why? i think it is alright to pass by reference like this, rather than using pointers to complexify things. – userzizzy Jan 26 '15 at 17:06
  • @PaulMcKenzie I don't think you're statement is true, the way it was worded, for example `vector` is common. If you were to change this to say, "It isn't a good idea to create a `vector` with a type which owns dynamically allocated elements but does have a custom destructor." That I would agree with. – Jonathan Mee Jan 26 '15 at 17:06
  • Normally you would store all your "things" in a separate place and keep pointers (or indexes) to those in the "open" list. – molbdnilo Jan 26 '15 at 17:06
  • @molbdnilo could you give a concrete c++ example or website to understand your very abstract wise advice? – userzizzy Jan 26 '15 at 17:13
  • @JonathanMee Your comment "It isn't a good idea to create a vector with a type which owns dynamically allocated elements but does have a custom destructor." is difficult to understand. Could you elaborate it as an answer to my question with concrete code example? i think this point can help me solve my issue. – userzizzy Jan 26 '15 at 17:15
  • @userzizzy I'm completely unsure what `parent` should be doing, Typically `parent`'s `parent` would be set to another `grid` already in existence. As it is, it may as well just be a `pair` and you could save yourself all the dynamic memory management. – Jonathan Mee Jan 26 '15 at 17:18
  • @userzizzy who is responsible for deleting, `parent`? `grid` owns `parent` so you should write a custom destructor to take care of that, or you should not store `grid`s in a `vector`. (Another alternative would be to use an auto-pointer, instead of a dumb pointer.) – Jonathan Mee Jan 26 '15 at 17:22
  • 1
    @JonathanMee - Copying is what a vector is going to do. Placing types in a vector that have bad copy semantics that will cause issues is not a good idea. – PaulMcKenzie Jan 26 '15 at 17:23
  • @JonathanMee I am trying to implement Astar. I have attached my entire code at the end of question. the code works perfectly fine as far as algorithmic performance is concerned. I checked the while loop and debugged it by printing out the parents and neighbours for reaching (53,50) from (50,50) so it worked fine but outside the while loop, the parents and neighbours were not updated at all as if operations under the while loop were temporary. – userzizzy Jan 26 '15 at 17:35
  • @PaulMcKenzie So if not using `` how to implement a bunch of `grid` points whose parents point to other `grid` members? And please give some concrete c++ web reference as i am very green at coding. – userzizzy Jan 26 '15 at 17:38
  • 1
    @userzizzy - Quite simply put, your `struct grid` is not safely copyable. The reference you're looking for is rule of 3: http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three Please go to the `Managing resources` section, as it directly applies to your struct and how you've set it up with that pointer member. – PaulMcKenzie Jan 26 '15 at 17:43
  • @PaulMcKenzie I see what you're saying with respect to copying. You could use a `shared_ptr` but that doesn't seem like it would yield expected behavior. I think you are correct that in order to use a vector in a way that makes sense here you'd have to have a custom copy constructor. – Jonathan Mee Jan 26 '15 at 17:57
  • @PaulMcKenzie So basically i should use class instead of struct. – userzizzy Jan 26 '15 at 18:03
  • @userzizzy - No. A struct can have member functions, just as a class can have. http://stackoverflow.com/questions/92859/what-are-the-differences-between-struct-and-class-in-c – PaulMcKenzie Jan 26 '15 at 18:03

1 Answers1

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;});
Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288