Recursion level limit

[UEZ]

Is there a way to increase max recursion level?

For example this code is using recursion to fill an area with a color but the job is interrupted because of reaching the recursion limit!

expandcollapse popup

#include <GDIPlus.au3>

$sRegPath = "HKLM\SOFTWARE\AutoIt v3\AutoIt"
If StringInStr("X64IA64", @OSArch) Then $sRegPath = StringReplace($sRegPath, "SOFTWARE", "SOFTWARE\Wow6432Node")

_GDIPlus_Startup()
$hImage = _GDIPlus_ImageLoadFromFile(RegRead($sRegPath, "InstallDir") & "\Examples\GUI\logo4.gif")
$iW = _GDIPlus_ImageGetWidth($hImage)
$iH = _GDIPlus_ImageGetHeight($hImage)
$hGUI = GUICreate("Test", $iW, $iH)
GUISetState()
$hGfx = _GDIPlus_GraphicsCreateFromHWND($hGUI)
AdlibRegister("UpdateView", 10)

$iColor2Fill = 0xFFFFFFFF
;~ _GDIPlus_FloodFillRec($hImage, 0, 0, 0xFF000080, 0xFFFFFF00)
_GDIPlus_FloodFillRec($hImage, 82, 24, 0xFF000080, 0xFFFFFF00)
_GDIPlus_ImageSaveToFile($hImage, @ScriptDir & "\Filled.png")
;~ ShellExecute(@ScriptDir & "\Filled.png")
AdlibUnRegister("UpdateView")
ConsoleWrite("Done" & @LF)
Do
Until GUIGetMsg() = -3

_GDIPlus_ImageDispose($hImage)
_GDIPlus_GraphicsDispose($hGfx)
_GDIPlus_Shutdown()
Exit

Func _GDIPlus_FloodFillRec(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-12
    Local Static $iRec = 1
    Local $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $iX, "int", $iY, "uint*", 0)
    If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
        DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $iX, "int", $iY, "uint", $iColorNew)
    Else
        Return 0
    EndIf
    Local $iRecLimit = 3899
    $aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)
    If ($iX + 1) < $aResult[2] + 1 Then
        $iRec += 1
        If $iRec = $iRecLimit Then Return -1
        _GDIPlus_FloodFillRec($hBitmap, $iX + 1, $iY, $iColorOld, $iColorNew) ;go east
        $iRec -= 1
    EndIf
    If ($iY + 1) < $aResult[3] + 1 Then
        $iRec += 1
        If $iRec = $iRecLimit Then Return -1
        _GDIPlus_FloodFillRec($hBitmap, $iX, $iY + 1, $iColorOld, $iColorNew) ;go south
        $iRec -= 1
    EndIf
    If ($iX - 1) > -1 Then
        $iRec += 1
        If $iRec = $iRecLimit Then Return -1
        _GDIPlus_FloodFillRec($hBitmap, $iX - 1, $iY, $iColorOld, $iColorNew) ;go west
        $iRec -= 1
    EndIf
    If ($iY - 1) > -1 Then
        $iRec += 1
        If $iRec = $iRecLimit Then Return -1
        _GDIPlus_FloodFillRec($hBitmap, $iX, $iY - 1, $iColorOld, $iColorNew) ;go north
        $iRec -= 1
    EndIf
    Return 1
EndFunc   ;==>_GDIPlus_FloodFillRec

Func UpdateView()
    _GDIPlus_GraphicsDrawImage($hGfx, $hImage, 0, 0)
EndFunc

Br,

UEZ

Edited January 13, 2013 by UEZ

[Kip]

Don't use recursion, use a loop.

[MvGulik]

Nothing wrong with recursion. Although generally not needed.

Just don't do it per pixel in this case.

[MvGulik]

On your original question. Probably not, as hitting a recursion limit is general a case of bad coding.

[willichan]

I could be wrong, but isn't recursion limited by available memory? I am able to reach 3899 recursions on one machine, and only 1899 on another. Shutting down my email allows me to reach 5848 on the first system.

[UEZ]

In some cases recursion is very easy to implement to get the wanted result, e.g. as shown in the example above.

