★csdn的算法高手们,有问题向大家求助

mngzilin 2010-07-23 07:58:46
问题描述:
现有大小不同圆形粒子若干,在一水平平面上运动,运动规律不用关心,现在关注的重点是粒子碰撞检测

传统的算法:
算法一:缩小时间间隔,定时检测是否相交,就是遍历粒子,看两粒子间距是否大于粒子半径和。但是这种不精确,可能出现粒子轨迹交叉度太大而无法检测到。淘汰!~~
算法二:包围盒检测,由于要求精确度较高,这种算法淘汰!~~~
算法三:在短时间间隔中检测粒子运动轨迹(直线)是否相交。这种精确度高,但是时间复杂度太大,淘汰!~~
算法四:N叉树。即划分网格,检查粒子所在网格的就近网格里面的粒子。这种算法要求粒子大小相同。淘汰!~~

这里的难点是粒子大小不同。目前可用算法一,将时间分隔成足够小的片段来检测。但是遍历粒子过程中耗时太长。

大家畅所欲言,只要算法原理即可,不用代码

望大家不吝赐教!~~
...全文
960 134 打赏 收藏 转发到动态 举报
写回复
用AI写文章
134 条回复
切换为时间正序
请发表友善的回复…
发表回复
mngzilin 2010-07-26
  • 打赏
  • 举报
回复
[Quote=引用 121 楼 yuxh81 的回复:]
不会,帮顶!

碰撞检测,游戏开发中也有这一说
不知道是否可借鉴一下
[/Quote]

游戏中检测不精确,这是精确模拟
yuxh81 2010-07-26
  • 打赏
  • 举报
回复
不会,帮顶!

碰撞检测,游戏开发中也有这一说
不知道是否可借鉴一下
denbes 2010-07-26
  • 打赏
  • 举报
回复
up
学习下.
mngzilin 2010-07-26
  • 打赏
  • 举报
回复
[Quote=引用 116 楼 ybfqzm 的回复:]
技术上我不是很懂。
但我有一个想法。
如果,都是圆形,大小也知道的情况下。
在第个粒子出现时,设置每个粒子的半径 + 1。
对每个坐标点进行 扫描 如果一个点上,有两个圆形。
那么证明他们碰撞。

这种方法不用考虑,粒子的个数。

只是一个想法,希望能忙上!
[/Quote]

因为在实际的地球坐标上面计算碰撞,所以关于像素的说法都不可取。
mngzilin 2010-07-26
  • 打赏
  • 举报
回复
如果扫描像素点的话,速度会慢很多,我的卫星图片在海湾的部分是2048*2048的大小。

上面有朋友说的“线段树”我真研究可用程度。
mngzilin 2010-07-26
  • 打赏
  • 举报
回复
其实大家都没说到点子上:

1.算法二可以精确找出速度过快的碰撞

2.主要是要实现减少 “找出与其中一个粒子相碰撞的其他点所需要的计算次数”,目前算法四方法可参考,但是网格大小划分没实现,因为粒子大小不同。

正纠结中.....


晚上回来结贴,满三天了!~~~
ybfqzm 2010-07-26
  • 打赏
  • 举报
回复
技术上我不是很懂。
但我有一个想法。
如果,都是圆形,大小也知道的情况下。
在第个粒子出现时,设置每个粒子的半径 + 1。
对每个坐标点进行 扫描 如果一个点上,有两个圆形。
那么证明他们碰撞。

这种方法不用考虑,粒子的个数。

只是一个想法,希望能忙上!
loveSoftandhxy 2010-07-26
  • 打赏
  • 举报
回复
网格,将粒子大小扩大,虚拟成统一大小,就近碰撞,与之前大小比较后缩减。
xiaowx2000 2010-07-26
  • 打赏
  • 举报
回复
能不能这样。给屏幕中所有像素编号。然后获取所有粒子在某个时间点包括进去的像素。如果某一像素出现一次以上就判定碰撞
hwbox 2010-07-26
  • 打赏
  • 举报
回复
[Quote=引用 111 楼 hwbox 的回复:]
开一个5000的list<>,记录当前球的半径,位置,速度,方向。再开5000*5000的存储区。计算任意两个球碰撞的时间(无视其它球)。找出第一时间碰撞的两个球(有多个球同一时间同时碰撞的,也一样),刷新5000个球的初始信息。再次计算下一次碰撞。运算量是N的平方。
[/Quote]

不好意思,运算量是2*(N的平方)
捷哥1999 2010-07-26
  • 打赏
  • 举报
回复
好贴,围观一下。
hwbox 2010-07-26
  • 打赏
  • 举报
回复
开一个5000的list<>,记录当前球的半径,位置,速度,方向。再开5000*5000的存储区。计算任意两个球碰撞的时间(无视其它球)。找出第一时间碰撞的两个球(有多个球同一时间同时碰撞的,也一样),刷新5000个球的初始信息。再次计算下一次碰撞。运算量是N的平方。
在路上20130607 2010-07-26
  • 打赏
  • 举报
回复
不懂的路过 帮顶
mngzilin 2010-07-26
  • 打赏
  • 举报
回复
时间已到,结贴了!~~~

谢谢大家!!~~~~~~
mngzilin 2010-07-26
  • 打赏
  • 举报
回复
[Quote=引用 132 楼 litaoye 的回复:]
既然要求精确解,我可以帮LZ简单分析一下这个问题。

