【图形学】计算网格中两点连成的直线所经过的格子

注意，本文的算法是建立在格子坐标都是整数的前提下.

目的

因为做的游戏中有个攻击阻挡的需求(战棋类),就需要判断两个单位的连线上经过的格子中是否有障碍物的.那么就需要知道这个连线(线段)到底经过了哪些格子.本文则是针对此类问题的一个解决方案.

效果

算法到底对没对,看看这张动态图演示就一目了然了,红色是起点,鼠标所在处是终点,黑色的格子则代表图中经过的格子.（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