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;

}

---

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. ;)

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.

>>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...

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...