Is this hitting the op limit?

[sethmachine]

Hi,

So this is a library that picks out a random point. The point must not be in X range of any destructables. To enforce this, it loops and repicks the point until it satisfies the condition.

My question is, how likely is it that this function could hit the OP limit and therefore crash? I suppose this is just a math problem (how much area is a valid point), but the area I am using is about 70% walkable, 30% tree.

I want to say no, that it's not hitting the OP limit, but I feel like it does occasionally (if only the OP limit were higher or non-existent :/).

If it is the OP limit, how can I reset it and continue searching for the point?

library RandomLoc

globals
	private integer count = 0 //if > 0, then there are destructables in range
endglobals

function getRandomPointOnCircle takes location origin, real diameter returns location
    local real a = GetRandomReal(0, 2* bj_PI) // random angle
    local real x = diameter * Cos(a) // x offset
    local real y = diameter * Sin(a) // y offset
    return Location(x + GetLocationX(origin), y + GetLocationY(origin))
endfunction

private function enum takes nothing returns nothing
	set count = count + 1
endfunction


private function isLocReachable takes location whichLoc, real range returns boolean
	set count = 0
	call EnumDestructablesInCircleBJ(range, whichLoc, function enum)
	if count > 0 then
		return false
	endif
	return true
endfunction
	
	

function getRandomReachableLoc takes location origin, real diameter, real range returns location
	local location randomLoc = getRandomPointOnCircle(origin, diameter)
	loop
		exitwhen isLocReachable(randomLoc, range)
		call RemoveLocation(randomLoc)
		set randomLoc = null
		set randomLoc = getRandomPointOnCircle(origin, diameter)
	endloop
	return randomLoc
endfunction

function getRandomReachableLocInRect takes rect whichRect, real range returns location
	local location randomLoc = GetRandomLocInRect(whichRect)
	loop
		exitwhen isLocReachable(randomLoc, range)
		call RemoveLocation(randomLoc)
		set randomLoc = null
		set randomLoc = GetRandomLocInRect(whichRect)
	endloop
	return randomLoc
endfunction

endlibrary

 

[IcemanBo]

You have to test it by yourself. But for this little function I guess you would need more than thousend of function calls. (but still strongly depending on size of loop of course)

If it is the OP limit, how can I reset it and continue searching for the point?

I also have/had this problem, and my solution was just to define a MAX_CALL constant and a counter for my function calls.
Each time you call your function you increment the counter by 1. And if counter == MAX_CALL, you start a timer that expires after 0 seconds and call that function again.
This way you start a new operation thread with only a minimal loss of time.
The initilization of MAX_CALL strongly depends to your needs, you might make some tests to get a fair big number, but still to ensure never hitting the limit.

 

[edo494]

a bit offtopic, but camelCase for public API is not nice, this aint no C++ stl

back on topic:

what happens if there are no trees in the rect? it will crash the thread because you never check that. This will also hit OP limit if the rect is very big and there are very few trees, or very dispersed in the rect.

Maybe a bit better solution would be to first check if there are any trees and while you iterate over trees that are inside the diameter of your location, if there are none you return invalid location, otherwise you return location of random one.

My implementation:

library GetRandomLocABC

    globals
        private destructable randDest = null
        private integer count = 0
    endglobals
    
    function GetRandomPointOnCircle takes location origin, real diameter returns location
        local real a = GetRandomReal(0, 2* bj_PI) // random angle
        local real x = diameter * Cos(a) // x offset
        local real y = diameter * Sin(a) // y offset
        return Location(x + GetLocationX(origin), y + GetLocationY(origin))
    endfunction
    
    private function enum takes nothing returns nothing
        set count = count + 1
        if GetRandomInt(0, 1) == 1 then
            set randDest = GetEnumDestructable()
        endif
    endfunction
    
    function GetRandomReachableLoc takes location origin, real diameter, real range returns location
        local location loc = null
        local location ret = null
        
        //reset the enumerator
        set count = 0
        set randDest = null
        
        //enum all trees in the the diameter from the origin
        call EnumDestructablesInCircleBJ(diameter, origin, function enum)
        
        //if there are no trees in the diameter of origin
        if count == 0 then
            //return invalid location, or return [0, 0]
            return null // or Location(0, 0)
        endif
        
        //set loc to pos of dest
        set loc = GetDestructableLoc(randDest)
        
        //find random point centered to location loc and within 
        //range "range"
        set ret = GetRandomPointOnCircle(loc, range)
        
        //remove and null location
        call RemoveLocation(loc)
        set loc = null
        
        //return
        return ret
    endfunction
    
    function GetRandomReachableLocInRect takes rect whichRect, real range returns location
        local location loc = null
        local location ret = null
        
        //reset the enumerator
        set count = 0
        set randDest = null
        
        //enum all trees in the rect
        call EnumDestructablesInRect(whichRect, null, function enum)
        
        //if there are no trees in the diameter of origin
        if count == 0 then
            //return invalid location, or return [0, 0]
            return null // or Location(0, 0)
        endif
        
        //set loc to pos of dest
        set loc = GetDestructableLoc(randDest)
        
        //find random point centered to location loc and within 
        //range "range"
        set ret = GetRandomPointOnCircle(loc, range)
        
        //remove and null location
        call RemoveLocation(loc)
        set loc = null
        
        //return
        return ret
    endfunction

