作者应该是个越南人感觉写的很细很好，现在虚幻4的相关库资源下载的飞快，有兴趣可以当游戏玩；

这是一个用虚幻引擎4制作Action RPG游戏的工作坊。但是我觉得哪一个很先进，会写出很多解释

第1集这将是一个准备。资源/资产。基本上使用虚幻市场中的免费项目，以便您可以快速启动研讨会。

打开Epic Games Launcher，之前下载虚幻引擎。本次研讨会将使用4.17版本。如果使用其他型号，请定位按钮/菜单 可能不匹配。

完成后，去市场

转到如下加载资产

• 无限之刃：敌人 - 无限之刃怪物

• 无限之刃：效果 - 来自无限之刃的效果

• Infinity Blade：Fire Lands - Infinity Blade中的一个场景

• Infinity Balde：Grass Lands - Infinity Blade中的一个场景

• 无限之刃：冰之地 - 无限之刃中的一个场景

• 无限之刃：勇士 - 来自无限之刃的主要角色

• 无限之刃：武器 - 来自无限之刃的武器

• Mixamo动画包 - 角色手势

一旦满载 然后开始创建项目。打开虚幻引擎。按New Project选项卡。选择Blueprint。选择Third Person。选择文件存储。设置项目名称，然后按“创建项目”。

完成后，将Asset添加到项目中，返回Epic Games Launcher，转到Library / Vault并转到已加载的资源。单击Add To Project。

选择刚刚创建的项目。如果不可用，请单击“显示所有项目”按钮并选择项目并选择最新版本，然后单击“添加到项目”。

添加加载到项目中的所有资源，完成后返回到虚幻引擎。

在内容浏览器中，单击“添加新项”按钮创建用于存储项目文件的文件夹。选择“新建文件夹”并将其命名。我将其命名为ARPG。

然后进入Folder ARPG。创建另一个文件夹，包括

• 动画 - 保持角色的姿势。

• 蓝图 - 保持蓝图用于控制角色/怪物/ UI等。

• 地图 - 将地图保留在游戏中，包括主菜单。

在内容浏览器中执行任何操作时，建议您按源面板以便于操作。

按此按钮

然后它会出现这个面板。复制文件时，移动文件会更容易。

完成所有文件夹。从Folder ThirdPersonBP / Blueprints复制Blueprint文件。里面有一个角色控制蓝图和游戏模式到ARPG /蓝图。

转到ThirdPersonBP / Blueprints，将ThirdPersonCharacter和ThirdPersonGameMode拖到ARPG /蓝图。

选择“复制到此处”以复制到所选文件夹。

完成了更改名称 ThirdPersonCharacter是ARPGCharacter，ThirdPersonGameMode是ARPGGameMode

返回Mannequin / Animations后，我们将重新定位主要角色的动画。重新定位动画是制作一个Skeleton Mesh的动画。可以玩我们可以设置的另一个 尽管有不同的结构 但如果非常不同，可能是不可能的。

重新定位动画有很多细节。扩展其他文章

为此，请右键单击该文件。ThirdPerson_AnimBP，然后选择Animarget Animations Blueprints / Duplicate Anim Blueprints和Retarget

完成后，找到sk_mannequin。选择Game / InfinityBladeWarriors / Character / CompleteCharacters的路径。如果未选择任何内容，请按Show Only Compatible Skeletons。

并将其设置为替换文件名，将ThirdPerson与MainCharacter匹配并选择Folder，转到ARPG / Animations并单击Retarget

完成后，将获得ARPG /动画中的新文件

接下来，转到ARPG / Blueprints。然后双击打开 ARPGCharacter 我们将解决这个角色的动画类和网格。

直接组件选择网格

然后在MainCharacter_AnimBP的详细信息和动画动画上右转

然后转到Skeleton Mesh的网格。找到sk_charm_并选择一个。任何一个，我会选择SK_CharM_Warrior。

