Thread: linked list recursive function spaghetti

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    465

    linked list recursive function spaghetti

    i know you guys are going to hate me for posting the code for this function, if not because its convoluted, simply because its long. but here is some background:

    this function is designed to be able to find a random meandering path between two points on a map ( for drawing roads, rivers, etc...). the mapInfo is a 2D array of intergers holding the terrain type of each square on the map, and MOUNTAIN, DESERT and so forth are all just #define-d ints.

    it compiles with no errors, and gives me no errors when its running, but the function never returns.

    so thats the last thing im going to say before posting my code, because i know only a handful of brave individuals will make it all the way to the bottom of it. i heavily commented it for somewhat ease of reading. if you can tell me why this doesnt work like i expect it to, it would be greatly appreciated...

    Code:
    // make a path of a certain type of terrain connecting two points
    // do not read this function if you have had trouble sleeping or have
    // a history of heart problems or depression
    void Map::makePath( int terrain, COORD source, COORD dest )
    {
    	// uh oh... its linked list time...
    	struct node
    	{
    		int x;
    		int y;
    		node * next;
    	} sourceNode;
    
    	sourceNode.x = source.X;
    	sourceNode.y = source.Y;
    	sourceNode.next = 0;
    
    	node * current = &sourceNode;
    
    	// find our way through the mountains and deserts 
    	while (  current->x != dest.X && current->y != dest.Y  )
    	{
    		// add a node to our search list
    		node * temp = new node;
    
    		if ( !sourceNode.next )
    		{
    			sourceNode.next = temp;
    			current = temp;
    			current->next = 0;
    		}
    		else
    		{
    			current->next = temp;
    			current = temp;
    			current->next = 0;
    		}
    
    		// 50% chance to change the y direction (unless we are already directly over/under our destination)
    		if ( rand() % 2 && current->y != dest.Y)
    		{
    			// if we are below where we want to go...
    			if ( source.Y > dest.Y )
    			{
    				// set this node up
    				current->y = source.Y - 1;
    				current->x = source.X;
    				
    				// hold our current location
    				int tempY = current->y;
    
    				// if we are now on a mountain or desert, find a way around it
    				if ( mapInfo[current->y][source.X] == MOUNTAIN || mapInfo[current->y][source.X] == DESERT )
    				{
    					// go up until you hit the top of the map, or a good square
    					while ( tempY > 0 && mapInfo[tempY][source.X] == MOUNTAIN || mapInfo[tempY][source.X] == DESERT )
    						tempY--;
    
    					// if you hit the top of the map, go down until you hit the bottom or a good square
    					if ( tempY <= 0 )
    					{
    						tempY = current->y;
    						while ( tempY < MapSizeY && mapInfo[tempY][source.X] == MOUNTAIN || mapInfo[tempY][source.X] == DESERT )
    							tempY++;
    
    						// if we couldnt find a good path...
    						if ( tempY >= MapSizeY ) 
    						{
    							// free up our memory
    							current = sourceNode.next;
    							while ( current->next )
    							{
    								node * temp = current;
    								current = current->next;
    								delete temp;
    							}
    							delete current;
    
    							// then exit the function
    							return;
    						}
    					}
    
    					else
    					{
    						// we want a wide path... 
    						// if you dont have a good wide path, go back and check the other side
    						if ( tempY - 5 <= 0 )
    						{
    							tempY = current->y;
    							while ( tempY < MapSizeY && mapInfo[tempY][source.X] == MOUNTAIN || mapInfo[tempY][source.X] == DESERT )
    								tempY++;
    
    							// if we couldnt find a good path...
    							if ( tempY + 5 >= MapSizeY ) 
    							{
    								// free up our memory
    								current = sourceNode.next;
    								while ( current->next )
    								{
    									node * temp = current;
    									current = current->next;
    									delete temp;
    								}
    								delete current;
    
    								// then exit the function
    								return;
    							}
    						}
    
    						// otherwise find the path between us and the spot we found
    						COORD tempDest;
    						tempDest.Y = tempY;
    						tempDest.X = source.X;
    
    						// recursion... *shudder*
    						makePath( terrain, source, tempDest ); 
    						
    						source.X = tempDest.X;
    						source.Y = tempDest.Y;
    					}
    
    
    
    				}
    			}
    
    			// if we are above where we want to go...
    			else
    			{
    				// set this node up
    				current->y = source.Y + 1;
    				current->x = source.X;
    
    				// hold our current location
    				int tempY = current->y;
    					
    				// if we are now on a mountain or desert, find a way around it
    				if ( mapInfo[current->y][source.X] == MOUNTAIN || mapInfo[current->y][source.X] == DESERT )
    				{
    					// go down until you hit the top of the map, or a good square
    					while ( tempY < MapSizeY && mapInfo[tempY][source.X] == MOUNTAIN || mapInfo[tempY][source.X] == DESERT )
    						tempY++;
    
    					// if you hit the bottom of the map, go up until you hit the top or a good square
    					if ( tempY >= MapSizeY )
    					{
    						tempY = current->y;
    						while ( tempY > 0 && mapInfo[tempY][source.X] == MOUNTAIN || mapInfo[tempY][source.X] == DESERT )
    							tempY--;
    
    						// if we couldnt find a good path...
    						if ( tempY <= 0 ) 
    						{
    							// free up our memory
    							current = sourceNode.next;
    							while ( current->next )
    							{
    								node * temp = current;
    								current = current->next;
    								delete temp;
    							}
    							delete current;
    
    							// then exit the function
    							return;
    						}
    					}
    
    					else
    					{
    						// we want a wide path... 
    						// if you dont have a good wide path, go back and check the other side
    						if ( tempY + 5 >= MapSizeY )
    						{
    							tempY = current->y;
    							while ( tempY < MapSizeY && mapInfo[tempY][source.X] == MOUNTAIN || mapInfo[tempY][source.X] == DESERT )
    								tempY--;
    
    							// if we couldnt find a good path...
    							if ( tempY - 5 <= 0 ) 
    							{
    								// free up our memory
    								current = sourceNode.next;
    								while ( current->next )
    								{
    									node * temp = current;
    									current = current->next;
    									delete temp;
    								}
    								delete current;
    
    								// then exit the function
    								return;
    							}
    						}
    
    						// otherwise find the path between us and the spot we found
    						COORD tempDest;
    						tempDest.Y = tempY;
    						tempDest.X = source.X;
    
    						// recursion... *shudder*
    						makePath( terrain, source, tempDest ); 
    						
    						source.X = tempDest.X;
    						source.Y = tempDest.Y;
    					}
    				}
    			}
    		}
    
    
    		// 50% chance to change the x direction
    		else
    		{
    			// if we are below where we want to go...
    			if ( source.X > dest.X )
    			{
    				// set this node up
    				current->x = source.X - 1;
    				current->y = source.Y;
    
    				// hold our current location
    				int tempX = current->x;
    					
    				// if we are now on a mountain or desert, find a way around it
    				if ( mapInfo[source.Y][current->x] == MOUNTAIN || mapInfo[source.Y][current->x] == DESERT )
    				{
    					// go up until you hit the top of the map, or a good square
    					while ( tempX > 0 && mapInfo[source.Y][tempX] == MOUNTAIN || mapInfo[source.Y][tempX] == DESERT )
    						tempX--;
    
    					// if you hit the top of the map, go down until you hit the bottom or a good square
    					if ( tempX <= 0 )
    					{
    						tempX = current->x;
    						while ( tempX < MapSizeY && mapInfo[source.Y][tempX] == MOUNTAIN || mapInfo[source.Y][tempX] == DESERT )
    							tempX++;
    
    						// if we couldnt find a good path...
    						if ( tempX >= MapSizeY ) 
    						{
    							// free up our memory
    							current = sourceNode.next;
    							while ( current->next )
    							{
    								node * temp = current;
    								current = current->next;
    								delete temp;
    							}
    							delete current;
    
    							// then exit the function
    							return;
    						}
    					}
    
    					else
    					{
    						// we want a wide path... 
    						// if you dont have a good wide path, go back and check the other side
    						if ( tempX - 5 <= 0 )
    						{
    							tempX = current->x;
    							while ( tempX < MapSizeY && mapInfo[source.Y][tempX] == MOUNTAIN || mapInfo[source.Y][tempX] == DESERT )
    								tempX++;
    
    							// if we couldnt find a good path...
    							if ( tempX + 5 >= MapSizeY ) 
    							{
    								// free up our memory
    								current = sourceNode.next;
    								while ( current->next )
    								{
    									node * temp = current;
    									current = current->next;
    									delete temp;
    								}
    								delete current;
    
    								// then exit the function
    								return;
    							}
    						}
    
    						// otherwise find the path between us and the spot we found
    						COORD tempDest;
    						tempDest.X = tempX;
    						tempDest.Y = source.Y;
    
    						// recursion... *shudder*
    						makePath( terrain, source, tempDest ); 
    						
    						source.X = tempDest.X;
    						source.Y = tempDest.Y;					
    					}
    
    				}
    			}
    
    			// if we are above where we want to go...
    			else
    			{
    				// set this node up
    				current->x = source.X + 1;
    				current->y = source.Y;
    				// hold our current location
    				int tempX = current->x;
    					
    				// if we are now on a mountain or desert, find a way around it
    				if ( mapInfo[source.Y][current->x] == MOUNTAIN || mapInfo[source.Y][current->x] == DESERT )
    				{
    					// go down until you hit the top of the map, or a good square
    					while ( tempX < MapSizeY && mapInfo[source.Y][tempX] == MOUNTAIN || mapInfo[source.Y][tempX] == DESERT )
    						tempX++;
    
    					// if you hit the bottom of the map, go up until you hit the top or a good square
    					if ( tempX >= MapSizeY )
    					{
    						tempX = current->x;
    						while ( tempX > 0 && mapInfo[source.Y][tempX] == MOUNTAIN || mapInfo[source.Y][tempX] == DESERT )
    							tempX--;
    
    						// if we couldnt find a good path...
    						if ( tempX <= 0 ) 
    						{
    							// free up our memory
    							current = sourceNode.next;
    							while ( current->next )
    							{
    								node * temp = current;
    								current = current->next;
    								delete temp;
    							}
    							delete current;
    
    							// then exit the function
    							return;
    						}
    					}
    
    					else
    					{
    						// we want a wide path... 
    						// if you dont have a good wide path, go back and check the other side
    						if ( tempX + 5 >= MapSizeY )
    						{
    							tempX = current->x;
    							while ( tempX < MapSizeY && mapInfo[source.Y][tempX] == MOUNTAIN || mapInfo[source.Y][tempX] == DESERT )
    								tempX--;
    
    							// if we couldnt find a good path...
    							if ( tempX - 5 <= 0 ) 
    							{
    								// free up our memory
    								current = sourceNode.next;
    								while ( current->next )
    								{
    									node * temp = current;
    									current = current->next;
    									delete temp;
    								}
    								delete current;
    
    								// then exit the function
    								return;
    							}
    						}
    
    						// otherwise find the path between us and the spot we found
    						COORD tempDest;
    						tempDest.X = tempX;
    						tempDest.Y = source.Y;
    
    						// recursion... *shudder*
    						makePath( terrain, source, tempDest ); 
    						
    						source.X = tempDest.X;
    						source.Y = tempDest.Y;
    					}
    				}
    			}
    		}
    
    	// end of while loop
    
    	}
    
    
    	// draw to the map and delete the list along the way
    	current = sourceNode.next;
    	while ( current->next )
    	{
    		node * temp = current;
    		current = current->next;
    
    		mapInfo[temp->y][temp->x] = terrain;
    
    		delete temp;
    	}
    
    	mapInfo[current->y][current->x] = terrain;
    
    	delete current;
    
    }
    I came up with a cool phrase to put down here, but i forgot it...

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Have you tried stepping through the function with a small test map in a debugger? That's generally more effective than asking us to eyeball you code and find the problem. And as you said, only a small fraction of us have the time and inclination to do so.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Feb 2002
    Posts
    465
    ive spent all day on this function...

    i had it working going in a semi-straight line from one point to another, but i want it to avoid mountains and deserts... ive stepped through it countless times, found hundreds of nit-picky errors, but its still not working...

    90% of that function is just repeated code ( i check for whether or not to move up, down, left, or right, but then the same code is excecuted every time ), but i just wanted to be sure i didnt miss anything...

    im not holding a gun to anyones head and telling them to debug my code, but if anyone can solve the problem before i do, i would be very grateful.
    I came up with a cool phrase to put down here, but i forgot it...

  4. #4
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    >>if ( mapInfo[current->y][source.X] == MOUNTAIN || mapInfo[current->y][source.X] == DESERT )


    On these types of if statements are you sure everything is evaluated in the correct order? Check operator precedence or add some parentheses...Not sure if that will help...
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  5. #5
    Registered User
    Join Date
    Feb 2002
    Posts
    465
    actually, the answer was on these lines:

    Code:
    // set this node up
    current->y = source.Y + 1;
    current->x = source.X;
    i didnt realize that i was updating the current node and not the source. i made it a doubly linked list and fixed it this way:

    Code:
    // set this node up
    current->y = current->prev->y + 1;
    current->x = current->prev->x;
    but thanks for the valliant effort...
    I came up with a cool phrase to put down here, but i forgot it...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  2. Undefined Reference Compiling Error
    By AlakaAlaki in forum C++ Programming
    Replies: 1
    Last Post: 06-27-2008, 11:45 AM
  3. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  4. Problem with Visual C++ Object-Oriented Programming Book.
    By GameGenie in forum C++ Programming
    Replies: 9
    Last Post: 08-29-2005, 11:21 PM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM