原文 译文

已翻译 Unity 六边形地图系列(十六) :寻路

2017-08-04 1 1483

翻译作者

版权所有,禁止匿名转载;禁止商业使用;禁止个人使用。

译者:王磊(未来的未来)   审校:白芷(白芷)


  • 突出显示单元格。
  • 选择搜索目的地。
  • 查找最短路径。
  • 创建优先级队列。

这是关于六边形地图系列教程的第十六部分。现在既然我们已经可以算出单元格之间的距离,我们将继续寻找这些单元格之间的路径。

从现在开始,六边形地图系列教程是用Unity 5.6.0开发的。

Unity 六边形地图系列(十六) :寻路

规划一个路线。

突出显示单元格

要搜索两个单元格之间的路径,我们必须首先选择这些单元格。不再需要选择单个单元格并且观看通过地图进行的搜索,举个简单的例子来说,我们首先选择一个起始单元格,后跟一个目标单元格。在做出这些选择之后,可以很方便地突出显示它们。所以我们来补充这个功能。我们现在不打算创造一个高效的突出显示方法,这只是一个有助于开发的快速方法。

显示纹理的轮廓

突出显示单元格的简单方法是向它们添加一个轮廓。最简单的方法是使用包含六边形轮廓的纹理。这有一个这样的纹理。它是透明的,除了有白色六角形外形。通过使其变为白色,我们可以稍后按照我们认为合适的方法将其着色。

在黑色背景上的单元格轮廓。

导入纹理并将其纹理类型设置为Sprite。它的Sprite模式为Single,具有默认设置。 因为它是一个纯白色的纹理,我们不需要进行sRGB转换。Alpha通道表示透明度,因此启用“Alpha is Transparency”。我也将它的过滤器模式设置为三线性过滤,因为其他的mip转换对于轮廓来说有点过于明显。

Unity 六边形地图系列(十六) :寻路

 纹理导入设置。

每个单元格一个精灵

向每个单元格添加一个潜在的轮廓的最快方法是给每个单元格一个精灵。创建一个新的游戏对象,并通过Component / UI / Image添加一个图像组件,并将我们的轮廓精灵分配给它。 然后,在场景中放置一个十六进制单元格标签预制件实例,使精灵对象成为一个子对象,并将这个更改应用于预制件。然后去掉这个实例。

Unity 六边形地图系列(十六) :寻路 Unity 六边形地图系列(十六) :寻路

突出显示预制件的子物体。

现在每个单元格都有一个精灵,但是它们太大了。 要使轮廓围绕单元格中心,将精灵的位移组件的宽度和高度改为17

Unity 六边形地图系列(十六) :寻路

突出显示精灵,部分被地形遮挡。

在顶部进行绘制

因为轮廓与单元格的边缘区域重叠,所以轮廓通常在地形几何体的下方。这使得轮廓的一部分会消失。对于一些小突起的区域可以通过改变精灵的垂直位置来防止这种变化,但对于悬崖区域这种方法则不行。我们可以做的是总是在顶部绘制轮廓。我们需要为此创建一个自定义的精灵着色器。我们可以通过复制Unity的默认精灵着色器并进行一些更改来做到这一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Shader "Custom/Highlight" {
    Properties {
        [PerRendererData] _MainTex ("Sprite Texture", 2D) = "white" {}
        _Color ("Tint", Color) = (1,1,1,1)
        [MaterialToggle] PixelSnap ("Pixel snap", Float) = 0
        [HideInInspector] _RendererColor ("RendererColor", Color) = (1,1,1,1)
        [HideInInspector] _Flip ("Flip", Vector) = (1,1,1,1)
        [PerRendererData] _AlphaTex ("External Alpha", 2D) = "white" {}
        [PerRendererData] _EnableExternalAlpha ("Enable External Alpha", Float) = 0
    }
 
    SubShader {
        Tags {
            "Queue"="Transparent"
            "IgnoreProjector"="True"
            "RenderType"="Transparent"
            "PreviewType"="Plane"
            "CanUseSpriteAtlas"="True"
        }
 
        Cull Off
        ZWrite Off
        Blend One OneMinusSrcAlpha
 
        Pass {
            CGPROGRAM
            #pragma vertex SpriteVert
            #pragma fragment SpriteFrag
            #pragma target 2.0
            #pragma multi_compile_instancing
            #pragma multi_compile _ PIXELSNAP_ON
            #pragma multi_compile _ ETC1_EXTERNAL_ALPHA
            #include "UnitySprites.cginc"
            ENDCG
        }
    }
}

