首页 > 资讯 > 后端开发 > 其他教程 >C# AStar寻路算法详解

136

分享到

C# AStar寻路算法详解

C# AStar寻路算法 C# A*寻路算法 C# 寻路算法 2023-05-14 05:05:14 136人浏览八月长安

摘要

目录概述思路代码示例位置定义方向定义估值函数节点定义算法上下文定义寻路算法初始化获取路径寻路完整代码概述 AStar算法是一种图形搜索算法，常用于寻路。他是以广度优先搜索为基础，集D

概述

AStar算法是一种图形搜索算法，常用于寻路。他是以广度优先搜索为基础，集Dijkstra算法和最佳优先(best fit)于一身的一种算法。

示例1:4向

示例2:8向

思路

递归的通过估值函数找到最佳路径，估值函数与距离相关，也有可能与通过代价系数相关（例如平地系数为1，坡地系数为2），有三个参数：

G：起点点到当前点的代价
H: 当前点到终点的代价
F: F = G + H 与最佳路径权重负相关的参数

过程大概：

代码示例

位置定义

public struct Vec2
{
    public int x;
    public int y;

    public Vec2(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public static Vec2 Zero
    {
        get
        {
            return new Vec2(0, 0);
        }
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Vec2))
            return false;

        var o = (Vec2)obj;
        return x == o.x && y == o.y;
    }

    public override int GetHashCode()
    {
        return x.GetHashCode() + y.GetHashCode();
    }

    public static Vec2 operator +(Vec2 a, Vec2 b)
    {
        return new Vec2(a.x + b.x, a.y + b.y);
    }

    public static Vec2 operator *(Vec2 a, int n)
    {
        return new Vec2(a.x * n, a.y * n);
    }

    public static Vec2 operator *(int n, Vec2 a)
    {
        return new Vec2(a.x * n, a.y * n);
    }

    public static bool operator ==(Vec2 a, Vec2 b)
    {
        return a.x == b.x && a.y == b.y;
    }

    public static bool operator !=(Vec2 a, Vec2 b)
    {
        return !(a.x == b.x && a.y == b.y);
    }
}

方向定义

public enum EDir
{
    Up = 0,
    Down = 1,
    Left = 2,
    Right = 3,
    UpLeft = 4,
    UpRight = 5,
    DownLeft = 6,
    DownRight = 7,
}

public abstract class CheckDirPol
{
    abstract public Dictionary<EDir, Vec2> GetDir();
}

public class CheckDir4Pol : CheckDirPol
{
    private Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2>
    {
        {EDir.Up, new Vec2(0, 1) },
        {EDir.Down, new Vec2(0, -1) },
        {EDir.Left, new Vec2(-1, 0) },
        {EDir.Right, new Vec2(1, 0) },
    };
    override public Dictionary<EDir, Vec2> GetDir()
    {
        return dirDict;
    }
}

public class CheckDir8Pol : CheckDirPol
{
    private Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2>
    {
        {EDir.Up, new Vec2(0, 1) },
        {EDir.Down, new Vec2(0, -1) },
        {EDir.Left, new Vec2(-1, 0) },
        {EDir.Right, new Vec2(1, 0) },
        {EDir.UpLeft, new Vec2(-1, 1) },
        {EDir.UpRight, new Vec2(1, 1) },
        {EDir.DownLeft, new Vec2(-1, -1) },
        {EDir.DownRight, new Vec2(1, -1) },

    };
    override public Dictionary<EDir, Vec2> GetDir()
    {
        return dirDict;
    }
}

运用策略模式的技巧，以实现4向，8向搜索切换

估值函数

public abstract class EvaPol
{
	abstract public float Calc(Vec2 a, Vec2 b);
}

public class MANEvaPol : EvaPol
{
    override public float Calc(Vec2 a, Vec2 b)
    {
        return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
    }
}

直接使用曼哈顿距离作为代价

节点定义

public class node
{
    public int id;
    public Vec2 pos;
    public float g;
    public float h;
    public float f;
    public Vec2 prePos;
    public bool hasPrePos;

