Sign in to follow this  
Zael

Program fails with return code 128

Recommended Posts

Hey everyone. I'm having an interesting problem that I am hoping somebody can help me with. I am trying to look at a map that has only water and land. I created this function that sets up all water set to 0 and all land set to 1. I am now trying to go through each cell and call the below function to identify separate land masses. It seems to work for maps 64x64, 128x128, 256x256, but dies with a return code of 128 when the map is 512x512. This function is called on every cell.
int followLand(std::vector <std::vector <unsigned int> > & tmpmap, unsigned int x, unsigned int y, unsigned short group)
{
	std::cout << "Following land\n";
	fflush(stdout);
	if(tmpmap[x][y] == 1)
	{
		tmpmap[x][y] = group;
		std::cout << "X: " << x << "\n";
		std::cout << "Y: " << y << "\n";
		std::cout << (x-1+tmpmap.size())%tmpmap.size() << "\n";
		std:: cout << (y-1+tmpmap.size())%tmpmap.size() << "\n";
		fflush(stdout);
/*Dies between here but before going inside the function of the next line.*/
		followLand(tmpmap, (x-1+tmpmap.size())%tmpmap.size(), (y-1+tmpmap.size())%tmpmap.size(), group);
		std::cout << "Ah1\n";
		fflush(stdout);
		followLand(tmpmap, (x-1+tmpmap.size())%tmpmap.size(), y, group);
		std::cout << "Ah2\n";
		fflush(stdout);
		followLand(tmpmap, (x-1+tmpmap.size())%tmpmap.size(), (y+1+tmpmap.size())%tmpmap.size(), group);
		std::cout << "Ah3\n";
		fflush(stdout);
		followLand(tmpmap, x, (y-1+tmpmap.size())%tmpmap.size(), group);
		std::cout << "Ah4\n";
		fflush(stdout);
		followLand(tmpmap, x, (y+1+tmpmap.size())%tmpmap.size(), group);
		std::cout << "Ah5\n";
		fflush(stdout);
		followLand(tmpmap, (x+1+tmpmap.size())%tmpmap.size(), (y-1+tmpmap.size())%tmpmap.size(), group);
		std::cout << "Ah6\n";
		fflush(stdout);
		followLand(tmpmap, (x+1+tmpmap.size())%tmpmap.size(), y, group);
		std::cout << "Ah7\n";
		fflush(stdout);
		followLand(tmpmap, (x+1+tmpmap.size())%tmpmap.size(), (y+1+tmpmap.size())%tmpmap.size(), group);
		std::cout << "Ah8\n";
		fflush(stdout);
	}
	std::cout << "Done Following land\n";
	fflush(stdout);
	return 0;
}

There is a lot of cout in the function for debugging purposes right now. The interesting thing is that the last line out for the cout is the line indicated instead of a line inside the function. I can't figure out what's going on. It seems to often die in the middle of the map; it's definitely not a segment fault. Interesting thing is when compiled in linux the program runs fine, but when compiled in windows with minGW it fails. Any ideas? Any recommendations for a better way to do this would be nice too. Thanks, -Zael-

Share this post


Link to post
Share on other sites
Not sure what your issue is. But did you know?

std::cout << "Following land\n";
fflush(stdout);

can be better written as:

std::cout << "Following land" << std::endl;


There is really only one way that your program would exit with the value 128 anyway. You either have a "return 128;" at the end of main. Or you or a library you used called "exit(128)".

Share this post


Link to post
Share on other sites
Does the std::endl automatically do the fflush part? I knew it was an alternative for "\n", but if it does the fflush part to then I will start using it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zael
Does the std::endl automatically do the fflush part? I knew it was an alternative for "\n", but if it does the fflush part to then I will start using it.

Yes it does. Whenever you don't want that behavior, just use '\n' instead.

Some more stream manipulators, if you're interested.

Share this post


Link to post
Share on other sites
Quote:
Original post by KulSeran
There is really only one way that your program would exit with the value 128 anyway. You either have a "return 128;" at the end of main. Or you or a library you used called "exit(128)".


Hm... The only library being used in that function is iostream and vector. SDL is used in the program, but it isn't even initialized until after this function returns.

Share this post


Link to post
Share on other sites
Is your map square? If not, I could see a potential problem. For both x and y you are keeping things in range by using the % operator with tmpmap.size(). The thing is, if tmpmap[0].size() were smaller than tmpmap.size(), you might have an out of bounds access.

[EDIT]
My bad, I just noticed you mention square maps in your original post. Keep this in mind for the future though :)

Share this post


Link to post
Share on other sites
Yeah. The maps are all square. I might try non-square at somepoint (and make the appropriate fixes), but right now I don't really care about non-square rectangles.

Share this post


Link to post
Share on other sites
At a guess, you are getting a stack overflow. Linux usually has larger stack sizes than Windows by default.

Share this post


Link to post
Share on other sites
Quote:

It seems to often die in the middle of the map;

Sorry i didn't see that before. You have a recursive function there.
If it is dieing in the middle of the map, you probably ran out of stack space due to recursing too deep.
You can likely rewrite the whole function as a while() loop on a std::stack.
each "followLand" call would push a new item into the stack. Each time through the loop, you pop an item, check "if(tmpmap[x][y]==1)" and either push more items, or loop and pop again.


--edit: mattd beat me to that realization.

Share this post


Link to post
Share on other sites
Quote:
Original post by KulSeran
Quote:

It seems to often die in the middle of the map;

