a*算法流程图 unity3d
2016-06-14 02:43:22 akailee 阅读数 789
using UnityEngine;
using System.Collections;

public class YScript : MonoBehaviour {
	public GameObject cm;
	private float angle=0;
	private float r=5;
	// Use this for initialization
	void Start () {
		Vector3 center = new Vector3(0,0,0);
		for (int i=0; i<36; i++) {

			GameObject cube= GameObject.CreatePrimitive(PrimitiveType.Cube);
			float hudu=(angle/180)*Mathf.PI;
			float xx=center.x+r*Mathf.Sin(hudu);
			float yy=center.y+r*Mathf.Cos(hudu);
			cube.transform.position=new Vector3(xx,yy,0);

			cube.transform.LookAt(cm.transform.position);

			angle+=10;
		}
	}
	
	// Update is called once per frame
	void Update () {
	
	}
}

2018-08-11 17:35:13 liaoshengg 阅读数 1163

前言


在两个物体之间寻找最短有效路径

  1. 学习A*思想
  2. 其他算法,计算机估计距离
  3. 曼哈顿(城市街区算法、直来直去)
  4. 几何法(对角线,勾股定理)
  5. 估算法(先对角线,再直线)本文使用估算法计算距离
  6. GHF
  7. G : 从开始到当前位置的移动步数
  8. H : 从当前位置到目标位置的距离,使用上面3种算法获得
  9. F :G + H 的总和
  10. OpenList 和 CloseList
  11. OpenList :被考虑最短有效路径的位置集合
  12. CloseList : 不被考虑最短语效路径的位置集合
  13. 寻路思想:知道F = G + H 且知道如何计算得出,知道OpenList 和CloseList并知道如何得出

F G H 分别表示什么,有什么用,如何计算机它们?


  1. 首先得G表示的是从起始结点走到下一个结点(下下…下个)的距离,因此这个G是每走一格就会叠加一次并赋值给新的结点,从而累计得到从当前结点到下下下..个结点的距离
    newCostg = gCost + GetDistance()
    nodeCell.gCost = newCostg; //移动步数
  2. 其次是H,它表示从当前结点到终点结点的最短距离
  3. F 就是 G + H 得到的估算值

再根据百度百科的解释做个比较或许更容易理解:

f(n)=g(n)+h(n)
f(n) 是从初始状态经由状态n到目标状态的代价估计,
g(n) 是在状态空间中从初始状态到状态n的实际代价,
h(n) 是从状态n到目标状态的最佳路径的估计代价。
(对于路径搜索问题,状态就是图中的节点,代价就是距离)

这里需要写一个两点之间的距离估算方法,来计算得出G H 从而得出F
注意最好避免小数计算,
因为计算机计算机浮点的效率较低
而这里的x表示长 y表示高 可以通过画图理解,x = y 就是正方形,两点距离就是1.4 ,避免小数计算乘10 就是14整数了

    //计算距离 ,这里是因为NodeItem是嵌套类,在Grid里面 
    public int GetDistance(Grid.NodeItem a,Grid.NodeItem b) {
        //估算法
        int x = Mathf.Abs (a.x - b.x);
        int y = Mathf.Abs (a.y - b.y);
        //根号2 = 1.4  然后都扩大10倍 去除小数计算,这里返回值都放大了10倍
        if (x > y) {
            return 14 * y + 10 * (x - y);  
        }else{
            return 14 * x + 10 * (y - x);
        }
    //也可以用曼哈顿得到距离
    //return Mathf.Abs (a.x-b.x)+Mathf.Abs(a.y-b.y);//得到正数,但是可能是浮点数
    }

OpenList和CloseList是什么,可以用来做什么?


OpenList :被考虑最短有效路径的位置集合
CloseList : 不被考虑最短语效路径的位置集合

1、从第一个结点开始,放入OpenList容器,然后这个结点获取全部周围符合条件(1)的结点;
2、把符合条件的结点全部放入OpenList容器;
3、并且还要对周围符合条件(2)的每个结点进行更新他们的G值和H值,记录这个当前结点为它们的父结点;
4、然后把这第一个结点放入CloseList容器里 这是第一次循环

5、随后进入第二次循环,
此时就从OpenList容器找到符合条件(3)的当前结点,
当前结点是要在OpenList容器中H值最小,且F值最小的;
6、找到后就获取这个当前结点的周围结点,然后重新进入第2步骤到第5步骤;
7、此时它会慢慢接近终点,直到发现当前结点==最终结点;
8、最终结点找到后根据最终结点的父结点一个一个返回(类似数据结构的链表)找到开始结点;
9、此时用一个容器(List容器、Stack容器等)来接收这些结点,这些结点的Position就是最短路径

