I’ve made a very simple and primitive JavaScript canvas engine that is simply not dependent on time, as in it assumes that t = 1 in the formula v = u + at - v is the current velocity, u the initial velocity and a is acceleration due to gravity.
Now, the issue with this method is that if the value of gravity, or velocity is large enough that the object it should collide, it just goes right through it. Now, I have been told that if time was a parameter, we could just increase the frame rate and dilate the time to resolve this, but this would mean that the engine would no longer be deterministic - as in, the simulation would not work out the exact as it we assumed it to be, owing to hardware and software requirement like decimal point handling and precision.
How can we deal with this issue on this simple deterministic engine, and improve collision detection?
I think you need to be more explicit about what you mean by “not dependent on time”. Setting t = 1 for that formula doesn’t eliminate time, it means you’re advancing time by 1 unit for every iteration of the formula defined by the units used to measure the velocity and acceleration (i.e. if v and u are measured in meters/second and a is meters/second^2 then t = 1 means you are modelling 1 second passing).
If you mean deterministic as in there are no outside influences, instead you’d want to take the distance the object needs to travel before it hits something in it’s current trajectory then work backward to find out how much time it would take to cover that distance at the current velocity and acceleration.
If I understand this right, you’re looking for Continuous Collision Detection
i.e. rather than calculating collision by looking at the intersection of objects in every frame, instead calculate collision by drawing out the path the object will go, and looking for collision along it.
Say, if I were to use a fixed gravity, and ensure that the speed is slow enough, should I have to pad numbers? I am worried about precision inconsistencies in different browser.
A few ideas:
- Instead of doing only one “update” per frame, do multiple smaller updates per frame. This doesn’t completely solve the issue but it does decrease the threshold of how small an object can be before this becomes a problem.
- Compute a region between the before and after locations, and detect if the collision object intersects that region. Then if there is an intersection you have to compute where the object would have intersected it, which is going to be a bit more complicated, depending on the shape of the bounding regions you are using.
- Just ignore the problem. Many games have this bug, but design their game so it only becomes noticeable in rare edge cases.
I’m not sure what you mean about decimal point handling - that’s always going on (unless you are trying to work with purely integer variable? Even then, there’s rounding involved whenever you need to divide…)
I’m also not sure what you mean by the engine becoming “nondeterministic”.
Here’s what I’m trying to implement - a plinkoo game. Disclaimer: I’m not into, or promote gambling, just wanted to use my knowledge of Monte-Carlo simulation on a toy project to figure out the pre-computed starting points, because client-side physics engine can be spoofed.
Now, this engine has to be “deterministic” at all cost, even at the cost of frame rates. Now, in my current scenario, gravity is fixed, however, the issue with larger gravity is that the object just phases through the obstacles.
This is why I was looking for a better solution, at least something that isn’t CPU-bound, because as I create more and more object, it hogs the memory, although not a lot, but it would hurt mobile devices (I think I should probably destroy objects after it reaches the bucket).
So far, I’ve considered using VanJS to avoid the ReactJS virtual DOM overhead.
So here’s the thing that confuses me about your use of the word “deterministic”: even if you have balls phasing through collision objects, the game will still be deterministic in the sense that the same initial conditions for the ball will result in the same final location of the ball.
Ways that it can become non-deterministic are usually either intentional randomness, race conditions from multithreading, or using a variable time delta for your update cycle, such that the time delta is dependent on the operating system, physical device, etc.
As long as you aren’t doing any of those things, the game will still be “deterministic”.
Is this for a game where it needs to be fast, or for science where it needs to be accurate?
Is the gravity constant, or does it vary as the objects move closer together?
Accuracy does not really matter here - it should be fast. But there has to be no compromise on collision. Gravity is constant, but it may change - not a strong requirement for now.
Compute the bounding volumes of the objects during the step. If the bounding volumes intersect, it’s a possible collision.
You can then use a root finder such as bisection to determine if, and at what position and instant the objects collide. This is slow so you only want to do it for pruned object pairs.
If gravity varies during the simulation, you would need to use a dynamic time step and the problem is a lot harder.