Sorry i didn't see that before. You have a recursive function there.
If it is dieing in the middle of the map, you probably ran out of stack space due to recursing too deep.



Hmm... Maybe, but the program never goes above 1% total memory usage according to top in linux. Anyway to increase stack space for a program?

Or maybe a better question is: Is there a better way to do what I am trying to accomplish?

Share this post


Link to post
Share on other sites
Quote:

Maybe, but the program never goes above 1% total memory usage according to top in linux. Anyway to increase stack space for a program?

stack space isn't going to show up as a huge memory usage. most the time you only have a few megs of stack space.
You can increase it with different compiler options, but you'd be better off rewriting the function to be non recursive. see my edit above.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zael
Quote:
Original post by KulSeran
Quote:

It seems to often die in the middle of the map;

Sorry i didn't see that before. You have a recursive function there.
If it is dieing in the middle of the map, you probably ran out of stack space due to recursing too deep.

Hmm... Maybe, but the program never goes above 1% total memory usage according to top in linux. Anyway to increase stack space for a program?

You could test the hypothesis using the ulimit command, namely the -s switch.

Quote:
Or maybe a better question is: Is there a better way to do what I am trying to accomplish?

Rewrite the function in question.

Share this post


Link to post
Share on other sites
Wow, talk about recursion. That function has a complexity of O(2^(3n)).

One thing you could do to seriously reduce this is marking each cell as closed after you visit it. For example, if all you're trying to do is determine if something is part of a connected land mass or water mass, then why do you care about a cell if you've previously arrived there through some other path? In that case you should already know what it's connected to.

So at the beginning of the function, you just check "is this cell closed, if so return immediately".

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
Wow, talk about recursion. That function has a complexity of O(2^(3n)).

One thing you could do to seriously reduce this is marking each cell as closed after you visit it. For example, if all you're trying to do is determine if something is part of a connected land mass or water mass, then why do you care about a cell if you've previously arrived there through some other path? In that case you should already know what it's connected to.

So at the beginning of the function, you just check "is this cell closed, if so return immediately".


It already does that. I didn't explained that group is never equal to 1. 1 is the initialized value though for land masses. As soon as a cell is placed into a group it is no longer equal to one. While the program doesn't immediately return it doesn't go through the if statement... so unless there is some low level stuff going on here that I don't realize, it essentially does return immediately.

Share this post


Link to post
Share on other sites
Let's clean up the code a bit first:

For a square (rectangular) array in general, boost::multi_array is a better idea than std::vector. Also, let's take out the debugging stuff for now (because it's told us as much as we can really figure out from it) - although for future reference, it's better to send debug output to std::cerr instead; that way you don't have to worry about flushing at all, and it actually exists for the purpose of reporting errors and stuff like that. Finally, let's not repeat ourselves; factor out the common sub-expressions for adjacent cell coordinates. (That provides some insurance against typos, too.) Finally, there is no point in having a return value from the function, and writing the initial check as a guard clause probably is cleaner (makes things less indented) even if it doesn't impact the actual algorithm.


void followLand(boost::multi_array<unsigned int, 2>& tmpmap, unsigned int x, unsigned int y, unsigned short group) {
if (tmpmap[x][y] != 1) return;

tmpmap[x][y] = group;
int size = tmpmap.shape()[0];
int next_x = (x + 1) % size;
int prev_x = (x + size - 1) % size;
int next_y = (y + 1) % size;
int prev_y = (y + size - 1) % size;

followLand(tmpmap, prev_x, prev_y, group);
followLand(tmpmap, prev_x, y, group);
followLand(tmpmap, prev_x, next_y, group);
followLand(tmpmap, x, prev_y, group);
followLand(tmpmap, x, next_y, group);
followLand(tmpmap, next_x, prev_y, group);
followLand(tmpmap, next_x, y, group);
followLand(tmpmap, next_x, next_y, group);
}


Then the next step is to convert to iteration with a stack. To do this we'll want to make a temporary structure to represent the data that changes with each currently recursive call, i.e. the coordinate.




void followLand(boost::multi_array<unsigned int, 2>& tmpmap, unsigned int x, unsigned int y, unsigned short group) {
int size = tmpmap.shape()[0];
std::vector<std::pair<int, int> > coordinates;
coordinates.push_back(std::make_pair(x, y));

while (!coordinates.empty()) {
std::pair<int, int> coordinate = coordinates.pop_back();
x = coordinate.first;
y = coordinate.second;
if (tmpmap[x][y] != 1) { continue; }
tmpmap[x][y] = group;
int next_x = (x + 1) % size;
int prev_x = (x + size - 1) % size;
int next_y = (y + 1) % size;
int prev_y = (y + size - 1) % size;
// These will be processed in the reverse order compared to the
// original code, but because we use the vector as a stack,
// we'll still process "depth-first". To process
// "breadth-first", use queue logic instead. For a queue you
// probably don't want to use std::vector, though. Consider
// std::deque instead.
coordinates.push_back(std::make_pair(prev_x, prev_y));
coordinates.push_back(std::make_pair(prev_x, y));
coordinates.push_back(std::make_pair(prev_x, next_y));
coordinates.push_back(std::make_pair(x, prev_y));
coordinates.push_back(std::make_pair(x, next_y));
coordinates.push_back(std::make_pair(next_x, prev_y));
coordinates.push_back(std::make_pair(next_x, y));
coordinates.push_back(std::make_pair(next_x, next_y));
}
}


BTW, why do you pass 'unsigned short group' if your group IDs are allowed to be 'unsigned int' within the actual storage?

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