介绍符合条件:
第一个符合条件(1)是对周围结点的判断,该结点如果是标有墙类标记、或不可走标记就是不符合条件的,
第二个符合条件(2)是在满足第一个条件的前提下,在CloseList容器下遍历过,或更新后的G值比原来G值还要大的结点,2者不满足一个就是不满足条件,不能更新该结点的G,H值
第三个符合条件(3)就是存储在OpenList容器中的结点中,找一个H值最小,且, F值最小的结点,找到这个H值且F值最小的结点后,就把这个结点设置为当前结点。

当前结点在这里指为离终点结点的最短距离估计点。这个点其实并不会太智能,一下就找到最短路径。
而是根据OpenList里的全部结点来判断找到离终点最短估计值最小的结点,让周围的结点加入OpenList。然后就放入CloseList容器这个最短估计值最小的结点以后不再做任何判断。

CS脚本代码

结点类
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarNode {

    public bool isWall;
    public int posX;
    public int posY;
    public int posZ;

    public Vector3 pos;
    public AStarNode parentNode;

    public int costG;
    public int costH;

    public int CostF{
        get{ return costG + costH; }
    }

    public AStarNode(bool _isWall,Vector3 _pos,int _z,int _x){
        this.isWall = _isWall;
        this.pos = _pos;
        this.posX = _x;
        this.posZ = _z;
    }
}

