Hey everyone,
I was just wondering if there was more info about __search in position__ type of collision detection. If anyone has found any more info about how to use it, I thought it would be a bit of an exercise trying to implement it in another context.
THanks in advance
I was just wondering if there was more info about __search in position__ type of collision detection. If anyone has found any more info about how to use it, I thought it would be a bit of an exercise trying to implement it in another context.
THanks in advance
I will be writing it up for The Witness Wednesday series later in the year. Right now, no, I don't think there's anything out there.
- Casey
- Casey
I just finished watching Day 45; the search-in-p approach concerns me a bit.
I looked through Working on The Witness serious on this [page](https://mollyrocket.com/casey/), but I can't locate any post on this topic.
If I understand the algorithm correctly, then given a confined circle space, where player (represented as a dot) can only move within it, and player original state (P, V), the search-in-p approach would first find `P'`, and find the closest valid point to `p'`. In this case, it's the intersection between `OP'` and the boundary.
Illustrated using the following image:
https://docs.google.com/presentat...Hjk/edit?usp=sharing&pref=2&pli=1
If we enlarge `V`, we should see players moving along the circle, but it's impossible to reproduce that using this algorithm, because even the infinite far point `P'` would not result into points below the horizontal line where `O` lies.
I looked through Working on The Witness serious on this [page](https://mollyrocket.com/casey/), but I can't locate any post on this topic.
If I understand the algorithm correctly, then given a confined circle space, where player (represented as a dot) can only move within it, and player original state (P, V), the search-in-p approach would first find `P'`, and find the closest valid point to `p'`. In this case, it's the intersection between `OP'` and the boundary.
Illustrated using the following image:
https://docs.google.com/presentat...Hjk/edit?usp=sharing&pref=2&pli=1
If we enlarge `V`, we should see players moving along the circle, but it's impossible to reproduce that using this algorithm, because even the infinite far point `P'` would not result into points below the horizontal line where `O` lies.
The answer to this is relatively complicated so it'd have to wait until I discuss the system in more detail, but the short answer is a) don't forget that P updates every frame, hence the line from P to P' is actually in continuous motion along with the player, and b) there is an additional circle of constraint you haven't drawn, which is the distance the player is allowed to travel in one timestep. If you draw that in, you can see that the area you're considering here as the constrained circle region is in fact so small that the player would never even be able to perceive it (it is effectively a single point of contact), hence your intuition about what this would "feel like" for the player to experience is not going to be correct.
EDIT: And c) don't forget that your geometric criteria can be whatever _you_ want. So for example, if you prefer the feel of "furthest along the direction of motion", you can trivially use that instead of "closest to the projected point". This is one of the great things about search-in-p - almost any criteria is trivially to implement, because it is implicitly evaluated rather than explicitly, so you don't only have to use criteria that can be calculated as a series of steps. You can evaluate your criteria effectively everywhere, and select the global maximum.
- Casey
EDIT: And c) don't forget that your geometric criteria can be whatever _you_ want. So for example, if you prefer the feel of "furthest along the direction of motion", you can trivially use that instead of "closest to the projected point". This is one of the great things about search-in-p - almost any criteria is trivially to implement, because it is implicitly evaluated rather than explicitly, so you don't only have to use criteria that can be calculated as a series of steps. You can evaluate your criteria effectively everywhere, and select the global maximum.
- Casey
Edited by Casey Muratori
on
Here's my attempt to abstract it to a pure physics/math problem and trying to solve it.
Given a point P at (0, R/2), with constant velocity V, after T time, it could move to P'. Now there's a circle wall centered at (0,0), with radius R. Collision with the wall would cause the object to lose its velocity component perpendicular to the tangent line at the contact point. The point starts with the identical state from P, hits point C, and slides to P2 after T time, because of the collision with the circle wall.
Assuming ∠COP = theta, R, length of CP' is known, what's ∠COP2 = phi?
After contacting with C, the point would move in uniform circular motion, with velocity `V*cos(theta)`. Then, we could calculate the arc length by `V * cos(theta) * CP' / V == CP' * cos(theta)`. On the other hand, `phi * R` is the arc length as well. Therefore, `phi * R = CP' * cos(theta)`.
The above reasoning assumes zero friction for simplicity, but the conclusion (the destination point after T time could go below y=0) still holds.
Now connecting it back to the game, T is rather small (one frame time), V can't be too large, so probably P1 is pretty good approximation.
Given a point P at (0, R/2), with constant velocity V, after T time, it could move to P'. Now there's a circle wall centered at (0,0), with radius R. Collision with the wall would cause the object to lose its velocity component perpendicular to the tangent line at the contact point. The point starts with the identical state from P, hits point C, and slides to P2 after T time, because of the collision with the circle wall.
Assuming ∠COP = theta, R, length of CP' is known, what's ∠COP2 = phi?
After contacting with C, the point would move in uniform circular motion, with velocity `V*cos(theta)`. Then, we could calculate the arc length by `V * cos(theta) * CP' / V == CP' * cos(theta)`. On the other hand, `phi * R` is the arc length as well. Therefore, `phi * R = CP' * cos(theta)`.
The above reasoning assumes zero friction for simplicity, but the conclusion (the destination point after T time could go below y=0) still holds.
Now connecting it back to the game, T is rather small (one frame time), V can't be too large, so probably P1 is pretty good approximation.
Well, I think I'm just repeating what I said before, but: the location of P' moves continuously as the player moves. After the first incident with the wall, P' will move downward because it is the projection of the player's point outward in the direction of movement, and the player is moving downward. Eventually P' will converge to a Y of 0, at which point it will become stationary, which is exactly what you would expect (the player has hit the furthest point they can be on in their direction of travel).
- Casey
- Casey
> the location of P' moves continuously as the player moves.
Possibly, I didn't state it explicitly that T is the per-frame duration. In other word, the player was in P at frame 0, and there's no input from the user. The simple prediction would place the player in P' at frame 1, but due to the existence of the circle wall, it's an invalid move.
Therefore, the process here is completely discrete, frame by frame, I think, though delta t is very small.
The search-in-p would give P1 as the player's location at frame 1, while the physics model would give P2 as the player's location at frame 1. In summary, the player is at P at frame 0, and would be at P1 at frame 1 using search-in-p, and would be at P2 using the physics model, but nowhere in between.
PS: Zero friction is assumed for above reasoning.
Possibly, I didn't state it explicitly that T is the per-frame duration. In other word, the player was in P at frame 0, and there's no input from the user. The simple prediction would place the player in P' at frame 1, but due to the existence of the circle wall, it's an invalid move.
Therefore, the process here is completely discrete, frame by frame, I think, though delta t is very small.
The search-in-p would give P1 as the player's location at frame 1, while the physics model would give P2 as the player's location at frame 1. In summary, the player is at P at frame 0, and would be at P1 at frame 1 using search-in-p, and would be at P2 using the physics model, but nowhere in between.
PS: Zero friction is assumed for above reasoning.
Yes, if you are talking for a single timestep, then you have two choices. Either you can use the "furthest point along the direction vector", which does (in a single step) the same operation as would happen over many timesteps with "closest point", or you can just do closest point, which takes multiple timesteps to converge.
In practice, I don't know that you can tell the difference between these two, but the overall algorithm doesn't change regardless of which you pick. All you do is change the edge functions you evaluate per geometry element when the goal point is not within that element.
- Casey
In practice, I don't know that you can tell the difference between these two, but the overall algorithm doesn't change regardless of which you pick. All you do is change the edge functions you evaluate per geometry element when the goal point is not within that element.
- Casey
Agree. Those two approaches (single step or multiple timestep) would place the player at (-1,0) pointer in the sketch. However, neither would be able to place the player below y=0, while the physics model allows that, which is where my concern originates.
Maybe, V and T (one frame duration) is too small for users to feel (or see) the divergence?
Maybe, V and T (one frame duration) is too small for users to feel (or see) the divergence?
No, physics can never put you below Y=0. Remember here that "physics" is applied before the search pass. You are saying "here is where physics wants to move you", and that velocity line is the mandate to the search. If the "physics" always maintains that the velocity is (-1, 0) as implied by your diagram, then there is no way to ever move past Y=0, as there is no way to produce a negative X displacement from a positive x velocity.
- Casey
- Casey
This is where we disagree. I have abstracted the collision to be a pure physics problem, and the above reasoning concludes, `phi * R = CP' * cos(theta)`, so it's possible that the point would end up below y=0, after T time, for CP' (~V*T) could be arbitrary large.
The intuition why a point with zero velocity component in Y-axis could move on Y-axis is that the wall is exerting an acceleration perpendicular to tangent line of the contact pointer. After the contact at C, the point is moving in uniform circular motion, which surely allows it to get below y=0.
This is the reasoning based on the physics model, not tired to the game, to avoid confusion.
The intuition why a point with zero velocity component in Y-axis could move on Y-axis is that the wall is exerting an acceleration perpendicular to tangent line of the contact pointer. After the contact at C, the point is moving in uniform circular motion, which surely allows it to get below y=0.
This is the reasoning based on the physics model, not tired to the game, to avoid confusion.
No, this is definitely not true. The Y=0 line happens to be at the maximal point along -X, which is where any point whose velocity is any constant negative value in X will always end up at t=infinity.
The only way to have something other than this happen would be to allow the wall to impart velocity onto the player, namely giving the wall a coefficient of restitution greater than 0 instead of 0. This is not the way FPSes ever work - the coefficient of restitution for any wall in any FPS I've ever seen (including the Witness) is always 0. You cannot "bounce" off a wall.
- Casey
The only way to have something other than this happen would be to allow the wall to impart velocity onto the player, namely giving the wall a coefficient of restitution greater than 0 instead of 0. This is not the way FPSes ever work - the coefficient of restitution for any wall in any FPS I've ever seen (including the Witness) is always 0. You cannot "bounce" off a wall.
- Casey
The deriving process to get `phi * R = CP' * cos(theta)` was laid out in my post containing the sketch. Could you point out the mistake since you don't agree with the result?
> You cannot "bounce" off a wall.
True; here the point is "sliding" along the wall. Rephrase it in physics/math language: the velocity component perpendicular to the tangent direction of the contact is lost, but the parallel component is kept in tact.
The reason why it's not seen in games is possibly: V and T is too small, and friction is not zero, which makes the resulting point above y=0.
> You cannot "bounce" off a wall.
True; here the point is "sliding" along the wall. Rephrase it in physics/math language: the velocity component perpendicular to the tangent direction of the contact is lost, but the parallel component is kept in tact.
The reason why it's not seen in games is possibly: V and T is too small, and friction is not zero, which makes the resulting point above y=0.
The problem here is that somehow you're generating some Y velocity that persists after interaction with the wall, which is not how these games are intended to work. There is no y velocity, only y displacement in this example. When a player pushes against a wall in an FPS and they come to a corner, they do not expect to shoot back up out of the corner in the opposite direction. They expect to stop at the corner.
Stated another way, the environment does not impart velocity in a walking simulator. The player is asking to walk, and it is assumed that they are under total control of their own movement. When they push up against a wall, we are assuming that the player is actually walking along the wall, not being glided along the wall by forcing themselves into the wall and letting the restitution push them diagonally.
Stated yet another way, I believe you are looking at this problem as if the player is in a dynamic friction state with respect to the environment. That's not what the goal is for this sort of system. The player is in a static friction state with respect to the environment, just as they would be if they were actually walking or running in the environment. Velocity that would have been implied by the movement step in order to put the player at the new location does not persist into the next frame.
To understand why this is important, consider the case where the player is walking forwards and encounters just the edge of a wall. What we want to have happen is for them to effectively "sidestep" the wall and continue moving forwards. What we do not want is to impart persistent sideways velocity sufficient to sidestep the wall thus continuing to move them laterally well after the point at which they have cleared the wall. This would lead to "arcing" around corners which would not make much sense if the idea is that the player is walking on two feet which are in static contact with the ground!
Hopefully that clears things up?
- Casey
Stated another way, the environment does not impart velocity in a walking simulator. The player is asking to walk, and it is assumed that they are under total control of their own movement. When they push up against a wall, we are assuming that the player is actually walking along the wall, not being glided along the wall by forcing themselves into the wall and letting the restitution push them diagonally.
Stated yet another way, I believe you are looking at this problem as if the player is in a dynamic friction state with respect to the environment. That's not what the goal is for this sort of system. The player is in a static friction state with respect to the environment, just as they would be if they were actually walking or running in the environment. Velocity that would have been implied by the movement step in order to put the player at the new location does not persist into the next frame.
To understand why this is important, consider the case where the player is walking forwards and encounters just the edge of a wall. What we want to have happen is for them to effectively "sidestep" the wall and continue moving forwards. What we do not want is to impart persistent sideways velocity sufficient to sidestep the wall thus continuing to move them laterally well after the point at which they have cleared the wall. This would lead to "arcing" around corners which would not make much sense if the idea is that the player is walking on two feet which are in static contact with the ground!
Hopefully that clears things up?
- Casey
Thank you very much for the elaborate explanation. The example where lateral velocity doesn't (shouldn't) persist is very insightful. I fully agree with your description of the intuitive (expected) behavior on user experience (macroscopic level).
> The problem here is that somehow you're generating some Y velocity that persists after interaction with the wall
The trajectory P->C->P2 is continuous and actual trajectory based on physics rules. Mapping it to the game, it happens within two frames, with pointer at P on frame 0, and point at P2 on frame 1. For sure, this would be very bad user experience if it's actually implemented in a game. In this sense, the velocity
don't need to be persistent to derive the conclusion that the point could end up below y=0. Well, my argument is possibly merely pedantic, because it's having significant displacement between two consecutive frames in a game is ridiculous.
Thanks again for your time and patience on explaining all this.
> The problem here is that somehow you're generating some Y velocity that persists after interaction with the wall
The trajectory P->C->P2 is continuous and actual trajectory based on physics rules. Mapping it to the game, it happens within two frames, with pointer at P on frame 0, and point at P2 on frame 1. For sure, this would be very bad user experience if it's actually implemented in a game. In this sense, the velocity
don't need to be persistent to derive the conclusion that the point could end up below y=0. Well, my argument is possibly merely pedantic, because it's having significant displacement between two consecutive frames in a game is ridiculous.
Thanks again for your time and patience on explaining all this.