detect if two grids overlap - GameCreators Forum

Author

Message

Phaelax

DBPro Master

23

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 21st Aug 2011 23:39

Link

I'm having a brain fart as this problem feels like it should be super simple.

Say I have two boxes, A and B. 'A' can be 1x1 or up to 4x4, same thing goes for box 'B'.

Because one box could be completely enclosed by the other but A isn't always bigger than B, or vice-versa, so I'm having trouble making a simple overlap function. Both boxes lie inside a larger grid, 12x6. Think inventory object placement.

I tried this thinking it work, but after thinking it through it won't.

+ Code Snippet

if ax1 >= bx1 and ax2 <= bx2 and ay1 >= by1 and ay2 <= by2

Hopefully someone knows what I'm talking about.

Back to top

Profile PM Email Website

Phaelax

DBPro Master

23

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 21st Aug 2011 23:52

Link

I think I worked something out, however using a nested FOR loop for this seems inefficient to me.

If it matters to anyone:

function isItemPlacementOK(gridX, gridY, itemId)
	gx = gridX + items(itemID).invWidth - 1
	gy = gridY + items(itemID).invHeight - 1
	
	rem make sure item fits on the inventory grid
	if gx >= 12 or gy >= 6 then exitfunction 0
	
	itemCount = array count(invItems())
	for i = 0 to itemCount
		ax = invItems(i).gridX
		ay = invItems(i).gridY
		bx = ax + items(invItems(i).itemID).invWidth-1
		by = ay + items(invItems(i).itemID).invHeight-1
		
		rem detects grid location directly under mouse pointer
		if gridX >= ax and gridX <= bx and gridY >= ay and gridY <= by
			rem if trying to place an item of the same type on each other
			if invItems(i).itemID = itemID
				rem if item is stackable
				if items(itemId).isStackable then exitfunction 1
				exitfunction 0
			else
				exitfunction 0
			endif
		endif
		
		rem This makes sure the selected item doesn't overlap any existing items
		rem The above IF statement is insufficient because some points of the selected
		rem object may lie in unoccupied cells but still have some parts overlapping
		rem occupied ones.
		for x = ax to bx
			for y = ay to by
				if x >= gridX and x <= gx and y >= gridY and y <= gy then exitfunction 0
			next y
		next x

next i
endfunction 1

+ Code Snippet

function isItemPlacementOK(gridX, gridY, itemId)
	gx = gridX + items(itemID).invWidth - 1
	gy = gridY + items(itemID).invHeight - 1
	
	rem make sure item fits on the inventory grid
	if gx >= 12 or gy >= 6 then exitfunction 0
	
	itemCount = array count(invItems())
	for i = 0 to itemCount
		ax = invItems(i).gridX
		ay = invItems(i).gridY
		bx = ax + items(invItems(i).itemID).invWidth-1
		by = ay + items(invItems(i).itemID).invHeight-1
		
		rem detects grid location directly under mouse pointer
		if gridX >= ax and gridX <= bx and gridY >= ay and gridY <= by
			rem if trying to place an item of the same type on each other
			if invItems(i).itemID = itemID
				rem if item is stackable
				if items(itemId).isStackable then exitfunction 1
				exitfunction 0
			else
				exitfunction 0
			endif
		endif
		
		rem This makes sure the selected item doesn't overlap any existing items
		rem The above IF statement is insufficient because some points of the selected
		rem object may lie in unoccupied cells but still have some parts overlapping
		rem occupied ones.
		for x = ax to bx
			for y = ay to by
				if x >= gridX and x <= gx and y >= gridY and y <= gy then exitfunction 0
			next y
		next x

	next i
endfunction 1

Back to top

Profile PM Email Website

WLGfx

18

Years of Service

User Offline

Joined: 1st Nov 2007

Location: NW United Kingdom

Posted: 22nd Aug 2011 00:27

Link

Quote: "if x >= gridX and x <= gx and y >= gridY and y <= gy then exitfunction 0"

To speed it up a tad you could nest the IF's.

Warning! May contain Nuts!

Back to top

Profile PM Email Website

BMacZero

20

Years of Service

User Offline

Joined: 30th Dec 2005

Location: E:/ NA / USA

Posted: 22nd Aug 2011 01:07 Edited at: 22nd Aug 2011 01:09

Link

It seems to me that if two rectangles overlap, at least one of their edges must fall between the two corresponding edges on the other rectangle.

I played with this idea some, and I think it is true in one dimension that if you find the leftmost edge of the two right edges of the two rectangles and the rightmost edge of the two left edges of the rectangles, you need only see if the the left one is less than the right one (less than or equal to, in this case, because the rectangles include the edges). If it is, they overlap horizontally.

In two dimensions:

+ Code Snippet

nleft = max(gridX, ax);
nright = min(gx, bx);

ntop = max(gridY, ay);
nbottom = min(gy, by);

if (nleft <= nright) and (ntop <= nbottom) then exitfunction 0

That seems really crazy but I tested every case in one dimension and it worked for all of them.

EDIT: Fixed me being dumb with min and max

http://brianmacintosh.com

Back to top

Profile PM Email Website

Phaelax

DBPro Master

23

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 22nd Aug 2011 05:18

Link

I guess all I had to do was sort the two different boxes. It does look odd but it seems to work. Kudos to you BMac!

Back to top

Profile PM Email Website

Neuro Fuzzy

19

Years of Service

User Offline

Joined: 11th Jun 2007

Location:

Posted: 22nd Aug 2011 05:41 Edited at: 22nd Aug 2011 06:02

Link

hahah dang... I just came across a problem where I need to figure out if one rotated rectangle intersects or is a part of another rotated rectangle, and I hoped this was about that.

WAIT just thought of a solution

[edit]
for anyone who cares, you have two rectangles A and B (with vertices A1, A2 ... A4, B1 etc)
using the SameSide function described here (http://www.blackpawn.com/texts/pointinpoly/default.html), we can make a function:

+ Code Snippet

pointInConvexQuadrilateral(p, a,b,c,d)
    if SameSide(p,a, b,c) and SameSide(p,b, c,d) and SameSide(p,c, d,a) and SameSide(p,d, a,b)
        return true;
    else
        return false;

(since rectangles are convex quadrilaterals, the verbose function name might not be needed. it's just there for clarity)

Since a rectangle is a space bounded by linear functions, for a rectangle A to have space that also belongs to a rectangle B, a vertex of A is in B, and/or a vertex of B is in A. So...
(with the pointInConvexQuadrilateral function renamed to the more concise pointInQuad(p, a,b,c,d))

+ Code Snippet

bool RectangleSpaceShared(Rectangle A, Rectangle B)
{
    if(
pointInQuad(A1, B1,B2,B3,B4)||
pointInQuad(A2, B1,B2,B3,B4)||
pointInQuad(A3, B1,B2,B3,B4)||
pointInQuad(A4, B1,B2,B3,B4)||
pointInQuad(B1, A1,A2,A3,A4)||
pointInQuad(B2, A1,A2,A3,A4)||
pointInQuad(B3, A1,A2,A3,A4)||
pointInQuad(B4, A1,A2,A3,A4) )
        return true;
    else
        return false;
}

not the most efficient way to do it, it's probably not the best algorithm, and the code itself could be sped up at the cost of readability, but it's good enough for my purposes. (my purposes are camera-culling which is done once per frame, on 30-40 rectangles, so that's not bad at all.)

Why does blue text appear every time you are near?

Back to top

Profile PM Email

Sorry your browser is not supported!

DarkBASIC Professional Discussion / detect if two grids overlap