结点地图生成类
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarMAP : MonoBehaviour {

    public AStarNode [,] AllNodeGroup; 

    public LayerMask wallLayer;
    public int xWidth;
    public int zHeight;
    private float nodeRange = 0.4f;

    public GameObject nodeWallPrefabs;

    void Awake(){
        Init();
    }

    void Init(){

        zHeight = 40;
        xWidth = 40;
        AllNodeGroup = new AStarNode[zHeight, xWidth];
        //初始化所有结点,把结点node存入二维数组里
        for (int i = 0; i < zHeight; i++) {
            for (int j = 0; j < xWidth; j++) {

                Vector3 nodePos =new Vector3 (j,0,i);
                nodePos += new Vector3 (0.5f, 0, 0.5f); 
                bool isWall = Physics.CheckSphere (nodePos, nodeRange, wallLayer);
                AStarNode nd = new AStarNode (isWall, nodePos,i,j);

                if (isWall) {
                    GameObject obj = GameObject.Instantiate (nodeWallPrefabs, nodePos, Quaternion.identity) as GameObject;

                }
                AllNodeGroup[i,j] = nd;

            }
        }
    }

    public List<AStarNode> GetAroundNodes(AStarNode curNode){

        List<AStarNode> retGroup = new List<AStarNode> ();
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                int z = curNode.posZ + i;
                int x = curNode.posX + j;

                if (x >= 0 && x < xWidth && z >= 0 && z < zHeight) {
                    retGroup.Add (AllNodeGroup [z, x]);
                }
            }
        }
        return retGroup;

    }

    public AStarNode GetItem(Vector3 pos){
        int x = Mathf.RoundToInt (pos.x - 0.5f);
        int z = Mathf.RoundToInt (pos.z - 0.5f);
        x = Mathf.Clamp (x, 0, xWidth - 1);
        z = Mathf.Clamp (z, 0, zHeight - 1);
        return AllNodeGroup [z, x];
    }
}
找最短路径类

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarFindPath : MonoBehaviour {

    private AStarMAP aStarMap;

    public List<Vector3> peoplePath;
    public List<AStarNode> peopleNodePath;

    void Start(){
        aStarMap = GetComponent<AStarMAP> ();
    }

    private int GetDistance(AStarNode startNode,AStarNode endNode){
        int x = Mathf.Abs (startNode.posX - endNode.posX);
        int z = Mathf.Abs (startNode.posZ - endNode.posZ);
        if (x > z) {
            return 10 * (x - z) + 14 * z;
        } else {
            return 10 * (z - x) + 14 * x;
        }
    }


    //根据开始和结束点来查找最优路径
    private void toFindPath(Vector3 startPos,Vector3 endPos) {

        //根据位置获取到NodeItem
        AStarNode start = aStarMap.GetItem (startPos);
        AStarNode end = aStarMap.GetItem (endPos);

        List<AStarNode> openList = new List<AStarNode> ();
        List<AStarNode> closeList = new List<AStarNode> ();

        openList.Add (start);
        //从开始点开始判断
        while (openList.Count > 0) {
            AStarNode curNode = openList [0];
            for (int i = 0; i < openList.Count; i++) {
                //h是估算法的距离  f是估算法加实际格子的距离g
                if (openList [i].CostF < curNode.CostF && openList [i].costH < curNode.costH) {
                    curNode = openList [i];
                }
            }

            openList.Remove (curNode);
            closeList.Add (curNode);

            //已经找到结束点
            if (curNode == end) {
                Debug.Log (">>");
                GetPathWithPos (startPos, endPos);
                return;
            }
            // 获取当前点的周围点
            List<AStarNode> nodeItemGroup =  aStarMap.GetAroundNodes(curNode);

            //遍历当前点周围的NodeItem 对其进行
            foreach (AStarNode nodeCell in nodeItemGroup) {
                //先过滤: 墙 closeList
                if (nodeCell.isWall || closeList.Contains (nodeCell)) {
                    continue;
                }

                //计算 G H F 进行赋值
                int newCostg = curNode.costG + GetDistance (curNode, nodeCell);

                if (newCostg <= nodeCell.costG || !openList.Contains (nodeCell)) {
                    //刷新g h
                    nodeCell.costG = newCostg; //移动步数距离
                    nodeCell.costH = GetDistance (nodeCell, end);//到该结点到终点的距离
                    //设置中心点为父亲
                    nodeCell.parentNode = curNode;
                    if (!openList.Contains (nodeCell)) {
                        openList.Add (nodeCell);
                    }
                }
            }
        }
    }

    //获取路径
    private void GetPathWithPos(Vector3 startPos,Vector3 endNodePos){
        //此处可以优化GC内存
        peopleNodePath = new List<AStarNode> ();
        peoplePath = new List<Vector3> ();

        AStarNode endNode = aStarMap.GetItem (endNodePos);
        AStarNode startNode = aStarMap.GetItem (startPos);

        if (endNode != null) {

            AStarNode temp = endNode;

            while (temp != startNode) {
                peoplePath.Add (temp.pos);
                peopleNodePath.Add (temp);
                temp = temp.parentNode;
            }
            peopleNodePath.Reverse ();
            peoplePath.Reverse ();
        }
    }
    //提供给人物移动类使用
    public List<Vector3> PeopleGoTo(Vector3 startpos,Vector3 endpos){
        toFindPath (startpos, endpos);
        return peoplePath;
    }

    public List<AStarNode> PeopleGoToWithNode(Vector3 startpos,Vector3 endpos){
        toFindPath (startpos, endpos);
        return peopleNodePath;
    }
}
人物移动实现类

这里是我以前实现了一个有点简单AI的A*移动,现在看起来有点丑,,还可以做优化,
实现的时候也可以发现:
A*算法可以做出接口来用的,不过需要根据需求情况设置一些值。
开始结点,最终点结点的位置(可自动获取开始结点位置,鼠标点击获取终点结点位置)
生成地图的大小,结点的大小,地图、结点坐标设计需要考虑
找到后的路径结点容器该怎么优化,实现是也是要考虑的

这里我使用了协程来写。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class PlayerTest : MonoBehaviour {

    AStarFindPath astarFindPath;
    public Vector3 endPos = new Vector3(12.5f,0,0.5f);
    RaycastHit hit;
    Ray ray;

    AStarNode currentNode;
    public bool isGO = true;
    List<AStarNode> pathGroupNode;
    void Awake(){
        astarFindPath = GetComponent<AStarFindPath> ();
    }
    void Start () {
        pathGroupNode = new List<AStarNode> ();
    }
    void Update(){
        peopleCtrl ();
    }
    void peopleCtrl(){
        if (Input.GetMouseButtonDown (0)) {
            ray = Camera.main.ScreenPointToRay (Input.mousePosition);
            if (Physics.Raycast (ray, out hit)) {
                endPos = hit.point;
                pathGroupNode.Clear ();
                i = 1;
                //执行A*算法
                pathGroupNode = astarFindPath.PeopleGoToWithNode (transform.position, endPos);
                if (pathGroupNode.Count <= 1) {
                    Debug.Log ("不需要走");
                    return;
                }
                currentNode = pathGroupNode [1];
                StopAllCoroutines ();
                StartCoroutine (pahtGo ());

            } else {
                Debug.Log ("重新点击");
            }
        }
    }
    IEnumerator pahtGo(){
        while (true) {
            if (Vector3.Distance (transform.position, currentNode.pos) <= 0.5f) {
                currentNode = pathGroupNode[i++];
                if (currentNode == null) {
                    Debug.Log ("到终点了...");
                    yield break;
                }   
                if (i >= pathGroupNode.Count) {
                    Debug.Log ("到达目的地");
                    yield break;
                }
            } else {
                transform.LookAt (currentNode.pos);
                transform.Translate (Vector3.forward * 2f * Time.deltaTime, Space.Self);
            }
            yield return new WaitForEndOfFrame ();
        }
    }
}

