next »

[DDRtist]

Hello,
I'm currently working on a 2d sprite based side-scroller. I'm using Flash and Actionscript 3. This is my first game built from scratch (Only used level editors and things like that in the past) and I've been really unsure about how to go about collision.

I've looked into it some and learned about hitTestObject and hitTestPoint, but both seem kind of awkward to me. Basically, I don't really like programming that much (more of a means to an end for me) so sitting down to build a really math heavy collision engine doesn't sound too fun to me, so I'm wondering if anyone here has any thoughts on what the best way of getting pretty accurate and non-intensive collision in AS3.

[kyn]

I don't really know of AS3, but in AS2 it was something like A.hitTest(B); being A and B the objects intersected, it would return true if they intersected and false if not. Hopefully it's the same thing in AS3.

And I also remembered that in AS2 the system was flawed, see pic below:

In this case the objects A and B are obviously not intersecting themselves but the hitTest function would return true, indicating they were intersecting.

Hopefully in AS3 they fixed this problem by now, but I really don't know, it's just wishful thinking at this point.

[DDRtist]

Well, in AS3 there are two built in functions. hitTestObject and hitTestPoint.

Basically, hitTestObject tests if the bounding boxes of two objects intersect while hitTestPoint tests if a specified point on an object intersects with something else. I've heard that a lot of people just make several points for it to test to get a reasonable approximation of the an objects shape. If that's really the best way to do it, I will, but it just seems kind of weird and apt to fail sometimes on more complex shapes unless you made a large number of points.

[kyn]

Yeah, that doesn't really look like the safest way to do it but nonetheless the fastest and cheapest way.

Sadly, there's not really much I can help you with except for this thread bump

[BorisTheBrave]

If you are trying to avoid programming, then yes, these two hit test functions are your best bet, even with the caveats given above. The bounding box thing works great for certain games, depending on what style you are going for. hitTestPoint has it's uses too. With enough points (and careful coding) you can have sophisticated collision detection, but I don't think that's what you want. It's only likely use for you is for bullets and particle effects.

kYn's right about the limitations of bounding boxes, but it's still misleading. For a start, that behaviour was by design. But anyway, you get to design the level as well as code it, so you would just split shape B into two parts, at which point it will work perfectly. Think of levels in the early Mario games - except for a few hacks, they are entirely done with bounding boxes.

For completion's sake, I'll discuss other possibilities, but honestly I cannot recommend anything which fits what you are looking for better than what you've got.

Pixel perfect collision are now possible in Flash. A quick google suggested http://troygilbert.com/2007/06/25/pixel-perfect-collision-detection-in-actionscript3/ , which gives you some code you can adapt. Collisions this way are SLOW, but for some games it is vital.

Or, you could have a look at using a physics engine, and stripping out the physics part to get at the meat of the collision detection. This would require a substantial knowledge investment, and would probably require you to "describe" the shape of your sprites in terms the engine can understand, but will pay dividends in extremely accurate detection, and likely faster than the other methods. Plus, you get physics for free, obviously. (Full disclosure: I have vested interested in Box2dAS3).

It's possible that there are game engines out there more suited to what you want to do. A half way house between your old level designing, and full on programming in AS3. I don't have any to recommend to you, though, sorry. Every time you search for one, you get inundated with "tutorials".

[isaac]

Yeh, Box2DFlash is great, but it does take a significant investment to really grok it enough to be properly usable. It's also probably overkill to use it only for it's hit detection.

Since you're not that into programming I would recommend just using Flash's built in collision detection. It's not an idea solution, but for anything fairly simple it'll perform just fine. In Postal Panic, my own 2D sprite-based side scroller, I just used the hitTestPoint. It's a bit slow but functions just fine.

[Problem Machine]

Axis-aligned bounding box(AABB) tests like hitTest uses are actually surprisingly useful; however, the method of having it tied directly to the sprite's area reduces its usefulness substantially. It's not too hard to write your own AABB tests to use instead, and those would let you define the areas to test independently of the dimensions of the sprite.
To do an AABB test, think of each rectangle as a set of four numbers, the left, right, top, and bottom. If you have two rectangles they overlap on the y axis if top1 is above top2 and bottom1 is below top2, OR if, conversely, bottom1 is below bottom2 and top1 is above bottom2. Do the same test on the left and right numbers (ie right1 > right2 && left2 < right2 ). If both of these tests return true, the bounding boxes overlap. Here's what it looks like in code:

Code:

if (( rect1.top > rect2.top && rect1.bottom < rect2.top) ||
		(rect1.bottom < rect2.bottom && rect1.top > rect2.bottom))
	if ((rect1.right > rect2.right && rect1.left < rect2.right) ||
			(rect1.left < rect2.left && rect1.right > rect2.left))
		return true;

return false;

