How continuous and accurate is the collision detection?

Entelect Challenge 2021 General
1

Doing some work on paper, and I for see a possible issue in predicting whether a collision might happen and the game engine indicating a collision has occurred.

Is there a risk in a glancing blow not being detected if my data type is not accurate to enough decimal places? As all objects will have integer radii, I wouldn’t think this is an issue.

Is there a risk in the “bullet through paper” problem? If a ship is at minimum size, and moving at a speed of 200, moving towards an enemy ship also at minimum size travelling in the opposite direction, so speed is at will their collision always be detected? Even if they were slightly offset? How continuous is the collision detection?

2

Hi @clbuttic,

Great questions you raised! Actually some of the most interesting challenges we faced during the development of the core movement mechanic - so excuse me if I slightly nerd out a bit here on my answer.

In terms of the data type and integer accuracy issue, this was a decision made pretty early on.

Dealing with decimals, floats, doubles, and the like all have unique accuracies across the different programming languages, and sometimes even within one depending on how you manage your data.

To combat this, we decided to stick with a purely integer based system, that uses specific and consistent rounding logic when performing calculations.
Most of these can be found in the VectorCalculatorService.cs file, in the Services folder of the game-engine.

Much like you mentioned, because they are all integer radii, this leaves us with three possible colliding states:

  1. Not colliding - the distance between the center points of two objects is greater than the sum of their radii
  2. Touching - the distance between the center points of two objects is exactly equal to the sum of their radii
  3. True overlap - the distance between the center points of two objects is less than the sum of their radii.

The engine only considers a collision when two objects have a true overlap - at least 1 (one) integer value worth of distance less than the sum of their radii.

In terms of the “bullet through paper”, this was a fascinating problem and is pretty well described in game engine development.

Typically referred to as the tunneling problem, there are some very interesting solutions to this.

The simplest approach, and the one we chose to go with, is to simulate the movement of all objects concurrently through the course of their total movement in that tick.

This means that, at any given moment during the simulation, each object has moved proportionally to their overall movement required, allowing us to detect collisions at each point across the entire movement, rather than just considering the change in position as a whole.

You can think of it much like a ray cast, through the entire movement, and collecting all collisions along the path.

Therefor, if at any point during their movement, those two objects overlapped by at least 1 integer worth of distance, they will have had a collision detected and the consequences thereof applied to them.

I hope this helped answer your question, my apologies if it was a bit overwhelming but this topic gets me really excited!

7 Likes
3

Thank you for the detail, James. The nerding out is very much appreciated.

With a discrete world, that would mean that paths won’t be straight lines, rather they will be aliased (assuming I am using this term correctly). So, imagining an example, a ship of size 1 travelling at 200 at a bearing of 22.5°, the path will be right, right, right, up, right, right, right, up, etc?

And just to make sure I fully understand the collisions, if we were to colour the world like a chessboard, and put clouds on all black cells, can I move in a diagonals on white squares without hitting a single cloud if my ship is size 1? I’m moving from 1,1 to 2,2 without passing through 1,2 or 2,1?

I’m focusing on the smallest possible ship here, which isn’t likely to be commonly used except perhaps for some weird strategies, but it’s just to help understand the world.

Thanks again.

4

The paths while indeed will be straight lines in the macro scale, when looking at the microscale, indeed it will look as nearly a “checkerboard”, due to the minimum size of an individual unit of space being 1 by 1 unit.

That being said, the idea you would move “right, right, up, right” a that bearing would be disingenuous.

Rather, consider yourself as moving to the next “block” in that bearing. Sometimes, you might move only one X, or another, one Y value.

Over the larger, whole movement that occurs in the tick, you would indeed see a straight line of 200 units long, at a bearing of 22.5 degrees.

While technically, I believe you are correct in your analysis - you would indeed miss the objects positioned on the direct left or right of your ship - the minimum ship size is specified. In this case, at the current balancing configuration, it is set to a minimum of 5 (five).

This means the scale at which you would consider objects should never be less than 5, as at that point, you would collide. This solves the problem of the microscale inaccuracy, we believe.

Hope this helps clarity!

For my own interest - as I’m not sure I follow - what is the value of analysing the world space in terms of squares, rather than working as though everything is a circle?

If this question gives away a technical benefit for your bot, feel free to ignore it and keep your secrets! (but I’ll bug you at the end of the year to understand :wink: )

1 Like
5

Thank you for clearing that up. I missed the minimum size specification, so things have become a lot clearer.

I don’t have any kind of a strategy here, just thinking of possibilities, and thinking how the world could be represented in different perspectives and whether that’d help with anything. Like could transforming to a polar coordinate system be useful? Maybe with some math, but could that cause different expected collision?

Thanks again.

6

We’ve just pushed quite a big update to the way this is processed inside a tick, especially with regards to maintaining the heading. Just thought I’d drop a follow up here so you could make sure you were looking at the latest stuff!
Good luck!

2 Likes
7

I have a question related to collisions, at what point does food get consumed, if for example, my bot is big enough, will it eat all the food in it’s radius or will it consecutively eat food per tick?

8

Hi there.
Your bot will consume all the food in its radius per tick. There is no cap on the amount of food you eat per tick, so we do consider everything you collide with. However, there is a cap on the size you can grow from eating food.

2 Likes
9

What is this size cap?
Maybe I’m missing it in the rules.

10

Cap is 200 (Player Size)

3 Likes
11

Thanks @UberGeoff :slight_smile: