在两个单元格之间查找网格空间的算法

Question

我正在制作一款基于网格的游戏，该游戏具有“视线”定位。通常游戏引擎会为此使用 Raycast，但我不想使用引擎，所以我尝试“推出自己的”解决方案。

所以基本上，给定 P1,P2 对，我想找到它们之间的所有空格（标记为 X）。

我很难弄清楚如何做到这一点。我必须以某种方式找出哪些边靠得最近，并将它们用作“光线投射”的起点。然后我想我可以以单元格大小为增量获取“样本”，并将它们与单元格的索引进行比较。

不幸的是，我还没有任何代码...我希望有人可以提供一些伪代码来帮助获得算法。我想如果我能弄清楚如何获得每条粉红色线条的起点和终点，那么我就可以用它来找到橙色方块。

Answer 1

1. 显然，Bresenham algorithm在这里是个不错的选择。

我希望我可以 post 除了 link 之外的一些内容，但这无助于我提供完整的上下文。因此，最好访问 link 并使用那里的信息。不要错过评论部分。那里也有很好的见解。

2. 请也检查这个Elegant/Clean (special case) Straight-line Grid Traversal Algorithm?。