然后按左上侧的编译/保存并关闭

然后打开ARPGGameMode并将Default Pawn Class更改为ARPGCharacter并按左侧的Compile / Save。

接下来，我们将打开地图，获取要运行的字符。转到文件夹 InfinityBladeFireLands / Maps或InfinityBladeGrassLands / Maps或InfinityBladeIceLands / Maps并打开Map文件。

当游戏开始时，它会在地图上运行一个白色的身体，为什么呢？这是因为游戏模式设置为白色。我们必须先改变游戏模式。

单击“编辑”菜单转到“项目设置”...

在项目中，选择“地图和模式”。将默认GameMode更改为ARPGGameMode。

然后尝试再次播放。

我们将在美丽的地图中获得诱惑。

下一章将更多地介绍蓝图。渐渐地，一次写一个月。它应该是一个可以玩的游戏。

====================================================================

http://jceipek.com/Olin-Coding-Tutorials/pathing.html

游戏路径规划

我为什么要在乎？

路径规划是游戏中人工智能（AI）的关键部分。这是单位如何移动到您在星际争霸中点击的位置。这就是质量效应中的敌人如何绕过掩护来找到你。让计算机控制的角色有效地朝着目标前进，同时避免障碍和危险，这是神奇的。

开始使用正确的寻路行为可能会令人生畏。互联网-上充满了基于网格的导航的经典“A *算法”的描述。但现代3D游戏通常涉及复杂的环境，对吗？程序员如何让角色在那些中移动？为什么在有良好AI的游戏中，角色没有朝着你的方向走来走去？

在本教程中，我们将介绍如何使用导航网格使角色导航世界，导航网格在当今许多最好的游戏中使用。该技术是Valve和Unreal在其游戏引擎中使用的一部分。

细分空间

任何寻路AI的第一部分是弄清楚如何以对导航有用的方式表示游戏世界。一些最常见的表示是

• 航点

• 网格

和

导航网格

一切都是图表

关于所有这些表示最重要的事情是它们只是图形。当我说“图形”时你想到的第一件事可能是条形图或折线图。

这不是我在这里的意思。在游戏AI（和数学）中，图形是由边缘连接的一系列节点。在寻路AI的上下文中考虑这些术语的最简单方法是图中的每个节点表示一个字符可能存在的位置，并且每个边指示字符可以在它连接的节点之间移动。每条边都有一个相关的成本，它表示角色从一个节点移动到下一个节点所需的工作量。当我们谈论寻路时，我们真的在谈论在图中的两个节点之间找到路径，理想情况下最小化路径的成本。

这是一个节点。它代表一个角色可以成为的地方。

字符只能通过边缘在节点之间移动。

注意：我们要看的边是双向的; 人物可以随意走在他们之间。更复杂的边缘可能只是一种方式。例如，角色可能会从平台跳下但无法跳回来。不过不要担心，如果你碰到这种情况，我们谈到的技术可以很容易地应用。

图是节点网络。在节点之间移动是昂贵的。

从A到B最便宜的路径需要3个步骤，总成本为4 = 2 + 1 + 1。

航点

空间的航点表示很容易创造和思考，但它们对于寻路并不是很好。尽管它们使用的内存很少，但它们会导致效率低下，不切实际的路径。

航点系统背后的主要思想是在游戏世界中放置少量节点和边缘，以便角色可以在静态障碍物周围找到方向。不幸的是，如果角色总是停留在航点之间的路径上，那么它们的行为将受到不切实际的约束。但是，如果他们离开航点网络，他们就会很容易陷入困境。

一个粗糙的岛屿世界。

岛屿周围的航点。每个航路点直接对应于一个节点。成本只是航路点之间连接的长度。请注意，某些区域无法访问。

网格

如果你寻找一个关于路径规划的入门教程，你很可能会找到一个使用网格的教程。网格对于小型环境非常有效，特别是对于角色已经在网格上移动的游戏。更复杂的环境需要更精细的网格，这可能会占用大量世界的不可靠的内存量。

