qq群接口对股票跟踪交易-A Star 寻路算法代码实现

基于基本原理,逐一实现算法中的功能

创建一个格子类里面包含每个格子节点的信息;

using System.Collections;
using System.Collections.Generic;
//格子类型
public enum E_Node_Type
{
    //可以走的地方
    Walk,
    //障碍
    Stop,
}

/// <summary>
/// A*格子类 每个格子需要包含的具体信息有那些
/// </summary>
public class AStarNode
{
    //格子对象的坐标
    public int x;
    public int y;

    //寻路消耗;
    public float f;
    //离起点的距离
    public float g;
    //离终点的距离
    public float h;
    //父对象
    public AStarNode father;
    //格子的类型
    public E_Node_Type type;
    /// <summary>
    /// 构造函数 传入坐标和格子类型 初始化单个格子对象
    /// </summary>
    /// <param name="x"></param>
    /// <param name="y"></param>
    /// <param name="type"></param>
    public AStarNode(int x,int y,E_Node_Type type)
    {
        this.x = x;
        this.y = y;
        this.type = type;
    }
}

AStarManager,单例管理类,方便外部直接调用,在这里我们实现A*的核心代码逻辑

通常的单例:

//管理器的单例
    //私有对象
    private static AStarManager instance;
    public static AStarManager Instance
    {
        get
        {
            if(instance == null)
                instance = new AStarManager();
                return instance;
        }
    }

5个必要的成员:

地的宽高,用来后续初始化地以及对节点的合法性判断

AStarNode类型的二维数组,用来存放地上所有格子的容器

A Star 寻路算法代码实现

开启和关闭列表

 //地图的宽高
    private int mapW;
    private int mapH;

    //存放地图上所有格子的容器
    private AStarNode[,] nodes;
    //开启列表
    private List<AStarNode> openList;
    //关闭列表
    private List<AStarNode> closeList;

先来初始化一个基本的地信息,创建这个方法,也会用到上方设定的地变量

public void InitMapInfo(int w,int h)//传入宽高 初始化地图
    {
        //根据宽高 创建格子 阻挡的问题 我们可以随机阻挡
        //因为我们没有地图相关的数据

        //初始化二维数组 地图多大 数组就多大
        nodes = new AStarNode[w, h];

        //for循环生成地图格子 一列一列生成格子
        for (int i = 0; i < w; i++)
        {
            for (int j = 0; j < h; j++)
            {
                //传入格子坐标 格子类型 在0~100的范围内随机取值 如果小于20就是障碍类型 大于20就是可行走的格子
                AStarNode node = new AStarNode(i, j, Random.Range(0, 100) < 20 ? E_Node_Type.Stop:E_Node_Type.Walk);
                //初始化后 装入容器
                nodes[i, j] = node;
            }
        }
    }

最核心的方法,寻路代码的实现,返回值是一个路径,也就是说,传入起点和终点两个参数,得到最短路径

首先判断传入的这两个点是否合法,也就是说这两个点均为超出地范围

 public List<AStarNode> FindPath(Vector2 starPos,Vector2 endPos)//传入两个参数 起点和终点
    {
        //实际项目中 传入的点应该是坐标系中的位置 进行换算 这个坐标是在具体哪个格子的范围内
        //我们这个省略换算的步骤 直接认为传入的是格子

        //首先判断传入的两个点是否合法
        //1.首先 要在地图范围内 判断起点和终点的x,y轴的范围都不能超出地图的范围
        if (starPos.x < 0 || starPos.y >= mapW || starPos.y < 0 || starPos.y >= mapH || endPos.x < 0 || endPos.y >= mapW || endPos.y < 0 || endPos.y >= mapH)
        {
            Debug.Log("开始或结束点在格子范围外");
            //如果不合法 应该直接 返回null 意味着不能寻路
            return null;
        }

判断是否是阻挡障碍,我们在初始化地的时候已经随机生成了障碍,由于给定的参数是V2类型的两个点,所以在一开始就对此进行类型转换,方便后续的使用

根据传入的起点和终点的信息,转换为AStarNode类型的两个点,然后进行阻挡判断

 //2.是不是阻挡 根据两个点的坐标信息 取出来进行判断 因为参数类型是Vector2类型 坐标参数一定会是float,需要进行强制转换
        AStarNode start = nodes[(int)starPos.x, (int)starPos.y];
        AStarNode end = nodes[(int)endPos.x, (int)endPos.y];
        if (start.type == E_Node_Type.Stop || end.type == E_Node_Type.Stop)
        {
            Debug.Log("开始或结束点是阻挡");
            return null;
        }

清空上一次相关的数据,避免影响这一次的寻路计算该函数是会被多次调用的,所以在每次执行的时候都要清空一次不然会保留上一次寻路所留下的列表信息

//清空上一次相关的数据,避免影响这一次的寻路计算
        //该函数是会被多次调用的,所以在每次执行的时候 都要清空一次 不然会保留上一次寻路所留下的列表信息
        closeList.Clear();
        openList.Clear();
        //每次的起点都是一个新的起点 所以起点的信息也要被清空
        start.father = null;
        start.f = 0;
        start.g = 0;
        start.h = 0;

将起点放入关闭列表中

从起点开始寻找周围的八个点这个八个点在合法的前提下无非是和起点的坐标不同罢了

找到这合法的八个点放入开启列表当中先将寻找方法的逻辑单独写出来因为是找八个方便复用

每个点都要计算出F值记录父对象

/// <summary>
    /// 找到周围的八个点放入开启列表当中
    /// </summary>
    /// <param name="x"></param>
    /// <param name="y"></param>
    private void Find8NearlyNodesToOpenList(int x,int y,float g,AStarNode father,AStarNode end)
    {
        //地图边界判断
        if (x<0||x>=mapW||y<0||y>=mapH)
        {
            return;
        }
        AStarNode node = nodes[x, y];
        //判断这些点是否是边界 是否是阻挡 如果都不是 才放入开启列表
        if (node==null||node.type==E_Node_Type.Stop||closeList.Contains(node)||openList.Contains(node))
        {
            return;
        }
        //计算F值
        //f = g + h;
        //记录父对象
        node.father = father;
        //计算g 离起点的距离就是父节点距离起点的距离+当前点距离父节点的距离
        node.g = father.g + g;
        node.h = Mathf.Abs(end.x - node.x) + Mathf.Abs(end.y - node.y);//曼哈顿街区算法
        node.f = node.g + node.h;
        //如果通过了上面的合法验证 就存到开启列表当中去
        openList.Add(node);
    }

找到这八个点后进行排序,取出最优点,每次取出最优点后都进行判断是否是终点,是终点就回溯,不是就继续搜索,直到找到终点为止,或者一直没找到终点,开启列表最后都滞空了,那就是死路

文章为作者独立观点，不代表股票交易接口观点