[Solved] Cannot find mistake - loop runs infinite times/rectangle intersection check wrong ?

[Ardenian]

After http://www.hiveworkshop.com/forums/triggers-scripts-269/operation-limits-276842/ and http://www.hiveworkshop.com/forums/...hecking-if-point-region-partly-region-276804/,
I would be glad to receive some final help on debugging and finding the mistake in my system.
I spent hours, I would say around six, trying to find a reason why my system does not work.

Basically, I create a random amount of rectangles, 'rooms', and check if a newly created one intersects with formerly created ones.
If so, I randomize the newest one again. If not, I keep it.

However, after the first rectangle is created, the function starts to infinitly loop trying to create the second one, but
calculating every time the second one intersects the first one.

Jass Script

function Overlapcheck takes integer i, real xMin1, real yMin1, real xMax1, real yMax1 returns boolean
    local integer overlap = 1
    local real yMax2
    local real yMin2
    local real xMin2
    local real xMax2
    loop // check if the room overlaps with another
    exitwhen overlap == i
        //call BJDebugMsg( "Current room overlap check: "+I2S(overlap))
        set xMin2 = GetRectMinX(udg_RoomRect[overlap]) 
        set yMin2 = GetRectMinY(udg_RoomRect[overlap])
        set xMax2 = GetRectMaxX(udg_RoomRect[overlap])
        set yMax2 = GetRectMaxY(udg_RoomRect[overlap])
        if xMin1 < xMax2 or xMax1 > xMin2 or yMin1 < yMax2 or yMax1 > yMin2 then
            //call BJDebugMsg( "overlap")
            return true // there is overlap
        endif
        set overlap = overlap + 1
    endloop
    call BJDebugMsg( "no overlap")
    return false // there is no overlap
endfunction

function CreateRooms takes nothing returns nothing 
    local integer i = 1 // i is the number of the room that is created
    local real x
    local real y
    local real breadth
    local real length
    local boolean xycheck = true
    local real x2
    local real y2 
    
    set udg_RoomCount = GetRandomInt( 3, 8) // total rooms
    loop
    exitwhen i > udg_RoomCount
        
        set xycheck = true
        
        // intial randomized room data
        loop
        exitwhen xycheck == false // true = there is intersection
            set x = 0 + I2R(GetRandomInt( -41, 25))*128 // x coordinate of the intial room point
            //call BJDebugMsg( "Current room X: "+R2S(x))
            set y = 0 + I2R(GetRandomInt( -25, 41))*128 // y coordinate of the inital room point
            //call BJDebugMsg( "Current room Y: "+R2S(y))
            set breadth = I2R(GetRandomInt( 6, 14)) // breadth of the room
            set length = I2R(GetRandomInt( 6, 14)) // length of the room
            set x2 = x + breadth*128 // last point in the room
            set y2 = y - length*128  // last point in the room
            set xycheck = Overlapcheck( i, x, y, x2, y2)     
        endloop
        set udg_RoomRect[i] = Rect( x, y, x2, y2)
        set udg_RoomX[i] = x
        set udg_RoomY[i] = y
        set udg_RoomBreadth[i] = breadth
        set udg_RoomLength[i] = length
        call BJDebugMsg( "current room: "+I2S(i))
        set i = i + 1
    endloop
endfunction

function InitTrig_CreateRooms takes nothing returns nothing
endfunction

My theory is that the intersect check is wrong, since it does not seem logical to me why the current check should work, since there is only a check for a direction, not a two-dimensional intersection ( or something, I suck at math).
However, several people approved the check for the intersection.

If you enable

//call BJDebugMsg( "Current room X: "+R2S(x))

and

//call BJDebugMsg( "Current room Y: "+R2S(y))

in the second function, CreateRooms, you see it runs infinite times.
Additionally, it occasionally seems to work appropiatly.

I would be very grateful if you could help me here, I am at a point I would say I am desperate.

 

[Flux]

Why not make OverlapCheck takes rect r1 and rect r2 as input arguments? Then do something like this for the overlap check.