您可能已经看到过这样的网格表示：

每个网格方格中的数字表示从相邻方格到该方格的难度或“成本”。粗糙的网格使许多区域无法到达。更高分辨率的网格将使用更多内存，但会更有效地代表世界。

您可能没有意识到的是，像这样的网格只是表示非常密集的图形的一种更紧凑的方式：

网格只是一个图形！

对于大型现代游戏来说，网格似乎并没有被大量使用。然而，尖端的AI研究人员正在寻找它们用于非常本地化的导航以及导航网格等其他技术。

导航网格

导航网格是表示游戏世界中可步行区域的有效方式。常见的实现依赖于连接的凸多边形。

导航网格有效地描述了世界上的可步行区域。

就像在网格表示中一样，每个多边形都是一个节点，两个多边形共享的每条边表示节点之间的连接。

导航网格也只是一个图形！

用A *寻找路径

大！我们可以代表空间：现在是什么？这将如何帮助我们的角色到达我们希望他们去的地方？答案是：搜索。A *（发音为“A-star”）算法是在图上找到两点之间最便宜路径的有效方法。

网-上有很多很好的解释，所以我不会详细介绍，但A *背后的主要思想是保持一个角色可以在任何时间点访问的未探测节点的前沿并探索最多的节点。可能是首先实现目标成本最低的一部分。为此，它使用启发式函数来估计从节点到目标的成本。适用于A *的最简单的启发式类型只返回节点和目标之间的距离。这是一个示例A *实现：

// Returns a list representing the optimal path between startNode and endNode or null if such a path does not exist // If the path exists, the order is such that elements can be popped off the path // Note: if you use this code in Javascript, make sure that the toString function of each node returns a unique value FindRoute = function (startNode, goalNode) { var frontier = PriorityQueue({low: true}); // Priority Queue (https://github.com/STRd6/PriorityQueue.js), // what have we not explored? var explored = new Set(); // Set (https://github.com/jau/SetJS), what have we explored? var pathTo = {}; // A dictionary mapping from nodes to nodes, // used to keep track of the path // The node that is the key var gCost = {}; // A dictionary mapping from nodes to floats, // used to keep track of the "G cost" associated with traveling to each node from startNode pathTo[startNode] = null; gCost[startNode] = 0.0; frontier.push(startNode, 0.0 + HeuristicCostEstimate(startNode, goalNode)); while (!frontier.empty()) { // While the frontier remains unexplored var leafNode = frontier.Values[0]; if (leafNode == goalNode) { // We found the solution! Reconstruct it. var path = []; var pointer = goalNode; while (pointer != null) { path.push(pointer); pointer = pathTo[pointer]; } return path; } frontier.pop(); explored.add(leafNode); for (var i = 0; i < leafNode.linkedTo.length; i++) { var connectedNode = leafNode.linkedTo[i]; if (!explored.contains(connectedNode) && !frontier.includes(connectedNode)) { gCost[connectedNode] = gCost[leafNode] + CostBetween(leafNode, connectedNode); pathTo[connectedNode] = leafNode; frontier.push(connectedNode, gCost[connectedNode] + HeuristicCostEstimate(connectedNode, goalNode)); } } } return null; // No path could be found }

导航网格上的A *结果。

将路径映射到空间

怎么办？我们在抽象图中有一些最佳路径。这有助于我们的角色移动？这个问题的答案很大程度上取决于你正在制作的游戏的具体细节。在某些游戏中，您可以将图形直接映射到物理空间。但是，在大多数情况下，您需要以某种方式平滑生成的路径。在Left 4 Dead中，角色在门户中点之间移动，并通过向可见节点移动来平滑其路径，该节点是最佳A *路径的一部分，但是前面几步。

