如何预先计算台球游戏中的轨迹？
台球中的大多数碰撞检测算法都使用一种简单的方法，即球的位置递增，然后检查碰撞。当速度非常高时，这种方法效果不佳，因为我们可能会“跳过”碰撞。
我一直在寻找一种方法来预先计算台球游戏中球的轨迹。一旦知道了轨迹，我就可以为球设置动画，直到它们停止移动。而且我不必担心速度，因为碰撞是通过数学方法检测和解决的。
你知道是否有人这样做过吗？我不想重新发明轮子。 谢谢。
Most collision detection algorithm in billiard uses a naive approch, where the balls' positions are incremented and then checked for collisions. This method dosen't work well when the speed are really high because we might "skip" collisions.
I have been searching for a way to pre-calculate the trajectories of the balls in a billiard game. Once the trajectories are know, I can animate the balls until they stop moving. And I don't have to worry about the speed, because the collisions are mathematically detected and resolved.
Do you know if anyone has done that? I don't want to reinvent the wheel.
Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
从四叉树开始，缩小采样间隔。但是，如果您的台球移动速度太快以至于穿过其他球，则您对游戏的建模不正确。您是否曾经玩过球移动得那么快的台球游戏？
或者
在时间步之间，将球的先前位置和当前位置建模为二维圆柱体。如果任意两个圆柱体发生碰撞，则减小时间步长并重试。通过这种方式，您可以非常快速地进行一般计算，并且仍然可以处理超高速度。
Start with quadtrees and make your sampling interval smaller. If your billiard balls are moving so fast that they pass through other balls, however, you're modeling the game incorrectly. Have you ever played a game of billiards where the balls ACTUALLY moved that fast?
Alternatively
Between your time steps, model the ball's previous position and current position as a 2-Dimensional cylinder. If any two cylinders collide, make the time step smaller and try again. In this fashion, you get very quick general calculations, and you can still handle super high velocities.
最简单的方法是仅使用具有非常精细步长的“天真的”方法，但实际上尚未对球进行动画处理。
The easy way is to just use the "naive" approach with a very fine step size, but don't actually animate the balls yet.
我针对类似问题实施的一种解决方案是使用可变时间步长。
实现是这样的：你有一个时间参数化的方法来确定球的位置（在当前时间 T 加上可变时间 V）；默认值是指定 V 为 1.0。在计算更新位置时，可以执行碰撞检测；碰撞检测的自然伪像是碰撞发生时间的分数指示器。如果发生这种情况，请重置当前迭代的位置，并重新提交带有分数 V 的所有移动，然后迭代 1.0 - V 的量。
这效果出奇地好，并且具有相对简单的实现的优点。值得关注的一点是，您需要足够的 CPU 能力才能在“自然”时间片（即一个显示帧等）内多次计算移动。然而，由于这种类型的计算对于现代处理器来说非常容易，所以这应该不是问题。
One solution that I've implemented for something similar is to use variable time steps.
The implementation goes something like this: you have a time-parameterized method to determine ball position (at current time T plus variable time V); the default is to specify a V of 1.0. In your calculation of updated position, you can perform collision detection; the natural artifact of collision detection is a fractional indicator of when a collision occurs. If this occurs, reset your positions for the current iteration, and resubmit all the moves with the fractional V, then iterate over the amount 1.0 - V.
This works surprisingly well, and has the benefit of being a relatively simple implementation. One point of concern is that you need enough CPU power to be able to calculate moves potentially many times during a "natural" time slice (i.e., one display frame, etc.). However, since this type of calculation is pretty easy for modern processors, that shouldn't be a problem.
许多年前我做了类似的事情，并将球的运动描述为位置随时间的变化。使用这种方法，我能够找到任意两个球相交的准确时间。每个球都保留一个交叉时间最小的优先队列放在队列的头部，当发生碰撞时会调整队列。这非常有效，并且对于第一传球来说非常容易，没有对球的加速。后来（通过一些更难的数学）我还能够将其扩展到增加摩擦力的情况下。
这种方法的主要缺点是，计算往往会同时发生，然后一段时间什么都不发生，而不是每帧都能做一点工作。这意味着您的帧速率将不稳定。它并没有对我八年前运行的硬件造成任何明显的故障。即使在休息时，或者奇怪的或多或少不可能的情况，比如几个球在撞到墙上时完全接触并朝同一方向移动，帧率也会下降，但不会有任何明显的变化。
I did something similar many years ago and described the motion of the balls with position as a function of time. Using this method I was able to find the exact time of intersection for any two balls. Each ball kept a priority queue with the smallest intersection time at the head of the queue, and the queues would be adjusted when a collision occurred. This worked very well and was pretty easy for the first pass, which had no accelleration to the balls. Later (with some harder math) I was also able to extend it to work with friction added.
The main drawback to this method is that the calculations tend to happen all at once, then nothing for a while, instead of being able to do a little bit of work each frame. This means that your framerate will not be stable. It didn't cause any noticeable glitches on the hardware I was running 8 or so years ago. Even on the break, or strange more or less impossible cases like several balls exactly touching and moving in the same direction when they hit the wall the would be a dip in framerate, but not anything noticeable.