第一个变化是忽略深度缓冲区,使Z值测试总是成功。

1
2
ZWrite Off
ZTest Always

第二个变化是在所有其他透明几何图形之后进行绘制。给透明队列加10应该足够了。

1
"Queue"="Transparent+10"

创建一个使用该着色器的新材质。 我们可以忽略这个材质所有其他属性,使用默认值。然后让我们的精灵预制件使用这种材质。

Unity 六边形地图系列(十六) :寻路 Unity 六边形地图系列(十六) :寻路

使用一个自定义的精灵材质。

我们的突出显示部分现在总是可见的。即使一个单元格被隐藏在较高的地形之后,它的轮廓仍将被绘制在其他一切内容之上。这可能看起来并不太好,但它确保我们可以总是找到突出显示的单元格,这是有用的。

Unity 六边形地图系列(十六) :寻路

忽略深度缓冲区。

控制高亮显示

我们不希望所有的单元格都被突出显示。事实上,我们想要在开始的时候,没有一个单元格被突出显示。我们可以通过禁用“Highlight ”预制对象的图像组件来执行此操作。

Unity 六边形地图系列(十六) :寻路

禁用图像组件。
要启用单元格的高亮显示,请将EnableHighlight方法添加到HexCell里面去。 它必须得到其uiRect的唯一子物体,并启用其图像组件。同时创建一个DisableHighlight方法。
1
2
3
4
5
6
7
8
9
public void DisableHighlight () {
    Image highlight = uiRect.GetChild(0).GetComponent<img>();
    highlight.enabled = false;
}
 
public void EnableHighlight () {
    Image highlight = uiRect.GetChild(0).GetComponent<img>();
    highlight.enabled = true;
}

最后,我们还可以提供一个颜色,以便在启用该功能时对其进行着色。

1
2
3
4
5
public void EnableHighlight (Color color) {
    Image highlight = uiRect.GetChild(0).GetComponent<img>();
    highlight.color = color;
    highlight.enabled = true;
}

项目文件下载地址:unitypackage

寻找一条路径

现在我们可以突出显示单元格了,我们可以继续选择两个单元格,然后搜索它们之间的路径。首先,我们必须实际选择单元格,然后限制搜索来找到路径,最后显示该路径。

选择起始单元格

我们有两个不同的单元格要选择,分别是搜索的起点和终点。假设要选择搜索的起点单元格的话,你必须在鼠标单击时按住左Shift键。 这样做会突出显示蓝色的单元格。 我们必须保留对这个单元格的引用以供以后搜索。 此外,当选择新的起始单元格的时候,应禁用旧的单元格。所以添加一个searchFromCell字段到HexMapEditor里面。

1
HexCell previousCell, searchFromCell;

HandleInput内部,我们可以使用Input.GetKeyKeyCode.LeftShift)方法来检查shift键是否被按下。

1
2
3
4
5
6
7
8
9
10
11
12
13
if (editMode) {
    EditCells(currentCell);
}
else if (Input.GetKey(KeyCode.LeftShift)) {
    if (searchFromCell) {
        searchFromCell.DisableHighlight();
    }
    searchFromCell = currentCell;
    searchFromCell.EnableHighlight(Color.blue);
}
else {
    hexGrid.FindDistancesTo(currentCell);
}


Unity 六边形地图系列(十六) :寻路

从哪里开始进行搜索。

选择目标单元格

我们现在要找的不是找到到这个起始单元格的所有距离,我们现在正在寻找两个特定单元格之间的路径。所以重命名HexGrid.FindDistancesToHexGrid.FindPath并给它一个HexCell参数。同时调整搜索方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void FindPath (HexCell fromCell, HexCell toCell) {
    StopAllCoroutines();
    StartCoroutine(Search(fromCell, toCell));
}
 
