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;
}