    public Node(Vec2 pos)
    {
        this.pos = pos;
    }

    public void SetPrePos(Vec2 pos)
    {
        prePos = pos;
        hasPrePos = true;
    }
}

算法上下文定义

Context context;
EvaPol disPol;
CheckDirPol checkDirPol;

public struct Context
{
    public Vec2 end;
    public Vec2 start;
    public Node[,] nodes;
    public List<Node> open;
    public List<Node> close;
    public int[,] map;
    public List<Vec2> result;
    public Vec2 size;
}

寻路算法

初始化

public void Init(Vec2 start, Vec2 end, int[,] map)
{
	var x = map.GetLength(0);
	var y = map.GetLength(1);
	context = new Context()
	{
		start = start,
		end = end,
		open = new List<Node>(),
		close = new List<Node>(),
		map = map,
		result = new List<Vec2>(),
		size = new Vec2(x, y),
	};

	context.nodes = new Node[x, y];
	for (int i = 0; i < x; i++)
		for (int j = 0; j < x; j++)
			context.nodes[i, j] = new Node(new Vec2(i, j));

	disPol = new MANEvaPol();
	//checkDirPol = new CheckDir4Pol();
	checkDirPol = new CheckDir8Pol();
}

获取路径

public List<Vec2> GetResult()
{
	return context.result;
}

寻路

寻路入口

public void FindPath()
{
	var s = context.start;
	var sn = context.nodes[s.x, s.y];
	sn.g = 0;
	sn.h = disPol.Calc(s, context.end);
	sn.f = sn.g + sn.h;
	context.open.Add(sn);

	FindArrangement(sn);
}

递归函数

void FindArrangement(Node node)
{
	context.close.Add(node);
	context.open.Remove(node);

	if (node.pos == context.end)
	{
		SetResult(node);
		return;
	}

	CheckRound(node);
	if (context.open.Count == 0)
		return;

	Node next = context.open[0];
	for (int i = 1; i < context.open.Count; i++)
		if (context.open[i].f < next.f)
			next = context.open[i];

	FindArrangement(next);
}

检查周围节点

void CheckRound(Node node)
{
	var dirDict = checkDirPol.GetDir();
	foreach (var pair in dirDict)
	{
		var dir = node.pos + pair.Value;

		if (IsBlock(dir))
			continue;
		var dn = context.nodes[dir.x, dir.y];

		if (context.close.Contains(dn))
			continue;

		if (context.open.Contains(dn))
			TryOverridePath(node, dn);
		else
		{
			dn.g = disPol.Calc(dn.pos, context.start);
			dn.h = disPol.Calc(dn.pos, context.end);
			dn.f = dn.g + dn.h;
			dn.SetPrePos(node.pos);
			context.open.Add(dn);
		}
	}
}

// 若是从邻节点到该节点路径更优，则替换更新
void TryOverridePath(Node a, Node b)
{
	var g = a.g + disPol.Calc(a.pos, b.pos);
	if (g < b.g)
	{
		b.g = g;
		b.SetPrePos(a.pos);
	}
}

bool IsBlock(Vec2 pos)
{
	return !InMap(pos) || context.map[pos.x, pos.y] == 1;
}

bool InMap(Vec2 pos)
{
	var x = pos.x;
	var y = pos.y;
	var size = context.size;
	return x >= 0 && x < size.x && y >= 0 && y < size.y;
}

生成路径

void SetResult(Node node)
{
	Queue<Node> q = new Queue<Node>();
	while(node.hasPrePos)
	{
		q.Enqueue(node);
		node = context.nodes[node.prePos.x, node.prePos.y];
	}
	while(q.Count > 0)
	{
		context.result.Add(q.Dequeue().pos);
	}
}

完整代码

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

public struct Vec2
{
    public int x;
    public int y;

    public Vec2(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public static Vec2 Zero
    {
        get
        {
            return new Vec2(0, 0);
        }
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Vec2))
            return false;

