检查大量圈子碰撞的最佳方法是什么？
检测两个圆之间的碰撞非常容易,但是如果我们检查每个组合,则它是O(n 2),这绝对不是最佳解决方案.
我们可以假设circle对象具有以下属性:
速度是恒定的,但方向可以改变.
我想出了两个解决方案,但也许有更好的解决方案.
解决方案1将
整个空间划分为重叠的正方形,并仅检查与同一正方形的圆形的碰撞.正方形需要重叠,因此当圆从一个方格移动到另一个方格时不会出现问题.
解决方案2
在开始时,需要计算每对圆之间的距离.
如果距离很小,那么这些对存储在一些列表中,我们需要检查每次更新中的冲突.
如果距离很大,那么我们存储后更新可能会发生碰撞(可以计算,因为我们知道距离和速度).它需要存储在某种优先级队列中.在先前计算的更新数量之后,需要再次检查距离,然后我们执行相同的过程 - 将其放在列表中或再次放入优先级队列中.
Mark Byers的答案问题
在.NET中是否有像堆这样的类？我需要某种收集,我可以从中检索最小值.元件.我只想要3个方法:
我不能使用排序列表,因为键必须是唯一的,我可能有几个相同的元素.
我想使用openMP并行生成伪随机数,如下所示:
int i;
#pragma omp parallel for
for (i=0;i<100;i++)
{
printf("%d %d %d\n",i,omp_get_thread_num(),rand());
}
return 0;
我已经在Windows上测试了它,并且我获得了巨大的加速,但每个线程生成了完全相同的数字.我已经在Linux上测试了它并且我得到了巨大的减速,8核处理器上的并行版本比顺序慢了大约10倍,但是每个线程生成了不同的数字.
有没有办法同时加速和不同的数字？
编辑27.11.2010
我想我已经用乔纳森杜尔西的一个想法解决了这个问题.似乎下面的代码在linux和windows上运行得很快.数字也是伪随机的.你怎么看待这件事？
int seed[10];
int main(int argc, char **argv)
{
int i,s;
for (i=0;i<10;i++)
seed[i] = rand();
#pragma omp parallel private(s)
{
s = seed[omp_get_thread_num()];
#pragma omp for
for (i=0;i<1000;i++)
{
printf("%d %d %d\n",i,omp_get_thread_num(),s);
s=(s*17931+7391); // those numbers should be choosen more carefully
}
seed[omp_get_thread_num()] = s;
}
return 0;
}
PS.:我还没有接受任何答案,因为我需要确定这个想法是好的.
我写了一个组件来显示当前的FPS.
其中最重要的部分是:
public override void Update(GameTime gameTime)
{
elapseTime += (float)gameTime.ElapsedRealTime.TotalSeconds;
frameCounter++;
if (elapseTime > 1)
{
FPS = frameCounter;
frameCounter = 0;
elapseTime = 0;
}
base.Update(gameTime);
}
public override void Draw(GameTime gameTime)
{
spriteBatch.Begin();
spriteBatch.DrawString(font, "FPS " + ((int)FPS).ToString(), position, color, 0, origin, scale, SpriteEffects.None, 0);
spriteBatch.End();
base.Draw(gameTime);
}
在大多数情况下它工作正常,但最近我遇到了问题.
当我把下面的代码放入游戏的更新方法时,奇怪的事情开始发生.
if (threadPath == null || threadPath.ThreadState != ThreadState.Running)
{
ThreadStart ts = new ThreadStart(current.PathFinder.FindPaths);
threadPath = new Thread(ts);
threadPath.Priority = ThreadPriority.Highest;
threadPath.Start();
}
这段代码的主要思想是始终在不同的线程中运行pathFinding算法.
奇怪的是,我的意思是有时FPS急剧下降,这是显而易见的,但显示FPS变化的频率超过每秒一次.如果我理解这段代码,FPS每秒钟的变化不会超过一次.
有人可以解释一下发生了什么吗？
编辑26.03.2010 …
我有两个类似的代码.
第一
#pragma omp parallel for shared(g) private(i) schedule(dynamic, 1)
for(i = (*g).actualNumberOfChromosomes; i < (*g).maxNumberOfChromosomes; i++)
{
AddCrossoverChromosome(g, i); // it doesnt change actualNumberOfChromosomes
#pragma omp atomic
(*g).actualNumberOfChromosomes++;
}
第二
#pragma omp parallel for shared(g) private(i) schedule(static, 1)
for(i = (*g).actualNumberOfChromosomes; i < (*g).maxNumberOfChromosomes; i++)
{
AddCrossoverChromosome(g, i); // it doesnt change actualNumberOfChromosomes
#pragma omp atomic
(*g).actualNumberOfChromosomes++;
}
唯一的区别在于第一行.第一个代码工作正常,但第二个代码崩溃.为什么？
问题在某处actualNumberOfChromosomes,但我想了解原因,而不只是解决这个问题.我可以通过创建附加变量解决这个问题p,并分配actualNumberOfChromosomes给它,并改变环路,这样i等于p.
XNA没有任何支持圆绘图的方法.
通常当我不得不绘制圆形时,总是使用相同的颜色,我只是使用该圆形图像,然后我可以将其显示为精灵.
但是现在圈子的颜色是在运行时指定的,任何想法如何处理？
让我说我有4Byte整数,我想把它转换为2Byte短整数.我是对的,在(小和大端)短整数将包含这个4Byte整数的2个最低有效字节？
第二个问题:
小端和大端处理器中这些代码的结果是什么？
int i = some_number;
short s = *(short*)&i;
在大端处理器2中的恕我直言,将复制最重要的字节,在小端,将复制2个最低有效字节.
假设我们有一些具有有限数量的可能结果的离散分布,是否可以比O(logn)更快地从该分布生成随机数,其中n是数字可能的结果？
如何在O(logn)中创建它:
- 创建一个具有累积概率的数组(Array [i] =随机数将小于或等于i的概率)
- 从均匀分布生成随机数(让我们用k表示)
-找到最小的i,使得k <Array [i].它可以使用二进制搜索来完成.
- 我是我们的随机号码.
android有一个代表2D矢量的内置类吗？我需要对2D矢量做一些基本操作,例如:
我知道我可以编写自己的类,但如果有内置类,它会更优雅,更快.