Alternately, circular collision detection is equally easy and some people prefer the results. If you know how the Pythagorean theorum works then circular collision is easy as pie. You just use it to derive the distance between the objects and compare it to the sum of the radii (Though, for efficiency reasons, it's usually better to compare against the distance squared).

Code:

var _DistanceSquared:Number = ((obj1.x - obj2.x) * (obj1.x - obj2.x)) + ((obj1.y - obj2.y) * (obj1.y - obj2.y));
if (_DistanceSquared <= (obj1.radius + obj2.radius) * (obj1.radius * obj2.radius))
	return true;

I hope that helps

[DDRtist]

Thanks all, that gives me some more things to think about. When I started using AS3 I kind just assumed so many people use collision in their games that it must not be too hard, but I guess that most people probably just use the built in.

[Titch]

As Kobel said, it's not that hard to write your own collision detection stuff. If you do it right it will be substantially more efficient that hitTest; which can kill your game speedwise in AS2 (I'm not sure about AS3, I've got my AS3 code open on the monitor next to me, but I'm not doing collision stuff yet). It's a really good idea to work out some broad/narrow phase methods to reduce the number of accurate tests you have to do each frame, which means less resources are gobbled up by performing collision detection on objects that are miles away from each other.

A simple, but not always effective, way to do this would be to divide your screen area into four sections. On the broad pass you check which of your four quadrants have moving objects in, then only do collision checks against static objects in the same quadrant. For doing pixel perfect collision, do a simple AABB or Circle based check first and if that turns up positive then do a per-pixel check.

The last game I did was tile based, which allows for all sorts of nifty tricks collision wise; since most objects you didn't need to know the position per pixel and just what there x and y tile was; which means you can skip out on cycling through an object array every frame and just test against tile areas; and even with non-static objects you can compare the current tile, rather than true x/y position.

There are a few solutions on how to handle hitTest effectively. Generaly the most effective one depends on what kind of game you are building. The very best tutorials general/physics flash collision stuff I've seen was on the N tutorials page. Although it's not for the faint of heart .

[Loren Schmidt]

Oh, I read the beginning of the N tutorials, but after a few pages I ran away and hid.

I'm not really a coder either, but doing simple bounding box checks isn't too complicated. Kobel's approach is good.

For me, the complicated part wasn't checking for collisions. It was figuring out what to do after that. If you're using simple rectangles, you can measure the offset needed to push the player to each side of the box, then just pick the shortest one.

Code:

are boxes overlapping?
    right - get offset
    top- get offset
    left- get offset
    underside- get offset
    
    compare offsets, pick the smallest one.

[Problem Machine]

That's a good approach if everything is moving slowly enough that there's little risk of objects passing through each other. A slightly more complex but stable solution would be to track the object's previous position and use that to determine which left/right and up/down side the object belongs on.

The easiest way to do it with circles is to get radius1 + radius2 - distance and move both objects that far along their respective vertices of movement... unfortunately, I think to do that right you really do need get into trigonometry which I was hoping to avoid talking about  :D

[BorisTheBrave]

Writing a "proper" collision detection system is quite complicated, as people are pointing out. You need to handle:

• Broadphase calculations - i.e. testing collision only between pairs likely to have a collision. Tiling engines come under this catagory
• Tunnelling issues - objects which are travelling too fast to catch between frames
• Collision resolution - what side did you hit an object on, and how to react to it. What do you do if an object is pressed on multiple sides, etc?

However, these are all optional tasks, and can be dealt with later. For small levels, without complex interactions, you do not need worry, short of adding the basics needed. Specifically, your "broadphase" is just testing every relevant pair of objects. You can avoid tunnelling by enforcing a max speed, and min size for objects. Collisions just do damage, or push the object to a safe distance.

So I'd second sparky's suggestion. Given the offset and a side, when the player hits a shape, just move him in that direction with the amount of the offset.
If, like Kobel, you want to write your own AABB test, which is probably nearly as fast, you can do the whole thing in one test:

Code:

Get left offset
Get right offset
Get top offset
Get bottom offset
If any of these are greater than 0:
    Return no collision
Pick the largest offset (i.e. smallest absolute offset)
Return that offset, with the corresponding side

I don't like the bounding circles approach. You end up with everything in your game being circular, as it is a lot of effort to mix other forms of collision in with circles, compared with the ease of coding them in the first place.
But you can do it without any trigonometry, like AABBs:

Code:

// Moves circle 2 away from circle 1
var dx = circle2X - circle1X;
var dy = circle2Y - circle1Y;
var d2 = dx*dx + dy*dy
var r = circle1radius + circle2radius
if(d2 > r * r)
    return;
var d = Math.sqrt(d2);
var offset = d - r;
dx *= offset / d;
dy *= offset / d;
circle2X -= dx;
circle2Y -= dy;

[JLJac]

You could make a radius based collision detection, wich is a really sloppy solution but really easy to make. Just check the distance between the objects in every frame by repeating through a list, and if the distance is less than the sum of the objects' radius you have a collision. Trouble is:

Only circle shaped collision boxes
Only relatively slow objects

But it's really easy and controllable, so I would recommend it if you're new to collision detection. Good luck!

[Titch]

If you mean the standard flash distance check, that's probably not a great idea as it has to square root in order to get the distance in pixels, which is something you should avoid doing as often as possible. In a way it's less efficient that just performing hit tests every frame.

