Advanced C++/Graphics Tutorial 41: Spatial Partition Pt. 1

Spatial partitioning yaay! Were gonna optimize the crap out of ball game! Would you believe me if I said we will be able to support 40k balls? We also go over std::unique_ptr in more detail!

Code will be included in part 2.

[davislast]

"Don't worry, I'll never stop making these tutorials" :(

[mujin]

Ben is the GOAT...very impressive that he had such knowledge at such a young age.

[makinggameswithben]

+Daniel Haugland that was for colliding with the world in the zombie game, which we aren't doing here. We still had to maintain a list of all zombies and humans and iterate through them to check collision between all the different agents. This is an optimization that can be applied to the agents on the zombie game to make it much faster, since instead of looping through one giant list, we loop through much smaller lists that are local.

[PaleyDaley]

There is a small bug which will give you a memory access violation under certain circumstances:

if (x >= m_numXCells) x = m_numXCells;

this should be

if (x >= m_numXCells) x = m_numXCells-1;

And same for Y. Maybe you spotted this later but I haven't seen part 2 yet.
This would be tricky to find because it would only crash when a ball heads out of the bottom of the screen, and even so, probably the way this code works the screen bounds would stop it trying to access beyond the y limit so it wouldn't crash. But if the screen bounds checking changed or this code was used elsewhere, you would either be checking the wrong cell for some balls or it would crash.

[MrDritten]

9:45 I might be wrong, but wouldn't it be more efficient if we visualized the grid, and just calculated the cell position like we do in the zombie game with the tiles.

Get the ball position withing the camera/screen, and use a CONST CELL WIDTH to calculate which "cell" it is in.

Wouldn't it be kinder to the CPU to do a few calculations instead of constantly updating a list?

[NeilRoy]

"Collision can also change the position of our balls", why does that sound so painful to me? ;)

Can we do this about squares, or triangles next time? ;)

[Lesterberne]

You are saying here that the position was originally the top left corner, but don't you mean the bottom left corner? I mean that's what it seemed like according to our sprite batch

[DJoppiesaus]

Waiittt so you created a pionter because you couldn't initialize it in the constructor?
So it isn't possible in C++ to allocate a variable from outside the constructor or am I wrong?

[owensoft]

simpler to use a fixed grid array than managing a dynamic array of pointers

[DJoppiesaus]

What if... We can multithread everything!
Let's say we have 4 cores, then divide the sorting grid by 4, and then we *have* 4 times the performance(actually not of course, but at least it's a huge bump)!
Would this be easy to implement?