[SOLVED] while loops throw 150001 iterations error - NOT

[Khris]

I've encountered something strange yesterday.

Among my favorite puzzle games are the Picross ones by Nintendo.
I've written a solver with AGS that relies heavily on while loops and recursion.

For testing & debugging purposes I had included some Wait(1); commands during various loops so I could follow on screen what was happening.

After I got rid of the bugs, both puzzles I entered were solved correctly; everything appeared to work fine.
Now I wanted to test the speed and removed the Wait(1);s. Suddenly the while loops inside the recursive function threw mentioned errors.

The code is strictly serial, there's no rep_exe stuff or anything like that. All while loops start and end at a low integer.
I thought maybe the recursion was too deep, but after I rearranged the code a bit, a different while loop threw the 150001 error.

Maybe it's a memory issue, I'm at a loss here.

I've uploaded the source here.
(3.0 beta 14, press o or p to see it work fine, shift-o or shift-p to see it crash)

Edit: I see, that's too bad. Well, go ahead and download it, I've removed the password.

[Gilbert]

Well, the problem is, even I can't see your IP (maybe only global mods can, or I missed something), so did you want help just from CJ or otherwise? If you only want help from CJ I think you can just PM him directly, in that case you don't even need a password.

[Scorpiorus]

Anyways, a recursive call may indeed get it very quickly to the 150000 limit point.
Say a 50 iterations loop called recursively 4 times will end up at 50^4 = 6250000 iterations in total.

Have you tried a noloopcheck keyword to stop it aborting the script?

[Khris]

Are you sure? I'm surprised iterations of nested loops multiply.
Given that's true, the current code throws the error in a non-recursive loop.

pseudo-code:
while (1 to 15) {
  while (1 to ~50) {
    ...
  }                      <----- line mentioned in the error message
}

And the weird thing is: it works perfectly fine as long as there are Wait(1);s in the code.
I've double- and triple-checked the loops; every one has its i++; in place; neither i nor the end var are changed inside the loop.

[Scorpiorus]

while (1 to 15) {
  while (1 to ~50) {
    ...
  }                      <----- line mentioned in the error message
}

That code alone should not abort, but maybe the function with that code is called recursively (or in an outer loop/loops ) ?

And the weird thing is: it works perfectly fine as long as there are Wait(1);s in the code.

Wait(1) has an effect of updating the engine state, so it doesn't count as a hang to the engine.

[Radiant]

And the weird thing is: it works perfectly fine as long as there are Wait(1);s in the code.

That's not weird, that's the way it's designed

If 150000 script commands pass in a single game cycle, the engine aborts. Wait means to delay until the next game cycle.

[Kweepa]

Are you sure? I'm surprised iterations of nested loops multiply.

I would imagine the algorithm for determining if there is an "infinite" loop is to increment a global counter at the point where each loop jumps back to the beginning, and reset it at the end of a script call.
You might be able to fool it by putting the inner loops into a different script module.
But I would just use noloopcheck.

[Khris]

Thanks for the replies!
You've all nailed it right on the head; the Solve function uses a while loop which calls the next, which calls the next, which calls the recursive one and so on.

I added a third puzzle which really puts the solver to the test, put a noloopcheck everywhere it's needed and had to increase the size of the main array from 1000 to 30000

It works like a charm now, thanks again!

Here's the executable, press l (L) to see the big one solved.

Edit: slight update

[Scorpiorus]

Glad to know you got it working

By the way, noloopcheck can be specified once for the most outer level function (say, on_key_press), and thus all subsequent inner calls are automatically treated as noloopcheck ones, which may be useful for testing purposes. Though, of course, as a general rule it is highly recommended to decide whether to disable the check or not on a per function basis in order to avoid possible hangs of the engine due to logic errors in the script code, as the manual suggests.



Having a global counter of loop iterations seems like the best way to implement the check, I believe. It is simple, yet effective means to provide general protection against infinite loops caused by logic errors. Strictly speaking, each loop instance, so to say, could have its own counter to make the check perfectly accurate for combinations of nested and successive loops but in practice it means increased overhead in terms of both performance and memory usage, as for instance nested loops would then require separate counters and their total number is generally undefined because of a possibility to have "nested" loops through recursive function calls. So such complications are not really necessary in my opinion.

We just should take into account that with the global loop counter the following code...

Code: ags

int i= 75000;
while (i>0) i--;

int j= 75001;
while (j>0) j--;

...will normally abort the game.

[TheMagician]

Ok, now I have no idea what exactly is happening when I press 'l' in your demo, but it sure looks very cool and professional.

I love the red arrows and especially the progress bar (is that a dynamic sprite or how did you do that?).

Great work.

[Kweepa]

That's pretty cool!
Oh great, now I got addicted to: http://www.thetimmys.com/flash/picross/

[Khris]

Scorpiorus: That's good to know, and I still have to clean up the code anyway.

The Magician:
The official name is Nonogram. Check out the wiki page for a full explanation.
The progress bar is drawn using RawDrawRectangle().

Steve:
That's a cool link; it somehow never occurred to me look for those on the web.
There are eight Volumes for the SNES; only in Japanese though.
There's a DS game out, too.