You could write your own distance calculation that DOESN'T sqrt the return value and work out the relative square root for the distances you want on a bit of paper. Which could be useful if you where creating a game where objects needed to know their relative distance from each other a lot (for AI handling for example). It won't stop the amount of on paper maths you have to do to avoid doing lots of sqrt calculations being a pain though. The third option is you could create a lookup table/array for the square root values of each number, although it would probably end up so large that it wouldn't save many resources in the long term.

[Loren Schmidt]

What do you do to ensure that you collide with the correct side when moving along a wall or floor? I always get errors.



In the past I've worked around this (in tile based games) by skipping the checks for sides facing another obstructed tile. So if the left side of a tile faces another filled cell, you can't collide with its left side. It feels like a hack, though.

[Problem Machine]

I don't see why that would be a hack unless it's done on a case by case basis, which would be weird because the math isn't that hard. I'd say stick with that if it works for you. Does it?

[BorisTheBrave]

It's only a hack in the sense it requires extra work for the level designers (assuming your game isn't strictly tile based).

But I'm not really sure how to avoid it otherwise, short of overly elaborate techniques. I've seen people on the Box2D forums recommend having the player as an octagon (i.e. smooth down those sharp corners slightly), but that is more a physics solution, and doesn't work for simpler engines.

You could just assume that any collision that occurs sufficiently near a top corner is in fact a collision on the top. That's hacky too, but in a nice way: it also means your player cannot get blocked by walking over a 1 inch high obstacle. I've done this once, and you can get a nice feel for it if you try, but that was for a top down game, not a platformer.

[JLJac]

It's only a hack in the sense it requires extra work for the level designers (assuming your game isn't strictly tile based).

Nah, don't see wy it's a hack. A game that is tile based is tile based, and then you can count on that you can check all of the neighbours of a tile to see if they are obstacles. That requires no extra work for the level designers, but maybe for the comupter. However, for some games tile-based levels is just not working, at least unless you have a very fine grid. I'd use a straight line, see where it crosses the sides of the box, and calculate which point of collision is the closest to the original position. But don't listen to me, my games aren't box-based at all

[grizzly]

I've been using as3 for a while and most of what I learn code wise is gleaned from forum threads such as this. perhaps my google searching is not what it used to be, but i had a very hard time finding good info on AABB/AABB collisions/intersection/etc.
most of the time people say 'it's really easy' but nothing else. resources like the N tutorials are great if you already have a grasp of what's going on, otherwise it's mind boggling.

actually, the best info by a mile came from this very thread (cheers to Kobel, Sparky and Boris in particular). i would have loved a post with some implemented as3 code, and since this is the first google result for 'aabb collision as3' i thought i'd give back to the community i have taken so very much from with my own implementation.
this code is dealing with a number of AABBs on the stage that bump into each other. note that it's probably not as efficient as it could be.

Code:

enCol(class1,class2);
//^ my entity info is stored in external classes

private function enCol(ob1,ob2){
	var a1=ob1;
	var a2=ob2;
	var a=0;var b=0;var c=0;var d=0;

	var rect1:Rectangle = new Rectangle(a1.wx,a1.wy,35,35);
	var rect2:Rectangle = new Rectangle(a2.wx,a2.wy,35,35);
	
	//^ .wx and .wy are just the world positions of the entity classes - the x and y positions for flash objects will work too i imagine.
	//35 is the size for all the entities i'm working with

	if(rect1.left<rect2.right) a=rect1.left-rect2.right;
	if(rect1.right>rect2.left) b=rect2.left-rect1.right;
	if(rect1.top<rect2.bottom) c=rect1.top-rect2.bottom;
	if(rect1.bottom>rect2.top) d=rect2.top-rect1.bottom;

	if(a<0&&b<0&&c<0&&d<0){

		var k = new Array();
		k = [a, b, c, d];
		var t=maxValue(k);

		//^ here we are placing the vars into an array and sending the array to the maxValue function below
		//which will return the largest value. i don't know if this is the most efficient means
		//of finding the largest value from a range of numbers in as3 
		//the maxValue function is from http://www.kirupa.com/developer/actionscript/array_max_min.htm
		
		if(a==t){
			a1.wx-=a/2;
			a2.wx+=a/2;
			//^ i altered each position by half the intersection value as it provides
			//a smoother collision... altering one of the positions by the entire
			//intersection value works too of course - the jumpy effect i experienced
			//may have something to do with my other code. of course if one of the tested objects is stationary, 
			//you'll only need to alter one of the positions anyway
		}else if(b==t){
			a1.wx+=b/2;
			a2.wx-=b/2;
		}else if(c==t){
			a1.wy-=c/2;
			a2.wy+=c/2;
		}else if(d==t){
			a1.wy+=d/2;
			a2.wy-=d/2;
		}
	}
}
		
private function maxValue(array:Array){
	var mxm = array[0];
	for (var i=0; i<array.length; i++) {
		if(array[i]>mxm) mxm = array[i];
	}
	return mxm;
}

hope it helps
edit: manbaby indeed. you guys suck.

[Eclipse]

edit: manbaby indeed. you guys suck.

it's only for the first post, and maybe you should also introduce yourself in "the obligatory introduce yourself thread".