2017-08-01 10:19:34 BattleTiger 阅读数 5083

1.向量转四元数
Quaternion.LookRotation(dir);—>返回值就是一个四元数
2.开始旋转
transform.rotation = Quaternion.Lerp(当前的四元数, 目标四元数, 旋转的速度);
3.普通相机跟随

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class CameraMovement : MonoBehaviour {
    /// <summary>
    /// 跟随目标
    /// </summary>
    public Transform followTarget;
    /// <summary>
    /// 方向向量
    /// </summary>
    private Vector3 dir;

    private void Start()
    {
        //获取方向向量
        dir = transform.position - followTarget.position;
    }

    private void Update()
    {
        transform.position = dir + followTarget.position;
    }

}

4.高级相机跟随,保证看到目标的相机最佳视角

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class CameraMovement : MonoBehaviour {

    /// <summary>
    /// 俯视距离的偏移量
    /// </summary>
    public float offset = 0.5f;
    /// <summary>
    /// 设置中间的相机位置个数
    /// </summary>
    public int gears = 5;
    /// <summary>
    /// 跟随目标
    /// </summary>
    public Transform followTarget;
    /// <summary>
    /// 方向向量
    /// </summary>
    private Vector3 dir;
    /// <summary>
    /// 待选的相机位置(观察点)
    /// </summary>
    private Vector3[] readyPosition;
    /// <summary>
    /// 射线碰撞检测器
    /// </summary>
    private RaycastHit hit;
    /// <summary>
    /// 相机跟随的移动速度
    /// </summary>
    public int moveSpeed = 1;
    /// <summary>
    /// 相机旋转的速度
    /// </summary>
    public float turnSpeed = 10f;
    private void Start()
    {
        //获取方向向量
        dir = transform.position - followTarget.position;
        //实例化观察点数组
        readyPosition = new Vector3[gears];

    }

    private void Update()
    {
        //相机的起点--->相机最佳视角
        Vector3 begin = dir + followTarget.position;
        //相机的终点--->相机最差视角保证能看到玩家
        Vector3 end = followTarget.position + Vector3.up * (dir.magnitude - offset);
        //把起点和终点放到观察点的数组中
        readyPosition[0] = begin;
        readyPosition[readyPosition.Length - 1] = end;
        //获取相机中间点的位置
        for (int i = 1; i < readyPosition.Length - 1; i++)
        {
            //求中间点各个点的坐标,比例为i / (gears - 1)
            readyPosition[i] = Vector3.Lerp(begin, end, i / (readyPosition.Length - 1));
        }
        //备选方案--->前面所有的观察点都看不到玩家
        //都看不到就把相机放到最佳视角
        Vector3 watchPoint = begin;
        //遍历观察点数组,挑选我们最佳观察点
        for (int i = 0; i < readyPosition.Length; i++)
        {
            if (CheckWatchPoint(readyPosition[i]))
            {
                //设置观察点
                watchPoint = readyPosition[i];
                //得到观察点退出循环
                break;
            }
        }
        //相机平滑移动到最佳观察点
        transform.position = Vector3.Lerp(transform.position, watchPoint, Time.deltaTime * moveSpeed);
        /*
          //旋转的不是很平滑
          //相机旋转到最佳角度看向玩家
          transform.LookAt(followTarget);
         */
        //获取方向向量
        Vector3 lookDir = followTarget.position - watchPoint;
        //获取四元数
        Quaternion lookQua = Quaternion.LookRotation(lookDir);
        //平滑转向玩家
        transform.rotation = Quaternion.Lerp(transform.rotation, lookQua, Time.deltaTime * turnSpeed);
        //固定相机y轴z轴的旋转
        transform.eulerAngles = new Vector3(transform.eulerAngles.x, 0, 0);

    }
    /// <summary>
    /// 检测观察点是否可以看到目标
    /// </summary>
    /// <param name="point">待选的观察点</param>
    /// <returns><c>true</c>看得到<c>false</c>看不到</returns>
    bool CheckWatchPoint(Vector3 point)
    {
        if (Physics.Raycast(point,followTarget.position - point,out hit))
        {
            //如果射线检测到的是玩家
            if (hit.collider.tag == "Player")
            {
                return true;
            }
        }

        return false;
    }

}