endlibrary

May not be 100% what you have tho, because I dont really understand the purpose of range argument in your functions

 

[sethmachine]

Edit: I posted this at the same time your reply came up edo.

I use camel case for function names because that's how I learned it for Java, and Java/JASS have very similar syntax, and it doesn't help that the names both are monosyllabic and begin with "J" haha.

what happens if there are no trees in the rect? it will crash the thread because you never check that.

I did not consider that, but it will always be true that there is at least one destructable inside a given rect, but many thanks for enlightening me of this. So you are saying that EnumDestructablesInCircleBJ crashes if it finds no destructables in the circle? Or where does it crash in the library if there are no trees in the rect?

This will also hit OP limit if the rect is very big and there are very few trees, or very dispersed in the rect.

I am not sure how this would hit the OP limit? If anything I would expect that the probability of the function hitting the OP limit to approach 0 as the number of trees approaches 0.

The more trees there are, the harder it is to find a point which satisfies "no trees within range X of this point." Or is my understanding wrong (please please correct me ^^!)?

I dont really understand the purpose of range argument in your functions

range is a parameter that I am trying to tune/optimize, which basically fits in this slot:

(i) NO-TREES: For all randomly generated points, there can be no trees within range X of that point.

If I choose a very high value for range, it makes it harder and harder to find a point which satisfies (i). The smaller range is, the more points which satisfy (i), but obviously if range approaches zero, the probability increases I choose a point that is unreachable (i.e. surrounded by trees).

In the function getRandomReachableLoc , the parameter diameter determines all the candidate points given an origin location (i.e. all points Y distance away from the origin loc). The parameter range then is just the parameter for constraint (i) NO-TREES, as described above.

For the function getRandomReachableLocInRect , there is no diameter parameter, because the function considers every point inside the rect.


@iceman
Aye I was thinking of doing that, I just did not know how to reset a thread / op limit.

If you could spare a moment, could you comment in the library where I should do the timer?

Or does the timer need to be put outside of the function (i.e. whereever I am calling "getRandomReachableLocInRect")?

Also, I can't use a single global to monitor the OP limit, since this function gets called for multiple players, or can I?

 

[edo494]

nah I dont have problem with that and you can check my implementation, which should never hit OP limit since it never iterates over anything pretty much, unless you have thousands and thousands of trees in your rect/diameter of origin.

If you wanted to do it Iceman's way, you would need to implement something like std::future, std:romise or some semaphore, because your function would need to wait for the result if you ever got to the timer

edit: To explain what my script does, it first checks if there are any destructables in given area. If there are none, there is no pickable location, hence return null. If there are, then we already have random tree in our destructable variable, since we check to GetRandomInt(0, 1) == 1 and if it is true, we set the currently enuming destructable to our variable. Then we get random point in range of that tree and return it

 

[sethmachine]

edo494 I think your script is solving the complement of my problem, namely satisfying the constraint (also see my edit):

(ii) TREES: For all randomly generated points, there must be at least one tree within range X of that point

 

[edo494]

your approach will crash your thread when there are no destructables, because you never check for that. This is true for very dispersed trees in large area too, because you have lower and lower chance to actually encounter tree at random location.

The first crash is because

