服装鞋帽商城网站建设,vps主机搭建wordpress,安卓应用开发工程师,嘉定装饰装修网站注意#xff1a;
本文是对基于下方文章链接的理论#xff0c;并最终代码实现#xff0c;感谢作者大大的描述#xff0c;非常详细#xff0c;流程稍微做了些改动#xff0c;文末有工程网盘链接#xff0c;感兴趣的可以下载。
A*算法详解(个人认为最详细,最通俗易懂的一…注意
本文是对基于下方文章链接的理论并最终代码实现感谢作者大大的描述非常详细流程稍微做了些改动文末有工程网盘链接感兴趣的可以下载。
A*算法详解(个人认为最详细,最通俗易懂的一个版本)-CSDN博客
1、效果演示 2、A*算法流程
1 把起点加入 open list 。
2 重复如下过程 a. 遍历 open list 查找 F 值最小的节点把它作为当前要处理的节点。 b. 对当前方格的 8连通的每一个方格 ◆ 如果它是不可抵达的或者它在 close list 中忽略它。否则做如下操作。 ◆ 如果它不在 open list 中把它加入 open list 并且把当前方格设置为它的父亲记录该方格的 F G 和 H 值。 ◆ 如果它已经在 open list 中检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样把它的父亲设置为当前方格并重新计算它的 G 和 F 值。 c. 把这个节点移到 close list 。 d. 停止当你 ◆ 把终点加入到了 open list 中此时路径已经找到了或者 ◆ 查找终点失败并且 open list 是空的此时没有路径。
3 保存路径。从终点开始每个方格沿着父节点移动直至起点这就是你的路径。
3、代码
逻辑层Node结点定义
using UnityEngine;public enum GridState
{Empty,Block,
}
public class Node
{public GridState curState;public int X;public int Y;public int F;public int G;public int H;public Node parentNode;public Node(int x, int y){X x;Y y;ResetNode();}public void ResetNode(){curState GridState.Empty;F 0;G 0;H 0;parentNode null;}public void CalculateValue(Node endNode){if (parentNode null) return;//计算GG GetPredictGValue(parentNode);//曼哈顿距离计算HH Mathf.Abs(endNode.X - X) Mathf.Abs(endNode.Y - Y);F G H;}public int GetPredictGValue(Node targetNode){int predictG 0;//四连通if (targetNode.X X || targetNode.Y Y){predictG targetNode.G 10;}//八连通else{predictG targetNode.G 14;}return predictG;}}寻路算法
using System.Collections.Generic;public partial class PathFind
{private ListNode openList;private ListNode closeList;private Node[,] allNodeList;public void AStarInit(Node[,] allNodes){openList new ListNode();closeList new ListNode();allNodeList allNodes;}public void FindRoad(Node startNode, Node endNode){openList.Add(startNode);LoopFindRoad(endNode);}private void LoopFindRoad(Node endNode){//找到终点或者不存在路径if (openList.Count 0||openList.Contains(endNode)){return;}//找到F值最小的Node smallestFNode null;for (int i 0; i openList.Count; i){if (smallestFNode null){smallestFNode openList[i];continue;}if (openList[i].FsmallestFNode.F){smallestFNode openList[i];}}//获得八连通格子ListNode eightAdjacent GetRoundNode(smallestFNode);//更新代价for (int i 0; i eightAdjacent.Count; i){//不在openList里面if (!openList.Contains(eightAdjacent[i])){eightAdjacent[i].parentNode smallestFNode;eightAdjacent[i].CalculateValue(endNode);openList.Add(eightAdjacent[i]);}else{//判断是否需要更新F,G,Hif (eightAdjacent[i].GetPredictGValue(smallestFNode) eightAdjacent[i].G){eightAdjacent[i].parentNode smallestFNode;eightAdjacent[i].CalculateValue(endNode);}}}//转移结点openList.Remove(smallestFNode);closeList.Add(smallestFNode);LoopFindRoad(endNode);}/// summary/// 获得八连通格子中可达到并且不在closeList中的格子/// /summary/// returns/returnsprivate ListNode GetRoundNode(Node targetNode){int x targetNode.X;int y targetNode.Y;ListNode tempList new ListNode();if (IsReachableNode(x, y 1)) tempList.Add(allNodeList[x, y 1]);if (IsReachableNode(x 1, y 1)) tempList.Add(allNodeList[x 1, y 1]);if (IsReachableNode(x 1, y)) tempList.Add(allNodeList[x 1, y]);if (IsReachableNode(x 1, y - 1)) tempList.Add(allNodeList[x 1, y - 1]);if (IsReachableNode(x, y - 1)) tempList.Add(allNodeList[x, y - 1]);if (IsReachableNode(x - 1, y - 1)) tempList.Add(allNodeList[x - 1, y - 1]);if (IsReachableNode(x - 1, y)) tempList.Add(allNodeList[x - 1, y]);if (IsReachableNode(x - 1, y 1)) tempList.Add(allNodeList[x - 1, y 1]);return tempList;}/// summary/// 判断格子是否可到达/// /summary/// param namex/param/// param namey/param/// returns/returnsprivate bool IsReachableNode(int x, int y){if (x allNodeList.GetLength(0) || x 0){return false;}if (y allNodeList.GetLength(1) || y 0){return false;}if (allNodeList[x, y].curState GridState.Block){return false;}if (closeList.Contains(allNodeList[x, y])){return false;}return true;}
}4、补充
如果希望过障碍时不允许他斜向过障碍可以额外加个判断原理很简单对于8连通的角落点判断角落点的4连通是否有障碍如果有障碍就不算入可到达格子。
代码如下 演示 5、工程网盘链接
通过网盘分享的文件AStarDemo.unitypackage 链接: https://pan.baidu.com/s/1L_f1DIkqe9Oqm_dnFSSVew 提取码: 1212
