1
\$\begingroup\$

This question can be generalized to "how does one efficiently determine if a collision has taken place between curvy lines"

On https://slither.io there are snakes that players play as that can grow in length and width as the player collects food.

Similar to the "snake" game, if you collide with any other snakes, you die, but how are these collisions determined?

My intuition was that each snake is just a long list of circles, and you just use an Octree or Spatial Hash of circle collisions, but even this seems like it could be too slow, considering some snakes can get extremely long, and I doubt that the solution is just to have a snake be 1,000 circles long.

So, how is this sort of collision detection done then? Do they go with the naïve circle approach, or is there a more efficient way of calculating collisions between arbitrarily shaped and sized curves?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ "How do they do this" is off topic here, we'd need to se their code to answer this correctly. If you're trying to implement something like this in your game, it looks like you know of at least one viable option, so I suggest you try it out and come back to us if you have more questions about your own implementation. If you've tried it yourself and have issues with the implementation, then please edit the question and ask about this instead. \$\endgroup\$
    – Vaillancourt
    Aug 5 at 13:00
  • \$\begingroup\$ I did not open slither.io, if it's like Snake then it's played on a grid, correct? \$\endgroup\$
    – user253751
    Aug 6 at 14:29
1
\$\begingroup\$

You are correct that circle collision is a good first approximation. I suggest you compare the square of the distance between the centers instead of the distance, so you can save a lot of square root computations.

The naive approach would have you check check each circle against each circle, for a total of comparisons (where n is the number of circles). And you can bring that number down by not checking against circles you have already checked, for a total of n * (n + 1)/2 comparisons.

However, you only care about the heads (and each snake only has one head). So you would have n * s comparisons (where s is the number of snakes). Which is better than n * (n + 1)/2 given that s ≪ n (read: s is much less than n).

Yet, you are correct again in that you should use some space partitioning structure.

I'll suggest to use a hierarchical space partitioning structure - such a quad-tree - because a large snake could be bundled up in a small space. And with that you would have s * log(n) comparisons.


Alternatively, you could add snakes to the hierarchical space partitioning structure, instead of their individual circles.

You can register the snakes by their middle position. Which is the center of one of the circles, if the number of circles is odd… Or it would be half way between two circles if the number of circles is even.

That way you can query for nearby snakes, and you might be able to prune some snake-snake collision by checking if the distance from center to center of the snakes is greater than the sum of the halves of their lengths. If it is, there is no position those snakes can be that they would be able to touch each other.

So you would only have to worry about collisions between snakes that are close enough. It is worth noting that in the game a snake does not collide with itself.

You would have s * log(s) possible snake-snake collisions. Which is potentially better than s * log(n) considering that s ≪ n. But that depends on how efficient we can make a snake-snake collision check.


For each snake-snake collision check, starting back at the naive approach, you would need p * q comparisons (where p is the number of circles of a snake, and q is the number of circles of the other). For a total of s * log(s) * p * q.

However, again, we only care when the head of a snake runs into the other other snake. I'll refer to these as snake-head collisions. If you need both snake-head collisions checks, that brings us down to p + q comparisons. For a total of s * log(s) * (p + q).


But we don't need both snake-head collisions checks! If the head of a small snake is nearby the body of a large one, it does not mean the head of the large one is nearby the body of the small one.

So, wait, rewind. Do not prune snake-snake collision. Prune snake-head collisions. For these prunes follow the same idea as before: check if the distance from the center of the head to the center of the other snake is greater than half the sum of the size of the head and the length of the snake.

And each snake-head collision check requires l comparisons (where l is the length of the snake). And of these we need at most double as before: 2 * s * log(s). For a total of 2 * s * log(s) * l comparisons. Which is good given that l ≪ n.


I had the idea that a large snake is like two shorter snakes connected head to tail. So you could check if the head could be close enough to collide to each half. And so on, like a binary tree. However, note that the sides of the tree are not mutually exclusive. The head of the snake could be close enough to collide with both halves of the other snake.

Yet, it is a good idea to put the circles of a snake in a convenient structure. For example, if you divide the circles in quadrants, and you find in which quadrant the head is…

Yep, make a quad-tree - or similar hierarchical space partitioning structure - per snake. And use it to find circles of the snake that are nearby the head of the other snake. So you don't have to compare the head with all of them. That should bring the number of comparisons down to log(l) per snake-head collision check. For a total of 2 * s * log(s) * log(l) comparisons.


This total of 2 * s * log(s) * log(l) is better than s * log(n) as long as s ≪ l. That is, if you have few large snakes, this is better. If you have a ton of small snakes, then storing all the circles in a single hierarchical space partitioning structure is better.

I believe the boundary condition is very low. I mean that the snakes will grow soon enough. However, if in doubt, profile to find the boundary conditions. Once you know those conditions, you can even write code that decides which approach to use according to those conditions. You might even decide per snake if it is short enough to store all its circles directly in the hierarchical space partitioning structure.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.