IEnumerator Search (HexCell fromCell, HexCell toCell) {
    for (int i = 0; i < cells.Length; i++) {
        cells[i].Distance = int.MaxValue;
    }
 
    WaitForSeconds delay = new WaitForSeconds(1 / 60f);
    List<hexcell> frontier = new List<hexcell>();
    fromCell.Distance = 0;
    frontier.Add(fromCell);
    
}

HexMapEditor.HandleInput现在必须调用调整后的方法,使用searchFromCellcurrentCell作为参数。 另外,当我们知道要搜索的单元格的时候,我们只能寻找一条路径。当目的地与起点相同的时候,我们就不必去寻路。

1
2
3
4
5
6
7
8
9
if (editMode) {
    EditCells(currentCell);
}
else if (Input.GetKey(KeyCode.LeftShift)) {
    
}
else if (searchFromCell && searchFromCell != currentCell) {
    hexGrid.FindPath(searchFromCell, currentCell);
}

一旦我们要搜索,我们应该首先摆脱以前的所有突出显示部分。 所以HexGrid.Search在重置距离时禁用突出显示部分。 由于这也会禁用起始单元格的突出显示,因此再次启用起始单元格的突出显示。此时,我们也可以突出显示目的地单元格。让我们把目的地单元格变成红色。

1
2
3
4
5
6
7
8
9
10
IEnumerator Search (HexCell fromCell, HexCell toCell) {
    for (int i = 0; i < cells.Length; i++) {
        cells[i].Distance = int.MaxValue;
        cells[i].DisableHighlight();
    }
    fromCell.EnableHighlight(Color.blue);
    toCell.EnableHighlight(Color.red);
     
    
}


Unity 六边形地图系列(十六) :寻路

潜在路径的终点。

限制搜索

在此时,我们的搜索算法仍然计算从起始单元格可到达的所有单元格的距离。 这个计算现在不再需要了。一旦我们找到到目的地单元格的最终距离之后,我们就可以停下来。所以当当前单元格是目的地的时候,我们可以跳出算法的循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
while (frontier.Count > 0) {
    yield return delay;
    HexCell current = frontier[0];
    frontier.RemoveAt(0);
 
    if (current == toCell) {
        break;
    }
 
    for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
        
    }
}


Unity 六边形地图系列(十六) :寻路

停在目的地单元格。

如果目的地不能达到会怎么样?

算法会继续,直到所有可访问的单元格都被搜索到。没有提前退出的可能性,它将像旧的FindDistancesTo方法一样。

显示整个路径

我们可以找到路径的开始单元格和结束单元格之间的距离,但是我们还不知道实际的路径是什么。要做到这一点,我们必须跟踪每个单元格是如何达到的。 我们该怎么做呢?

当向边界添加单元格的时候,我们这样做是因为它是当前单元格的邻居。唯一的例外是起始单元格。所有其他单元格都是通过当前单元格达到。如果我们跟踪每个单元格是从哪个单元格到达的,我们最终会有一个单元格网络。一个树形网络,起始单元格为根。一旦我们到达目的地单元格,我们可以使用它来构建路径。

Unity 六边形地图系列(十六) :寻路

描述到中心点路径的树形网络。

我们可以通过向HexCell添加另一个单元格引用来存储此信息。我们不需要序列化这个数据,所以让我们为它使用默认属性。

1
public HexCell PathFrom { get; set; }

返回到Hex Grid.Search,在将邻接单元格添加到边界的时候,将邻接单元格的PathFrom 设置为当前单元格。当我们找到一条较短的路径到邻接单元格的时候,我们也必须改变这个引用。

1
2
3
4
5
6
7
8
9
if (neighbor.Distance == int.MaxValue) {
    neighbor.Distance = distance;
    neighbor.PathFrom = current;
    frontier.Add(neighbor);
}
else if (distance < neighbor.Distance) {
    neighbor.Distance = distance;
    neighbor.PathFrom = current;
}

到达目的地后,我们可以通过将这些引用返回到起始单元格来显示路径,并将其突出显示出来。