function OverlapCheck takes rect rect1, rect rect2 returns boolean
    local real xMin1 = GetRectMinX(rect1)
    local real xMin2 = GetRectMinX(rect2)
    local real xMax1 = GetRectMaxX(rect1)   
    local real xMax2 = GetRectMaxX(rect2)
    local real yMin1 = GetRectMinY(rect1)
    local real yMin2 = GetRectMinY(rect2)
    local real yMax1 = GetRectMaxY(rect1)   
    local real yMax2 = GetRectMaxY(rect2)
    if xMin1 < xMax2 or xMax1 > xMin2 or yMin1 < yMax2 or yMax1 > yMin2 then
        return true
    endif
    return false
endfunction

Example

 

[Ardenian]

Overlapcheck takes the rectangle Min and Max coordiantes of a newly created rectangle, a rectangle that will be compared to all previously created rectangles saved in udg_RoomRect[].
So, if Overlapcheck takes rect 1, you wil have to convert them to the Min and Max anyways and rect 2 is initialized in CreateRooms, every time the newly created one overlaps with one of the previous ones.

It would not make a difference, would it ?

 

[Flux]

Yeah you're right. I misread it. Hmmm, it's possible that the OverlapCheck is wrong because I suggested that algorithm at a state where I have no sleep so I must have been wrong. Did the diagram made sense?

 

[Ardenian]

It is matching with the graphic you created:

xMin1 < xMax2 or xMax1 > xMin2 or yMin1 < yMax2 or yMax1 > yMin2

Visualization

My theory, I don't know how the two rectangles are located towards each other, do I have to take that into concern ?

 

[Flux]

The algorithm I gave was a flaw. It can't detect correctly at a situation like this.

EDIT: Try this instead, I'm merely just using trial and error with you doing the trial.

if (xMin1 < xMax2 or xMax1 > xMin2) and (yMin1 < yMax2 or yMax1 > yMin2) then

 

[Ardenian]

The edited one does not work, it does not detect overlaps, sadly

 

[Flux]

    function CheckOverlap takes rect rect1, rect rect2 returns boolean
        local real xMin1 = GetRectMinX(rect1)
        local real xMin2 = GetRectMinX(rect2)
        local real xMax1 = GetRectMaxX(rect1)   
        local real xMax2 = GetRectMaxX(rect2)
        local real yMin1 = GetRectMinY(rect1)
        local real yMin2 = GetRectMinY(rect2)
        local real yMax1 = GetRectMaxY(rect1)   
        local real yMax2 = GetRectMaxY(rect2)
        if (xMin1 < xMax2 and xMax1 > xMin2) and (yMin1 < yMax2 and yMax1 > yMin2) then
            call BJDebugMsg("OVERLAP!!!")
            return true
        endif
        call BJDebugMsg("SAD")
        return false
    endfunction

 

[Ardenian]

Here is my updated script:

EDIT Updated once more

Jass script

function GridPointX takes integer i, integer i2 returns real
    local real x = I2R(i2)/udg_RoomBreadth[i] - R2I(I2R(i2)/udg_RoomBreadth[i]-0.05)
    set x = x*udg_RoomBreadth[i] -1
    set x = udg_RoomX[i] + x*128
    return x
endfunction

function GridPointY takes integer i, integer i2 returns real
    local real y = R2I(I2R(i2)/udg_RoomBreadth[i] -0.05)
    set y = udg_RoomY[i] - y*128
    return y
endfunction

function GridPoint takes integer i, integer i2 returns location
    local real x = GridPointX(i,i2)
    local real y = GridPointY(i,i2)
    return Location(x,y)
endfunction

function CheckOverlap takes rect rect1, rect rect2 returns boolean
        local real xMin1 = GetRectMinX(rect1)
        local real xMin2 = GetRectMinX(rect2)
        local real xMax1 = GetRectMaxX(rect1)  
        local real xMax2 = GetRectMaxX(rect2)
        local real yMin1 = GetRectMinY(rect1)
        local real yMin2 = GetRectMinY(rect2)
        local real yMax1 = GetRectMaxY(rect1)  
        local real yMax2 = GetRectMaxY(rect2)
        if (xMin1 < xMax2 and xMax1 > xMin2) or (yMin1 < yMax2 and yMax1 > yMin2) then
            call BJDebugMsg("OVERLAP!!!")
            return true
        endif
        call BJDebugMsg("no overlap")
        return false
