Play the game at
Check the source code on Github.

Thursday, 12 February 2015

Optimizing Entity Collisions

Testing the collision between an actor and an attack is a very CPU intensive problem. Effectively, it's a n^2 problem: for every actor (n), you need to test if it collides with every attack (n). The worst part is that in a HTML5 MMORPG, we need to perform that operation very often so it's a crucial part to optimize.

Every time you need to handle a n^2 problem, you try to minimize the n as much as possible.

Splitting the group in two subgroups then running the algorithm will speed up the process:
2 * (n/2)^2 = n^2 / 2 (x2 faster)

Splitting in 3 groups would be :
3 * (n/3)^2 = n^2 / 3 (x3 faster)

So now, the question is: how to subdivide the group without missing collision? That's where the ActiveList comes into play. Every actor keeps a list of other entities around him (seen within a screen). When testing the collision, only the attacks within that ActiveList are tested, resulting in far less calculations. The thing you need to make sure though is that the ActiveList is relevant by refreshing it often. Refreshing it completely works every time but for every actor, that's a n problem (resulting in a overall n^2 test). This means we want to minimize when we do it. Let's say that we refresh every second. I should be good since it's very rare that an entity will travel an entire screen within 1 second.

However, when a new bullet is spawned, we can't wait for 1 second for the ActiveList to be refreshed. That means every time a new entity is spawned, we need to generate its ActiveList and add it to the concerned entities. This is the system Raining Chain is using and it is working very fine.

The same logic is used to set the target of a monster. The possible targets are only searched within the ActiveList of the monster rather than the map entity list.

No comments:

Post a Comment