标签：art 设置 贪心算法 list amp move 添加 tiles 感受
找了份新工作之后，忙的要死，都没时间鼓捣博客了，深深的感受到资本家的剥削，端午节连粽子都没有，每天下班累得跟条咸鱼一样(可能就是)。
刚好最近忙里偷闲，就来写写unity在2D下的AStar寻路算法。
地图用untiy的tilemap来贴。
大概的效果，没有去找好看的图片，将就弄点颜色表示：
黑色表示障碍，绿色表示路径，开头和结尾也是用的绿色，好懒o(╥﹏╥)o
原理和详细解释，还是参考的这位国外的大神：
https://www.redblobgames.com/pathfinding/a-star/introduction.html
解说如下：
A*算法其实可以理解为是贪心算法和广度优先搜索算法的结合体。
广度优先搜索算法，每次都可以找到最短的路径，每走一步都会记下起点到当前点的步数，优点是绝对能找到最短的路径，缺点就是地图越大计算量会变得很巨大。
贪心算法，每次都是走当前点距离终点最近的格子，在没有障碍的情况下效率很高，但是如果有障碍的话，就很绕路。
A*算法结合两者，计算当前走过的步数 与 当前点到终点的距离 之和作为走格子的依据，优点就是当有障碍物时，能找到最短距离并且计算量没有广度优先搜索大，没有障碍物时，效率和贪心算法一样高。
其实代码量没多少，直接贴出来了，具体也不解释，看注释吧，我好懒。
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Tilemaps;
public class MapBehaviour : MonoBehaviour
{
public Vector2Int mapSize;//地图尺寸
public Tilemap tilemap;
public Tile normalTile;//白色tile
public Tile obstacleTile;//黑色tile
public Tile pathTile;//绿色tile
public int obstacleCount;//要生成的障碍物数量
public Vector3Int startPos;//起点
public Vector3Int endPos;//终点
private bool hasStartPosSet;//是否设置了起点
private bool hasEndPosSet;//是否设置了终点
private Dictionary search = new Dictionary();//要进行的查找任务
private Dictionary cost = new Dictionary();//起点到当前点的消耗
private Dictionary pathSave = new Dictionary();//保存回溯路径
private List hadSearch = new List();//已经查找过的坐标
private List obstacle = new List();//障碍物坐标
private void Start()
{
CreateNormalTiles();
CreateObstacleTiles();
}
private void Update()
{
if (Input.GetMouseButtonDown(0))
{
if (!hasStartPosSet)//第一次点击设置起点
{
startPos = tilemap.WorldToCell(Camera.main.ScreenToWorldPoint(Input.mousePosition));
tilemap.SetTile(startPos, pathTile);
hasStartPosSet = true;
}
else if (!hasEndPosSet)//第二次点击设置终点
{
endPos = tilemap.WorldToCell(Camera.main.ScreenToWorldPoint(Input.mousePosition));
tilemap.SetTile(endPos, pathTile);
hasEndPosSet = true;
AStarSearchPath();
}
else//重置
{
hasStartPosSet = false;
hasEndPosSet = false;
foreach (var item in pathSave)
{
tilemap.SetTile(item.Key, normalTile);
}
search.Clear();
cost.Clear();
pathSave.Clear();
hadSearch.Clear();
}
}
}
//创建白色地图
public void CreateNormalTiles()
{
for (int i = 0; i blankTiles = new List();
for (int i = 0; i 0)
{
Vector3Int current = GetShortestPos();//获取任务列表里的最少消耗的那个坐标
if (current.Equals(endPos))
break;
List neighbors = GetNeighbors(current);//获取当前坐标的邻居
foreach (var next in neighbors)
{
if (!hadSearch.Contains(next))
{
cost.Add(next, cost[current] + 1);//计算当前格子的消耗，其实就是上一个格子加1步
search.Add(next, cost[next] + GetHeuristic(next, endPos));//添加要查找的任务，消耗值为当前消耗加上当前点到终点的距离
pathSave.Add(next, current);//保存路径
hadSearch.Add(next);//添加该点为已经查询过
}
}
}
if (pathSave.ContainsKey(endPos))
ShowPath();
else
print("No road");
}
//获取周围可用的邻居
private List GetNeighbors(Vector3Int target)
{
List neighbors = new List();
Vector3Int up = target + Vector3Int.up;
Vector3Int right = target + Vector3Int.right;
Vector3Int left = target - Vector3Int.right;
Vector3Int down = target - Vector3Int.up;
//Up
if (up.y = 0 && !obstacle.Contains(left))
{
neighbors.Add(target - Vector3Int.right);
}
//Down
if (down.y >= 0 && !obstacle.Contains(down))
{
neighbors.Add(target - Vector3Int.up);
}
return neighbors;
}
//获取当前位置到终点的消耗
private int GetHeuristic(Vector3Int posA, Vector3Int posB)
{
return Mathf.Abs(posA.x - posB.x) + Mathf.Abs(posA.y - posB.y);
}
//获取任务字典里面最少消耗的坐标
private Vector3Int GetShortestPos()
{
KeyValuePair shortest = new KeyValuePair(Vector3Int.zero, int.MaxValue);
foreach (var item in search)
{
if (item.Value
其实没什么难点，主要是理解，每次取出来计算下一步的点，是字典里面最少消耗值的那个点，然后每个点的消耗值都是，起点到当前的步数与当前到终点的距离(专业名词叫曼哈顿距离Manhattan distance2333)之和。
完结。
欢迎交流，转载注明出处！
unity利用A*算法进行2D寻路
标签：art 设置 贪心算法 list amp move 添加 tiles 感受
原文地址：https://www.cnblogs.com/JinT-Hwang/p/11141202.html