【图形学】计算网格中两点连成的直线所经过的格子
注意,本文的算法是建立在格子坐标都是整数的前提下.
目的
因为做的游戏中有个攻击阻挡的需求(战棋类),就需要判断两个单位的连线上经过的格子中是否有障碍物的.那么就需要知道这个连线(线段)到底经过了哪些格子.本文则是针对此类问题的一个解决方案.
效果
算法到底对没对,看看这张动态图演示就一目了然了,红色是起点,鼠标所在处是终点,黑色的格子则代表图中经过的格子.(Unity中的Demo效果)
几张静态图
原理
任何线段都可以通过平移方式,将起点平移到原点处,而陡峭的线段可以通过延y=x翻转(x,y进行交换),得到不陡峭的线段,所以无论参与计算是线段是哪种,都可以先通过平移,翻转等操作得到类型于下面这样的线段(在第一象限,起点在原点,且不陡峭),最终在通过逆变换推算出正常的结果即可,简化计算,只用考虑下面这一种情况的处理即可.
采用x方向每0.5为递增梯度的思路,初略的以1为单位递增的话不够精确,比如这样的:
第一种情况, 如下需要检测C,D,E三点,对于C和E在格子的相交点,则需要排除掉,既视为与周围四个格子都不接触,而D在格子中,则当前格子则视为接触点.
第二种情况, 如下需要检测CDEFG五个点,C,E,G处于边界上,所以C的左右两侧格子则判断为接触.
第三种情况,检测点在上下边界上,如下的C点,C在横向边界上,所以C的上下两个格子则视为接触.
完整代码:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// Created by Vitens on 2020/7/25 16:27:02
///
/// Description :
/// 涉及格子间的一些数学计算
/// </summary>
public class GridHelper
{
/// <summary>
/// 计算两点间经过的格子
/// </summary>
public static List<Vector2Int> GetTouchedPosBetweenTwoPoints(Vector2Int from, Vector2Int to)
{
List<Vector2Int> touchedGrids = GetTouchedPosBetweenOrigin2Target(to - from);
touchedGrids.Offset(from);
return touchedGrids;
}
/// <summary>
/// 计算目标位置到原点所经过的格子
/// </summary>
static List<Vector2Int> GetTouchedPosBetweenOrigin2Target(Vector2Int target)
{
List<Vector2Int> touched = new List<Vector2Int>();
bool steep = Mathf.Abs(target.y) > Mathf.Abs(target.x);
int x = steep ? target.y : target.x;
int y = steep ? target.x : target.y;
//斜率
float tangent = (float)y / x;
float delta = x > 0 ? 0.5f : -0.5f;
for (int i = 1; i < 2 * Mathf.Abs(x); i++)
{
float tempX = i * delta;
float tempY = tangent * tempX;
bool isOnEdge = Mathf.Abs(tempY - Mathf.FloorToInt(tempY)) == 0.5f;
//偶数 格子内部判断
if ((i & 1) == 0)
{
//在边缘,则上下两个格子都满足条件
if (isOnEdge)
{
touched.AddUnique(new Vector2Int(Mathf.RoundToInt(tempX), Mathf.CeilToInt(tempY)));
touched.AddUnique(new Vector2Int(Mathf.RoundToInt(tempX), Mathf.FloorToInt(tempY)));
}
//不在边缘就所处格子满足条件
else
{
touched.AddUnique(new Vector2Int(Mathf.RoundToInt(tempX), Mathf.RoundToInt(tempY)));
}
}
//奇数 格子边缘判断
else
{
//在格子交点处,不视为阻挡,忽略
if (isOnEdge)
{
continue;
}
//否则左右两个格子满足
else
{
touched.AddUnique(new Vector2Int(Mathf.CeilToInt(tempX), Mathf.RoundToInt(tempY)));
touched.AddUnique(new Vector2Int(Mathf.FloorToInt(tempX), Mathf.RoundToInt(tempY)));
}
}
}
if (steep)
{
//镜像翻转 交换 X Y
for (int i = 0; i < touched.Count; i++)
{
Vector2Int v = touched[i];
v.x = v.x ^ v.y;
v.y = v.x ^ v.y;
v.x = v.x ^ v.y;
touched[i] = v;
}
}
touched.Except(new List<Vector2Int>() { Vector2Int.zero, target });
return touched;
}
}
因为是在Unity环境运行的,所以用的是Vector2Int记录点的位置,这里有几个对List运算的扩展,为了使代码看起来更简洁,少些很多是否Contains的校验.
扩展脚本
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// Created by Vitens on 2020/7/25 16:31:43
///
/// Description :
/// 格子相关计算扩展
/// </summary>
public static class GridsExtension
{
//添加元素(如果已经有了则不需要重复添加)
public static void AddUnique(this List<Vector2Int> self, Vector2Int other)
{
if (!self.Contains(other))
{
self.Add(other);
}
}
//添加元素(如果已经有了则不需要重复添加)
public static void AddUnique(this List<Vector2Int> self, List<Vector2Int> others)
{
if (others == null)
return;
for (int i = 0; i < others.Count; i++)
{
if (!self.Contains(others[i]))
{
self.Add(others[i]);
}
}
}
//偏移
public static void Offset(this List<Vector2Int> self, Vector2Int offset)
{
for (int i = 0; i < self.Count; i++)
{
self[i] += offset;
}
}
//移除操作
public static void Except(this List<Vector2Int> self, List<Vector2Int> other)
{
if (other == null)
return;
for (int i = 0; i < other.Count; i++)
{
if (self.Contains(other[i]))
{
self.Remove(other[i]);
}
}
}
}
如果本文对您有帮助,不妨动动小指给个赞 O(∩_∩)O
本文地址:https://blog.csdn.net/Vitens/article/details/107588013
下一篇: 重温统计学--python实现概括性度量