欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-05 14:31:54
注意,本文的算法是建立在格子坐标都是整数的前提下.目的因为做的游戏中有个攻击阻挡的需求(战棋类),就需要判断两个单位的连线上经过的格子中是否有障碍物的.那么就需要知道这个连线(线段)到底经过了哪些格子.本文则是针对此类问题的一个解决方案.效果算法到底对没对,看看这张动态图演示就一目了然了,红色是起点,鼠标所在处是终点,黑色的格子则代表图中经过的格子.(Unity中的Demo效果)几张静态图原理任何线段都可以通过平移方式,将起点平移到原点处,而陡峭的线段可以通过延y=x翻转(x,y进行交...

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

目的

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

效果

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