Regions and Rects - Did you know

08-12-2008, 01:09 AM

I always thought regions were lists of rects, but it turns out they aren't. They are a set of cells (I think 128x128, maybe smaller).

I found this out debugging a spell for the spell olympics contest. If you add two overlapping rects, then remove either one of them, the overlapping section is removed. If the region was a list of rects, the overlapping section would remain.

Obviously that has some serious implication if you have overlapping rects being added and removed.

08-12-2008, 02:08 AM	#2
Anitarf	So, if you have two overlapping rects, and you add only one to the region and then remove the other one from it, does that reduce the size of the region too? Or are you only allowed to remove rects that were previously added (which would mean the region still kept a list of rects, even if it didn't use them).

08-12-2008, 02:10 AM	#3
Strilanc	I'm not sure how it all works out internally, but I would say yes. For example, if you have a region with one big rect, then add and remove a small rect from the center, you should get a region with a hole in the middle (a donut).

08-12-2008, 02:25 AM

Anitarf

Quote:

For example, if you have a region with one big rect, then add and remove a small rect from the center, you should get a region with a hole in the middle (a donut).

My question was, what happens if you don't add and remove the small rect, but only remove it; I assumed you had a testing environment set up and would test this rather than speculate.

08-12-2008, 03:06 AM	#5
Strilanc	If you don't add first then it will still remove the intersecting area from the region. (tested) In other words, the region rect functions are just delegating to the region cell functions.

08-12-2008, 03:26 AM	#6
Vexorian	I considered them a set of points, at least that seems to be the abstraction, they got this RegionAddCell native, I think that someone else already knew about 128x128 cause I remember seeing a post recently about regions being a set of XxX cells.

08-12-2008, 03:54 AM	#7
Strilanc	I suppose it makes sense: it's much faster to evaluate whether or not a unit is in a set of cells than a set of rects. With the cells a quad-tree will be very efficient. It's also nice to be able to make donut-type shapes easily. But it is kindof annoying that I now need to keep track of overlapping regions manually. If there was a RegionClearRegion function, that would be very useful.

08-12-2008, 07:03 AM	#8
cohadar	Regions are bitmaps.

08-12-2008, 09:44 AM

d07.RiV

I saw someone saying they are 32x32, just like the pathing cells.

Hmm one should try creating many regions and see how much KB they take up. It should be 32k for a 128x128 map if they actually are bitmaps with 1 bit per cell.

And you don't need a quad tree if you're actually storing the entire image :p
It would be much less efficient to store them as separate cells because that would be at least 4 or 8 bytes per cell, and Region (bj_mapInitialPlayableArea) would take up much more memory than we probably expect.

08-12-2008, 04:47 PM	#10
Troll-Brain	The size of a cell for a regions is definitely 32*32. I already tried it, and it's strange for me that you didn't test before that. Ok they are pretty useless in many cases, but ...

08-12-2008, 05:38 PM	#11
Anitarf	What about rects, are they also cell based? Is there a difference between a 128x128 and a 130x130 rect?

08-12-2008, 05:39 PM	#12
Captain Griffen	Rects hold 4 reals. I highly doubt they are cell based. However, it is entirely possible that Blizzard's implementation is incredibly lame...there is no reason for them to be linked to any grid though.

08-12-2008, 05:43 PM

#13

Troll-Brain

Test this code for the cells :

JASS:

library CellSize initializer init

    public function R32 takes real r returns real
        return 32.0*(R2I(r/32.0))
    endfunction
    
    //! textmacro display takes X , Y
        if IsPointInRegion(reg,x+$X$,y+$Y$) then
            call BJDebugMsg("the point ("+ R2S(x+$X$) + "," + R2S(y+$Y$) + ") is in the region")
        else
            call BJDebugMsg("the point ("+ R2S(x+$X$) + "," + R2S(y+$Y$) + ") is outside the region")
        endif
    //! endtextmacro
    
    function Test takes real x, real y returns nothing
        local region reg= CreateRegion()
        
        call RegionAddCell(reg,x,y)
        call BJDebugMsg(" the xMin for the Cell("+ R2S(x) + "," + R2S(y) +") is " + R2S(R32(x)))
        call BJDebugMsg(" the yMin for the Cell("+ R2S(x) + "," + R2S(y) +") is " + R2S(R32(y)))
        call BJDebugMsg(" the xMax for the Cell("+ R2S(x) + "," + R2S(y) +") is " + R2S(R32(x)+32.0))
        call BJDebugMsg(" the yMax for the Cell("+ R2S(x) + "," + R2S(y) +") is " + R2S(R32(y)+32.0))
        call BJDebugMsg(" ")
        set x= R32(x)
        set y= R32(y)
        //! runtextmacro display("-0.1","0.0")
        //! runtextmacro display("0.0","-0.1")
        //! runtextmacro display("0.0","0.0")
        //! runtextmacro display("31.9","31.9")
        //! runtextmacro display("32.0","31.9")
        //! runtextmacro display("31.9","32.0")
        //! runtextmacro display("32.0","32.0")

        
    endfunction
    
    public function init takes nothing returns nothing
    endfunction
    
endlibrary

No rects aren't cells based, just test the function GetRectMinX and so one.
But ofc if you add a rect to a region, it will be cell based.
I guess that's why in the map editor the rects are always a multiple of 32 and follow the rule like the function R32 i posted in my preview post.
Or let's say it follow the grid :p
In fact if you use only gui without any jass script, then your rects will become regions exactly as they are rect.
I think it's also the reason they call them regions for don't confuse noob gui users ( i don't want say all they are ...)

The only need of 128*128 is for the terraintype.
Btw that's not exactly 128 but kinda a "random" strange value.

Oh and other thing if you use an attachment system or simply a global var,you can edit the region and then it will be affect his register enter/leave event as well.
But like all i said in this topic it's logical ...

08-13-2008, 12:14 AM

#14

ToukoAozaki

I made a test map that checks and adds all cells matching criteria in the entire map. The cells are checked and loaded during map loading (I had to use some tricks to avoid op limit).

1. It takes up much more time to load. On 32x32 the effect was not so visible, but on over 128x128 took slightly longer-over 20~30 sec.
2. It takes up more memory space. It increases as more cells are loaded, and I remember the increased amount of memory was multiple of 10MBytes (I remember it as 60MBytes at 480x480, but I'm not sure.).

Attached Files

regiontest.w3m (53.8 KB)

08-13-2008, 05:19 PM

#15

Strilanc

This explains why the entering unit may not be in the rect you registered. When you add the rect it rounds to the cell borders to create the region it will register the event to, so the region will be (potentially) larger than the rect.

That might also explain a post I saw complaining about how the different sides of the rects are treated differently. The rounding acts differently on each side (eg. floor will tend to move left and down, but maybe it always rounds out and the tester picked only one set of test coordinates).