1
2
3
4
5
6
7
8
if (current == toCell) {
    current = current.PathFrom;
    while (current != fromCell) {
        current.EnableHighlight(Color.white);
        current = current.PathFrom;
    }
    break;
}


Unity 六边形地图系列(十六) :寻路

找到了一条路径

请注意,通常有多条最短路径。找到哪个最短路径取决于处理单元格的顺序。 一些路径可能看起来不错,其他路径可能看起来不那么好,但是永远不会找到一条更短的路径。我们稍后再回来继续这个话题。

调整搜索开始的部分

一旦选择了起始单元格,更改目标单元格将触发新的搜索。当选择新的起始单元格的时候也应该这样做。为了使之成为可能,HexMapEditor还必须记住目标单元格。

1
HexCell previousCell, searchFromCell, searchToCell;

使用此字段,我们也可以在选择新的起始单元格的时候启动新的搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
else if (Input.GetKey(KeyCode.LeftShift)) {
    if (searchFromCell) {
        searchFromCell.DisableHighlight();
    }
    searchFromCell = currentCell;
    searchFromCell.EnableHighlight(Color.blue);
    if (searchToCell) {
        hexGrid.FindPath(searchFromCell, searchToCell);
    }
}
else if (searchFromCell && searchFromCell != currentCell) {
    searchToCell = currentCell;
    hexGrid.FindPath(searchFromCell, searchToCell);
}


1
2
3
4
5
6
7
8
if (editMode) {
    EditCells(currentCell);
}
else if (
    Input.GetKey(KeyCode.LeftShift) && searchToCell != currentCell
) {
    
}


项目文件下载地址:unitypackage

更聪明的搜索

虽然我们的搜索算法能够找到最短的路径,但花费了大量时间来搜索那些显然不会成为该路径的一部分的单元格。至少这对我们来说很明显。 该算法没有地图的高层视图。看不到在某些方向的搜索是毫无意义的。 它更喜欢跟随道路,即使他们远离目的地。我们能做得更聪明吗?

目前,我们只是在决定下一个处理哪个单元格的时候考虑一个单元格的距离。 如果我们想要这么聪明搜索的话,我们还要考虑到目的地的距离。不幸的是,我们还不知道这个信息。但是我们可以估计剩下的距离。将其添加到单元格距离的时候给出了通过该单元格的总路径长度的指示。然后,我们可以使用它来确定单元格的搜索优先级。

启发式搜索

当我们依靠估计或猜测而不是确切知道的数据的时候,我们说我们使用的是启发式搜索方法。这个启发式代表了我们对剩余距离的最好猜测。我们必须为我们搜索的每个单元格确定此值,因此为HexCell添加一个整数属性。我们不需要序列化它,所以我们可以使用另一个默认属性。

1
public int SearchHeuristic { get; set; }

我们如何猜到剩下的距离? 在最理想的情况下,会有直达目的地的道路。 如果是这样,距离等于该单元格的坐标与目的地单元格之间的未修改的距离。让我们用它作为我们的启发式距离。

由于启发式距离不依赖于到目前为止所算出的路径,所以在搜索过程中是不变的。所以当HexGrid.Search添加一个单元格到边界的时候,我们只需要计算一次。

1
2
3
4
5
6
7
if (neighbor.Distance == int.MaxValue) {
    neighbor.Distance = distance;
    neighbor.PathFrom = current;
    neighbor.SearchHeuristic =
        neighbor.coordinates.DistanceTo(toCell.coordinates);
    frontier.Add(neighbor);
}

搜索优先级

从现在开始,我们将基于单元格距离加上启发式距离来确定搜索优先级。让我们为HexCell添加一个方便的属性。

1
2
3
4
5
public int SearchPriority {
    get {
        return distance + SearchHeuristic;
    }
}

为了使这个工作,调整HexGrid.Search方法,以便这个方法使用这个属性来排序边界。

1
2
3
frontier.Sort(
    (x, y) => x.SearchPriority.CompareTo(y.SearchPriority)
);

Unity 六边形地图系列(十六) :寻路 Unity 六边形地图系列(十六) :寻路

