Collision detection 50+ objects?

[lennu]

Ok, I have found some tutorials online for advanced collision detection like this, but not understood them.

Like this one: http://lab.polygonal.de/articles/rec...al-clustering/ But the source is way too complicated for my scripting skills.

Can someone share their knowledge on massive collision detection done without hitTest?

I'm trying to make the enemies collide with each other and not overlap:
http://www.lrstudio.eu/si/ - WASD+mouse are the keys
All tips are more than welcome!

PS! I'm using raycasting for bullets.

[YaiEf]

Well, you don't need to understand much of the link you provided to understand what they write under Con's: "the worst case is when all objects are in contact with each other and the recursion depth is very high - the algorithm cannot isolate groups and is just wasting valuable processing time."
I think that describes what is happening in your case pretty well if the demo is anything to go by

In your case flocking will probably work quite well. Take a look here: http://parentnode.org/flash/influenc...flash/#more-30

It should be able to handle about 50 "boids". I wrote an AS3 version that can do about a 100 and can probably be optimized further: http://enwire.dk/flash/Flocking.html
I'll post the source if you want it ... but there are different pro's and con's of the different methods. My implementation uses influence maps so the map size itself kinda limits the implementation, but should be sufficient in many cases. It's probably not a speed advantage in flash, but it's kinda pretty

[lennu]

Wow, thanks very much for the flocking idea, it seems to be perfect for me.


Have a look here: http://www.lrstudio.eu/si/

I have only 30 objects, but the fps seems to be very unstable, especially when shooting at enemy. Any suggestions how to improve it?

The source on which I built: http://parentnode.org/flash/influenc...flash/#more-30

Here's the flocking code:

class boid extends MovieClip {
	public var xspeed:Number;
	public var yspeed:Number;
	public var xs:Number;
	public var ys:Number;
	private var maxSpeed:Number;
	function boid() {
		xspeed = xspeed == undefined ? Math.random()*maxSpeed-maxSpeed/2 : xspeed;
		yspeed = yspeed == undefined ? Math.random()*maxSpeed-maxSpeed/2 : yspeed;
	}
	function onEnterFrame() {
		var angle = Math.atan2(yspeed, xspeed);
		var speed = Math.sqrt(yspeed*yspeed+xspeed*xspeed);
		xs = xspeed/speed;
		ys = yspeed/speed;
		if (speed>maxSpeed) {
			speed = maxSpeed;
			xspeed = xs*speed;
			yspeed = ys*speed;
		}
		this._x += xspeed;
		this._y += yspeed;
		if (this._x<-333.1) {
			this._x = -333;
		}
		if (this._x>333.1) {
			this._x = 333;
		}
		if (this._y<-244.1) {
			this._y = -244;
		}
		if (this._y>276.1) {
			this._y = 276;
		}
		_rotation = (180/Math.PI)*Math.atan2(yspeed, xspeed)+90;
	}
	public function getDistance(n:boid) {
		return Math.sqrt(Math.pow(this._x-n._x, 2)+Math.pow(this._y-n._y, 2));
	}
	public function getAngle(n:boid) {
		return Math.atan2(this._y-n._y, this._x-n._x);
	}
	public function getDifference(n:boid) {
		var oX = this._x-n._x;
		var oY = this._y-n._y;
		return {distance:Math.sqrt(oX*oX+oY*oY), angle:Math.atan2(oY, oX)};
	}
	public function get nX() {
		return _x;
	}
	public function get nY() {
		return _y;
	}
	public function ajustVector(x:Number, y:Number) {
		xspeed += x;
		yspeed += y;
	}
	public function ajust(angle:Number, power:Number) {
		xspeed += Math.cos(angle)*power;
		yspeed += Math.sin(angle)*power;
	}
	public function addMovement(n:boid, power:Number) {
		xspeed += (xspeed-n.xspeed)*power;
		yspeed += (yspeed-n.yspeed)*power;
	}
}

[Q-Rious]

Wow, thanks very much for the flocking idea, it seems to be perfect for me.


Have a look here: http://www.lrstudio.eu/si/

I have only 30 objects, but the fps seems to be very unstable, especially when shooting at enemy. Any suggestions how to improve it?

The source on which I built: http://parentnode.org/flash/influenc...flash/#more-30

Here's the flocking code:

