Collision detection is slow

[Toktik]

When col_width and row_height are small and there are big enough grid items on grid, collision detection becomes slow.

Grid configuration looks like this:

private gridOptions = {
    cascade: 'off',
    col_width: 2,
    row_height: 2,
    min_height: 12,
    min_width: 12,
    margins: [5],
    max_cols: 100,
    auto_resize: false,
    maintain_ratio: true,
    prefer_new: true
  };

(we actually want resizing step to be 12, but I have set it to 2, because margins gets added to the col_width/row_height, not sure why, should not it only added around grid item only?)

_hasGridCollision performance is applicable, it's below 0.5 sec, but the hassle is in _fixGridCollisions.

For example there are two grid items with sizex: 40, sizey: 30. Colliding one to another takes 3-4 seconds.

I'm having a look and I think the reason is brute forcing through all cells for affected items, btw which looks like "recursive", if there are many grid items, they most likely will get recursively collided.

I did a little research and one suggested solution is building a quadtree from grid and use it for CD. What do you think? http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374

[Diazbesjorge]

Hi Ben,

This is a critical issue. Using settings above and adding just four items to the grid rendered Chrome totally unresponsive.

Thanks for looking into it.

[BTMorton]

Yes, you are correct that the margins get included in the colums/rows. Each row/column is the width, plus the border, with the thinking that you can control the smallest item with the row height/col width. The border then gets added into the height/width of the item when it's bigger than a single row, that way the items align into a grid correctly. Obviously, that's more the case for larger items which was the envisioned use case when I developed this. The alternative is to subtract the margin from the total height/width, which is probably more applicable in your case.

I'll take a look and see if there's any immediate improvements I can make to the collision fixing. I'll also look into the quad trees for a potential bigger speed boost later on, thanks for that.

[BTMorton]

OK, I've had a look and made some initial improvements, caching the max col/rows for later use, rather than getting dynamically every time (turns out that's really slow...). Also, now it moves collided items all the way out in one step, rather than one row/col at a time... (oops...). Give that a try! :D

[Toktik]

Hey Ben, thanks for looking into this.

I've tried it, but when colliding items, the browser gets hanged forever.

I think it hangs also in cases when it was not hanging before (big values for cols/rows)

[BTMorton]

So, after doing some CPU profiling, it's definitely not caused by the colliding. It's the getMaxRow/getMaxCol functions. I've made some improvements there, which hopefully speeds things up. I've tried it with your settings from the other thread (col/row = 2), but only with 4 items. Is that similar to what you've been using?

[Toktik]

I've actually reverted 99074888b3d144820cec7b8cb271034e5cb6346e locally, to be able to use grid, because it was hanging.

I have two items currently with above grid options. Here are item options.

Item #1
col:2
height:290
left:17
payload:"57608a94a56f07de2ea927fe"
row:1
sizex:34
sizey:25
top:5
width: 398
---------------
Item #2
col:43
height:290
left:509
payload:"57608a95a56f07de2ea927ff"
row:1
sizex:42
sizey:25
top:5
width:494

Also I did CPU profiling, it seems like you are totally right, the bottleneck is getMaxCol. Here is the output: http://prntscr.com/bggu66

[Toktik]

As per hanging with new commit, the code never gets past of this cycle when colliding two items. https://github.com/BTMorton/angular2-grid/commit/99074888b3d144820cec7b8cb271034e5cb6346e#diff-b5893a7b91d84dda1c178acf6df33b79R731

Update

I've reverted this block only. And I think performance is much much better. It's around 0.5 to 1 second when dragging items.

However now I noticed the grid initializes slowly, I guess because the same maxCol calcs work on init. Right? http://prntscr.com/bghhi7

[BTMorton]

D'oh! That should be itemDims.x not itemDims.y. I'll fix it and push the rest of my changes

[Toktik]

@BTMorton it's blazing fast! Congrats!

[Diazbesjorge]

Woah, impressive, good job Ben, it is really faster than expected! Now if you could just fix remaining issues in #89 we'll be ready for public release :-)