使用启发式搜索vs不启发式搜索。

可接受的启发式距离

使用我们新的搜索优先级,我们确实最终访问了更少的单元格。然而,在无特征图上,算法仍然会处理方向错误的单元格。这是因为我们的默认移动成本是每步5个,而启发式算法则仅仅每步增加1个。所以启发式距离的影响力不是很强。

如果地图上的移动成本相同,那么我们可以在确定启发式距离的时候使用相同的成本。在我们的情况下,这将是我们目前的启发式距离乘以5。这将大大减少要处理单元格的数量。

Unity 六边形地图系列(十六) :寻路

使用启发式距离乘以5的结果。

但是,如果地图上有道路,我们可能会高估剩下的距离。 因此,该算法可能会产生错误并产生实际上不是最短路径的结果。

Unity 六边形地图系列(十六) :寻路 Unity 六边形地图系列(十六) :寻路

高估的启发式距离与可接受的启发式距离。

为了保证我们找到最短的路径,我们必须确保我们从不高估剩余的距离。这被称为可接受的启发式搜索方法。因为我们的最低运动成本是1,我们别无选择,只能在确定启发式距离的时候使用相同的成本。

在技术上,使用更低的成本是件好事,但这只会使启发式搜索更弱。最低的启发式距离是零,那么这就演变成Dijkstra的算法。当启发式距离非零的时候,该算法被称为A *,发音为A星。

为什么叫A *

Nils Nilsson首先介绍了对Dijkstra算法添加启发式距离的想法。他命名他的变种为A1。后来,Bertram Raphael做了一个更好的版本,他命名为A2。 之后,彼得·哈特证明,A2如果带有一个很好的启发式距离的话,就是最佳选择,所以没有一个更好的版本。这促使他把它命名为A *,表明永远不会有其他改进,如A3A4。 所以是的,A *算法是你将会获得的最好的算法,但是它只是和启发式搜索算法一样好。

项目文件下载地址:unitypackage

优先队列

虽然A *是一个很好的算法,但我们的实现并不那么有效。这是因为我们正在使用列表来存储边界,我们必须对每个迭代进行排序。 如上一个教程所述,我们需要的是一个优先级队列,但优先级队列没有一个标准的实现。现在我们来创造一个优先级队列。

我们的队列必须基于优先级来支持入队和出队操作。它还必须支持改变已经在队列中的单元格的优先级。在理想情况下,我们实现这一点,同时最小化搜索、排序和内存分配。而且我们也想保持简单。

创建自定义队列

创建一个具有必需的公共方法的新HexCellPriorityQueue类。我们将使用一个简单的列表来跟踪队列的内容。另外,给它一个清除方法重置队列,所以我们可以重用它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using System.Collections.Generic;
 
public class HexCellPriorityQueue {
 
    List<hexcell> list = new List<hexcell>();
 
    public void Enqueue (HexCell cell) {
    }
 
    public HexCell Dequeue () {
        return null;
    }
     
    public void Change (HexCell cell) {
    }
     
    public void Clear () {
        list.Clear();
    }
}</hexcell></hexcell>

我们将单元格优先级存储在单元格本身中。 因此,在添加到队列之前,必须先设置单元格的优先级。但是,在优先级更改的情况下,知道什么是旧的优先级可能是有用的。所以我们把它添加为一个名为Change的参数。

1
2
public void Change (HexCell cell, int oldPriority) {
}

知道队列中有多少个单元格也很有用,因此添加一个Count属性。这个字段只需要适当的递增和递减就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int count = 0;
 
public int Count {
    get {
        return count;
    }
}
 
public void Enqueue (HexCell cell) {
    count += 1;
}
 
public HexCell Dequeue () {
    count -= 1;
    return null;
}
 
 
public void Clear () {
    list.Clear();
    count = 0;
}


添加到队列

当一个单元格被添加到队列中的时候,我们首先简单地使用它的优先级作为其索引,将该列表作为一个简单的数组。

1
2
3
4
5
public void Enqueue (HexCell cell) {
    count += 1;
    int priority = cell.SearchPriority;
    list[priority] = cell;
}

