Sign in to follow this  
adam23

Requesting some help please

Recommended Posts

I have been working on a simple pathfinding program using the A* algorithm. I originally started using std::priority_queue and std::list for the open and closed lists respectfully. Then I got this error message during debug. Error Message So I switched to a LinkedList class and and created a function that orders them in the correct order, but no luck I still get the same error. The next thing I tried was adding a logging class so I could track through the program since all my attempts at debugging didn't work. I found out the path is being found everytime, so the algorithm works. Oh I forgot to mention I have to run the program in Release mode since I get that error above anytime I run the debug version. Once I press exit in Release mode the program terminates after asking me if I want to debug the application. The Engine works fine as I have used it for several applications with no problems so I know that isn't the problem. What confuses me the most is that I got the same thing whether I used std::priority_queue or LinkedList.h. Anyway you guys wouldn't mind taking a look at it to let me know what I'm doing wrong. You can download the source for VS 2003 here:Program Here is what a portion of my logging file looks like: n current xy values are 22 14 ------------------ Node is added Node is added Node is added Node is added Node is added node is blocked 15 21 Node is added In Enemy::Render() In Enemy::FindPath() ------------------ n current xy values are 21 13 ------------------ In Enemy::Render() Path found Just a note there are a few things that are not complete like getting the sprite to turn in the righ direction, but right now I am just concerned with the bigger problems.

Share this post


Link to post
Share on other sites
Something is either a) using a pointer that's already been freed, b) using a pointer that's been stomped on, c) using a pointer that's not been allocated, or d) your program is stomping on memory it shouldn't be.

So, you should run the program in the debugger, and look at the call stack where the assert triggers - then take a look at the pointer that's being passed down, and figure out what's wrong with it.

VC++ (in debug) fills memory with different patterns to assist debugging, so you should be able to figure out what's going on. There are also a bunch of _Crt debugging functions that can help narrow down where things are going wrong.

Share this post


Link to post
Share on other sites
I think your right, so I redesigned my program by creating an orderedLinkedList class. Everything seems to work well except my search function. I declare it like this:

OrderedLinkedList<Node*> m_open;
OrderedLinkedList<Node*> m_closed;

So when I use this search function for some reason it never returns true.

//===========================================
//Returns true if searchItem is in list
//===========================================
bool search(const Type& searchItem)const
{
nodeType<Type> *current;
bool found = false;
current = first;
while(current != NULL && !found)
{
if(current->info == searchItem)
found = true;
else
current = current->link;
}
return found;
}


I have an overloaded operator in struct Node that test for the value of m_f which is the overall cost to travel to the node. Here is my node structure.

struct Node{
bool blocked;
bool visited;
int weight;
Node *parent;
int x, y;
int m_f,m_h,m_g;
bool operator==(const Node& node)const
{
return (x == node.x && y == node.y);
}
bool operator <= (const Node& node)const
{
return( m_f <= node.m_f);
}
const Node& operator=(const Node& rhs)
{
blocked = rhs.blocked;
visited = rhs.visited;
weight = rhs.weight;
x = rhs.x;
y = rhs.y;
parent = rhs.parent;
m_f = rhs.m_f;
m_g = rhs.m_g;
m_h = rhs.m_h;
return *this;
}
bool operator < (const Node& rhs)const
{
return(m_f < rhs.m_f);
}


};


This is the entire OrderedLinkedList class in case it will help solve any problems.

#ifndef _ORDERED_LINKED_LIST_H
#define _ORDERED_LINKED_LIST_H

//Define the node

template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};

template <class Type>
class OrderedLinkedList
{
public:
OrderedLinkedList()
{
count = 0;
first = NULL;
last = NULL;
}
~OrderedLinkedList()
{
destroyList();
}//end destructor
//===============================================
//Destroys List
//===============================================
void destroyList()
{
nodeType<Type> *temp;
while(first != NULL)
{
temp = first;
first = first->link;
delete temp;
}
last = NULL;
count = 0;
}
//===========================================
//Returns the length of the list
//===========================================
int length()
{
return count;
}
//===========================================
//Returns the info contained at the front of
//the list
//===========================================
Type front()
{
return first->info;
}
//============================================
//Removes the front item from the list
//============================================
void removeFront()
{
if(first != NULL)
{
nodeType<Type> *current;
current = first;
first = first->link;
if(first == NULL)
last = NULL;
delete current;
count--;
}
}
//===========================================
//Returns true if searchItem is in list
//===========================================
bool search(const Type& searchItem)const
{
nodeType<Type> *current;
bool found = false;
current = first;
while(current != NULL && !found)
{
if(current->info == searchItem)
found = true;
else
current = current->link;
}
return found;
}
//========================================================
//Function inserts Node based on < criteria
//========================================================
void insertNode(const Type& newItem)
{
nodeType<Type> *current;//pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
nodeType<Type> *newNode; //pointer to create new node

bool found;
newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = NULL;

if(first == NULL)
{
first = newNode;
count++;
}
else
{
current = first;
found = false;

while(current != NULL && !found)
{
if(current->info < newItem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
}
if(current == first)
{
newNode->link = first;
first = newNode;
count++;
}
else
{
trailCurrent->link = newNode;
newNode->link = current;
count++;
}

}
}
//==============================================
//Function deletes specific deleteItem from list
//==============================================
void deleteNode(const Type& deleteItem)
{
nodeType<Type> *current;
nodeType<Type> *trailCurrent;
bool found;

if(first == NULL)
{
//Cannot remove from an empty list
}
else
{
current = first;
found = false;
while(current != NULL && !found)
{
if(current->info >= deleteItem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
}
if (current == NULL)
{
//The item is not in the list
}
else
{
if(current->info == deleteItem)
{
if(first == current)
{
first = first->link;
delete current;
}
else
{
trailCurrent->link = current->link;
delete current;
}
count--;
}
else
{
//Item is not in the list
}
}
}
}//End function





private:
int count;

nodeType<Type> *first;
nodeType<Type> *last;
};
#endif



It looks like everything is working except for the search, I don't know if it is because I am passing by reference or not. Does anyone know what I am doing wrong.

Thanks in advance for helping me, this program is really kicking me around today.

Share this post


Link to post
Share on other sites
Quote:
Original post by adam23
Does anyone know what I am doing wrong.

Yes.
Quote:
Original post by adam23
I redesigned my program by creating an orderedLinkedList class.

That. Stick with the standard containers and algorithms. I don't remember enough about A* to suggest a solution, but I'm quite certain a custom linked list class is not one.

Share this post


Link to post
Share on other sites
Please, if at all possible, scrape up the old std::list/std::priority_queue version and show that. :s

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this