Get a random point in region (not rect)

[sethmachine]

Hi,

There is the native GetRandomLocInRect(), but is there a native for a region, where a region is a union of rects in JASS?

 

[Pharaoh_]

I've never wondered about this to be honest. I guess you can add the dimensions of each rect and create a new one, of which you will generate the random location; you can also loop to check if the random location is indeed within any of these rects, in case it is misplaced through the generation of a bigger one. There must be another way around that I'm missing though.

 

[Ceday]

You can attach all rects to region.(most likely to handle id)You probably thought this already but, don't think there is an easy solution.

 

[sethmachine]

Well basically I've got a single region with several, possibly disjoint, rects attached to it (added via: "AddRectToRegion").

I don't keep track of these rects in any additional data structure. Is there still no way to to pick a random point in the region (which really means choose a random point in one of the attached rects) without keep track of these rects making up the region, i.e. does region have any way of referencing the rects that make it up?

 

[WaterKnight]

RegionAddRect actually adds the cells of the rect. The region has no connection to the rect afterwards. There is a IsPointInRegion function but randoming points until one hits is a poor solution. On the other side not only do you have to keep track of the cells/rects added but also watch out for overlappings and balance the randomization.

 

[Dr Super Good]

There is the native GetRandomLocInRect()

No there is not. That is a BJ...

function GetRandomLocInRect takes rect whichRect returns location
    return Location(GetRandomReal(GetRectMinX(whichRect), GetRectMaxX(whichRect)), GetRandomReal(GetRectMinY(whichRect), GetRectMaxY(whichRect)))
endfunction

but is there a native for a region, where a region is a union of rects in JASS?

A region is not a union of rects, it is a collection of cells. These cells can be read in from a rect or individually but still there is not a 1:1 relationship in the area represented by a rect and a region made from the rect. This is why a unit may leave a region while still be inside the rect.

Specifically cells have a very limited granularity (some fraction of a tile) where as rects have bounds defined by 32 bit floats.

Is there still no way to to pick a random point in the region (which really means choose a random point in one of the attached rects) without keep track of these rects making up the region, i.e. does region have any way of referencing the rects that make it up?

There are no attached rects. A region is a collection of cells and has no active relationship with rects.

If the bounding rect of a region (the rect representing the maximum extents of all cells composing the region) is densely populated (mostly filled by the region) then you can pick a random point inside the bounding rect, test if it is in the region and if not try again (limited to a finite number of tries). Some form of failure management is required.

Do not think that even if you have a collection of rects finding a random point is straight forward. Anyone who has studied probability theory is probably shuddering at the thought even. The idea is you want to get a uniform probability distribution across the entire area the rects represent meaning that all possible random points are equally likely to be choosen.

If you pick a random rect from the collection you are not factoring in area the rect represents. This will result in it being as likely to return a point in huge half map rect as returning a point in a tiny few tile rect. The mathematics behind it is unequal probability distribution where each rect unit is given the same total chance that is then distributed evenly throughout the rect area so having a point fall within a small area inside a large rect is considerably less likely than having a point fall within a small area inside a small rect.

However the problems do not stop there. What about overlapping rects? When rects overlap the area of intersection is a random point in both composing rects resulting in the probability distribution from both composing rects being used at the area of intersection. This again results in uneven point distribution, a deviation for a truly random point.

Problem: Getting a random rect fairly.
Solution: Weights based on rect area.
Instead of assigning every rect a random index and picking one, like how random heroes work, you need to give them a range of values proportional to their area. This works by making large rects more likely to be picked than smaller ones equalling out their probability distribution across the area. A search tree is the perfect structure to carry out this mapping as you can assign rects a range of values and then from a random function call search for the rect that contains that random result.

Problem: Prevent overlapping summing probability distribution.
Solution: Non-overlapping rects.
Since rects are rectangular and aligned to the map axis, any intersection will result in a new rect (the area of intersection) and some rect fragments (the excluded area). Since none of these resulting rects overlap the problem simply disappears.

What about performance? Generating the input for a random rect is O(1) from the random function call, finding the rect is O(log2(n)) from the search tree and getting a random location from the rect is O(1) from the two required random calls. All in all the complexity is O(log2(n)) where n is the number of rects that compose up the set (after overlap removal).

There is a IsPointInRegion function but randoming points until one hits is a poor solution.

Depends on the region density with respect to the bounding box. If 99.99% of the region is solid then the number of re-rolls required will be few and far between. However if is is 0.01% dense (worse case, tiny rects far apart in corners) then it will probably result in a thread crash before a suitable point is found. Improvable? Possibly if you write off dead area (random number ranges that can never fall in the region) it will certainly help with sparse regions.

 

[WaterKnight]

Well, there is the bruteforce solution to simply store every cell of the region. For adding a whole rect you would iterate over it. You can index a cell by its corner coordinates R2I(((y - minY) / 32) * (maxX - minX) / 32 + ((x - minX) / 32)). Put them in a list, you can check if it already contains the element, maybe additionally use a 2d array to directly save under the coordinates. Anyway, you will need a hashtable or a super array. At least the randomization then is quite fast. Pick a random index of the list, reconvert it to coordinates y = index / ((maxX - minX) / 32) * 32; x = index % ((maxX - minX) / 32) * 32. Add a random number between 0 and 32 to x and y each.