So it is legitime to use / prefer recursion rather than iteration in some cases. I cannot say anything about the AutoIt internal procedure how recursion (stacks) are handled but in this particualar simple example to fill a small image (169x68) fails which I cannot understand.

I don't know how to optimize the code not to reach any limits.

When I run the code it will increase the memory consumption from 5 MB to 10 MB until it reaches the limit.

Br,

UEZ

Edited January 11, 2013 by UEZ

[trancexx]

Recursion limit is artificial. Jon did some testings and concluded that in order for AutoIt to function correctly in low memory coditions it would be good to use the numbers willichan shows. It's not machine specific, it's related to the bitness of the interpretter. x86 have one limit and x64 other.

The problem with the numbers used before is that undrelying API couldn't load string resource (as docummented by MSDN) used for displaying the "error". This means that in reality these numbers could be set higher if the strings wouldn't be loaded from resources. Still the limit would also be reached at some point, so the question is really why to change it.

[iamtheky]

is this way just slower, or not the intended effect at all? Because it seems the implementation is equally easy.

#include <GDIPlus.au3>

$sRegPath = "HKLM\SOFTWARE\AutoIt v3\AutoIt"
If StringInStr("X64IA64", @OSArch) Then $sRegPath = StringReplace($sRegPath, "SOFTWARE", "SOFTWARE\Wow6432Node")

_GDIPlus_Startup()
$hImage = _GDIPlus_ImageLoadFromFile(RegRead($sRegPath, "InstallDir") & "\Examples\GUI\logo4.gif")

_GDIPlus_FloodFill($hImage, 0, 0, 0xFF000080, 0xFFFFFF00)
_GDIPlus_ImageSaveToFile($hImage, @ScriptDir & "\Filled.png")
_GDIPlus_ImageDispose($hImage)
_GDIPlus_Shutdown()
ShellExecute(@ScriptDir & "\Filled.png")
Exit

Func _GDIPlus_FloodFill(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-11
$aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)

For $x = 1 to $aResult[2]
For $y = 1 to $aResult[3]
Local $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $X, "int", $Y, "uint*", 0)
If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $X, "int", $Y, "uint", $iColorNew)
EndIf

Next
Next

EndFunc

Edited January 11, 2013 by boththose

[UEZ]

@boththose: this is not same! You change every color in the image not the area of the color.

Try _GDIPlus_FloodFill($hImage, 73, 22, 0xFFFFFFFF, 0xFFFFFF00) in the recursive example to see the difference!

Br,

UEZ

Edited January 11, 2013 by UEZ

[iamtheky]

fair enough, then. Same questions using $iX and $iY instead of 1 to ....

is there an advantage going with recursion instead of for loops?

#include <GDIPlus.au3>

$sRegPath = "HKLM\SOFTWARE\AutoIt v3\AutoIt"
If StringInStr("X64IA64", @OSArch) Then $sRegPath = StringReplace($sRegPath, "SOFTWARE", "SOFTWARE\Wow6432Node")

_GDIPlus_Startup()
$hImage = _GDIPlus_ImageLoadFromFile(RegRead($sRegPath, "InstallDir") & "\Examples\GUI\logo4.gif")

_GDIPlus_FloodFill($hImage, 73, 22, 0xFFFFFFFF, 0xFFFFFF00)
_GDIPlus_ImageSaveToFile($hImage, @ScriptDir & "\Filled.png")
_GDIPlus_ImageDispose($hImage)
_GDIPlus_Shutdown()
ShellExecute(@ScriptDir & "\Filled.png")
Exit

Func _GDIPlus_FloodFill(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-11
$aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)

For $x = $ix to $aResult[2]
For $y = $iY to $aResult[3]
Local $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $X, "int", $Y, "uint*", 0)
If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $X, "int", $Y, "uint", $iColorNew)
EndIf

Next
Next

EndFunc

Edited January 11, 2013 by boththose

[monoceres]

In some cases recursion is very easy to implement to get the wanted result, e.g. as shown in the example above.

So it is legitime to use / prefer recursion rather than iteration in some cases. I cannot say anything about the AutoIt internal procedure how recursion (stacks) are handled but in this particualar simple example to fill a small image (169x68) fails which I cannot understand.

I don't know how to optimize the code not to reach any limits.

