# linked list recursive function spaghetti

• 09-02-2003
...
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; }```
• 09-02-2003
Prelude
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. ;)
• 09-02-2003
...
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.
• 09-02-2003
JaWiB
>>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...
• 09-02-2003
...
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...