Adding jaws.QuadTree

[videlais]

Adding quadtree functionality to JawsJS.

Using QuadTree.collide(), it will take as arguments two of any objects that can be inserted into a SpriteList (or even two SpriteLists themselves) and return if, at any point, they overlap with each other.

If the third argument, callback function, is set, collide will call that function, with the two objects that collided as arguments, per collision detected.

[ippa]

Hi Dan. So you got quad-trees going, very nice! :) You probably know what I'm going to ask for now... tests. Extra important for a big addition like this. And some documentation for individual functions (and not only the constructor).

Would be cool with a simple example showing where QuadTree shines too. Maybe a modified http://jawsjs.com/jawsjs/examples/example4.html where you can toggle with between normal collision detection and quad-tree-optimized detection with space or similar? Hopefully the quad-tree version will be faster :P.

This will provide direct visual feedback that the quad-tree is solving what it's supposed too.. also ppl love reading examples to learn.

Thanks again for the hard work.. can't wait to test this out myself in a game soon.

[videlais]

I've created a simple QuadTree demo (http://videlaisstudios.info/testing/quadtree/) and worked with Example 4 some.

Here is the original but with 300 sprites (http://videlaisstudios.info/testing/quadtree/example4.html) and the QuadTree version with 300 sprites (http://videlaisstudios.info/testing/quadtree/example4quad.html).

[ippa]

WOW.. that's a lot of rects colliding with a somewhat chopped up pacman :), this is awesome! Suddenly I'm in the mood for a bullet hell shmup! Great work.

Having looked more at your code I have one remaining thing I would like to discuss with you before we go public. The API differs quite from jaws standard collision detection in 2 ways:

1) You take a third callback-argument while standard collision detection returns arrays 2) You have one "smart" collision()-function while jaws has more explicit collideOneWithMany(), collideManyWithMany() and so on.

Regarding #1 I'm not sure if there's a big upside with either of the solutions, but rather just different styles? Was there a specific reason for going with callbacks rather then returning arrays? An API that feels the same across jaws would be preferable.

With that said, I guess it would be rather easy to add a third callback argument to the existing collision detection functions without breaking the API, but there should be a good enough reason to do it.

About #2 I actually had something similar with the existing collision detection, see: https://github.com/ippa/jaws/blob/master/src/collision_detection.js#L130

I had some reasons for it:

• collideOneWithOne() returns true|false, collideOneWithMany() returns an array and collideManyWithMany() returns an array with arrays. But it's also explicit and logical why they do so. In the end I didn't like the magic with a single collide() which could return different types of result.
• It felt like collide() got messy with tons of conditions. Maybe this was a pretty weak reason. And some premature optimization with the reasoning that you would always get better speed with the explicit functions.. but the slowness of collision detection wouldn't lie within those conditions anyhow.

So, maybe it's time undeprecate and have it work like your quad-tree collide():

jaws.collide(item, list, function(a,b) { 
  /* a will always be item, b will be individual items from list */ 
})
jaws.collide(item, item2, function(a,b) { 
  /* a will always item, b will always be item2 */ 
})
jaws.collide(list, list2, function(a,b) { 
  /* a will be individual items from list, b will be individual items from list2 */ 
})

What's your thoughts on the above? Let's think hard on this, make a decision and stick with it.

[McFunkypants]

Personally, I prefer the callback approach. One reason is that you don't need to iterate through a potentially multidimensional array (again) since the collide func is iterating why not save another big loop every frame?

Another reason is that I prefer the result of a collide (thing to thing, thing to list, list to list) to always just react as thing to thing for a single way to handle.

That said ,here's one good reason to return a list: rendering using quadtree with a new style:

List to rect!

This would be faster than tilemap for off the grid and different sized sprites in a big world.

So... There no best way to do this...

[videlais]

@ippa I debated as to whether to keep it as returning an array or using the callback function. I looked at how Flixel (the ActionScript 3 game library) does it and saw that they do the callback function too. After doing some research into what the general trend was in JavaScript, most people tend to prefer using a callback function than having to iterate over some data structure. (Async is a major trend right now.)

I agree with @McFunkypants on this. In the worst case of the current OneWithMany and ManyWithMany, it is n iterations and then a returned array iterated over n times again (potentially n^2 if not n^n for multidimensional nested cases). Lots of unnecessary looping.

I also think that returning a Boolean is a good idea too. Sometimes, I don't care which sprites collided, merely that they did. In those cases, I don't want to loop at all outside of the collision checking. I need a conditional.

So, I vote for a smarter collision checking that will take item and item, item and list, or even list and list. That way, as a programmer, I know I can always check to see if two sets are colliding and, if I care about the results, I register a callback and handle it on a item with item basis. That way, I don't need to remember if I am dealing with an item or a list when I use the function. I know it will take both.

jaws.collide(item OR list, item OR list, callback) { 
  ...
  return overlap; 
})

The other thing to consider in this conversation though is if this might be something to work into the next version of JawsJS. I know currently that Jaws doesn't seem to have any public numbering, but it might be time to think about that some. Maybe taking everything (except maybe QuadTree) and making it 1.0 or something. And from that, make a list of features to add in (like QuadTree and this possible collide()) and setting some type of milestone.

I bring that up because the other things on my Jaws-related TODO list include working on jaws.assets to finalize the audio and video work, and finishing the Emitter code. Not that I think my own code is more important or anything, but I was thinking that if we decide to change the collide code, it might be time to shift to a whole new version number and introduce new features with that release.

[ippa]

Thanks for the feedback guys. By listening to you and by looking at my own code.. the most common case for collision detection would be to instantly iterate through the colliding items and do something. With that in mind a callback as third argument makes sense.

So I'll merge this as it is now. After that I'll bring back (the now removed) jaws.collide() with the same API as Dans QuadTree collide(). I'll leave the rest of the collision functions intact until further. This way we get a simple streamlined API without breaking any old API. Adding a third callback argument to collideManyWithMany() and so on could be a future idea.. but it will probably be less important with the new collide().

@videlais about the 3 arguments to QuadTree(). It's not instantly clear to me what they do.. maybe it could be made clearer? I'm not a fan of long argumentlists either.. to the degree it's even a point under the readme highlights:

"Often does object literals as arguments for readabillity (ie. new Sprite({image: “player.png”, x: 100, y: 100})"

Maybe we could do QuadTree({depth: 123, bounds: 456, maxlevels: 789}) ?

[ippa]

Thanks for the feedback guys. By listening to you and by looking at my own code.. the most common case for collision detection would be to instantly iterate through the colliding items and do something. With that in mind a callback as third argument makes sense.

So I'll merge this as it is now. After that I'll bring back (the now removed) jaws.collide() with the same API as Dans QuadTree collide(). I'll leave the rest of the collision functions intact until further. This way we get a simple streamlined API without breaking any old API. Adding a third callback argument to collideManyWithMany() and so on could be a future idea.. but it will probably be less important with the new collide().

@videlais about the 3 arguments to QuadTree(). It's not instantly clear to me what they do.. maybe it could be made clearer? I'm not a fan of long argumentlists either.. to the degree it's even a point under the readme highlights :P

Often does object literals as arguments for readabillity (ie. new Sprite({image: “player.png”, x: 100, y: 100})

Maybe we could do QuadTree({depth: 123, bounds: 456, maxlevels: 789}) ?