I guess finding the closest instance of a particular type of component will be something that's useful, which would require doing the check inside the raycasting? I wish there was a way to avoid that, though the only other option would to basically have the raycaster be an iterator of some sort, maintaining it's internal state and allowing you to grab the next intersection through a method call.

It might be worth thinking about how this would interact with some sort of compiled asm.js collision engine. I believe that the first approach would be tough (the compiled code couldn't interact with general crafty code, and so it would be tricky for it to inspect entities for the presence of components), while the latter approach would perhaps be more natural in such a context?

I still have to test whether the approximate broadphase intersection check is worth it, and how many segments a polygon must have (increases complexity of the exact intersection check) to be worth it.

I'd expect that it's not worth it -- if used properly (i.e. don't put 100s entities in the same cell) the spatial map is itself the broadphase check. This is probably more true of raycasting than regular collisions, since SAT is more expensive than the simpler checks here.

Having separate hashmaps for collision stuff and for each layer would help in configuring each hashmap so that the correct property gets accessed for the bounding rectangle. A more immediate fix would be to provide an optional argument to each of the hashmaps methods, which dictates which bounding rectangle property to use.

I wonder if the best approach for Canvas redrawing would be to have it flag cells of the hashmap as dirty, rather than carefully keeping track of the bounding areas of individual entities.

Crafty.map.boundaries(findKeys) was extended to find only hashmap cell keys if optional parameter is provided. Should this stay here (introduces some branching in code) or make an explicit method Crafty.map.keyBoundaries() (code duplication)?

IIRC calling boundaries is actually pretty expensive, maybe not something we want to do every time raycast is called. A possible optimization is caching them, and only recalculating the boundaries if the hashmap has been modified? (i.e. have a dirty flag on the hashmap)

@starwed Thanks for the feedback!

I guess finding the closest instance of a particular type of component will be something that's usefu

Added

I'd expect that the approximate intersection test is not worth it

Removed

A possible optimization is caching the hashmap boundaries, and only recalculating the boundaries if the hashmap has been modified?

Added

What's still missing:

• follow-up PR: let Crafty.map.boundaries and Viewport.bounds return a flat object minX, minY, maxX, maxY
• follow-up PR: setting the _cbr doesn't update the entry in spatial map, until the entity is moved/rotated/resized
• api documentation
• split the single large test file into smaller ones
• search the spatial map for the _mbr instead of the _cbr in the render code

If you're ok with it, I'd include the latter 2 points into a follow-up PR (with some additional proposals in regards to bounding rectangle handling).

I feel confident about the implementation now, so if you have time and are up for it, take a look at it, I've included extensive implementation-specific documentation.

It might be worth thinking about how this would interact with some sort of compiled asm.js collision engine. I believe that the first approach would be tough (...), while the latter approach would perhaps be more natural in such a context?

I don't quite understand what the 1st approach and 2nd approach is :)

I wonder if the best approach for Canvas redrawing would be to have it flag cells of the hashmap as dirty, rather than carefully keeping track of the bounding areas of individual entities.

In an 'Asteroids' like game, where you have small entities scattered all around the scene, it might perhaps require redrawing all cells? Might work well in the general case though. Maybe some additional metrics / statistics could be considered here, like heuristical cluster analysis? Might be overkill though :)

I don't quite understand what the 1st approach and 2nd approach is :)

No worries, I was just trying to think through how an underlying optimized algorithm would work, and probably wasn't very clear. In the end the API the user calls would be unchanged.

In an 'Asteroids' like game, where you have small entities scattered all around the scene, it might perhaps require redrawing all cells? Might work well in the general case though.

Well, it would work the same way it does now -- if a large fraction of entities need redrawing, just do them all.

search the spatial map for the _mbr instead of the _cbr in the render code

I might be forgetting how our existing code works, but what's the change here?

search the spatial map for the _mbr instead of the _cbr in the render code

I might be forgetting how our existing code works, but what's the change here?

Ah, I'm glad you asked, there is no problem at all. Render code calls Crafty.map.search(rect), where rect is just a plain rectangle object, which does not have _cbr and _mbr properties.

Side-note:
Canvas clears some-dirty-entity-encompassing rects and then proceeds to draw all overlapping entities. Note that it does not clear the overlapping entities that are partly inside and partly outside these rects, thus these get drawn again. When drawing the same line multiple times in Canvas, I noticed it getting thicker and thicker. However, these artifacts may not apply here.

In an 'Asteroids' like game, where you have small entities scattered all around the scene, it might perhaps require redrawing all cells? Might work well in the general case though.

Well, it would work the same way it does now -- if a large fraction of entities need redrawing, just do them all.

True, I was just wondering about the edge case where percentage of dirty entities < 50% and their dimension << cellsize.

I like this proposal, as it could potentially improve performance for Canvas rendering. Drawing dirty entities requires merging their dirty rectangles, which sounds like an expensive operation. Drawing dirty cells could be done by just clearing each individual cell and drawing its entities.

True, I was just wondering about the edge case where percentage of dirty entities < 50% and their dimension << cellsize.

From what I understand, you always want your cellsize to be some small multiple of the typical entity size. If you have lots of small entities moving around inside a single cell, collision performance will suffer because the broad-phase pass will leave too many candidates for the more expensive check.

We kind of support setting the cellsize before init, but it should probably be an actual option exposed through the api.

Ok, added the missing stuff (api docs, test file organization and some minor tweaks).

@starwed
Do you want to take a look at this or should I go ahead and merge it?
We can still fine-tune it before release, if there are any issues.

@mucaho I haven't had time to fully look through it, but so long as it doesn't seem likely to affect performance I don't have any problem with landing it. Like you say, we can always tune it up before release. (And if we're concerned, add a warning to the docs that the api is new and possibly unstable.)

Feel free to merge once the conflicts are resolved.

There may be certainly some things that could get optimized.
One notable thing that could be added in future: It would be nice to have method which does multiple raycasts (in different directions, from same origin point) at once. That would remove the need to check if the origin point lies inside the map for each raycast, but rather do it only once.
I'm particularly proud that the implementation does not use a single Math.sqrt statement. It uses basic math operations instead. It's a marginal improvement though :)