2014년 12월 11일 목요일

Recursive calls of procedures lead to undefined runtime errors, can you fix it?

I programed a Minesweeper game like you know from Mircrosoft Windows. I also liked to have the comfort to open surrounding areas when clicking on an area with no bombs in its neighbourhood. By doing so, a procedure is called recursively serval times, until all opened "border" areas have bombs in their neighbourhood. 
My program works fine on my phone if the procedure is not called more than 40 times. I chose an array size of 9x9 with 10 bombs in it. This means that in the biggest case, the procedure could be called 71 times... 

Is their a possibility to fix "undefined runtime" errors, that occure, when the procedure ist called more than 40 times recursively? 
There is the possibility to ignore this error on your phone (I use samsung galaxy s3 mini) and continue your game like nothing had happened, but it would be fine, if you could avoid that error.

I attached my code, the problematic procedure is called "fuellen", but I think, it is a problem with the recursive call, not with the code itself.

MyApp_short.aia



I notice in your recursive procedure you have not created any local variables,
specifically the number of neighbors.  Doing recursion using only global variables
is very tricky.

Please add comments to your code explaining how you keep a two dimensional
board in a list - is it a list of lists, or a simple list wrapping thru each row by row?

Your neighbor counting technique can't be explained .



I took some more time to read your blocks.
You are using lists of lists to store your board.

I suggest you avoid recursion by adding a heat propagation metaphor
to your loop.
Use the background color of each cell or use the contents of a hidden board
 to indicate if it is hot, warm, or cold.

When you get a cell touch, start all cells as cold.
If the cell touched is empty, set it to warm.
Then start cycles of heat propagation to neighboring empty cells.
In each cycle, for each warm cell, 
    set each neighboring empty cold cell to warm then
    set that previously warm cell to hot,
    counting how many cells got warm in each cycle.
    Stop cycling if no cells got warm.

This propagation technique can be used instead of recursion
to propagate zero cells from a touch.



Thanks for your answer.
This sounds like a good possibility, but in which order would you do the cycling to get every cell catched?



The brute force heat propagation cycle method I discussed
can use a pair of nested 1 to 9 for loops to cover every cell in each cycle.

It's simple but inefficient.

There's an alternative way to do heat propagation using three lists,
named Cold, Warm, and Hot, containing cell addresses, 
representing cells using 6 digit numbers - 
(1000 * x) + y
where x and y are row or column numbers (1...9).
Each cell name would reside in just one list at a time,
and would be moved from list to list as its state changes.
I picked 1000 to make the numbers easy to read and decode
and to accommodate big boards.

This single-quantity (sparse) approach lets you take advantage of 
the more powerful list handling blocks (is in list, look up in pairs,
find index of in list)

For convenience and simplicity, you might consider writing
a return value routine NEIGHBORS that will accept a cell address and
return a list of its neighbor addresses.
Other likely small functions:
X(nnnnnn) = QUOTIENT(nnnnnn,1000)
Y(nnnnnn) = REMAINDER(nnnnnn, 1000)
CELL(i,j) = (1000*i) + j

By using little routines like this you can make your
code fit in screen shots, the most enduring way to 
save your code for eternity (if you can find cave walls for them.)



I now programed my game with the heat propagation you suggested and it works really fine. I used a while block to control that every cell in the "warm" list is included. There are no more errors occuring. So, thank you very much for your help.

I'm still wondering what the problem with recursive calls is? Should you always try to avoid recursive calls or just use them with the certainty that it is not called too often?



I have been cautioned against depending on recursion in App Inventor
in the past, based on constraints in AI.

Here are some threads I found ...



The stack depth needed to hold procedure arguments and variables
local to procedure calls is limited.


댓글 없음:

댓글 쓰기