        var o = (Vec2)obj;
        return x == o.x && y == o.y;
    }

    public override int GetHashCode()
    {
        return x.GetHashCode() + y.GetHashCode();
    }

    public static Vec2 operator +(Vec2 a, Vec2 b)
    {
        return new Vec2(a.x + b.x, a.y + b.y);
    }

    public static Vec2 operator *(Vec2 a, int n)
    {
        return new Vec2(a.x * n, a.y * n);
    }

    public static Vec2 operator *(int n, Vec2 a)
    {
        return new Vec2(a.x * n, a.y * n);
    }

    public static bool operator ==(Vec2 a, Vec2 b)
    {
        return a.x == b.x && a.y == b.y;
    }

    public static bool operator !=(Vec2 a, Vec2 b)
    {
        return !(a.x == b.x && a.y == b.y);
    }
}

public enum EDir
{
    Up = 0,
    Down = 1,
    Left = 2,
    Right = 3,
    UpLeft = 4,
    UpRight = 5,
    DownLeft = 6,
    DownRight = 7,
}

public class AstarFindPath
{
    public class Node
    {
        public int id;
        public Vec2 pos;
        public float g;
        public float h;
        public float f;
        public Vec2 prePos;
        public bool hasPrePos;

        public Node(Vec2 pos)
        {
            this.pos = pos;
        }

        public void SetPrePos(Vec2 pos)
        {
            prePos = pos;
            hasPrePos = true;
        }
    }

    public abstract class EvaPol
    {
        abstract public float Calc(Vec2 a, Vec2 b);
    }

    public class MANEvaPol : EvaPol
    {
        override public float Calc(Vec2 a, Vec2 b)
        {
            return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
        }
    }

    public abstract class CheckDirPol
    {
        abstract public Dictionary<EDir, Vec2> GetDir();
    }

    public class CheckDir4Pol : CheckDirPol
    {
        private Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2>
        {
            {EDir.Up, new Vec2(0, 1) },
            {EDir.Down, new Vec2(0, -1) },
            {EDir.Left, new Vec2(-1, 0) },
            {EDir.Right, new Vec2(1, 0) },
        };
        override public Dictionary<EDir, Vec2> GetDir()
        {
            return dirDict;
        }
    }

    public class CheckDir8Pol : CheckDirPol
    {
        private Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2>
        {
            {EDir.Up, new Vec2(0, 1) },
            {EDir.Down, new Vec2(0, -1) },
            {EDir.Left, new Vec2(-1, 0) },
            {EDir.Right, new Vec2(1, 0) },
            {EDir.UpLeft, new Vec2(-1, 1) },
            {EDir.UpRight, new Vec2(1, 1) },
            {EDir.DownLeft, new Vec2(-1, -1) },
            {EDir.DownRight, new Vec2(1, -1) },

        };
        override public Dictionary<EDir, Vec2> GetDir()
        {
            return dirDict;
        }
    }

    public struct Context
    {
        public Vec2 end;
        public Vec2 start;
        public Node[,] nodes;
        public List<Node> open;
        public List<Node> close;
        public int[,] map;
        public List<Vec2> result;
        public Vec2 size;
    }

    Context context;
    EvaPol disPol;
    CheckDirPol checkDirPol;

    public void Init(Vec2 start, Vec2 end, int[,] map)
    {
        var x = map.GetLength(0);
        var y = map.GetLength(1);
        context = new Context()
        {
            start = start,
            end = end,
            open = new List<Node>(),
            close = new List<Node>(),
            map = map,
            result = new List<Vec2>(),
            size = new Vec2(x, y),
        };
        
        context.nodes = new Node[x, y];
        for (int i = 0; i < x; i++)
            for (int j = 0; j < x; j++)
                context.nodes[i, j] = new Node(new Vec2(i, j));

        disPol = new MANEvaPol();
        //checkDirPol = new CheckDir4Pol();
        checkDirPol = new CheckDir8Pol();
    }

