Android 设备上的每像素碰撞检测

引言

我目前正在我的 Android 设备上开发一款游戏，不用说，由于我想覆盖尽可能广泛的受众，因此我省略了硬件加速。因此，我需要编写最快的代码，使其能在大多数设备上运行。我从一个简单的 SurfaceView 开始，并使用工作线程对视图执行所有操作。然后，在测试过程中遇到了一个难题——我的碰撞检测算法在图像边框重叠时报告了误报——尽管图像本身并没有重叠。

背景

在本文中，我假设您已经了解碰撞检测的含义，并且熟悉 Java 编码。我还假设您对线程和其他 UI 元素有一定的基本了解。您只需了解基础知识即可，但一个明确的要求是您需要对图像如何在内存中布局有扎实的理解，即，计算机如何看待位图。

使用代码

一位经验丰富的 Java 开发人员可以在 15 分钟内将本文的核心概念编码出来，前提是框架（游戏、碰撞检测机制）已经到位。其他大多数开发人员，从初学者到中级，都可以在 1.5 小时内编码出本文的核心元素——考虑到它打破了流行的方法，这算是不错了。

已有哪些算法？

在我介绍这个相当简单的算法之前，我想花点时间简要介绍一下仅使用软件（无硬件加速）进行碰撞测试的最流行的方法。

• 旧式碰撞检测 - 迭代测试位图边界，直到边界矩形相交，此时报告碰撞。
• 边框优化碰撞检测 - 为位图设置“边框”以缩小要测试相交的矩形——当缩小区域相交时，报告碰撞。
• 逐像素碰撞检测 - 测试位图边界的相交。当相交发生时，测试两个位图的每个像素，以查看不透明像素是否重叠——如果发生重叠，则报告碰撞。

如您所见，普通开发者在决定实现哪种算法时有相当多的选择，但每种算法都有其缺点，让我们看看可能出现哪些潜在问题。

• 旧式碰撞检测 - 坦白说，此方法仅在位图是矩形且边缘没有透明区域时才可靠。这是实现最快（也最容易理解）的方法，但结果非常糟糕。
• 边框优化碰撞检测 - 当使用规则几何形状时，此方法稍为可靠，但需要添加额外的代码来区分位图尺寸及其包含的缩小图像，易于实现，但结果并不理想——可能会出现误报和漏报。
• 逐像素碰撞检测 - 这是大多数现代游戏的实际标准，但需要硬件加速才能避免游戏速度急剧下降。编写接近硬件的代码会有一个陡峭的学习曲线，尽管使用 OpenGL 等库可以简化这一点。无误报，需要中级到高级技能。

如您所见，每种方法都有其优缺点，但任何对接触硬件有顾虑的开发人员，或者只是不想承担硬件库学习曲线的开发人员，都可以放心，有一种方法可以在保持良好帧率的同时测试单个像素。

算法介绍

我称我的方法为 n 分布式逐像素碰撞检测算法，还有其他名称（例如，抖动碰撞检测、n 采样碰撞检测等），但这些名称要么文档不全，要么适用于大多数新手不愿深入研究的特定科学应用。我的方法实现起来非常简单，我们先编写一个非常简单的旧式碰撞检测算法（可以用边框优化碰撞检测替换，但会使代码更难阅读，并且对一般应用没有多大速度优势），然后，当我们找到相交区域时，我们不报告碰撞，而是报告一个“相交矩形”——这是一个描述两个位图重叠区域尺寸的矩形区域——聪明的程序员只需返回两个矩形结构（每个位图一个），分别描述各自原始位图的一个子区域。一旦我们有了相交区域，我们就将每个维度除以 n，这在软件光栅化时相当直观，并将我们要比较的像素数量在每个维度上减少 n 倍。让我们看一个例子：