endfunction

function CreateRooms takes nothing returns nothing 
    local integer i = 1 // i is the number of the room that is created
    local integer i2 = 1
    local real x
    local real y
    local real breadth
    local real length
    local boolean xycheck = true
    local boolean looplap = false
    local real x2
    local real y2
    local rect rect1
    local rect rect2 
    
    set udg_RoomCount = GetRandomInt( 3, 8) // total rooms
    loop
    exitwhen i > udg_RoomCount
        
        set xycheck = true
        
        // intial randomized room data
        loop
        exitwhen xycheck == false // check if there is an overlap
            call BJDebugMsg( "current room: "+I2S(i))
            set x = 0 + I2R(GetRandomInt( -41, 25))*128 // x coordinate of the intial room point
            call BJDebugMsg( "Current room X: "+R2S(x))
            set y = 0 + I2R(GetRandomInt( -25, 41))*128 // y coordinate of the inital room point
            call BJDebugMsg( "Current room Y: "+R2S(y))
            set breadth = I2R(GetRandomInt( 6, 14)) // breadth of the room
            set length = I2R(GetRandomInt( 6, 14)) // length of the room
            set x2 = x + breadth*128 // last point in the room
            set y2 = y - length*128  // last point in the room
            set rect1 = Rect(x,y,x2,y2)
            set i2 = 1
            set looplap = false
            loop
            exitwhen i2 > i
            exitwhen looplap == true
                call BJDebugMsg( "current overlapcheck "+I2S(i2))
                set rect2 = udg_RoomRect[i2]
                set looplap = CheckOverlap( rect1, rect2)
                set i2 = i2 + 1
            endloop
            if looplap == false then
                set xycheck = false
            endif
            call BJDebugMsg( "end of xycheck loop")     
        endloop
        set udg_RoomRect[i] = rect1
        set udg_RoomX[i] = x
        set udg_RoomY[i] = y
        set udg_RoomBreadth[i] = breadth
        set udg_RoomLength[i] = length
        call BJDebugMsg( "finalized room: "+I2S(i))
        set i = i + 1
    endloop
endfunction

function InitTrig_CreateRooms takes nothing returns nothing
endfunction

It still overlaps, but I start doubting the formula you gave me causes it.

EDIT: I think it does not overlap anymore. However, the script stops working if a higher room count than 5 is chosen.

 

[Anitarf]

My guess is that you're hitting the op limit. As you add more rooms, it becomes increasingly more difficult to randomly find a new room that won't overlap with existing rooms. Therefore, your system needs to retry so many times that it hits the JASS op limit and dies. The proper solution to this problem would be to use a more intelligent algorithm that doesn't rely on blind luck to get a non-overlapping room. Alternatively, you could use TriggerEvaluate to bypass the limit - in that case, if you reach a situation where it is impossible to place another room, the game will freeze.

 

[Ardenian]

Yes, I agree, thank you, in the mean-time I thought about changing the loops to ExecuteFunction, using global variables, to reduce the operations.
Should work, too, shouldn't it ?

To make the algorithm more intelligent,
I thought about adjusting the minimum and maximum length and breadth of a room, so
the initial rooms would be average-big sized, but rooms after a count of 5 would be small-average sized.
Do you have another suggestion towards intelligence of my algorithm ?

 

[Anitarf]

Gradually reducing the size of the rooms would be a good first step in reducing the number of failed room creation attempts. If you are hitting the op limit with just 8 rooms, though, then that will likely not be a sufficient fix. I recommend TriggerEvaluate instead of ExecuteFunc, that way you can see from the return value if the branch completed successfully or whether it hit the op limit.

Another possible algorithm would be to take the area and start randomly splitting it into more areas with vertical/horizontal walls, you would pick which area to split randomly but make it so larger areas have a bigger chance of getting picked, that way you'd get some size variation but not too much. You could also pick a minimum size below which areas would no longer get split. Also, the more narrow an area is, the more likely you make it to get split in the shorter direction so you don't get super long rooms. In the end, you would pick a certain percentage of your areas to be your rooms.

 

[Ardenian]

Hm, an interesting approach, I will follow it once my current new ( unstable) version keeps failing.
Thanks a lot!

 

