0

这是我的问题。

我的游戏，为了高效的渲染和碰撞被划分为区域。每个区域中都会有许多动态移动的对象。当他们移动时，我确定他们在哪些区域。

这意味着和对象可以在多个区域中。

如果我知道对象 A 在区域 1 和 2 中并且对象 B 也在区域 1 和 2 中，那么会发生什么我会做：

for each object in region 1 and 2
if A collides with B...

我会有效地检查同一对两次。

我该怎么做才能只检查一次？是否有我应该使用的数据结构或算法？

4

4 回答 4

1

如果您可以对 objects 进行排序，那么您只需要检查a < b排序所在的对。可以是任何东西：数组中的索引、指针（对于允许指针值访问的语言来说是这样）。

for(Object a : list) {
    for(Object b : list) {
        if (a.compare(b) < 0) {

非常简单，实际上可以解决问题。

如果你有整数索引存储，你可以这样做

for(int i = 0; i < list.length; i++) {
    for(int j = i + 1; j < list.length; j++) {

你不会得到重复的。这适用于任意类型，ArrayList但可能不适用于任意类型。您也许可以克隆一些迭代器，但我不会打赌...

for(Iterator<Object> iter = list.iterator(); iter.hasNext(); ) {
    Object a = iter.next();
    Iterator<Object> iter2 = iter.clone();
    for(;iter2.hasNext();) {
        Object b = iter.next();

但说真的，这是一个黑客。如果它适用于所有 java 集合，我会感到惊讶。使用 Java 迭代器的一种更可靠但同样骇人听闻的解决方法：

for(Object a : list) {
    Iterator<Object> biter = list.iter();
    while(biter.next() != a) { };
    for(; biter.hasNext(); ) {
        Object b = biter.next();

一般来说，java foreach 语法for(Clazz object : iterable) {是“可爱的”，但远不如s强大。Iterator事实上，上面的旧整数 for 循环也很有魅力。

于 2012-11-08T20:11:46.280 回答
0

不，可能是您的网格太小了。边界框在碰撞检测方面也不是很好，您可以避免空白区域，但要以插入和删除为代价。

于 2012-11-08T18:40:10.270 回答
0

为什么不存储以前计算的结果？

实际上，它将变为：

for each object in region 1 and 2
    if results doesn't contain (A collides with B)
       ...
       results = result of (A collides with B)
于 2012-11-08T17:59:35.260 回答
0

Instead of a regular spaced grid you could use a quadtree ( http://en.wikipedia.org/wiki/Quadtree ), which lends itself better to index objects of varying size. Instead of having to pick a single cell size (which might be too big for some objects and too small for others), you can let the quadtree determine the appropriate cell size.

However, even then you can't prevent a single object from occuring in multiple tree nodes, but this shouldn't be a goal that you should try to achieve - the only thing you should prevent is that every object occurs in tens or hundreds of cells or Quadtree nodes, because that does hurt performance.

Hence, if all your objects are about the same size, a regular grid might still be the best choice as long as the cells are at least as large (or maybe twice as large?) as your objects.

于 2012-11-08T20:07:06.430 回答