Sign in to follow this  
15Peter20

dam function problems

Recommended Posts

hey guys (and girls). im creatng a demo which implements breadth-first pathfind finding algorithem, and after much brain stress i thought it was complete. i ran the program, however when it its supposed to output the closed and open list nodes, instead of outputting the real values, its outputs the machien code values (anyway this is what i think its doing). im guessing its a problem with my functions that i have created, especially when im passing the nodes to and forth. here is my source code extract:
#include <iostream>
using namespace std;
#include <deque>

const int COORD_SIZE = 10;

struct coords
{
	int x;
	int y;
	coords* parent;
};// end struct

deque <coords*> openList;
deque <coords*> closedList;
coords* coord[COORD_SIZE];
coords* start;
coords* end;
coords* currentNode = new (coords);
coords* north = new (coords);
coords* south = new (coords);
coords* east = new (coords);
coords* west = new (coords);
coords* prior;
coords* path;
coords* node;

// function protoypes
void StartCoord();
void GoalCoord();
void AddNodeOpen(coords* node);
void AddNodeClosed(coords* node);
bool CheckEnd(coords* currentNode);
bool CheckNode(coords* node);
void DisplayOpen();
void DisplayClosed();

coords* CreateNorth(coords* currentNode);
coords* CreateEast(coords* currentNode);
coords* CreateSouth(coords* currentNode);
coords* CreateWest(coords* currentNode);

// main program
void main()
{		
	StartCoord();
	GoalCoord();

	// add start node to Open List
	AddNodeOpen(start);
	
	// check that the current node is not the goal node and node list is not empty
	while(currentNode != end || openList.empty())
	{
		// check is the openList is empty and break loop if true
		if(openList.empty())
		{
			cout<< "The list is empty!!"<< endl;
			break;
		}// end if
		
		//Pop the first element from the list and call it current
		currentNode = openList.front();
		openList.pop_front();

		//output current node!!!

		// check current node is goal node, break loop if true
		if(CheckEnd(currentNode))
		{
			cout<< "\nGoal co-ordinate found!!"<< endl;
			break;
		}// end if

		
		// create north node
		CreateNorth(currentNode);

		//create east node
		CreateEast(currentNode);

		//create south node
		CreateSouth(currentNode);

		// create west node
		CreateWest(currentNode);

		
		// check the list and add the new nodes if they are not already there
		if(CheckNode(north))			
		{
			AddNodeOpen(north);
		}// end if

		if(CheckNode(east))			
		{
			AddNodeOpen(east);
		}// end if

		if(CheckNode(south))			
		{
			AddNodeOpen(south);
		}// end if

		if(CheckNode(west))			
		{
			AddNodeOpen(west);
		}// end if

		// add current to closed list
		AddNodeClosed(currentNode);
		
		// display contents of list's
		DisplayOpen();
		DisplayClosed();

		system("pause");
	}// end while

	system("pause");
}//end main


// function that asks user for start co-ordinates
void StartCoord()
{
	int x, y;
	start = new (coords);
	cout<< "\nEnter start X co-ordinate: ";
	cin>> x;
	cout<< "\nEnter start Y co-ordinate: ";
	cin>> y;

	start->x = x;
	start->y = y;
	return;
}// end void StartCoord()


// function to ask user for goal co-ordinates
void GoalCoord()
{
	int x, y;
	end = new (coords);
	cout<< "\nEnter in destination X co-ordinate: ";
	cin>> x;
	cout<< "\nEnter in destination Y co-ordinate: ";
	cin>> y;

	end->x = x;
	end->y = y;
	return;
}// end void Goal Coord()


void AddNodeOpen(coords* node)
{
	node = new (coords);	
	openList.push_back(node);
}// end void addNodeOpen()


void AddNodeClosed(coords* node)
{
	node = new (coords);
	closedList.push_back(node);
}// end void addNodeClosed()


// function that checks if the current node is the goal co-ordinates
bool CheckEnd(coords* currentNode)
{
	if(currentNode == end)
	{
		return true;
	}else
	{
		return false;
	}
}// end bool check()


// function that checks if the node is in the OpenList already
bool CheckNode(coords* node)
{
	int x, y;
	x = node->x;
	y = node->y;

	// create lsit iterator
	deque <coords*>::iterator i;
	
	// assign iterator to start of openList
	i = openList.begin();

	// search through list untill the end,
	// and returns true if node is found
	while(i != openList.end())
	{
		if((*i)->x == x && (*i)->y == y)
		{
			return false;
		}
		i++;
	}
	return true;
}// end bool checkNode()


// function that creates a node north by 1
coords* CreateNorth(coords* currentNode)
{
	north->y = currentNode->y+1;
	north->x = currentNode->x;
	return north;	
}// end north()


// function that creates a node east by 1
coords* CreateEast(coords* currentNode)
{
	east->x = currentNode->x+1;
	east->y = currentNode->y;
	return east;
}// end east()


