4

我一直在做一个幼稚的小程序:屏幕上有一堆小圆圈,颜色和大小不一。当一个较大的圆圈遇到一个较小的圆圈时,它会吃掉较小的圆圈,当一个圆圈吃掉足够多的其他圆圈时,它就会繁殖。这有点整洁!

然而,我实现它的方式是,检测附近圆圈并检查它们是否可食用的过程是通过一个循环来完成的,该循环遍历整个活生生的圆圈群体......随着人口趋于激增,这需要越来越长的时间在它开始下降之前的3000。这个过程不会让我的电脑变慢,我可以去玩《战争黎明》或其他什么的,而且没有任何变慢:它只是检查每个圈子看它是否与其他圈子发生碰撞的过程。 .

所以我想到的是,我可以尝试将应用程序窗口分成四个象限,并让象限中的圆圈同时进行检查,因为它们几乎没有机会相互干扰:或者类似的东西!

那么,我的问题是:如何让 for 循环并排运行?在Java中,说。

4

7 回答 7

9

您在这里遇到的问题实际上可以在没有线程的情况下解决。

您需要的是空间数据结构。四叉树最好,或者如果球体移动的场是固定的(我假设是),您可以使用简单的网格。继承人的想法。

将显示区域划分为一个方形网格,其中每个单元格至少与您最大的圆圈一样大。对于每个单元格,保留一个列表(最好是链表),其中包含中心在该单元格中的所有圆圈。然后在碰撞检测步骤中遍历每个单元格并检查该单元格中的每个圆圈与该单元格和周围单元格中的所有其他圆圈。

从技术上讲,您不必检查每个单元格周围的所有单元格,因为其中一些单元格可能已经被检查过。

您可以将此技术与多线程技术结合使用,以获得更好的性能。

于 2008-11-08T07:16:16.380 回答
8

计算机通常是单任务的,这意味着它们通常可以每个 CPU 或内核一次执行一条指令。

但是,正如您所注意到的,您的操作系统(和其他程序)似乎同时运行许多任务。

这是通过将工作拆分为进程来实现的,每个进程都可以通过产生线程来进一步实现并发。操作系统然后在每个进程和线程之间非常快速地切换,从而产生多任务的错觉。

在您的情况下,您的 java 程序是一个进程,您需要创建 4 个线程,每个线程都运行自己的循环。它可能会变得很棘手,因为线程需要同步它们对局部变量的访问,以防止一个线程在另一个线程试图访问它时编辑一个变量。

因为线程是一个复杂的主题,所以需要比我在这里做的更多的解释。

但是,您可以阅读 Suns 优秀的并发教程,其中涵盖了您需要了解的所有内容:

http://java.sun.com/docs/books/tutorial/essential/concurrency/

于 2008-11-08T06:51:04.403 回答
5

您正在寻找的不是让这些同时运行的方法(正如人们所指出的,这取决于您拥有多少内核,并且只能提供 2 倍或 4 倍的加速),而是以某种方式减少您必须检测的碰撞次数。

您应该考虑使用四叉树。简而言之,您递归地将您的 2D 区域分解为四个象限(根据需要),然后只需要检测附近组件中的对象之间的碰撞。在好的情况下,它可以有效地将您的碰撞检测时间从 N^2 减少到 N * log N。

于 2008-11-08T07:00:31.950 回答
1

您可能希望寻找碰撞检测优化,而不是尝试进行并行处理。因为在很多情况下,在一个线程中执行较少的计算比在多个线程之间分配计算要好,而且在这种多线程业务中很容易自爆。尝试使用谷歌搜索“碰撞检测算法”,看看它在哪里;)

于 2008-11-08T18:23:27.623 回答
0

如果您的计算机有多个处理器或多个内核,那么您可以轻松运行多个线程并在每个线程中运行较小的循环部分。如今,许多 PC 确实有多个内核——所以要有它,以便每个线程获得循环计数的 1/n,然后创建 n 个线程。

于 2008-11-08T06:50:32.470 回答
0

如果你真的想进入并发编程,你需要学习如何使用线程。

Sun 在这里有一个 Java 线程编程教程:http: //java.sun.com/docs/books/tutorial/essential/concurrency/

于 2008-11-08T06:52:38.440 回答
0

这听起来和我的一个实验很相似——检查一下……

http://tinyurl.com/3fn8w8

我也对四叉树感兴趣(这就是我来这里的原因)......希望你能明白这一切。

于 2009-08-25T08:04:32.203 回答