2D 基于瓦片的环境中的射线投射
4.39/5 (9投票s)
一篇关于在2D瓦片环境中进行光线投射的文章。
引言
光线投射是一种广泛应用于3D环境的技术。它包括从给定位置沿给定方向投射“光线”。然后，该算法将告诉你诸如碰撞发生的位置、表面的法线等信息。在本文中，我将描述一种在2D瓦片环境中实现类似技术的方法。在你的游戏引擎中实现此技术可以为你带来诸如像素级精确碰撞检测等好处。
对于本文，我不会详细介绍加载或绘制2D场景。 我将只专注于2D光线投射技术。 这里描述的所有代码都可以在Scene和Tile类中找到。
使用代码
Tile类
为了实现这项技术，我们的Tile类需要具有两个主要属性：Bitmap和SolidityMap。Bitmap属性简单地包含瓦片的图形表示。SolidityMap属性是一个二维数组，它将告诉我们瓦片的哪些部分是实心的，哪些部分不是。可以使用每个像素的alpha值从位图构建此数组 - 如果像素是透明的，则可以穿过，否则是实心的（图1）。
图1：瓦片位图和实体图。
public class Tile {
private Bitmap bitmap;
private bool[,] solidityMap;
public void BuildSolidityMap() {
solidityMap = new bool[bitmap.Width, bitmap.Height];
for (int x = 0; x < bitmap.Width; x++) {
for (int y = 0; y < bitmap.Height; y++) {
// if the pixel is not transparent set
// the solidity map value to "true"
solidityMap[x, y] = bitmap.GetPixel(x, y).A != 0;
}
}
// We will need some additionnal processing here if the tile is
// transformed in some way
// (like horizontally or vertically flipped)
// I don't put the code here to keep it simple
// but if needed you can find it in Tile.cs
}
public bool[,] SolidityMap {
get { return solidityMap; }
}
public Bitmap Bitmap {
get { return bitmap; }
set { bitmap = value; }
}
}
检查像素是否可以穿过
在进行任何光线投射之前，我们需要能够确定场景的给定像素是否可以被光线穿过。我不会详细介绍，因为现在很明显如何使用我们的SolidityMap属性来实现它
// Find out if the given pixel is traversable.
// X and Y are the scene pixel coordinates
public bool IsPointTraversable(int x, int y) {
// Get the tile coordinates from the pixel coord.
int tileX = (int)Math.Floor((float)x / (float)tileSize);
int tileY = (int)Math.Floor((float)y / (float)tileSize);
// If the point is out of bound, we assume it's traversable
if (tileX < 0) return true;
if (tileX >= horizontalTileCount) return true;
if (tileY < 0) return true;
if (tileY >= verticalTileCount) return true;
Tile tile = GetTile(tileX, tileY);
// If the tile is blank the point is traversable
if (tile == null) return true;
// Get the coordinates of the point within the tile
int localPointX = x % tileSize;
int localPointY = y % tileSize;
// Return "true" if the pixel is not solid
return !tile.SolidityMap[localPointX, localPointY];
}
使用Bresenham算法投射光线
我们光线投射功能的核心将是良好的旧式Bresenham算法，经过44年后，它仍然是从A到B绘制（非抗锯齿）线的最快方法。网上有很多资源可以实现它。在这里，我选择实现Wikipedia上描述的优化版本。该函数将两个点作为输入，并将返回该线穿过的所有点的列表。此函数并非完全优化 - 最好提前计算该线将包含的点数，以便我们可以使用固定大小的数组而不是列表。它应该显着提高速度，特别是对于较长的线。无论如何，这是该函数
// Swap the values of A and B
private void Swap<T>(ref T a, ref T b) {
T c = a;
a = b;
b = c;
}
// Returns the list of points from p0 to p1
private List<Point> BresenhamLine(Point p0, Point p1) {
return BresenhamLine(p0.X, p0.Y, p1.X, p1.Y);
}
// Returns the list of points from (x0, y0) to (x1, y1)
private List<Point> BresenhamLine(int x0, int y0, int x1, int y1) {
// Optimization: it would be preferable to calculate in
// advance the size of "result" and to use a fixed-size array
// instead of a list.
List<Point> result = new List<Point>();
bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
if (steep) {
Swap(ref x0, ref y0);
Swap(ref x1, ref y1);
}
if (x0 > x1) {
Swap(ref x0, ref x1);
Swap(ref y0, ref y1);
}
int deltax = x1 - x0;
int deltay = Math.Abs(y1 - y0);
int error = 0;
int ystep;
int y = y0;
if (y0 < y1) ystep = 1; else ystep = -1;
for (int x = x0; x <= x1; x++) {
if (steep) result.Add(new Point(y, x));
else result.Add(new Point(x, y));
error += deltay;
if (2 * error >= deltax) {
y += ystep;
error -= deltax;
}
}
return result;
}
最后，实际的光线投射功能
RayCast()函数将执行光线投射。 光线将从给定的Position沿给定的Direction投射，并具有指定的RayLength（图2），并将返回一个RayCastingResult类，以允许我们在游戏中处理碰撞。
图2：Position、Direction和RayLength参数
// Class returned by the RayCast() method
public class RayCastingResult {
// Does the ray collide with the environment?
private bool doCollide;
// And if so, at which position?
private Vector position;
public bool DoCollide {
get { return doCollide; }
set { doCollide = value; }
}
public Vector Position {
get { return position; }
set { position = value; }
}
}
在RayCast()方法中，我们将首先使用Bresenham算法检索光线穿过的所有点的列表
List<Point> rayLine = BresenhamLine(position,
position + (direction.GetNormalized() * rayLength));
然后，我们将循环遍历所有这些点，从指定位置开始，直到光线的整个长度或直到找到碰撞点为止。 一旦找到该点，我们将退出循环并返回RayCastingResult实例。
while (true) {
Point rayPoint = rayLine[rayPointIndex];
if (!IsPointTraversable(rayPoint.X, rayPoint.Y)) {
result.Position = Vector.FromPoint(rayPoint);
result.DoCollide = true;
break;
}
有关更多详细信息，请参见完整的RayCast()方法
public RayCastingResult RayCast(Vector position,
Vector direction, float rayLength) {
RayCastingResult result = new RayCastingResult();
result.DoCollide = false;
// Exit the function now if the ray length is 0
if (rayLength == 0) {
result.DoCollide = IsPointTraversable((int)position.X,
(int)position.Y);
result.Position = position;
return result;
}
// Get the list of points from the Bresenham algorithm
List<Point> rayLine = BresenhamLine(position,
position + (direction.GetNormalized() * rayLength));
if (rayLine.Count > 0) {
int rayPointIndex = 0;
if (rayLine[0] != position) rayPointIndex = rayLine.Count - 1;
// Loop through all the points starting from "position"
while (true) {
Point rayPoint = rayLine[rayPointIndex];
if (!IsPointTraversable(rayPoint.X, rayPoint.Y)) {
result.Position = Vector.FromPoint(rayPoint);
result.DoCollide = true;
break;
}
if (rayLine[0] != position) {
rayPointIndex--;
if (rayPointIndex < 0) break;
} else {
rayPointIndex++;
if (rayPointIndex >= rayLine.Count) break;
}
}
}
return result;
}
性能
进行这种像素级精确光线投射可能看起来有点过度，但是，我发现它在游戏环境中合理使用时可用且快速。 最重要的是正确使用光线长度参数，并将其设置为尽可能小的值。 例如，如果在一个帧上，一颗子弹从A移动到B，则不要在整个场景中投射光线，而是将光线的长度限制为|B-A|。
在大多数情况下，光线将穿过几个空瓦片（这转化为许多快速的tile == null测试）。 一旦我们找到一个非空瓦片，在最坏的情况下，我们将有23个值要在SolidityMap数组中进行测试（对于16x16像素的瓦片）。 唯一可能出现问题的情况是，当尝试在具有许多孔的瓦片的场景中投射长光线时（图3）。 但是同样，将光线长度设置为适当的值应该可以消除问题。
图3：最坏的情况。 光线穿过的所有瓦片都不是空的，并且它们中间都有一个大孔。
参考文献
历史
- 2006年9月15日 - 文章的第一个版本。