相机跟随一直观察角色背部

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class CameraFollow : MonoBehaviour {

    public Transform target;
    public float distanceUp = 5f;
    public float distanceAway = 5f;
    public float smooth = 2f;//位置平滑移动值
    public float camDepthSmooth = 2f;
    // Use this for initialization
    void Start()
    {

    }

    // Update is called once per frame
    void Update()
    {
        // 鼠标轴控制相机的远近
        if ((Input.mouseScrollDelta.y < 0 && Camera.main.fieldOfView >= 3) || Input.mouseScrollDelta.y > 0 && Camera.main.fieldOfView <= 80)
        {
            Camera.main.fieldOfView += Input.mouseScrollDelta.y * camDepthSmooth * Time.deltaTime;
        }

    }

    void LateUpdate()
    {
        //相机的位置
        Vector3 disPos = target.position + Vector3.up * distanceUp - target.forward * distanceAway;
        transform.position = Vector3.Lerp(transform.position, disPos, Time.deltaTime * smooth);
        //相机的角度
        transform.LookAt(target.position);
    }


}
2018-10-23 16:14:56 Mr_chenxiansheng 阅读数 451

欢迎加入U3D交流群,群号码:308093702~~~~

先创建一个cube来作为中心点,并在程序中声明一个public变量。

再声明两个私有变量:半径r和角度angle。

在start()函数中,定义一个Vector3类型的变量center获取中心位置。在for循环中创建36个小cube,每个小cube通过三角函数进行位置计算后传给自己的position(有需要的改变缩放比例)。这时的圆环中每个cube是呈阶梯状的,需要用LookAt()函数来使小cube旋转指向center,这样的话圆环就更加光滑。最后角度逐步累积。

using UnityEngine;
using System.Collections;

public class CircleCS : MonoBehaviour 
{
    public GameObject cubeModel;
    private float r = 5;
    private float angle = 0;

    void Start ()
    {
       Vector3 center = cubeModel.transform.position;

        for (int i = 0; i < 36; i++)  //10度
        {
            GameObject cube = (GameObject)GameObject.Instantiate(cubeModel);
            float hudu = (angle / 180) * Mathf.PI;
            float xx = center.x + r * Mathf.Cos(hudu);
            float yy = center.y + r * Mathf.Sin(hudu);
            cube.transform.position = new Vector3(xx, yy, center.z);
//            cube.transform.localScale = new Vector3(1, 1, 5);
            cube.transform.LookAt(center);
            angle += 10;
        }
    }
}

运行结果:

Unity3D中的圆环算法

2017-04-10 22:08:19 Mogoson 阅读数 633

MGS-Backpack

概述

Unity3D 开发算法积累

文件

Converter.cs

  • ByteConverter:byte数组转bool,int16,int32,char,float,double
  • ArrayConverter:不同维数的数组相互转换
  • StructureConverter:byte数组与结构体相互转换

Exchanger.cs

  • 对象交换

GameObjectExtention.cs

  • 递归设置物体Layer

TerrainExtension.cs

  • 获取地形上某个位置对应到地形高度图中的位置
  • 获取地形上某个位置对应到地形贴图中的位置

TextureExtention.cs

  • 更新贴图像素

VectorExtension.cs

  • 计算旋转角度

BinaryFileOperater.cs

  • 大文本文件分页读取

BezierCurve.cs

  • 贝塞尔曲线公式

MathSmooth.cs

  • 三点线性拟合
  • 五点线性拟合
  • 七点线性拟合
  • 五点二次拟合
  • 七点二次拟合
  • 五点三次拟合
  • 七点三次拟合

Planimetry.cs

  • 平面几何定义,点,线,三角形,圆
  • 计算点,线,圆位置关系
  • 计算点,线,圆距离
  • 计算线,圆交点

源码

没有更多推荐了,返回首页