// function that creates a node south by 1
coords* CreateSouth(coords* currentNode)
{
	south->y = currentNode->y-1;
	south->x = currentNode->x;
	return south;
}// end south()


// function that creates a node west by 1
coords* CreateWest(coords* currentNode)
{
	west->x = currentNode->x-1;
	west->y = currentNode->y;
	return west;
}// end west()


void DisplayOpen()
{
	// create itterator
	deque <coords*>::iterator i;

	// asign iterator to start of open list
	i = openList.begin();
	
	cout<< "\nOpen list: "<< endl;
	// iterate through the list and display contents untill end of list
	while(i != openList.end())
	{
		cout<< (*i)->x<< " "<< (*i)->y<< endl;
		i++;
	}// end while
}// end void displayOpen()


void DisplayClosed()
{
	// create iterator
	deque <coords*>::iterator i;

	//asign iterator to start of closed list
	i = closedList.begin();

	cout<< "\nClosedList: "<< endl;
	// iterate through closed list adn display contents untill end of list
	while(i != closedList.end())
	{
		cout<< (*i)->x<< " "<< (*i)->y<< endl;
		i++;
	}// end while
}// end void displayClosed()

if u can see where i am going wrong i would be very appreciative. on a second little note im kinda new to visual studio, and if anyone can tell me how to debug my program line by line instead of adding breakpoints that would be helpfull too. 15Peter20 x

Share this post


Link to post
Share on other sites
Quote:
Original post by 15Peter20
on a second little note im kinda new to visual studio, and if anyone can tell me how to debug my program line by line instead of adding breakpoints that would be helpfull too.

There's an introduction to the debugger here.

Share this post


Link to post
Share on other sites

void AddNodeOpen(coords* node)
{
node = new (coords);
openList.push_back(node);
}// end void addNodeOpen()


Assigning 'new (coords)' to 'node' overwrites the pointer, so that it now points at a different node from the one you pointed at in the passed-in value. The open list does not contain the pointer you passed in; it contains a pointer to a newly created node with default values.

// function that creates a node north by 1
coords* CreateNorth(coords* currentNode)
{
north->y = currentNode->y+1;
north->x = currentNode->x;
return north;
}// end north()


Every time you call this function, you get the same pointer. You can keep changing the pointed-at coord all you like, but there is only one such object, and you iteratively return pointers to it. All your "north" pointers will point to the same coord, and you will just change its position each time.

But you don't need creation functions like this; just make a constructor that accepts x and y values.


bool CheckNode(coords* node)
{
int x, y;
x = node->x;
y = node->y;

// create lsit iterator
deque <coords*>::iterator i;

// assign iterator to start of openList
i = openList.begin();

// search through list untill the end,
// and returns true if node is found
while(i != openList.end())
{
if((*i)->x == x && (*i)->y == y)
{
return false;
}
i++;
}
return true;
}// end bool checkNode()


This returns false if the node is found, and true if it is not found, contrary to the comment. Which is a good thing, because of how you use the function:


if(CheckNode(north))
{
AddNodeOpen(north);
}// end if


i.e. adding the node if it is not in the list already.

Try giving things more descriptive names, like "notInOpenList()".


// function that checks if the current node is the goal co-ordinates
bool CheckEnd(coords* currentNode)
{
if(currentNode == end)
{
return true;
}else
{
return false;
}
}// end bool check()


This is needlessly verbose. 'return currentNode == end;' would suffice, and be more clear.




Basically, you aren't anywhere close. Sorry.

In fact, you are using far, FAR more pointers than are really relevant. Store coord objects by value in your deque, not pointers to them. The deque takes care of dynamic allocation. You should probably not have any 'new' statements in final, correct code at all - and far fewer global variables. Let 'start' and 'end' be coords, not pointers thereto. Similarly the results of "creation". Return a coord from the function. Make it a local variable; don't modify some global instance, because you need it to be a different one each time.

Share this post


Link to post
Share on other sites
jsut ebfore u posted your reply, i realised this problem with creating the new node coords* in the north, south, east adn west node cteationg fucntion, and have jsut got rid of them. i am trying now to cut down on the function use in this to keep thigs easier to read and follow.

the program now outputs the correct numbers, but i think i am expericing the other problem u mentioned, the program jsut keeps on going even if it finds the goal. ill take your advice on board and see what i can do.

cheers my friend. x

Share this post


Link to post
Share on other sites
firstly i am new to pointer and am jsut about gettin to grips with it, skills come with time and experience :)

1. constructor? i know i should know this but at this time it is slipping my mind, what i have done with the north, south, east and west is now:


north->x = currentNode->x+1;
north->y = currentNode->y;



is this doing exactly the same as the fucntion before? or will it create its own node now,

and with the goal state checking, in the function if i type return currentNode == end, will that return true then im guessing if curretnNode = goal?

whats verbose??

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