[Ardenian]

Update:
Wow, Anitarf, that suggestion is awesome! Took me 15 minutes to write it and it works like a charm ( more or less, I have to adjust/add some lines, so it does not exceed map border and doesn't look so linear)

This thread can be marked solved now.

 

[Anitarf]

Looking at the result, I don't think you're using the kind of algorithm that I had in mind, but if you like what you are getting then that's fine.

This is what my algorithm looks like, taken from a map of mine and slightly cleaned up for readability:

//! zinc

library TerrainGenerator requires CycList
{
    public real TERRAIN_TILE_SIZE = 128.0;
    public real TERRAIN_GRID = 256.0;
    public real TERRAIN_BOUNDS = 15296.0;

    public real FIELD_TERRAIN_TILE = 'Odtr';
    
    // function for converting grid point into map coordinates
    function G2C ( real grid ) -> real
    { return -TERRAIN_BOUNDS + TERRAIN_GRID * grid; }
    
    // the Field struct and the FieldList struct are based on the Node struct
    // this allows us to store Fields in sorted lists
    struct Node
    {
        module CycList;
    }

    struct FieldList extends Node
    {
        static method create() -> thistype
        {
            return allocate().exclude(); // proper initialization of a new CycList node
        }
        
        method debugList()
        {
            Node n = next;
            BJDebugMsg("debugging list " +I2S(this));
            while (n!=this){
                BJDebugMsg( "  node "+I2S(n));
                n=n.next;
            }
        }
    }

    struct Field extends Node
    {
        integer startX, startY;
        integer sizeX, sizeY;
        
        integer size = -1;
        
        FieldList parentList;

        // the size is used to sort fields inside lists so that larger fields are closer tot he start of the list
        // this allows us to make it so larger fields have a larger chance of being picked for division
        method calculateSize()
        {
            size = sizeX*sizeY;
            if (size<0) size = -size;
        }

        // this inserts a field into a list, it inserts it so that the list stays sorted by size
        method listInsert ( FieldList list )
        {
            // lists are sorted based on size
            Node listNode = list.prev;
            parentList = list;

            while (listNode != list && thistype(listNode).size < size) listNode = listNode.prev;
            if (listNode!=this) listNode.next = this.exclude();
        }
        
        static method create (FieldList list, integer x, integer y, integer sx, integer sy)-> thistype
        {
            thistype this;
            
            this = allocate();
            startX = x;
            startY = y;
            sizeX = sx;
            sizeY = sy;
            calculateSize();
            
            // exclude(); //initialization of CycList node not needed because it is done automatically in listInsert
            listInsert( list );
            return this;
        }


        // the following two methods are used to resize a field after it's been divided
        method resizeX ( integer newX )
        {
            sizeX = newX;
            calculateSize();
            listInsert( parentList );
        }
        method resizeY ( integer newY )
        {
            sizeY = newY;
            calculateSize();
            listInsert( parentList );
        }
        
        // the following two methods are used to divide fields
        method divideX ( integer divX, integer wallwidth ) -> thistype
        {
            thistype that;
            if (divX <= 0 || divX+wallwidth >= sizeX) {
                debug BJDebugMsg("Field.divideX error: divide outside of field bounds.");
                return 0;
            }

            that = thistype.create( parentList, startX+divX+wallwidth, startY, sizeX-divX-wallwidth, sizeY);
            resizeX( divX );
            //Debug lightning effects along the divides
            //AddLightningEx( "HWPB", false, G2C(startX+sizeX),G2C(startY),0.0, G2C(startX+sizeX),G2C(startY+sizeY),0.0 );
            //if (divide.width>1) AddLightningEx( "HWSB", false, G2C(startX+sizeX+1),G2C(startY),0.0, G2C(startX+sizeX+1),G2C(startY+sizeY),0.0 );
            return that;
        }

        method divideY ( integer divY, integer wallwidth ) -> thistype
        {
            thistype that;
            if (divY <= 0 || divY+wallwidth >= sizeY) {
                debug BJDebugMsg("Field.divideY error: divide outside of field bounds.");
                return 0;
            }

            that = thistype.create( parentList, startX, startY+divY+wallwidth, sizeX, sizeY-divY-wallwidth);
            resizeY( divY );
            //Debug lightning effects along the divides
            //AddLightningEx( "HWPB", false, G2C(startX),G2C(startY+sizeY),0.0, G2C(startX+sizeX),G2C(startY+sizeY),0.0 );
            //if (divide.width>1) AddLightningEx( "HWSB", false, G2C(startX),G2C(startY+sizeY+1),0.0, G2C(startX+sizeX),G2C(startY+sizeY+1),0.0 );
            return that;
        }


        // this is the main method that sets everything up
        static method initialize()
        {
            // create a list of fields
            FieldList mainList = FieldList.create();
            thistype this;
            integer i;
            // create an initial field that covers the playable area
            this = Field.create( mainList, 0,0,60,60);
            
            // do field division
            for (0<i<120) {
                if (!doDivision.evaluate(mainList, i)) i-=1;
            }

            // once we've cut our starting field up into many smaller fields
            // initialize those fields (do terrain tile modification etc)
            this = mainList.next; 
            while (this!=mainList) {
                initFieldTiles.evaluate();
                this=next;
            }
        }


        // placed below the calling method to prevent zinc optimizer
        // from changing an .evaluate into a normal function call
        static method doDivision( Node mainList, integer i )->boolean
        {
            thistype this;
            DivideType dt;
            integer n;

            // choose a random field to divide, larger fields have a bigger chance
            n = R2I(Pow( GetRandomReal(0.0, SquareRoot(i)), 2)); // 0 <= n <? i
            if (n==i) n=i-1; // safety check, not sure about bounds of GetRandomReal
            this = thistype( mainList.next );
            // loop through the list of fields until we get to our random field
            while (n>0) {
                this = next;
                n -= 1;
            }
            // choose a random width of the dividing wall
            wallwidth = GetRandomInt(1,3);
            // choose the direction of division, larger dimension have a bigger chance
            if (GetRandomReal( 0.0, 1.0+Pow(sizeX/sizeY, 2) ) > 1.0 && sizeX>2+wallwidth) {
                // choose the position of division, center of field has a bigger chance
                n = R2I( (Pow( GetRandomReal(-1.0, 1.0), 3 ) + 1.0) / 2.0 * (sizeX-2-wallwidth) + 1.0 );
                if (n==sizeX-dt.width) n=sizeX-dt.width-1; //safety check, same reason as above
                this.divideX(n,dt);
            } else if (sizeY>2+wallwidth) {
                //same as above, only for y division
                n = R2I( (Pow( GetRandomReal(-1.0, 1.0), 3 ) + 1.0) / 2.0 * (sizeY-2-wallwidth) + 1.0 );
                if (n==sizeY-wallwidth-1) n=sizeY-dt.width-2; //safety check, same reason as above
                this.divideY(n,dt);
            } else {
                // field too small for division, retry
                return false;
            }
            return true;
        }

        method initFieldTiles()
        {
            real x,y, ex,ey;
            real offset = (TERRAIN_GRID-TERRAIN_TILE_SIZE)*0.5;
            y = G2C( startY ) - offset;
            ey = G2C( startY+sizeY ) - offset ;
            while (y<ey) {
                x = G2C( startX ) - offset;
                ex = G2C( startX+sizeX ) - offset;
                while (x<ex) {
                    SetTerrainType( x,y, FIELD_TERRAIN_TILE, -1,1,0 );
                    x=x+TERRAIN_TILE_SIZE;
                }
                y=y+TERRAIN_TILE_SIZE;
            }
        }

        private static method onInit()
        {
            initialize();
        }

    }
}

//! endzinc

Uses CycList.

 

[Ardenian]

Hm, true, but I came to the new idea after reading it.
I fixed the ovlerap over the map border now.
The only problem is to randomize the position now ( as you can see, each room in each 'row' has the same initial X) within the 'room slot'.

I get back tot his later, now I would like to write the script for connecting the rooms, a script that is quite challenging for me. Do you have an advice/basic idea for it ?

Up to now, I choose a random room and run along the axis, searching for the first match with another room ( x or y) and then create connections based in what quadrant ( from the inital randomized room viewn) the new room is located. That will be quite inefficient though, I foresee.