采用划分网格的方法,起源于算法中的分治思想,也就是说不用拿每个粒子和剩余的n-1个粒子去比较(n是粒子个数),而是先把粒子分到网格里面,这个复杂度是O(n)。然后只要和附近的几个网格内的例子判断碰撞就可以了,假设划分了10000个网格,平均每个格子里面不到1个粒子,检测周围9个格的话,大概只需要处理9次,复杂度就是9*10000,这里可以称……
[/Quote]

其实划分网格主要是粒子大小不同,而传统的划分网格只是在粒子大小一致时候才可行。
假设如果我选择了这个,就抛弃了快速粒子的检测。

关于“线段树”,其实我认为还是要划分网格后才能用。不知意下如何。我在118#中有些许的肯定。但是还需要进一步研究下。
绿色夹克衫 2010-07-26
  • 打赏
  • 举报
回复
既然要求精确解,我可以帮LZ简单分析一下这个问题。

采用划分网格的方法,起源于算法中的分治思想,也就是说不用拿每个粒子和剩余的n-1个粒子去比较(n是粒子个数),而是先把粒子分到网格里面,这个复杂度是O(n)。然后只要和附近的几个网格内的例子判断碰撞就可以了,假设划分了10000个网格,平均每个格子里面不到1个粒子,检测周围9个格的话,大概只需要处理9次,复杂度就是9*10000,这里可以称为O(m*k),m是网格的数量,k是搜索范围。

不过网格方法的前提是要划分最小的时间粒度(实际上是一个3维的网格)。才好知道如何把每个粒子划分到具体对应的网格。如果不漏解的话,这个时间粒度就不能够太大。比如每次都搜索临近的8个格子的话,最快的粒子就不能在这个单位时间里穿过这8个格子,否则会产生漏解。这样的话要么扩大搜索范围,要么减少这个单位时间,都会增加计算的复杂度。另外,粒子的面积如果过大,甚至超过了单位网格的大小,那么需要搜索的范围也会跟着扩大。此外采用网格还会出现某些极端情况,比如所有的粒子都很小,并且在同一个网格里面,极端情况算法会退化为n^2。

假设粒子速度都非常快,但个头都很小,采用上面的网格的方法,时间粒度也许会被划分的很小,在整个平面很大的情况下,其实碰撞概率并不高,也许每分钟才出现一次碰撞,那么这个算法的复杂度。也许还会高于直接用解析的方法计算2个粒子之间的碰撞。
bidisty 2010-07-26
  • 打赏
  • 举报
回复
以最小圆形半径为距离做网格,求网格内有两个以上圆的边数的网格位置。
得网格位置后求圆是否相交,得结果。
lanse20_2010 2010-07-26
  • 打赏
  • 举报
回复
不懂。学习学习
yanlingoffice 2010-07-26
  • 打赏
  • 举报
回复
数学没学好
绿色夹克衫 2010-07-26
  • 打赏
  • 举报
回复
对于这个问题,需要评估各种方法以及具体实现的复杂度,这点从头到尾几乎没有看到LZ做过仔细的分析。另外LZ可能并没有看明白所有好的建议。比如楼上gbb21同志提到的线段树,也许LZ还并不清楚这种数据结构,那么当然就会一直抱着5000*5000的想法(用线段树应该可以解决用网格时,会出现极限情况的问题)。

其实不要说解决5000个粒子的问题,假设只是2个粒子,在一个很大的空间里面高速运动,应该怎么设计这个算法?基础问题没有解决的话,是很难在上面建楼的,不过反过来说,这又是多么难得的一个机会,可以让我们认真的去学习运用算法方面的知识。

LZ所列举的几种常用的算法,应该是由前辈们积累下来的(只是我的猜测,具体情况我也不懂),相信很难在短时间找出更好的方法来解决这个问题。但仔细说起来,其实都不能叫做算法,只是一种方法,具体的算法是要在实现当中体现的,这些相对细节的地方,才是体现算法设计能力的关键,只是到现在还没有讨论到这一层。

[Quote=引用 119 楼 mngzilin 的回复:]
因为在实际的地球坐标上面计算碰撞,所以关于像素的说法都不可取。
[/Quote]
加载更多回复(107)
内容简介: 无论你是从事业务开发,还是从事架构设计,想要优化设计模式,数据结构与算法是必备的一门学科,本课程使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。为什么学数据结构与算法算法是一个程序员真正的核心竞争力。无论用哪种语言做开发,算法从程序角度而言都是灵魂内核般的存在。程序的躯体可以各式各样,但是内核一定要追求高效整洁。同时掌握了算法,大厂名企的Offer不再是梦寐以求的梦想,而让程序高效且健壮,也不再是难以完成的技术难题。所以无论是为提升自我内功修炼,还是提升程序灵魂内核健全,学习算法,都是现有可供选项里的最优解。课程大纲:为了让大家快速系统了解数据结构与算法知识全貌,我为你总结了「数据结构与算法框架图」,帮你梳理学习重点,建议收藏!! CSDN学院Java答疑群:

110,499

社区成员

发帖
与我相关
我的任务
社区描述
.NET技术 C#
社区管理员
  • C#
  • Web++
  • by_封爱
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告

让您成为最强悍的C#开发者

试试用AI创作助手写篇文章吧