文章目录
俗话说，好记性不如烂笔头，对于有了解过寻路算法的同学，对于A星算法应该不陌生；为了巩固下这个算法的理解，所以利用Unity演示了算法的过程；本文的基本构成分为
基本原理+
算法实现+
Unity演示三个步骤。
寻路算法是在指定地图中，NPC可以根据起始点和目标点，计算出一条比较合理的链接路线（通常需要最短路径）；在地图中，路点可以分为两种，一种是普通路点，一种是障碍路点（墙、水、坑等），算法的目的就是要绕过障碍物，使得NPC尽可能的走最短路线到达目标点(targetPoint)。
对于最基本的A星寻路算法，是把一张地图分为一个二维数组，每一个格子代表一个路点；或者如下图如所示，将一张地图分为一个一个的格子，格子为正方形，下方的绿色格子周围有8个相邻的格子；
对于上述九宫格图，假设最小方格的边长是10,那么从绿色格子出发，到达红色格子的距离为
200
\sqrt{200}
200，这里可以简化为14，因为这样可以简化算法的计算难度（浮点数比整数的计算复杂）；到达黄色格子的距离为10；
每一个路点都有一个评估值F，其中
F
=
G
+
H
F = G + H
F=G+H，G值是起点移动到指定方格的移动代价，H是指定的方格移动到终点的估算成本，H值的计算方式有如下两种：
方式一：计算横向和纵向移动的距离，不能斜着走；
方式二：比如该点和目标点为对角顶点组成的举行的边长是a 和 b，那么H值是
m
i
n
(
a
,
b
)
×
14
+
a
b
s
(
a
−
b
)
×
10
min(a, b) \times 14 + abs(a - b) \times 10
min(a,b)×14+abs(a−b)×10
，
本文算法选择的是方式二，H值的计算需要注意的地方是，不需要考虑障碍物，只需考虑起始点和目标点即可。对于F、G、H三个评估值的什么这么命名，我也不清楚，猜测是就和我们平时用来替代临时变量用的i、j、k一样，仅仅是26英文字母中连续的三个而已，方便记忆😎;
这个算法需要两个数组，openList和closeList，openList里面存放的是当前状态可以到达的路点，closeList存放不能到达的路点和已经经过判断的路点；具体步骤如下：
这里列出算法用的大部分代码，其中最关键的就是RefreshFind函数和AddOpenlistNode函数，执行的就是算法的关键部分----遍历openList然后不断的进行判断，直到找到目标路点或者openList为空，如果有不理解的地方，请留言。
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
namespace AStar
{
public static class cconst
{
public static int NormalTile = 0;
public static int WaterTile = 1;
public static int DestinationTile = 2;
public static int MarkTile = 3;
public static int FindTile = 4;
public static int StartTile = 5;
public static int RowLineNum = 16; // 行数
public static int ColLineNum = 32; // 列数
public static Vector2 startPos = new Vector2(-617, 298);
public static float itemRate = 1.0f;
public static float width = 40 * itemRate;
public static float height = 40 * itemRate;
public static int SlideDis = 14;
public static int UnSlideDis = 10;
public static int slideValNum = 4;
public static List<Vector2> UnSlideDisVal = new List<Vector2> { new Vector2(-1, 0), new Vector2(0, 1), new Vector2(1, 0), new Vector2(0, -1) };
public static List<Vector2> SlideDisVal = new List<Vector2> { new Vector2(-1, -1), new Vector2(-1, 1), new Vector2(1, 1), new Vector2(1, -1) };
//障碍点类型
public static int BattleNum = 5;
public static int BattleTypeNum = 3;
public static Dictionary<int, List<List<int>>> BattleTypeDic = new Dictionary<int, List<List<int>>>
{
{ 0, new List<List<int>>{ new List<int> {1,0,0 }, new List<int> { 1,1,0 }, new List<int> { 1,1,1 },new List<int> { 1,1,1 }, new List<int> { 1,1,0 }, new List<int> { 1,0,0 } } },
{ 1, new List<List<int>>{ new List<int> {1,1,1,1}, new List<int> {1,1,1 }, new List<int> { 1, 1, 1,1,1 } } },
{ 2, new List<List<int>>{ new List<int> {1,0, 0, 0, }, new List<int> {1,1,1,1 }, new List<int> {0,0,0,1 }, new List<int> { 0, 0, 0, 1 } } },
};
}
}
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
namespace AStar
{
public class GObject
{
public GameObject gameobject;
public int objType;
GameObject fValText;
GameObject gValText;
GameObject hValText;
GameObject textPanel;
public GObject(GameObject _gameobject, int _type)
{
gameobject = _gameobject;
objType = _type;
textPanel = _gameobject.transform.Find("Panel").gameObject;
fValText = textPanel.transform.Find("FText").gameObject;
gValText = textPanel.transform.Find("GText").gameObject;
hValText = textPanel.transform.Find("HText").gameObject;
textPanel.SetActive(false);
}
public bool IsObstacle
{
get { return objType == cconst.WaterTile; }
}
public void UpdateDis(int g, int h)
{
textPanel.SetActive(true);
gValText.GetComponent<Text>().text = g.ToString();
hValText.GetComponent<Text>().text = h.ToString();
int f = g + h;
fValText.GetComponent<Text>().text = f.ToString();
}
public bool Visible
{
set { gameobject.SetActive(value);
if(!value)
{
textPanel.SetActive(false);
}
}
get { return gameobject.activeSelf; }
}
public void SetParent(Transform transform)
{
gameobject.transform.SetParent(transform);
}
public Vector2 localPosition
{
set { gameobject.transform.localPosition = value; }
get { return gameobject.transform.localPosition; }
}
}
public class Node
{
public Node parent;
public GObject gameobject;
int idx = 0;
public Node(GObject obj, int _idx) { gameobject = obj; idx = _idx; }
int g = 0;
int h = 0;
public int Idx
{
get { return idx; }
}
public int F
{
get { return G + H; }
}
public int G
{
get { return g; }
set { g = value; }
}
public int H
{
get { return h; }
set { h = value;}
}
public int xIdx
{
get { return idx / cconst.ColLineNum; }
}
public int yIdx
{
get { return idx % cconst.ColLineNum; }
}
public void UpdateGVal(int gVal)
{
if(gVal < G)
{
G = gVal;
}
}
public void UpdateLocalPosition()
{
int rowIdx = xIdx;
int colIdx = yIdx;
float posX = cconst.startPos.x + colIdx * cconst.width;
float posY = cconst.startPos.y - rowIdx * cconst.height;
gameobject.localPosition = new Vector2(posX, posY);
}
public void UpdateDescDis()
{
gameobject.UpdateDis(G, H);
}
public void UpdateDescDis(Node node)
{
G = node.G;
H = node.H;
gameobject.UpdateDis(G, H);
}
public void SetParrent(Node node)
{
parent = node;
}
public bool Visible
{
set { gameobject.gameobject.SetActive(value); }
get { return gameobject.gameobject.activeSelf; }
}
}
public class AStarTest : MonoBehaviour
{
// Start is called before the first frame update
public List<int> map;
public Dictionary<int, string> mapTypeDic;
public Dictionary<int, GObject> mapTypeObjDic;
public Dictionary<int, GObject> idxObjDic;
GameObject normalTile;
GameObject waterTile;
GameObject destinationTile;
GameObject markTile;
GameObject findTile;
GameObject startTile;
public int startIdx;
public int targetIdx;
public List<int> battleList;
public List<Node> openList;
public Dictionary<int, Node> openListIdxDic;
public List<Node> closeList;
public Dictionary<int, Node> closeListIdxDic;
public List<GObject> totalObjList;
public Dictionary<int, Stack<GObject>> nodeDicPool;
Node targetNode;
Node markTargetNode;
public List<Node> markNodeList;
public Coroutine curCoroutine;
void Start()
{
idxObjDic = new Dictionary<int, GObject>();
nodeDicPool = new Dictionary<int, Stack<GObject>>();
mapTypeDic = new Dictionary<int, string> {
{0, "normalTile" },
{1, "waterTile" },
{2, "targetTile" },
{3, "markTile" },
{4, "findTile" },
{5, "startTile" },
};
normalTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.NormalTile]);
waterTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.WaterTile]);
destinationTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.DestinationTile]);
markTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.MarkTile]);
findTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.FindTile]);
startTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.StartTile]);
mapTypeObjDic = new Dictionary<int, GObject>
{
{cconst.NormalTile, new GObject(normalTile,cconst.NormalTile)},
{cconst.WaterTile, new GObject(waterTile,cconst.WaterTile)},
{cconst.DestinationTile, new GObject(destinationTile,cconst.DestinationTile)},
{cconst.MarkTile, new GObject(markTile,cconst.MarkTile)},
{cconst.FindTile, new GObject(findTile,cconst.FindTile)},
{cconst.StartTile, new GObject(startTile,cconst.StartTile)},
};
InitData();
}
public void InitData()
{
transform.DetachChildren();
int _totalIdx = cconst.RowLineNum * cconst.ColLineNum;
//初始化乜有障碍物的地图
map = new List<int>();
for (int i = 0; i < cconst.RowLineNum; ++i)
for (int j = 0; j < cconst.ColLineNum; ++j)
{
map.Add(cconst.NormalTile);
}
//初始化地图障碍物
battleList = new List<int>();
for (int i = 0; i < cconst.BattleNum; i++)
{
int curBattleType = Random.Range(0, 100) % cconst.BattleTypeNum;
int curBattleStartIdx = Random.Range(0, _totalIdx);
List<List<int>> curBattleList = cconst.BattleTypeDic[curBattleType];
int curBattleRow = curBattleStartIdx / cconst.ColLineNum;
int curBattleCol = curBattleStartIdx % cconst.ColLineNum;
curBattleRow = Mathf.Min(curBattleRow, cconst.RowLineNum - curBattleList.Count - 1);
curBattleCol = Mathf.Min(curBattleCol, cconst.ColLineNum - curBattleList[0].Count - 1);
for(int j = 0; j< curBattleList.Count; ++j)
for(int k=0; k<curBattleList[j].Count; ++k)
{
if(curBattleList[j][k] > 0)
{
int curCalIdx = (curBattleRow + j) * cconst.ColLineNum + (curBattleCol + k);
map[curCalIdx] = cconst.WaterTile;
battleList.Add(curCalIdx);
}
}
}
//初始化起始点
startIdx = Random.Range(0, _totalIdx / 2);
while (battleList.Contains(startIdx))
{
startIdx = Random.Range(0, _totalIdx / 2);
}
//初始化目标点
targetIdx = Random.Range(_totalIdx / 2, _totalIdx);
while (battleList.Contains(targetIdx) || startIdx == targetIdx)
{
targetIdx = Random.Range(_totalIdx / 2, _totalIdx);
}
totalObjList = new List<GObject>();
map[startIdx] = cconst.StartTile;
map[targetIdx] = cconst.DestinationTile;
InitMapRes();
// ---------------- A*
openList = new List<Node>();
openListIdxDic = new Dictionary<int, Node>();
closeList = new List<Node>();
closeListIdxDic = new Dictionary<int, Node>();
markNodeList = new List<Node>();
targetNode = new Node(idxObjDic[targetIdx], targetIdx);
markTargetNode = null;
InitAStarStart();
curCoroutine = StartCoroutine(FindNextPoint());
}
public IEnumerator FindNextPoint()
{
RefreshFind();
yield return new WaitForSeconds(0.05f);
if (!openListIdxDic.ContainsKey(targetNode.Idx))
{
curCoroutine = StartCoroutine(FindNextPoint()); //目标点没在dic里面，继续执行
}
else
{
markTargetNode = openListIdxDic[targetNode.Idx];
curCoroutine = StartCoroutine(ShowFindPath(markTargetNode));
Debug.Log("find the way to the target !!!");
}
}
void InitMapRes()
{
int _totalIdx = cconst.RowLineNum * cconst.ColLineNum;
for (int i=0; i< _totalIdx; ++i)
{
int rowIdx = i / cconst.ColLineNum;
int colIdx = i % cconst.ColLineNum;
var obj = GetTypeObject(map[i]);
idxObjDic[i] = obj;
float posX = cconst.startPos.x + colIdx * cconst.width;
float posY = cconst.startPos.y - rowIdx * cconst.height;
obj.localPosition = new Vector2(posX, posY);
}
}
void InitAStarStart()
{
GObject startObj = idxObjDic[startIdx];
Node startNode = new Node(startObj, startIdx);
AddOpenlistNode(startNode);
}
void AddOpenlistNode(Node node) //出发点是node，遍历其周围8个点，更细其F、G、H值
{
if(openListIdxDic.ContainsKey(targetNode.Idx))
{
Debug.Log("find the way to the target !!!");
return;
}
int xIdx = node.xIdx;
int yIdx = node.yIdx;
List<Vector2> curDisVal;
int curValDis;
for (int i =0; i<2; i++)
{
if(i == 0)
{
curDisVal = cconst.UnSlideDisVal;
curValDis = cconst.UnSlideDis;
}
else
{
curDisVal = cconst.SlideDisVal;
curValDis = cconst.SlideDis;
}
for (int j = 0; j < cconst.slideValNum; ++j)
{
var addVal = curDisVal[j];
var curXIdx = xIdx + (int)addVal.x;
var curYIdx = yIdx + (int)addVal.y;
if (curXIdx < 0 || curXIdx >= cconst.RowLineNum || curYIdx < 0 || curYIdx >= cconst.ColLineNum) continue;
int cur_Idx = curXIdx * cconst.ColLineNum + curYIdx;
if (closeListIdxDic.ContainsKey(cur_Idx)) continue;
Node curNode = null;
if (openListIdxDic.ContainsKey(cur_Idx))
{
curNode = openListIdxDic[cur_Idx];
int cur_G = node.G + curValDis;
if (curNode.G > cur_G)
{
curNode.SetParrent(node);
curNode.UpdateGVal(cur_G);
}
}
else
{
GObject gobject = GetTypeObject(cconst.FindTile);
float posX = cconst.startPos.x + curYIdx * cconst.width;
float posY = cconst.startPos.y - curXIdx * cconst.height;
gobject.localPosition = new Vector2(posX, posY);
curNode = new Node(gobject, cur_Idx);
if (idxObjDic[curXIdx * cconst.ColLineNum + curYIdx].IsObstacle)
{
closeListIdxDic[cur_Idx] = curNode;
curNode.gameobject.gameobject.SetActive(false);
return;
}
curNode.SetParrent(node);
openList.Add(curNode);
openListIdxDic[cur_Idx] = curNode;
curNode.G = node.G + curValDis;
SetHVal(curNode);
}
curNode.UpdateDescDis();
}
}
closeListIdxDic[node.Idx] = node;
closeList.Add(node);
}
// Update is called once per frame
void Update()
{
if(Input.GetKeyDown(KeyCode.A))
{
//dosomething
}
}
void DoNextOperation()
{
StopCoroutine(curCoroutine);
foreach (var obj in totalObjList)
{
obj.Visible = false;
Stack<GObject> tmpList;
if (nodeDicPool.ContainsKey(obj.objType))
{
tmpList = nodeDicPool[obj.objType];
tmpList.Push(obj);
}
else
{
tmpList = new Stack<GObject>();
tmpList.Push(obj);
}
nodeDicPool[obj.objType] = tmpList;
}
InitData();
}
void RefreshFind()
{
Node findNode = null;
int tmpMax = int.MaxValue;
if(openList.Count == 0)
{
Debug.Log("can not find the way to the target !!!");
DoNextOperation();
return;
}
foreach(var node in openList)
{
if (node.F < tmpMax)
{
tmpMax = node.F;
findNode = node;
}
}
if (findNode == null) return;
GObject gobject = GetTypeObject(cconst.MarkTile);
Node curNode = new Node(gobject, findNode.Idx);
curNode.UpdateLocalPosition();
curNode.UpdateDescDis(findNode);
markNodeList.Add(curNode);
openList.Remove(findNode);
AddOpenlistNode(findNode);
}
IEnumerator ShowFindPath(Node targetNode)
{
foreach (var _node in markNodeList)
{
_node.Visible = false;
}
Node temp_node = targetNode;
while(temp_node != null)
{
int curTile = cconst.MarkTile;
if(temp_node.Idx == startIdx)
{
curTile = cconst.StartTile;
}
else if(temp_node.Idx == targetIdx)
{
curTile = cconst.DestinationTile;
}
GObject gobject = GetTypeObject(curTile);
Node curNode = new Node(gobject, temp_node.Idx);
curNode.Visible = true;
curNode.UpdateLocalPosition();
temp_node = temp_node.parent;
yield return new WaitForSeconds(0.2f);
}
yield return new WaitForSeconds(0.5f);
DoNextOperation();
}
void SetHVal(Node node)
{
int xDelVal = Mathf.Abs(node.xIdx - targetNode.xIdx);
int yDelVal = Mathf.Abs(node.yIdx - targetNode.yIdx);
node.H = Mathf.Min(xDelVal, yDelVal) * cconst.SlideDis + Mathf.Abs(xDelVal - yDelVal) * cconst.UnSlideDis;
}
GObject GetTypeObject(int objType)
{
if(nodeDicPool.ContainsKey(objType))
{
var typeStack = nodeDicPool[objType];
if(typeStack.Count > 0)
{
var obj = typeStack.Pop();
obj.SetParent(transform);
nodeDicPool[objType] = typeStack;
obj.Visible = true;
totalObjList.Add(obj);
return obj;
}
else
{
GameObject gameObject = Instantiate(mapTypeObjDic[objType].gameobject);
gameObject.transform.SetParent(transform);
GObject obj = new GObject(gameObject, objType);
totalObjList.Add(obj);
return obj;
}
}
else
{
GameObject gameObject = Instantiate(mapTypeObjDic[objType].gameobject);
gameObject.transform.SetParent(transform);
GObject obj = new GObject(gameObject, objType);
obj.Visible = true;
totalObjList.Add(obj);
return obj;
}
}
}
}
这里的演示样例，都是跑的同一份代码，每次循环都是随机出发点、目的点、障碍物。
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非
1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva
我一直在尝试用Ruby实现Luhn算法。我一直在执行以下步骤:该公式根据其包含的校验位验证数字，该校验位通常附加到部分帐号以生成完整帐号。此帐号必须通过以下测试:从最右边的校验位开始向左移动，每第二个数字的值加倍。将乘积的数字(例如，10=1+0=1、14=1+4=5)与原始数字的未加倍数字相加。如果总模10等于0(如果总和以零结尾)，则根据Luhn公式该数字有效；否则无效。http://en.wikipedia.org/wiki/Luhn_algorithm这是我想出的:defvalidCreditCard(cardNumber)sum=0nums=cardNumber.to_s.s
下面是我写的一个计算斐波那契数列中的值的方法:deffib(n)ifn==0return0endifn==1return1endifn>=2returnfib(n-1)+(fib(n-2))endend它工作到n=14，但在那之后我收到一条消息说程序响应时间太长(我正在使用repl.it)。有人知道为什么会这样吗？ 最佳答案 Naivefibonacci进行了大量的重复计算-在fib(14)fib(4)中计算了很多次。您可以将内存添加到您的算法中以使其更快:deffib(n,memo={})ifn==0||n==1returnnen
为了防止在迁移到生产站点期间出现数据库事务错误，我们遵循了https://github.com/LendingHome/zero_downtime_migrations中列出的建议。(具体由https://robots.thoughtbot.com/how-to-create-postgres-indexes-concurrently-in概述)，但在特别大的表上创建索引期间，即使是索引创建的“并发”方法也会锁定表并导致该表上的任何ActiveRecord创建或更新导致各自的事务失败有PG::InFailedSqlTransaction异常。下面是我们运行Rails4.2(使用Acti
重新定义Float#/似乎没有效果:classFloatdef/(other)"magic!"endendputs10.0/2.0#=>5.0但是当另一个中缀运算符Float#*被重新定义时，Float#/突然采用了新的定义:classFloatdef/(other)"magic!"enddef*(other)"spooky"endendputs10.0/2.0#=>"magic!"我很想知道是否有人可以解释这种行为的来源，以及其他人是否得到相同的结果。ruby:ruby2.0.0p353(2013-11-22)[x64-mingw32]要快速确认错误，请运行thisscript.
我正在开发一个类似微论坛的项目，其中一个特殊用户发布一条快速(接近推文大小)的主题消息，订阅者可以用他们自己的类似大小的消息来响应。直截了当，没有任何形式的“挖掘”或投票，只是每个主题消息的响应按时间顺序排列。但预计会有很高的流量。我们想根据它们引起的响应嗡嗡声来标记主题消息，使用0到10的等级。在谷歌上搜索了一段时间的趋势算法和开源社区应用示例，到目前为止已经收集到两个有趣的引用资料，但我还没有完全理解它们:Understandingalgorithmsformeasuringtrends，关于使用基线趋势算法比较维基百科页面浏览量的讨论，在SO上。TheBritneySpearsP
我收到错误:unsupportedcipheralgorithm(AES-256-GCM)(RuntimeError)但我似乎具备所有要求:ruby版本:$ruby--versionruby2.1.2p95OpenSSL会列出gcm:$opensslenc-help2>&1|grepgcm-aes-128-ecb-aes-128-gcm-aes-128-ofb-aes-192-ecb-aes-192-gcm-aes-192-ofb-aes-256-ecb-aes-256-gcm-aes-256-ofbRuby解释器:$irb2.1.2:001>require'openssl';puts
文章目录一.Dijkstra算法想解决的问题二.Dijkstra算法理论三.java代码实现一.Dijkstra算法想解决的问题解决的问题:求解单源最短路径,即各个节点到达源点的最短路径或权值考察其他所有节点到源点的最短路径和长度局限性:无法解决权值为负数的情况二.Dijkstra算法理论参数:S记录当前已经处理过的源点到最短节点U记录还未处理的节点dist[]记录各个节点到起始节点的最短权值path[]记录各个节点的上一级节点(用来联系该节点到起始节点的路径)Dijkstra算法步骤:(1）初始化:顶点集S:节点A到自已的最短路径长度为0。只包含源点，即S={A}顶点集U:包含除A外的其他顶
文章目录认识unity打包目录结构游戏逆向流程Unity游戏攻击面可被攻击原因mono的打包建议方案锁血飞天无限金币攻击力翻倍以上统称内存挂透视自瞄压枪瞬移内购破解Unity游戏防御开发时注意数据安全接入第三方反作弊系统外挂检测思路狠人自爆实战查看目录结构用il2cppdumper例子2-森林whoishe后记认识unity打包目录结构dll一般很大，因为里面是所有的游戏功能编译成的二进制码游戏逆向流程开发人员代码被编译打包到GameAssembly.dll中使用il2ppDumper工具，并借助游戏名_Data\il2cpp_data\Metadata\global-metadata.dat