不过，我们可以做得更好。如果我们使用网格或导航网格，我们可以实现一种称为简单愚蠢漏斗算法的平滑技术，这是一种实用的路径平滑技术，由原始的孤岛危机的主要AI程序员开发，基于寻路的PHD论文。

简单的愚蠢漏斗算法

该算法通过在导航网格的最小距离路径上找到角而不离开可行走区域来平滑路径。结果就像A *路径被拉动直到它拉紧一样。

算法如下：

1. 创建A *路径上的门户列表。确保每个门户的点以相对于角色的相同方式存储。你需要知道一个点是在角色的左边还是右边。

2. 创建一个包含三个点的“漏斗”：角色起始位置（顶点），门户右侧和门户左侧。

3. 替代更新“漏斗”的左侧和右侧，使其每次都变窄

4. 当漏斗的两侧交叉时，请指出您没有更新新漏斗的顶点，并将其存储为平滑路径的一部分。

漏斗算法的逐步演示。

您可以在此处找到漏斗算法的事实C实现。但是，您可能必须调整它以适应您的项目，因为它高度依赖于实现。

编写自己的实现的关键部分取决于了解如何判断漏斗是否穿过自身。最简单和最有效的方法之一涉及交叉产品。在2d中，我们可以使用叉积的非零分量的符号来告诉我们三角形中点的顺序。在大多数3D游戏环境中，为了路径平滑，我们可以简单地忽略第三维，因为大多数角色不需要在天花板或完美垂直的墙壁上行走。

// This function from http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html // is called "triarea2" because the cross product of two vectors // returns the area of the parallellogram the two sides form // (which has twice the area of the triangle they form) // The sign of the result will tell you the order of the points passed in. inline float triarea2(const float* a, const float* b, const float* c) { const float ax = b[0] - a[0]; const float ay = b[1] - a[1]; const float bx = c[0] - a[0]; const float by = c[1] - a[1]; return bx*ay - ax*by; }

操舵

我们采用了A *路径并对其进行了平滑处理，但角色仍然不自然地移动！这就是转向行为发挥作用的地方。真正的人在拐角处不会转弯（或者至少大多数人不会，但无论如何......），为什么你的角色？平滑的A *路径是环境导航的一个很好的指南，但不需要完全遵循。您可以做的最简单的事情之一是实现一个跟随行为的路径，该行为告诉字符通常保持在平滑路径的范围内，并且如果它们偏离轨道则转向它。您可以将多个行为组合在一起以获得更好的结果。

资源

这就是现在！如果您有兴趣进一步探索寻路，我高度推荐以下内容：

• 关于游戏AI的消化鸭博客

• Valve的Left 4 Dead演示文稿

• 多边形汤演示中的人群

玩得开心！

==============================================

https://gameinstitute.qq.com/community/detail/100041

大规模寻路算法优化

本来经过优化的Normal A*算法已经足以应付最大1024*1024（单位：阻挡格，每个阻挡格大小为：520mm*520mm）的地图了。然而当策划提出野外地图尺寸将达到4096*4096时，Normal A*算法在长距离寻路时就显得力不从心了。在Normal A*算法代码已经没什么优化空间的前提下，我们开始尝试从算法本身着手做一些优化。在参考了《Near Optimal Hierarchical Path-Finding》中提出的一种层次A*算法后，我们给出了优化的思路：

1）预处理：将地图按N*N大小划分区块，其中N为阻挡格数。找出每个区块与周围四个区块在边界上的互通点，然后在区块内使用Normal A*对找出的点做连通性测试并将结果保存下来；

2）层次A*：如果我们将预处理步骤中的区块作为Normal A*算法中搜索的一个阻挡格，那么4096*4096大小的地图，当N=32时的搜索域将会降到128*128。在客户端执行寻路请求时，寻路线程使用预处理得到的数据，在区块一级做一次A*找出路径经过的区块互通点，再在每个区块内使用Normal A*得到互通点之间的路径，最终得到完整路径。