如果我们取两个图像——我们称它们为精灵（技术术语，指屏幕上绘制的任何可移动位图——就我们而言，我们将使用此术语来描述任何可交互的绘制位图），尺寸为 200x200 像素。我们假设这些精灵在水平方向上相交，重叠 50 像素，这意味着第二个精灵的左边缘与第一个精灵的右边缘重叠 50 像素。通常我们会称之为碰撞然后结束，但对于我们的算法，我们增加了一个最后一步——遍历图像像素，在每个迭代中（在每个图像维度中）跳过 n 像素，只有当任何不透明像素重叠时才返回正面命中。此算法虽然仍受 CPU 限制，但速度比 n 数量级快。让我们来算算：对于逐像素碰撞检测算法，我们将比较两个源图像的每个像素，直到在图像的不透明区域找到重叠——我们不妨假设我们可能需要比较几乎所有图像的像素。如果精灵完全重叠，则需要 200 * 200 = 40000 次像素比较操作。对于改编的算法，我们可以使用任何小的任意数字来表示 n，我喜欢使用 n=2 以获得更好的结果。当 n = 2 时，我们比较 (200/n)*(200/n) = 100*100 = 10000 次像素比较。我们将比较次数减少了四分之三！在现实世界中，我们将主要使用更大的图像，并且主要比较图像的子区域，因此我们几乎总是比较少于 (宽度/n) * (高度/n) 像素——这在大多数情况下可以带来显着的加速。我喜欢尝试更大的 n 值，当精度不是限制因素时，这可以减少比较次数，让我们有更多的 CPU 用于其他游戏逻辑子系统——例如物理。

让我们看一些示例代码

我不对代码的正确性作任何声明，因此对于实施此处介绍的创意所可能产生的任何崩溃或混乱概不负责。

// This function is written specifically to test intersections only
// on the horizontal plane - meaning only sidelong collisions
// are reported - this is easily generalized to any/all axis(es)
boolean detectCollisions(Sprite sprite)
{
  //I assume that _sprites is an ArrayList<Sprite> which contains
  //the bounding regions of the sprites (As well as the bitmaps) we are hit testing.
  int n = 2;
  Rect overlap = new Rect(0, 0, 0, 0);
  for each (Sprite _object : _sprites)
  {
    if (intersect_rect(sprite.rect, _object.rect, overlap))
    //if the two rectangles intersect, we determine the intersect regions and perform the pixel test
    {
      //let's also pretend that we went through the schlep of figuring
      //out which rectangle is on the right and which is on the left
      //the intersect_rect functions returns the intersecting region
      //in the overlap rect, if the width and height are both non zero, then we have overlap!
      if (overlap.getWidth() && overlap.getHeight())
        if (intersect_pixels(overlap, n, sprite, _object))
          return true;  //if no collision is detected, then continue testing the rest of the sprites
    }
  }
}

//This function takes an ordered pair of sprites and tests their
//images using dithered algorithm to determine if opaque regions overlap
boolean intersect_pixels(Rect _overlapRegion, int n, Sprite left, Sprite right)
{
  for (int y = 0; y < _overlapRegion.Height() / n; y+=n)
  {
    for (int x = 0; x < _overlapRegion.Width() / n; x+=n)
    {
      //did not add test to check if pixel is on image bounds,
      //since overlapping region assumes to be within the bounds of BOTH images
      //the left image has its bounds starting BEFORE _overlapRegion
      int left_image_color = left.image.getPixel(_overlapRegion.left + x, _overlapRegion.top + y);
      //the right image has its bounds starting AT _overlapRegion
      int right_image_color = right.image.getPixel(x, y);
      if ((Color.alpha(left_image_colour) != 255) || (Color.alpha(right_image_colour) != 255))
        return true;  //there are non-transparent pixels which overlap!
     return false;
    }
  }
} 

请记住，您仍然需要编写 `intersect_rect` 函数——我将其留作一个很好的家庭练习。这里提供的大部分代码都是功能性的，并从我的游戏中提取。我故意省略了重叠区域测试函数作为读者的练习。

关注点

我最初编写的所有碰撞检测函数都严格用于矩形，但这很快就变得很糟糕，因为我需要额外的变量来跟踪循环索引，并且需要回调来通知发现了相交区域。我后来发现，将矩形和图像封装在一个名为 Sprite 的类中要简单得多，这样所有与 sprite 相关的函数都可以在一个方便的对象中访问。有趣的是，对于小图像，优化逐像素检测并非关键，因为循环迭代通常不会过多降低性能，但当图像宽度和高度超过 100 像素时，就需要进行智能像素测试，因为屏幕上有 10 个精灵（完全重叠，每个 100x100 像素）很快就会导致测试 10 * (100*100) * 10 * (100*100) 像素——或者（100 亿像素）。现代显卡可以在几毫秒内轻松测试这么多像素，但用软件执行相同的操作会拖慢最强大的处理器。我通常发现 n 的值直接与图像大小相关，并且测试表明，任何维度超过 200 像素的图像从更大的 n 值中受益匪浅——请注意，建议不要使用 n 值超过图像任何维度的值（例如，如果您的图像尺寸是 10x5，则 n 应该小于 5）。

历史

1 月 11 日 - 更新了文章源以更正语法错误。

目前，没有改进，因为该算法满足了我实现的性能要求。