Collision between objects

[sharkadder]

Hi there,

 

I have recently started to create some HTML5 games on a canvas in a web browser using JavaScript as the engine.  What i would like to know is, if i create an object and want multiple instances of the same object to exist, what is the best way of detecting collision between them?

 

When detecting collision between two objects i currently use this code:

 

Collision detection function:

function enemy(){    this.x = 300    this.y = 300    this.width = 50    this.height = 50    this.speed = 200    this.color = '#c00'}function hitTestPoint(x1, y1, w1, h1, x2, y2, w2, h2){    //x1, y1 = x and y coordinates of object 1    //w1, h1 = width and height of object 1    //x2, y2 = x and y coordinates of object 2 (usually midpt)    if ((x1 < x2 + w2) && (y1 < y2 + h2) && (x1 + w1 > x2) && (y1 + h1 > y2))    {            alert('collision');        return true;    }    else        return false;}

I then call the code during the render of the program which gets called automatically every 1000 milliseconds

    hitTestPoint(mySprite.x, mySprite.y, mySprite.width, mySprite.height, enemy.x, enemy.y, enemy.width, enemy.height);

As you can see, i check for collision between the player sprite i.e. mySprite and then enemy.  What if i have multiple enemies?  How do i set collision up so that i can deect collions between one object type even if i do collision?  At the moment i am just alerting the word collision when a collision happens when i tested it out.

 

I have realised that i could loop through an array of enemy objects which are drawn on the screen but that would mean constantly searching through them at runtime for collision events, is this the best way to do it do you know?

 

Many thanks

[Gio]

What you're doing is perfectly reasonable with a small number of objects, but when you have more objects doing all those tests isn't really an option.

 

One way to deal with it, is to store references to your objects in a quadtree.

 

Depending on the number, size and distribution of your objects, it may or may not be a better idea to have a broadphase collision pass. To put it simply, maintain two sorted lists of your objects (one sorted according their X coordinate, the other sorted by Y), which will then help you select potential colliders without going through the whole list of objects. However, while this approach is simple in principle, its implementation can be really tricky, because updating the lists is slow, and you have to use a few tricks to do that efficiently. Still, that's what many physics engines do.

[sharkadder]

Hi,

 

So if i am only having a few objects, it is ok to just loop through a list of items and then if i choose to have any more than say 10 enemies it would be best for me to put the co-ordinates into two lists; one for x and one for y?

 

I can see how the list idea can be benefitial as you could search for objects which are close to you can then just pick the one which is closest to avoid issues of searching all objects.  I assume that you prefer to use physics engines than write your own collision code between a player and multiple instances of the same object?

 

Glad that i seem to be on the right sort of lines to look at.

[Qqwy]

Since most of the time, you dont need to track collisions between ALL objects (depending on your game, collision between two different enemies might be unimportant, for example), it is the easiest to put all objects of one kind in one array.

Then simply check for each of these objects if they collide with another object (for instance the player, or each of the objects in a second array).

 

By using multiple lists the impact on the performance can be kept low. If you check collision between ALL objects every time, the execution time will effectively DOUBLE for each new object you add to the game.

[Gio]

To be honest, I'd go with the quadtree first, as it's a bit easier to implement. The sorted lists may be more efficient, but like I said, it's also quite tricky to optimize them. If you want to go that way though, google "sweep and prune" for some optimization ideas.

 

Regarding the use of an external physics engine - that's up to you really. But personally, if you only need to check for collisions between axis-aligned boxes and don't need any physics simulation, I think that an external physics engine would be overkill.

[Kapsonfire]

I have realised that i could loop through an array of enemy objects which are drawn on the screen but that would mean constantly searching through them at runtime for collision events, is this the best way to do it do you know?

 

Many thanks

 

I don't know how you render your game, but I'm just rendering Objects/Persons which are visible in Viewport.

I have a array which I loop though, checking positions to current position ingame and adding them to a second array.  It's fast enough, cause the array has to be loop through anyways for rendering

After that I have a small array which I can test for collisions.

[mechel178]

you should do a bounding Box ... 

[xerver]

As Gio has said many times now, a QuadTree is the way to go here. Each object will have a bound box that represents it in the tree and you can check for collisions only between likely candidates.