class boid extends MovieClip {
	public var xspeed:Number;
	public var yspeed:Number;
	public var xs:Number;
	public var ys:Number;
	private var maxSpeed:Number;
	function boid() {
		xspeed = xspeed == undefined ? Math.random()*maxSpeed-maxSpeed/2 : xspeed;
		yspeed = yspeed == undefined ? Math.random()*maxSpeed-maxSpeed/2 : yspeed;
	}
	function onEnterFrame() {
		var angle = Math.atan2(yspeed, xspeed);
		var speed = Math.sqrt(yspeed*yspeed+xspeed*xspeed);
		xs = xspeed/speed;
		ys = yspeed/speed;
		if (speed>maxSpeed) {
			speed = maxSpeed;
			xspeed = xs*speed;
			yspeed = ys*speed;
		}
		this._x += xspeed;
		this._y += yspeed;
		if (this._x<-333.1) {
			this._x = -333;
		}
		if (this._x>333.1) {
			this._x = 333;
		}
		if (this._y<-244.1) {
			this._y = -244;
		}
		if (this._y>276.1) {
			this._y = 276;
		}
		_rotation = (180/Math.PI)*Math.atan2(yspeed, xspeed)+90;
	}
	public function getDistance(n:boid) {
		return Math.sqrt(Math.pow(this._x-n._x, 2)+Math.pow(this._y-n._y, 2));
	}
	public function getAngle(n:boid) {
		return Math.atan2(this._y-n._y, this._x-n._x);
	}
	public function getDifference(n:boid) {
		var oX = this._x-n._x;
		var oY = this._y-n._y;
		return {distance:Math.sqrt(oX*oX+oY*oY), angle:Math.atan2(oY, oX)};
	}
	public function get nX() {
		return _x;
	}
	public function get nY() {
		return _y;
	}
	public function ajustVector(x:Number, y:Number) {
		xspeed += x;
		yspeed += y;
	}
	public function ajust(angle:Number, power:Number) {
		xspeed += Math.cos(angle)*power;
		yspeed += Math.sin(angle)*power;
	}
	public function addMovement(n:boid, power:Number) {
		xspeed += (xspeed-n.xspeed)*power;
		yspeed += (yspeed-n.yspeed)*power;
	}
}

As the amount of calculations pr frame is constant the random lag you experience is pretty strange. It is however pretty easy to fix!

The problem is not actually with the code but with the way flash handles onEnterFrame requests. To be honest I do not exactly know what's going on but flash seems to stumble over its on feet when having a lot of onEnterFrames running side by side.

The simple solution is to rename onEnterFrame to Tick and execute Tick for all Boids in a global onEnterFrame method.

And, ye, I wrote the boids code you use

[Q-Rious]

Ohh and as YaiEf points out, porting the code to as3 would make it a lot faster!

Likewise the code is rather naive so re-factoring it a but could make it a lot faster as well

[webgeek]

It looks like you are going to use flocking in the end but to answer your initial question about high-performance collisiion detection, here are some things of interest. 1000 objects colliding against eachother:
http://lab.polygonal.de/2007/09/09/q...demonstration/

Quadtrees works great and are pretty straightforward to implement. It not as powerful or as capable as a SphereTree though - so if you want the ultimate in spacial partitioning you can read these to learn more:
http://isg.cs.tcd.ie/spheretree/
http://csdl2.computer.org/persagen/D...CONIEL.2005.29
http://portal.acm.org/citation.cfm?id=545267
http://mustapha.bismi.free.fr/articles/obb.pdf (in French? - good pictures though)

We ended up building a QuadTree (for 2d), then OctTree (for 3d) and finally settling on a SphereTree (also 3d) for our MMO engine. In the end, it supported the fastest and most CPU-friendly "near-neighbor" lookups over all the other approaches. We were able to do "near neighbor" searches of 10,000 entries in under a millisecond on my laptop (running Java 1.6). That was good enough for me

The code we used was based on an article by one of the Verant engineers (makers of EverQuest) in one of the Game Gems books. I can look up which bookl and chapter title if you are curious. We took his C++ code and ported it/tuned it for Java. Works perfectly and is incredibly fast - it's also very complicated. I'm really glad he wrote it, because it would have been agony to write it ourselves.

[YaiEf]

Flocking and spatial subdivision are not mutually exclusive, so using something like what webgeek points to with flocking is possible.

Especially if you take out the cohesive behavior of flocking and go for just alignment and separation (avoidance), since cohesion tends to be the one with the longest sensor-range thus setting a lower limit on the grid size with resulting poor performance in crowded situations.

[lennu]

I tried the quadtree before boids, but I never got it work the way I wanted. I think boids are perfect for me, but I need some help improving the code.

Can anyone point me out what is so expensive in that code that when I go over 20 boids the lagg starts?

[JerryScript]

Having 20 separate onEnterFrames with the amount of code you are using may be your issue. You should instead use a single onEnterFrame or timer event. Place your objects in an array, and pass it to the class. You should also perform some preliminary checks that will isolate the objects that need to be checked deeper, and eliminate those that don't.