Feedback Recursive script

[NazGhuL]

I had a lot of problem while trying to do recursive pathfinding with gm:s
I tried this one with gms2:

create event:

randomize();
global.count = 0;
scr_rnd_number();
show_debug_message("Found!");

the script:

global.count++;
show_debug_message(global.count);

var value = irandom_range(0, 1000000);

if(value == 0)
{
exit;
}
else
{
scr_rnd_number();
}

And had this result:

885553
Found!

The script calls himself 885553 times!

I close the window and it takes me half a second to use the IDE again.

I did the same thing with gms:s but with irandom_range(0, 100 000) instead of 1 000 000;

I hit on 361019x. But it takes around 1 minute to be able to use the IDE again.

So I guess there is some optimization here. Maybe we'll be able to use more recursive pathfinding.

 

[csanyk]

I had a lot of problem while trying to do recursive pathfinding with gm:s
I tried this one with gms2:

create event:

randomize();
global.count = 0;
scr_rnd_number();
show_debug_message("Found!");

the script:

global.count++;
show_debug_message(global.count);

var value = irandom_range(0, 1000000);

if(value == 0)
{
exit;
}
else
{
scr_rnd_number();
}

And had this result:

885553
Found!

The script calls himself 885553 times!

I close the window and it takes me half a second to use the IDE again.

I did the same thing with gms:s but with irandom_range(0, 100 000) instead of 1 000 000;

I hit on 361019x. But it takes around 1 minute to be able to use the IDE again.

So I guess there is some optimization here. Maybe we'll be able to use more recursive pathfinding.

The problem is with your algorithm. You're seeking the number 0 by randomly selecting a number between 0 and 100000 over and over until you eventually hit it. There's no guarantee you will ever hit 0. It could hit on the very first iteration, or it could run for days or years.

Good recursive algorithms work by taking a large job and breaking it up into smaller pieces, doing a little bit of the work each iteration, and converging on a solution, ideally in a predictable, efficient manner.

Let's rewrite your script to reflect this:

global.count++;
show_debug_message(global.count);

var value = irandom_range(0, argument0);

if(value == 0)
{
exit;
}
else
{
scr_rnd_number(argument0/2);
}

Here, we're searching for 0 out of a random pick, but the range of random numbers is shrinking every iteration. This should converge on 0 much more quickly.

Of course, it's still a script that lacks any practical application, but at least it expresses how good recursive functions actually work.

 

[mMcFab]

I had a lot of problem while trying to do recursive pathfinding with gm:s
I tried this one with gms2:

create event:

randomize();
global.count = 0;
scr_rnd_number();
show_debug_message("Found!");

the script:

global.count++;
show_debug_message(global.count);

var value = irandom_range(0, 1000000);

if(value == 0)
{
exit;
}
else
{
scr_rnd_number();
}

And had this result:

885553
Found!

The script calls himself 885553 times!

I close the window and it takes me half a second to use the IDE again.

I did the same thing with gms:s but with irandom_range(0, 100 000) instead of 1 000 000;

I hit on 361019x. But it takes around 1 minute to be able to use the IDE again.

So I guess there is some optimization here. Maybe we'll be able to use more recursive pathfinding.

This is pretty good! I used to get a stack error over about 500 recursions before in GM:S. I just did a quick test myself, using a slightly different script:

///RecursiveTest();

show_debug_message(string(global.count));

++global.count;

RecursiveTest();

So it kept running and printing.
I found that the program slows down as more recursions occur, and was reasonable up to about 22,000.The slowdown was only super significant at over 1,000,000 recursions, though the program no longer throws an error, which is a great relief.

 

[rwkay]

This is the same in 1.x none of that has changed for 2.0! we fixed this a long time ago

Russell

 

[NazGhuL]

Great! Haven't take out any pathfinding script yet but gms1 clearly freeze a minute or so when closing it after running the example I posted above. Gms2 doesnt freeze at all.

 

[Nallebeorn]

Great! Haven't take out any pathfinding script yet but gms1 clearly freeze a minute or so when closing it after running the example I posted above. Gms2 doesnt freeze at all.

I think the freeze in GM:S 1.4 is because of all those show_debug_message() calls, actually. I don't know why, but I've seen many times in my own projects that filling the compile form with crazy amounts of messages makes the IDE freeze when exiting the game. It can easily happen when printing to the console in step events, and it had me scratch my head for quite a while once, thinking it was a memory leak or some sort of bug in my game. Nice to hear that's fixed in GMS2, though.

 

[renex]

I think the freeze in GM:S 1.4 is because of all those show_debug_message() calls, actually.

Can confirm.