    public void FindPath()
    {
        var s = context.start;
        var sn = context.nodes[s.x, s.y];
        sn.g = 0;
        sn.h = disPol.Calc(s, context.end);
        sn.f = sn.g + sn.h;
        context.open.Add(sn);
        
        FindArrangement(sn);
    }

    public List<Vec2> GetResult()
    {
        return context.result;
    }

    void FindArrangement(Node node)
    {
        context.close.Add(node);
        context.open.Remove(node);

        if (node.pos == context.end)
        {
            SetResult(node);
            return;
        }

        CheckRound(node);
        if (context.open.Count == 0)
            return;

        Node next = context.open[0];
        for (int i = 1; i < context.open.Count; i++)
            if (context.open[i].f < next.f)
                next = context.open[i];
        
        FindArrangement(next);
    }

    void SetResult(Node node)
    {
        Queue<Node> q = new Queue<Node>();
        while(node.hasPrePos)
        {
            q.Enqueue(node);
            node = context.nodes[node.prePos.x, node.prePos.y];
        }
        while(q.Count > 0)
        {
            context.result.Add(q.Dequeue().pos);
        }
    }

    void CheckRound(Node node)
    {
        var dirDict = checkDirPol.GetDir();
        foreach (var pair in dirDict)
        {
            var dir = node.pos + pair.Value;

            if (IsBlock(dir))
                continue;
            var dn = context.nodes[dir.x, dir.y];

            if (context.close.Contains(dn))
                continue;

            if (context.open.Contains(dn))
                TryOverridePath(node, dn);
            else
            {
                dn.g = disPol.Calc(dn.pos, context.start);
                dn.h = disPol.Calc(dn.pos, context.end);
                dn.f = dn.g + dn.h;
                dn.SetPrePos(node.pos);
                context.open.Add(dn);
            }
        }
    }

    void TryOverridePath(Node a, Node b)
    {
        var g = a.g + disPol.Calc(a.pos, b.pos);
        if (g < b.g)
        {
            b.g = g;
            b.SetPrePos(a.pos);
        }
    }

    bool IsBlock(Vec2 pos)
    {
        return !InMap(pos) || context.map[pos.x, pos.y] == 1;
    }

    bool InMap(Vec2 pos)
    {
        var x = pos.x;
        var y = pos.y;
        var size = context.size;
        return x >= 0 && x < size.x && y >= 0 && y < size.y;
    }
}

到此这篇关于C# AStar寻路算法详解的文章就介绍到这了,更多相关C# AStar寻路算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C# AStar寻路算法详解

本文链接: https://www.lsjlt.com/news/202749.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

C# AStar寻路算法详解

目录概述思路代码示例位置定义方向定义估值函数节点定义算法上下文定义寻路算法初始化获取路径寻路完整代码概述 AStar算法是一种图形搜索算法，常用于寻路。他是以广度优先搜索为基础，集D...

99+

2023-05-14

C# AStar寻路算法 C# A*寻路算法 C# 寻路算法
C# AStar寻路算法怎么使用

这篇文章主要讲解了“C# AStar寻路算法怎么使用”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C# AStar寻路算法怎么使用”吧！概述AStar算法是一种图形搜索算...

99+

2023-07-05
C#中Astar寻路算法怎么实现

以下是一种基本的A*寻路算法的实现示例，可以用于C#语言：```csharpusing System;using System.Co...

99+

2023-09-22

C#
如何用C++实现A*寻路算法

目录一、A*算法介绍二、A*算法步骤解析三、A*算法优化思路3.1、openList使用优先队列（二叉堆）3.2、障碍物列表，closeList 使用二维表（二维数组）3.3、深度限...

99+

2024-04-02
C++ DFS算法实现走迷宫自动寻路

C++ DFS算法实现走迷宫自动寻路，供大家参考，具体内容如下深度优先搜索百度百科解释：事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Searc...

99+

2024-04-02
java寻路算法怎么实现