但是,这个方法只有在列表足够长的情况下才有效果,否则我们会超出范围。 我们可以通过在列表中添加虚拟元素,直到它具有所需的长度来阻止出现超出范围的情况。这些空元素不引用单元格,因此它们是通过向列表中添加null来创建的。

1
2
3
4
5
int priority = cell.SearchPriority;
while (priority >= list.Count) {
    list.Add(null);
}
list[priority] = cell;


Unity 六边形地图系列(十六) :寻路

带有孔的列表。

但是,这只为每个优先级存储一个单元格,但是可能会在一个优先级存在多个单元格。为了跟踪所有具有相同优先级的单元格,我们必须使用另一个列表。虽然我们可以根据优先级使用实际列表,但我们也可以向HexCell添加一个属性以将它们链接在一起。这允许我们创建一个称为链表的单元格链。

1
public HexCell NextWithSamePriority { get; set; }

要创建链,请使用HexCellPriorityQueue.Enqueue使新添加的单元格在更换之前以相同的优先级引用当前值。

1
2
cell.NextWithSamePriority = list[priority];
list[priority] = cell;


Unity 六边形地图系列(十六) :寻路

链表的链表。

从队列中删除

要从优先级队列中检索单元格,我们必须访问最低非空索引处的链表。所以对列表进行循环,直到我们找到最低非空索引处的链表。如果我们没有找到最低非空索引处的链表,那么队列是空的,我们返回null

我们可以从发现的链表中返回任何单元格,因为它们都具有相同的优先级。 在链表的开头返回单元格是最简单的。

1
2
3
4
5
6
7
8
9
10
public HexCell Dequeue () {
    count -= 1;
    for (int i = 0; i < list.Count; i++) {
        HexCell cell = list[i];
        if (cell != null) {
            return cell;
        }
    }
    return null;
}

为了保持对链表的其余部分的引用,请使用与新开始的单元格具有相同优先级的下一个单元格。如果在此优先级别中只有一个单元格,元素将变为null,将来会被跳过。

1
2
3
4
if (cell != null) {
    list[i] = cell.NextWithSamePriority;
    return cell;
}


跟踪最低优先级

这种方法有效,但要求我们在每次检索单元格的时候遍历列表。我们不能避免搜索最低非空索引,但是我们不必每次从零开始。相反,我们可以跟踪最低优先级,并从那里开始搜索。 在起始的地方,最低优先级是无限的。

1
2
3
4
5
6
7
8
9
int minimum = int.MaxValue;
 
 
public void Clear () {
    list.Clear();
    count = 0;
    minimum = int.MaxValue;
}

将单元格添加到队列中的时候,在必要的时候调整最小值。

1
2
3
4
5
6
7
8
public void Enqueue (HexCell cell) {
    count += 1;
    int priority = cell.SearchPriority;
    if (priority < minimum) {
        minimum = priority;
    }
    
}

当出队的时候,使用最小值来遍历列表,而不是从零开始。

1
2
3
4
5
6
7
8
9
10
11
public HexCell Dequeue () {
    count -= 1;
    for (; minimum < list.Count; minimum++) {
        HexCell cell = list[minimum];
        if (cell != null) {
            list[minimum] = cell.NextWithSamePriority;
            return cell;
        }
    }
    return null;
}

这大大减少了我们必须花费在我们的优先级列表中循环的时间。

改变优先级

当单元格的优先级更改的时候,我们必须将其从链接列表中删除,它当前是其中的一部分。为了做到这一点,我们必须跟踪链表,直到找到它为止。

首先将旧优先级列表的头部声明为当前单元格,并跟踪下一个单元格。我们可以直接获取下一个单元格,因为我们知道这个索引至少有一个单元格。

1
2
3
4
public void Change (HexCell cell, int oldPriority) {
    HexCell current = list[oldPriority];
    HexCell next = current.NextWithSamePriority;
}

如果当前单元格是更改后的单元格,那么它就是头部单元格,我们可以将其去掉,就好像它们出队了一样。

1
2
3
4
5
HexCell current = list[oldPriority];
HexCell next = current.NextWithSamePriority;
if (current == cell) {
    list[oldPriority] = next;
}

