Suggestion: Pixel Perfect >> AreThingsOverlapping()

Snake · Wed 12/04/2006 05:47:05

Hello, Everybody,
I was just wondering if anyone else would find making the command AreThingsOverlapping(); "pixel perfect" worth while (if possible yet), or at least having an option for it:
AreThingsOverlapping(thing1, thing2, pixel perfect 0=no 1=yes);

Personally I think it could come in very handy in various instances.

If nobody agrees, then, well, shoot me down in flames like the idiot boy from retardville that I am :'(

--Snake

Gilbert · Wed 12/04/2006 06:20:08

I agree that it can be useful, but I think there're certain issues that might be examined before it can be done, one of them, for obvious reasons, is speed, as it might be quite demanding; second is, when your game's at 32-bit and the sprites have alpha channel, there must be some criteria on judging whether a pixel in it is considered transparent (I'm not quite sure, I think currently it probably only consider 100% opacity pixels as opaque, or split it with 50% transparency, when using pixel-perfect click detection).

But bear in mind that, actually most games in the 2D eras (e.g. console action games) checked collisions using blocks only, and since AGS' basic aim is still adventure games (compared to platform/action/shooting/etc. games which require collision detections a lot), I doubt if it's worth the hassle (in case it's hard to do) to implement such features.

Snake · Wed 12/04/2006 13:38:32

Good points, Gilbert.
In my case it isn't nessesary, it would be nice, but I've got ways around it. I wouldn't bother either if it was going to be a pain in the ass to implement, concerning the alpha channels. It would be a good option if you weren't using such "high-tech" things, if it still didn't slow the game down any.

Gotta go, half hour late for work

--Snake

Pumaman · Wed 12/04/2006 18:14:45

It would probably be quite slow, since every pixel of each bitmap would need to be checked against the corresponding pixel in the other one, so for large sprites especially it would be rather on the slow side. Still, if you didn't use it in repeatedly_execute it would probably be ok.

Snake · Thu 13/04/2006 02:16:47

I wouldn't bother then, Chris, nobody likes slowdown in a game

Just curious though, would it make a difference if it were in 320x200 rather than 640x400 (screw 800x600 anyway

)? Usually 320x200 games run beautiful anyway no matter what you add in.

--Snake

Gilbert · Thu 13/04/2006 02:21:08

I think hi-res games are probably similar to lo-res ones, as AGS uses lo-res for game resolutions internally, unless the checking function is to be designed for checking the pixels in hi-res.

SSH · Thu 13/04/2006 10:34:43

I'd have thought that one optimisation would be that AGS could do the rectangle check first then only do pixel-perfect if the rectangle check sees a hit...

GarageGothic · Thu 13/04/2006 12:36:03

Ok, I did this quick script as an attempt to check collision using pixel perfect click detection. It seems to work ok, but slow when using big objects:

Code: ags


 // script for Room: Repeatedly execute

  if (oWhite.IsCollidingWithObject(oBlue)) {
    int detectx = oWhite.X;
    int detecty;
    bool collide;
    int whitewidth = Game.SpriteWidth[oWhite.Graphic];
    int whiteheight = Game.SpriteHeight[oWhite.Graphic];
		while (detectx <= oWhite.X + whitewidth) {		  
		  detecty = oWhite.Y - whiteheight;
			while (detecty <= oWhite.Y) {
				if (Object.GetAtScreenXY(detectx, detecty) == oBlue) {
					oBlue.Visible = false;
					Object* detectobject = Object.GetAtScreenXY(detectx, detecty);
					oBlue.Visible = true;
					if (detectobject == oWhite) {
                                                detectx = 999999; //to end while loop
                                                detecty = 999999; //to end while loop
						collide = true; 		  
						}
					   }
				detecty++;
				}
			detectx++;  
			}
		if (collide == true) collideoverlay = Overlay.CreateTextual(100, 100, 100, 1, 5, "Collided");
		else collideoverlay = Overlay.CreateTextual(100, 100, 100, 1, 7, "DIDN'T Collide");
	}
}

Download for tiny demo added: http://s49.yousendit.com/d.aspx?id=15EVX432X7M9B12KWJWSFQ101I
(it's the blue and the white shapes that are colliding. Roger is just standing around like a dumbass)

Edit: Although I haven't tried, this shouldn't suffer much of a slow down in hi-res, since it only checks for collision within a 320x200 grid anyway as Gilbot said. You can also speed it up even further by lowering the collision resolution to 160x100 (by adding 2 instead of 1 to detectx and detecty). Further optimization could involve starting the collision check from whatever side of the sprite the other sprite is located.

Edit 2: Updated the code with some of Radiant's optimization suggestions.

SSH · Thu 13/04/2006 13:34:54

Awesome! Now, modulify it!

Radiant · Thu 13/04/2006 13:59:39

It it's slow, you can speed it up by
(1) if (detectobject == oWhite) {collide = true; detectx = 9999; detecty = 9999; }
(2) creating a local value to store Game.SpriteWidth[oWhite.Graphic] and Game.SpriteHeight[oWhite.Graphic]
(3) simply using "if (Object.GetAtScreenXY(detectx, detecty) == oBlue)" rather than creating the unneeded temp variable detectobject

GarageGothic · Thu 13/04/2006 14:24:16

Quote from: Radiant on Thu 13/04/2006 13:59:39(1) if (detectobject == oWhite) {collide = true; detectx = 9999; detecty = 9999; }

Not sure where you mean to put this?

Quote(2) creating a local value to store Game.SpriteWidth[oWhite.Graphic] and Game.SpriteHeight[oWhite.Graphic]

Implemented this. Not sure if the SpriteHeight and SpriteWidth commands are actually slow.

Radiant · Thu 13/04/2006 18:20:22

Quote from: GarageGothic on Thu 13/04/2006 14:24:16
Quote from: Radiant on Thu 13/04/2006 13:59:39(1) if (detectobject == oWhite) {collide = true; detectx = 9999; detecty = 9999; }
Not sure where you mean to put this?

Put this in place of the current "if (detectobject == White) { collide = true }". Rather than checking for (collide == false) during every single iteration of the while loop, it would be easier to simply set detectx and detecty to ludicrous values when you find a collision, as this will automatically ensure you'll break out of the loop.

Quote
Quote(2) creating a local value to store Game.SpriteWidth[oWhite.Graphic] and Game.SpriteHeight[oWhite.Graphic]
Implemented this. Not sure if the SpriteHeight and SpriteWidth commands are actually slow.

Well, it's a triple pointer derefence inside an inner loop. It might not make a huge difference but there's no real reason for doing it the slow way.

GarageGothic · Thu 13/04/2006 18:31:42

Quote from: Radiant on Thu 13/04/2006 18:20:22Put this in place of the current "if (detectobject == White) { collide = true }". Rather than checking for (collide == false) during every single iteration of the while loop, it would be easier to simply set detectx and detecty to ludicrous values when you find a collision, as this will automatically ensure you'll break out of the loop.

Ah yes, now I see your point.

Edit: Now implemented

Kweepa · Fri 14/04/2006 03:15:58

Another optimisation is to get the intersection of the two boxes and only loop over those pixels.

Code: ags



int min(int a, int b)
{
Ã,Â  if (a < b) return a;
Ã,Â  return b;
}

int max(int a, int b)
{
Ã,Â  if (a > b) return a;
Ã,Â  return b;
}

...

int wx1 = oWhite.X;
int wx2 = wx1 + Game.SpriteWidth[oWhite.Graphic];

int bx1 = oBlue.X;
int bx2 = bx2 + Game.SpriteWidth[oBlue.Graphic];

int minx = max(wx1, bx1);
int maxx = min(wx2, bx2);

int wy2 = oWhite.Y;
int wy1 = wy2 - Game.SpriteHeight[oWhite.Graphic];

int by2 = oBlue.Y;
int by1 = by2 - Game.SpriteHeight[oBlue.Graphic];

int miny = max(wy1, by1);
int maxy = min(wy2, by2);

int y = miny;
while (y < maxy)
{
Ã,Â  int x = minx;
Ã,Â  while (x < maxx)
Ã,Â  {
Ã,Â  Ã,Â  // do pixel check here
Ã,Â  Ã,Â  x++;
Ã,Â  }
Ã,Â  y++;
}

scotch · Fri 14/04/2006 05:02:50

With that box optimisation it's actually quite fast in C, most of the time the collision will be rejected even before any pixels are visited. And alpha against alpha channel testing with that 50% threshold is pretty fast, just check for overlapping 8th bits like (pixelA & 0x00000080) & (pixelB & 0x00000080).
I've used this in the "repeatedly execute" of a game, testing loads of sprites against each other and it works great. (I was even adding the positions of the overlapping pixels together to get a collision angle at the same time). So I'd say it's worth adding, perhaps, for minigames or something.

Quintaros · Fri 14/04/2006 17:04:21

If`you're just looking for a show of hands, I would use it.

Snake · Wed 19/04/2006 02:05:47

Quote from: Quintaros on Fri 14/04/2006 17:04:21
If`you're just looking for a show of hands, I would use it.

I know this is somewhat of a waist of a post, but so would I 8)

--Snake

PS
I greatly appreciate the code, I'll give it a try.

strazer · Wed 19/04/2006 14:07:47

In the meantime, GarageGothic, are you working on turning this into a module?

GarageGothic · Wed 19/04/2006 14:36:47

I could, but it would take ages for me to make sure it complied to the module formatting conventions. Also, there's more to it than just putting the code into a module. Ideally I would like to write a single IsCollidingPixelPerfect that could be used for characters/characters, objects/objects and characters/objects. But I don't think there's any way to make a common function that accepts pointers of either type and then acts accordingly depending on their type, is there?

In other words, if anyone else feels like making a module, please do so. I'm sure your code will be much more user friendly than mine.

SSH · Thu 27/04/2006 19:22:44

Just so no-one has to duplicate things, I'll let everyone know that I've started work on modulifyicating this

Edit by strazer:

PPColliding module released: http://www.adventuregamestudio.co.uk/yabb/index.php?topic=26307