private function isLocReachable takes location whichLoc, real range returns boolean
    set count = 0
    call EnumDestructablesInCircleBJ(range, whichLoc, function enum)
    if count > 0 then
        return false
    endif
    return true
endfunction
//...

    loop
        exitwhen isLocReachable(randomLoc, range)
        call RemoveLocation(randomLoc)
        set randomLoc = null
        set randomLoc = GetRandomLocInRect(whichRect)
    endloop

//....

While your function returns false if there are no trees, you dont check for that fact, you just keep looping. If there are no trees this will loop forever.

I have rechecked the way that the enumeration works, and there seems to be no loop, so neither mine nor yours would crash if too many destructables were placed inside the diameter of location/rect.

Basically what you do is you generate a point and then check if there is tree around it, while I take random tree and then generate random location from that. Your method is worse than mine, because I base it on what you want to satisfy, have a tree. But you generate point and then check if there is a tree around it

 

[sethmachine]

Your method is worse than mine

I do not recall discussing which library is "better" or "worse." The OP asks

how likely is it that this function could hit the OP limit...If it is the OP limit, how can I reset it and continue searching for the point?

This is what I want to satisfy

(i) NO-TREES: For all randomly generated points, there can be no trees within range X of that point.

Below is what I believe your code is trying to satisfy, and what I am not trying to do.

(ii) TREES: For all randomly generated points, there must be at least one tree within range X of that point

This is not what my code is trying to do

I base it on what you want to satisfy, have a tree

I do not want a tree, in fact. The library searches for a random point in a given rect that is not within range of X of any destructable.

The point must not be in X range of any destructables

AFAIK, these constraints generate complement set of points (assuming the ranges are the same). So I understand that if I wanted to satisfy (ii) my code would crash if there are no trees in the rect. This is because it is impossible to satisfy (ii), since if there are no trees in the rect, there cannot be any points which are in range X of at least one tree. But if there are no trees in the rect and I need to satisfy (i), I am guaranteed with 100% probability to find a point on the very first iteration.

 

[edo494]

well not worse per se, but I mean mine is straight with no loop, while yours performs loop. Sorry if that sounded too selfish or arrogant.

Also, you dont want tree, but you want(or at least I understood your script this way) a tree in range of your random point.

Can you write somehow noncryptically what you want to achieve? because your (i) and (ii) is like reading C++ standard, unreadable by normal human being