如果没有,我们必须跟踪链表,直到我们在变化的单元格前面找到一个单元格。那个对已经改变的单元格的引用已经发生了改变。

1
2
3
4
5
6
7
8
9
if (current == cell) {
    list[oldPriority] = next;
}
else {
    while (next != cell) {
        current = next;
        next = current.NextWithSamePriority;
    }
}

此时,我们可以通过跳过链表来删除已更改的单元格。

1
2
3
4
5
while (next != cell) {
    current = next;
    next = current.NextWithSamePriority;
}
current.NextWithSamePriority = cell.NextWithSamePriority;

单元格删除后,必须重新添加单元格,以便最终在列表中显示新的优先级。

1
2
3
4
public void Change (HexCell cell, int oldPriority) {
    
    Enqueue(cell);
}

Enqueue方法增加了计数,但是实际上并没有添加新的单元格。所以我们不得不减少这个计数来进行补偿。

1
2
Enqueue(cell);
count -= 1;


使用这个队列

现在我们可以在HexGrid中使用我们自定义的优先级队列。我们可以使用对所有搜索重复使用的单个实例来做到这一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
HexCellPriorityQueue searchFrontier;
 
 
IEnumerator Search (HexCell fromCell, HexCell toCell) {
    if (searchFrontier == null) {
        searchFrontier = new HexCellPriorityQueue();
    }
    else {
        searchFrontier.Clear();
    }
     
    
}

Search方法现在必须在开始循环之前将fromCell 入队,并且每次迭代都是通过对一个单元进行出队操作开始。这取代了旧的边界代码。

1
2
3
4
5
6
7
8
9
10
11
        WaitForSeconds delay = new WaitForSeconds(1 / 60f);
//      List<hexcell> frontier = new List<hexcell>();
        fromCell.Distance = 0;
//      frontier.Add(fromCell);
        searchFrontier.Enqueue(fromCell);
        while (searchFrontier.Count > 0) {
            yield return delay;
            HexCell current = searchFrontier.Dequeue();
//          frontier.RemoveAt(0);
            
        }</hexcell></hexcell>

调整用于添加和更改邻居单元格的代码。但在更改之前,请务必记住旧的优先级。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
                if (neighbor.Distance == int.MaxValue) {
                    neighbor.Distance = distance;
                    neighbor.PathFrom = current;
                    neighbor.SearchHeuristic =
                        neighbor.coordinates.DistanceTo(toCell.coordinates);
//                  frontier.Add(neighbor);
                    searchFrontier.Enqueue(neighbor);
                }
                else if (distance < neighbor.Distance) {
                    int oldPriority = neighbor.SearchPriority;
                    neighbor.Distance = distance;
                    neighbor.PathFrom = current;
                    searchFrontier.Change(neighbor, oldPriority);
                }

最后,我们不再需要排序边界。

1
2
3
//              frontier.Sort(
//                  (x, y) => x.SearchPriority.CompareTo(y.SearchPriority)
//              );

使用优先级队列进行搜索。

如前所述,找到哪个最短路径取决于单元格处理的顺序。我们的队列产生的是一个与排序列表不同的顺序,因此可以获得不同的路径。因为我们每个优先级都添加到链表的头部并从其中删除,所以它们的功能更像堆栈而不是队列。最后添加的单元格将首先被处理。这种方法的副作用是算法倾向于曲折的路径。这使得它更有可能产生锯齿形的路径。幸运的是,这样的路径往往看起来更好,所以这是一个很好的副作用。

Unity 六边形地图系列(十六) :寻路 Unity 六边形地图系列(十六) :寻路

排序列表与优先队列的对比结果。

这个教程的下一个部分将会关注实时寻路,将于20175月发布。。

项目文件下载地址:unitypackage

项目文档下载地址:PDF

 

【版权声明】

原文作者未做权利声明,视为共享知识产权进入公共领域,自动获得授权。

分类: 标签: HexMap
举报 分享

想免费获取内部独家PPT资料库? 观看行业大牛直播?

立即扫码加群

评论(1)

1个评论

GAD译馆

更多