2017-08-10 13:48:40 (edited by Rastislav Kish 2017-08-10 13:51:27)

Hi all,
I am continuing with Blindcraft development, adding more and more featuures every day. Yesterday I planned to increase interactivity of the game and make it ready for some first animals and mobs, hovever I encountered a strange problem, which I can not solve.

My plan was to able player to delete zone, in which he stands currently. So I wrote simple recursive function, which should to do it. It looks as follows:

void zone_delete(std::string searched_zone, int x, int y, int z)
{
world[x][y][z].zone="";
if (y+1<200) {if (world[x][y+1][z].zone==searched_zone) zone_delete(searched_zone, x, y+1, z);}
if (x+1<200) {if (world[x+1][y][z].zone==searched_zone) zone_delete(searched_zone, x+1, y, z);}
if (y-1>0) {if (world[x][y-1][z].zone==searched_zone) zone_delete(searched_zone, x, y-1, z);}
if (x-1>0) {if (world[x-1][y][z].zone==searched_zone) zone_delete(searched_zone, x-1, y, z);}
if (z+1<200) {if (world[x][y][z+1].zone==searched_zone) zone_delete(searched_zone, x, y, z+1);}
if (z-1>=0) {if (world[x][y][z-1].zone==searched_zone) zone_delete(searched_zone, x, y, z-1);}
}

I think code is selfcommenting, it is very easy function. I tested it hovever and gave this results:
Deletion of me created zone was done succesfully, algorithm removed it reliably, hooray!
Deletion of biom zone was successful too, for better imagination forest size is 100*100, and three blocks above the ground are always zoned as forest, this all was successfully removed, hooray!
And finally, deletion of cutted tree zone, hem, application crashed, wtf?
Really, I stand in a tree zone, pressed ctrl+r and program crashed, when removing zone of a normal tree. And this is happening again and again, nowhere else, just when removing tree zone, it does have problems. I can not understand it. Only explanation I do have is, that some limit of recursive calls was passed, hovever why, when removing of whole biom zone did not made problems? Is there something like recursive limit, so this theory is possible? I really haven't imagination how many blocks of trees are zoned, one tree is about 12 blocks tall and about 7 wide, zone is allways used to distance of two blocks from object, hovever trees are relatively near themselves, so zones of few trees can be joined to one large, or it can be also from few tens of trees, it depends how thicky is forest generated.

Hovever, that is not important, if there is zone from more trees, algorithm should to delete it full, not crash the application. Does someone have explanation for this please?

Thank you in advance.

Best regards

Rastislav

P.S. Luckyly I backed up a copy of full message, ag has shredded it successfully.

2017-08-10 14:13:21

If you have infinite recursion, it can crash the program with stack overflow. You could print a message every time the function is called, so that when it crashes, you have an idea of if it's stack overflow or not.

看過來!
"If you want utopia but reality gives you Lovecraft, you don't give up, you carve your utopia out of the corpses of dead gods."
MaxAngor wrote:
    George... Don't do that.

2017-08-10 17:51:37

@Rastislav Kiss, it's caused by something called stack overflow. The semantics are a bit tricky to explain, but I'll try my best.
When you start a new program, such as a game, a command prompt, or any other program out there, interpreted or otherwise, it is always allocated two things: heap memory and stack memory. Heap memory is a dynamic store of memory that can be allocated and deallocated at any time. If you create a new variable, heap memory is allocated for it. If you then delete that variable, the memory is returned to the heap for reallocation later; it is not "truly" deleted. Instead, "true" deletion happens when the program exits by either crashing or exiting normally. However, beware that heap memory allocation is random. If you allocate a variable with the address 0xfffffff7, the chance that the next variable you allocate will be at address 0xfffffff8 is incredibly slim, and rarely ever happens.
The next part is stack memory. The stack is where all the really interesting things happen. (The stack is also known as the 'call stack'.) The call stack keeps track of all the active functions (those that have been called but have not yet terminated) from the start of the program to the current point of execution, and handles allocation of all function parameters and local variables. The stack can be visualized using the plate analogy:
Consider a stack of plates in a cafeteria. Because each plate is heavy and they are stacked, you can really only do one of three things:
1) Look at the surface of the top plate
2) Take the top plate off the stack (exposing the one underneath, if it exists)
3) Put a new plate on top of the stack (hiding the one underneath, if it exists)
The stack is almost like an array, but, whereas an array lets you modify elements in any order you want, the stack is very limited. The stack only has three main operations that can be performed: topping (or peeking), pushing and popping. Topping/peeking is used when you want to look at the currently visible element on the stack. Pushing refers to adding an item onto the stack, hiding all the others underneath it. Finally, popping refers to removing the currently visible element from the stack to reveal the next one. If we go back to the plate analogy now, topping/peeking would refer to glancing at the currently visible plate that's on the stack (you know the stack is composed of multiple plates, but you can't see the others yet); pushing refers to adding another plate on top of the currently visible one, hiding it from view and revealing to you the current plate: the one you just added; and popping refers to removing the new plate you just added, perhaps, and revealing the one that was there before you added (or pushed) the plate on the stack. These actions are named for their C function equivalents: examining the stack uses a function either named top () or peek (), while pushing and popping items off of the stack are done via functions named push () and pop (). (There are Intel assembly instruction/register equivalents, too: for peeking, we have the SS/ESP/RSP registers; for popping, we have the POP (Pop a Value from the Stack), POPA/POPAD (Pop All General-Purpose Registers), POPCNT (Return the Count of Number of Bits Set to 1), and POPF/POPFD/POPFQ (Pop Stack into EFLAGS Register); for pushing, we have PUSH (Push Word, Doubleword or Quadword Onto the Stack), PUSHA/PUSHAD (Push All General-Purpose Registers), and PUSHF/PUSHFD/PUSHFQ (Push EFLAGS Register onto the Stack); and for miscellaneous operations we have CALL, RET, ENTER, and LEAVE.
But back to your issue: the reason your suffering stack overflow is that your recursive function is recursively -- or repeatedly -- calling itself. This simply makes the stack larger, as when the function is called, it is pushed onto the stack. So then it calls itself again and again, and pushes more and more of itself on the stack until there is no more stack space available, whereupon the operating system kills it.

"On two occasions I have been asked [by members of Parliament!]: 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out ?' I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question."    — Charles Babbage.
My Github

2017-08-13 22:02:52

hello,
so, i must append something else:
variables also pushed/poped into stack (peeking is included)
for example:

int x;

this is allocated on the stack (if it is on the function, it will be released when the function is called)
now, lets see this:

int* x=new int[4];

this allocates the pointer on the heep (which should be deallocated by the programmer by using delete[] operator
but your problem is, your function calls itself, then it comes to the same condition, then again call and call until stack is more than of its size and then your app crashes
check it with a debugger such as microsoft debugger (visual studio's debugger), or if using GCC, use gdb debugger to debug it

2017-08-21 14:45:33

Hi,
ouh, so it seems I must code a newone algorithm without recursion, which will do some linear processing. Thank you for your help, I did not know anything about stack memory before, but it looks important to know for program's run.

Best regards

Rastislav