其中，预处理步骤是离线完成的，可在每次变更地图阻挡时执行。如果预处理步骤中预存了区块内的互通点路径，那么在进行层次A*时便可避免在区块内使用Normal A*。

下面详细阐述一下该优化方案的关键算法。

一、预处理

1.1 区块间互通点查找算法

每个相邻区块（C1和C2）都有一条由公共边，该边两侧的格子组成L1和L2，则互通点集E满足下列条件：

o   E ⊂ L1 ∪ L2

o   ∀t ∈ L1 ∪ L2 : t ∈ E ⇔ symm(t) ∈ E ，其中symm(t)为对称关系

o   E不含不可行走点

对在E中且同边的连续格子取其中点，如下图所示：

1.2 区块内的路径搜索

一个区块如果与周围区块存在互通点，必定在其内部有一个与之对称的点，通过在区块内执行Normal A*可以得到这些点之间的连通性，该连通关系实际上反映了该区块周围的上下左右区块的连通性。

1.3 预存路径

为了避免客户端在执行层次A*时再耗时去搜索区块内的路径，我们在预处理步骤中将其保存下来。由于A*算法输出的原始结果包含了路径经过的所有格子，为了减少存储消耗，需要对路径进行简化，假设P为A*算法输出的原始路径点集合，O为简化路径点集合：

O[1] = P[1]

for i =2 to size(P)-1 then

if IsLineConnectivity(get_back(O) , P[i+1]) = false then

push_back(O , P[i])

end

end

push_back(O , P[size(P)])

其中，IsLineConnectivity为直线连通判定，get_back为取集合最尾元素操作，push_back将元素放入集合最尾。

1.4 预处理结果的存储格式

区块尺寸 

区块1： 

连通点： 

           UP方向互通点信息：数量，点1索引、点2索引... 

           DOWN方向互通点信息：... 

           LEFT方向互通点信息： ... 

           RIGHT方向互通点信息： … 

           连通性： 

           通路数 

           通路1：两连通点索引，权重，路径长度，路径 

           通路2：... 

区块2： 

… 

其中，索引均为全局索引。 

二、层次A*

2.1 启发式函数

在Normal A*中，启发式函数为F = G + H。在层次A*中，我们沿用这一公式来计算每个搜索节点的权重，只是G与H的计算方法不同了：

o   G：从起点到当前区块边界上互通点路径点的个数

o   H：当前区块到终点所在区块的直线距离

2.2 起点和终点的处理

因为起点与终点是在游戏过程中动态给出的，需要计算它们所处的区块索引，然后先在起点所处区块内以起点到各互通点（区块内部分）做一次Normal A*，将可达互通点对称的点所在的区块放入OpenList并用路径长度作为该区块的G值，如果有多条路径可达同一区块，选取G值最小者。针对终点也做同样处理，但并不放入OpenList，而是将其作为判定是否可达终点所处区块的依据。

三、优化结论及评价

我们对一张1024*1024的地图分别采用32*32、64*64、128*128划分区块，随机产生50个不在阻挡内的起点-终点对，分别使用Normal A*、层次A*、预存路径的层次A*进行测试，结论如下：

从对比数据可以看出，采用层次A*算法在寻路效率上有很大提升，而且针对不同尺寸的地图N值的选择也需要考虑。此外，该算法也有一定的局限性，主要表现在下面两个方面：

1）不能处理阻挡动态改变的情况；

2）由于区块间的互通点固定，形成的路径可能不是最优的，如下图所示。

由于这两方面的限制，我们主要将其应用在了超过（包括）1024*1024尺寸的主城和野外地图的中远距离寻路中。

参考资料

• A* Pathfinding for Beginners

http://theory.stanford.edu/~amitp/GameProgramming/

•  Amit’s A* Pages

http://www.policyalmanac.org/games/aStarTutorial.htm

• Near Optimal Hierarchical Path- Finding

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.7041&rep=rep1&type=pdf