Java中的寻路算法可以使用图的搜索算法来实现。以下是一个简单的示例，使用BFS（广度优先搜索）算法来寻找路径。```javaimp...

99+

2023-09-22

java
C++ DFS算法如何实现走迷宫自动寻路

小编给大家分享一下C++ DFS算法如何实现走迷宫自动寻路，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！C++ DFS算法实现走迷宫自动寻路，供大家参考，具体内容...

99+

2023-06-15
C++ 基于BFS算法的走迷宫自动寻路的实现

目录1.效果图2.实现代码1.队列方法类2.地图方法类3.main函数3.思路1.效果图其中正方形代表障碍物，实心菱形代表移动者（人），空心菱形代表目标位置（都是可以在代码中修改...

99+

2024-04-02
Java C++ 算法题解leetcode652寻找重复子树

目录题目要求思路一：DFS+序列化JavaC++Rust思路二：DFS+三元组JavaC++Rust总结题目要求思路一：DFS+序列化设计一种规则将所有子树序列化，保证不同子...

99+

2024-04-02
C# 递归算法详解

目录1）1、1、2、3、5、8.......用递归算法求第30位数的值？2）编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）斐波那契数列为：0、1、1、2、3、……...

99+

2024-04-02
js中A*寻路算法原理的示例分析

这篇文章主要为大家展示了“js中A*寻路算法原理的示例分析”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“js中A*寻路算法原理的示例分析”这篇文章吧。简易地图如...

99+

2024-04-02
C/C++最短路径算法之迪杰斯特拉Dijkstra的实现详解

目录前言一、迪杰斯特拉（Dijkstra）算法是什么二、实现步骤1.算法思路2.进入主函数ShortestPath()1.创建final数组并且初始化path[]、dist[]数组2...

99+

2024-04-02
C++归并排序算法详解

目录一.算法简介二.实现过程总结一.算法简介归并排序算法的平均时间复杂度是O(nlo...

99+

2024-04-02
C++最短路径Dijkstra算法的分析与具体实现详解

目录前言Dijkstra 算法分析初始条件第一轮第二轮及以后Dijkstra 代码实现输入输出格式时间复杂度前言经典的求解最短路径算法有这么几种：广度优先算法、Dijkstra算法...

99+

2023-03-10

C++最短路径Dijkstra算法 C++最短路径算法 C++ Dijkstra算法
详解Dijkstra算法之最短路径问题

目录一、最短路径问题介绍二、Dijkstra算法介绍2.1、算法特点2.2、算法的思路三、Dijkstra算法示例演示四、Dijkstra算法的代码实现（c++）一、最短路径问题介绍...

99+

2024-04-02
GoJava算法之简化路径实例详解

目录简化路径方法一：栈（Java）方法二：标准库（Go）简化路径给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格绝对路径（以 '/'...

99+

2024-04-02
路径规划 | 详解维诺图Voronoi算法(附ROS C++/Python/Matlab仿真)

目录 0 专栏介绍 1 维诺图规划原理 2 ROS C++实现(栅格图搜索) 3 Python实现(路图搜索) 4 Matlab实现(路图搜索) 0 专栏介绍 🔥附C++/P...

99+

2023-08-30

ROS 机器人自动驾驶人工智能路径规划原力计划
C++并查集算法简单详解

目录1、并查集的初始化2、并查集的查找操作3、并查集的合并操作4、为什么要路径压缩？5、实现路径压缩总结1、并查集的初始化并查集是用一个数组实现的。首先先定义一个数组： int f...

99+

2024-04-02
C BlowFish对称加密算法详解

1.算法原理 BlowFish算法基于Feistel网络，加密函数迭代执行16轮，分组长度为64位，密钥长度可以从32位到448位。算法由两部分组成，密钥扩展部分和数据加密部分，密钥...

99+

2024-04-02
C#算法设计与分析详解

目录1. 什么是科学方法？？1.观察2.将问题规模和运行时间的关系量化2.数学模型近似近似运行时间成本模型总结3. 增长数量级的分类4. 倍率实验5.注意事项6. 处理对于输入的依赖...

99+

2024-04-02