When I run the code it will increase the memory consumption from 5 MB to 10 MB until it reaches the limit.

Br,

UEZ

Use a loop with a stack, it will be just like recursion, but you will not hit any recursion depth limits.

Example:

Put initial pixel in stack.

While there are data on stack:

Pop stack and process the pixel

If pixel to left is same color: put on stack

if pixel to right is same color: put on stack

if pixel above is same color: put on stack

if pixel below is same color: put on stack

Done.

Funny thing with this aproach is that if you visualize the process and use something else instead of a stack (like a queue) the results are very interesting to watch!

Edited January 11, 2013 by monoceres

[willichan]

There are some non-recursive C++ implementations posted here

http://stackoverflow.com/questions/1257117/does-anyone-have-a-working-non-recursive-floodfill-algorithm-written-in-c

that you might be able to translate into AI code.

[UEZ]

boththose: simplicity. Try to convert this into iteration.

Br,

UEZ

[UEZ]

@monoceres: thanks for the hint. It looks like the code from the link willichan has provided.

@willichan: thanks for the link.

Br,

UEZ

[iamtheky]

Try to convert this into iteration.

I apologize, if there is something following that statement (like a pretty picture) it is getting websensed, if not then i dont understand how my previous posts are not iterative. Thanks for trying to educate me!

Edited January 11, 2013 by boththose

[UEZ]

@boththose: your version is iterative but it replaces all colors within the image not only a region of colors!

Try with your code to replace only white color (0xFFFFFFFF) within the AutoIt logo for all letters.

Br,

UEZ

[iamtheky]

This only changes the letters from white to yellow, and is just an adjustment of x value you supplied in your func from post #9, I have a feeling I may be missing something completely...

#include <GDIPlus.au3>

$sRegPath = "HKLM\SOFTWARE\AutoIt v3\AutoIt"
If StringInStr("X64IA64", @OSArch) Then $sRegPath = StringReplace($sRegPath, "SOFTWARE", "SOFTWARE\Wow6432Node")

_GDIPlus_Startup()
$hImage = _GDIPlus_ImageLoadFromFile(RegRead($sRegPath, "InstallDir") & "\Examples\GUI\logo4.gif")

_GDIPlus_FloodFill($hImage, 63, 22, 0xFFFFFFFF, 0xFFFFFF00)
_GDIPlus_ImageSaveToFile($hImage, @ScriptDir & "\Filled.png")
_GDIPlus_ImageDispose($hImage)
_GDIPlus_Shutdown()
ShellExecute(@ScriptDir & "\Filled.png")
Exit

Func _GDIPlus_FloodFill(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-11
$aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)

For $x = $ix to $aResult[2]
For $y = $iY to $aResult[3]
Local $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $X, "int", $Y, "uint*", 0)
If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $X, "int", $Y, "uint", $iColorNew)
EndIf

Next
Next

EndFunc

Edited January 11, 2013 by boththose

[UEZ]

This fills the letters but it fills in a defined rectangle area all colors whereas a flood fill algorithm fills the area where the color is bounded by other colors.

E.g. _GDIPlus_FloodFill($hImage, 88, 27, 0xFFFFFFFF, 0xFFFFFF00) should fill only the left part of the U.

Br,

UEZ

Edited January 11, 2013 by UEZ

[MvGulik]

but in this particualar simple example to fill a small image (169x68) fails which I cannot understand.

The recursion seems to work like this:

- go north until there is no more north. (possible one recursion level dropped.)

- than go east, until there is no more east. (possible one recursion level dropped.)

- than go south, until there is no more south. (possible one recursion level dropped.)

- than go west, until there is no more west. (possible one recursion level dropped.)

So that code seem to be allowed to make a full circle(square one) while its collection recursion levels.

That still not explains it totally. so it probably run's in multiple, smaller and smaller, circles, while ranking up its recursion level.

If you make the added color depending on the recursion level (gradiant's), It should me more easy to see what path is taken.

Edited January 11, 2013 by MvGulik

[UEZ]

@MvGulik: sorry for misunderstanding (my fault) but with ...fails which I cannot understand. I mean why the recursion limit is choosen so low but trancexx has already answered it.

Maybe I will update the code to show in realtime how the alg. works.

Br,

UEZ