You only provide the searchers, not the callers, so I have to assume you do not perform the checks if there are trees in the rect, since you never showed how you call the code.(you mentioned it before my last post, so yeah I could've ommited that comment kind of, but still you can only be sure that there is a tree inside the rect or inside diameter from point, if you actually check. You cant just assume there will be trees without checks)

edit: If you havent read this yet, also can you state the coditions which this satisfies? In a bit more understandable way than the (i) (the (ii) is quite readable)

edit2: lol Ive re-read your post above this one, I will update the lib and post it.

edit3: thinking about this, your resource is almost exactly the same thing I would write

But it can still hit the op limit if you are unlucky and keep picking points around trees. If you want this to use timer, you can but all code that uses those functions must also use timers to check if there has been any point successfuly found

 

[sethmachine]

Edit: Here are two images. The black circle represents the rect/area (forget that it's a circle) we want to find a random point in. The green arrow represents a tree. The solid black area represents all points that are valid according to a given constraint. In this simple case, suppose there is only a single tree in the entire rect. The first image shows all the points my library wants to generate. The second image is all the points your library will generate. Anything that is colored black is a valid point. Otherwise if it is white or green, it is not a valid point according to that constraint.

(i) NO-TREES vs (ii) TREES

Hope this clarifies your confusion.

well not worse per se, but I mean mine is straight with no loop, while yours performs loop. Sorry if that sounded too selfish or arrogant.

No. I was wrong about your library generating the complement set of points. It does generate some points which satisfy (i) NO-TREES, because if a point is exactly X distance away from all trees, then it satisfies both (i) and (ii).

However, since your library does not check to see if there are other trees next to your point, you only satisfy this constraint:

(ii) TREES: For all randomly generated points, there must be at least one tree which is exactly range X away from a generated point.

You do not need to loop because this constraint only cares about a single tree, which you can find in constant time, as long as there is at least one tree in the rect.

On the other hand, to satisfy (i), I have to make sure that the point I pick is at least X distance away from every single tree. This requires a search (therefore a loop is required) and cannot be done in constant time (like your library), unless all such points were cached ahead of time, in which case I would just choose a random point in an array.

Thus there is no comparison between our libraries, since they are tackling different problems.

you do not perform the checks if there are trees in the rect

It doesn't matter if there are trees or not. If there are no trees, then my library is equivalent to this native: GetRandomLocInRect(...).

 

[edo494]

yea sorry I misunderstood and for some reason I didnt most likely read properly your last post

Thus there is no comparison between our libraries, since they are tackling different problems.

I just now understood that my library does exactly the opposite thing that yours does so that is more than correct

Now I see why my code is not good, and your is sufficient, but as pointed under edit3, it still may hit the OP limit.

Basically everything Ive wrote in this thread up to this point except the fact that it may hit OP limit is complete bullshit, cause I totally misunderstood how this resource is supposed to work

 

[sethmachine]

No worries. I am glad everything is straightened out now so we can try to solve the OP limit problem.

But actually your solution is not the opposite necessarily. Consider the pictures above in my last post.

If there is a single tree, then all your points will actually be a subset of the points generated in my method, since those points will satisfy both (i) and (ii), if there is only a single tree, necessarily.

However, with more trees, the library your wrote does not take into account the positions of other trees, so it will be harder to find points which satisfy both (i) and (ii) (they exist, but get very hard to find as the number of trees increases).

 

[edo494]

yea true, I would still need to iterate over all enumed trees to check distance, and if it didnt satisfy the positioning, I would need to go to the beginning, just like yours.

As I said, you can hook timer in there with Table or hashtable to keep indicies to some private struct and keep some data there.

This however means that everything that is going to wait for result of this function will have to also use timer to wait for solution, and that the function can no longer return the location, you will have to set global variable for that

 

[Dr Super Good]

Place a debug message at the end of the script you are worrying hits the op limit. If it shows then not it is not hitting the op limit. If it does not show then you are hitting the op limit.

In SC2 the game is polite enough to send you an op limit error message when ever a thread ends pre-maturely due to the op limit. In WC3 you can only detect op limit thread terminations by the lack of something happening.

For automatic run time detection you can use a boolean variable. At the start of the thread you set the global boolean to true. At the end of the thread set it to false. You can then check this boolean for if it is true to see if a thread crash occurred (will also pick up other thread crashes like division by 0). Obviously this only works if the code is run by a single thread at a time (no overlapping threads such as can occur with TriggerSleepAction or recursion). Why bother? Well you can always display an error message to users who can report back to you that a op limit thread crash occurred allowing you to modify the thread load and hopefully reduce the likelihood of it occurring in the future.

It should be noted that to prevent all op limit thread crashes you need to place very strict bounds on your map. An example could be no more than 50 instances of an ability at once.

Avoiding the op limit can be done in three main ways.
1. TriggerSleepAction (Wait). Resets op counter at the cost of a variable delay. Good for non timing critical tasks and easy to implement. Not possible in most cases but is great for big sequential things.
2. More threads. If one thread op limit is too little, break the task over many. You can even make one thread spawn another (chain them!). Can be difficult to code iteratively. The op limit is also there for a reason to prevent excessive processor time being used by a thread and so this can allow for absolutely abysmal performance (unplayable frame rate).
3. Stagger load. Instead of running everything immediately. Run it over several updates with a frame or few gap between. Kind of like 1 except a timer is used requiring instancing techniques. Also needs a load manager for periodic tasks to make sure the stagger frames have symmetrical load. This is best for very demanding tasks that would cause frame drops if run with method 2 yet method 1 will produce unusable results.

 

[PurgeandFire]

I haven't read through the thread, but ideally, this is how you would go about it:

(1) Determine how many function calls (rough estimate) to hit the op limit.
(2) Add a counter to the system that increases each time you have to loop. When you hit a certain threshold (# of function calls), just start a new thread. You can do this with ForForce, TriggerEvaluate, etc.

The important thing: you don't have to be perfect about it. You can just make a rough estimate (e.g. 1000 function calls). It is better to low-ball it than to depend on a precise number. And just for extra security, the first time the function is called, you should start the process on a separate thread, because if the current thread has enough function calls already, it'll break prematurely.

 

[sethmachine]

Many thanks for your advices everyone.

I did put in a debug message and did some manual testing (no idea how I would automate this without replicating the placement of trees outside of WC3).

Obviously the results I get are dependent on the placement of the trees in the given rect. Calculating the probability of how long (i.e. how many loops) it would take to find a random point given a placement of trees and a range parameter would probably tell me if I would realistically ever hit the OP.

In any case, I tried using range 1000.0 as an upper bound parameter--if range 1000.0 never hits the OP limit, then anything lower should also never hit it (or rather the probability is near zero).

I averaged about ~35 iterations over 100 trials--there were some outliers, like the occasional 200 or so iterations before finding a suitable point, but that's not even close to the OP limit (somewhere around 1000 as Purge suggests or slightly lower from my previous explorations).

However, even with a low range value (r = 200.0), very rarely I would get iterations that took over a 100 hundred steps, as it almost always was in the range of 0-4.

So I am think I am not hitting the OP limit and rather just have poor vision (I am using this method to place items randomly, and many times I couldn't find the correct items). But the debug messages have proven I was wrong.

Of course I think to really polish the library I should handle the rare event that it might hit the OP limit. Again I can't calculate the exact probability without encoding the placement of the trees outside of WC3 (e.g. a Python data structure). But I am guessing it is near zero.

 

[Xonok]

One idea is that you can simply detect thread crashes.

Before you start the loop, set a boolean to true. When the loop ends, set it to false. Then have a separate trigger checking whether this boolean is true. If it is, then you know for sure that the thread crashed.

 

[edo494]

I wanted to write something, but it just overloaded my brain and I removed the Trigger

Basically what you can do is store number of current iterations to hashtable under handleid of timer, then the timer will restart the operation(you must store the passed arguments in the hashtable too), and return null. This will let the caller know that it didnt find any valid location, so he has to wait for the timer to finish, so you can either start timer, or somehow register callback to it and when you find the location store it inside global variable and call the callback(effectivelly signaling it that you have found valid location). You can also store number of max times the timer will restart it to prevent infinite loop, or you must ensure that for any given input, there is always at least one valid location

 

[sethmachine]

Many thanks. The advice and replies have turned this into a valuable resource when I polish that library ^^.

But a sort off topic question, why does an OP limit exist at all?

We know the halting problem can't be solved. So why does Blizzard (or any language) say: "Well after N calls/iterations, the function must be looping forever, so crash the thread." That seems a bit haughty, as it's entirely wrong. Let the calls go ad infinitum, and trust the programmer that he/she wrote correct logic.

 

[edo494]

the game has a lot of things to handle, graphics, game logic, and finally the interpreter. You cannot let the interpreter run forever, and make no space for logic or graphics. It is game, not interpreter or Jass simulator, so eventually the game logic must make progress and so does the graphic must get outputed to the screen. Also there are ways to deadlock map.

Nowhere is it said that the interpreter will say: "Oi, the code is running forever, better halt it down", it will just say after certain OPcodes that it takes too long, and that the game logic and graphics shall make progress, and halt it.

Yes they could've made it run forever, but a looot of people make stupid stuff that hits the OP limit very easily, if they let the code run, you could theoretically deadlock the map even before the map loads(cause some poeple do crazy shit on map initialization)

 

[Ruke]

for getRandomReachableLocInRect.

1) take rect, divide it by range (so you will have possible locations)

_______            ______
|     |           |__|__|
|_____|     ->    |__|__|

2) iterate over all those locations, if it is valid, add to an array
3) check length of array, return null if it is equal to 0
4) return array[rand(0, length array-1)]

hope it helps.

answering to your question, it can/will (rare situation) hit the op limit.

 

[edo494]

it can? Imagine rect that is 600x600, there is no way you iterate over 600x600 locations before hitting OP limit, considering some of the op limit is eaten up by the caller of your function, and it still wishes to do something with the location afterwards, so it still requires a bit of OP limit to run

edit: and no, 600x600 is not big, some spells have 1000+ range on them, and they dont even go beyond your view on the screen.

 

[Ruke]

I'm really bad at trigonometry, I tried to divide the area into small areas and I failed miserably xD. If anyone can help here, the function/idea should work pretty well.