六边形地图的生成算法
六边形地图系列的第一部分。许多游戏,尤其是战略游戏,都常使用六边形的网格地图。包括《奇迹时代3》,《文明5》和《无尽传奇》等等
六边形网格
为什么用六边形
相比于正方形网格,六边形网格的相邻格由八个变成了六个,并且都是在边上相邻。也就是说每个相邻格对于中间的单元格距离是一致的,这无疑简化了很多事情。
在开始之间,我们先定义六边形的大小。如下图,以边长10作为基准,所以圆心到每个角的距离也是10,因为六边形是由六个等边三角形组成的。我们把圆心到角的距离称作六边形的外径。
网格构建
六边形坐标
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using UnityEngine;
[ ]
public struct HexCoordinates
{
[ ]
private int x, z;
public int X
{
get { return x; }
}
public int Z
{
get { return z; }
}
public int Y
{
get
{
return -X - Z;
}
}
public HexCoordinates(int x, int z)
{
this.x = x;
this.z= z;
}
public static HexCoordinates FromOffsetCoordinates(int x, int z)
{
return new HexCoordinates(x - z / 2, z);
}
public override string ToString()
{
return "(" + X.ToString() + "," + Y.ToString()+","+ Z.ToString() + ")";
}
public string ToStringOnSpearateLines()
{
return X.ToString() + "\n"+ Y.ToString() +"\n" + Z.ToString();
}
public static HexCoordinates FromPosition(Vector3 position)
{
float x = position.x / (HexMetrics.innerRadius * 2);
float y = -x;
float offset = position.z / (HexMetrics.outerRadius * 3f);
x -= offset;
y -= offset;
int iX = Mathf.RoundToInt(x);
int iY = Mathf.RoundToInt(y);
int iZ = Mathf.RoundToInt(-x - y);
if(iX+iY+iZ!=0)
{
float dX = Mathf.Abs(x - iX);
float dY = Mathf.Abs(y - iY);
float dZ = Mathf.Abs(-x - y - iZ);
if (dX > dY && dX > dZ)
{
iX = -iY - iZ;
}
else if (dZ > dY)
{
iZ = -iX - iY;
}
}
return new HexCoordinates(iX, iZ);
}
}六边形单元格
1
2
3
4
5
6
7
8
9
10using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class HexCell : MonoBehaviour
{
public HexCoordinates coordinates;
public Color color;
}网格创建
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
public class HexGrid : MonoBehaviour
{
public int width = 6;
public int height = 6;
public HexCell cellPrefab;
public Text cellLabelPrefab;
Canvas gridCanvas;
HexMesh hexMesh;
HexCell[] cells;
private void Awake()
{
gridCanvas = GetComponentInChildren<Canvas>();
hexMesh = GetComponentInChildren<HexMesh>();
cells = new HexCell[width*height];
for(int z=0,i=0; z<height;z++)
{
for(int x=0;x<width;x++)
{
CreateCell(x, z, i++);
}
}
}
private void Start()
{
hexMesh.TriangulateAll(cells);
}
void CreateCell(int x,int z,int i)
{
Vector3 position;
position.x = (x+z*0.5f-z/2) * (HexMetrics.innerRadius * 2f);
position.y = 0f;
position.z = z * (HexMetrics.outerRadius * 1.5f);
HexCell cell = cells[i] = Instantiate(cellPrefab);
cell.transform.SetParent(transform, false);
cell.transform.localPosition = position;
cell.coordinates = HexCoordinates.FromOffsetCoordinates(x, z);
cell.color = Color.white;
Text label = Instantiate(cellLabelPrefab);
label.rectTransform.SetParent(gridCanvas.transform, false);
label.rectTransform.anchoredPosition = new Vector2(position.x, position.z);
label.text = cell.coordinates.ToStringOnSpearateLines();
}
public void ColorCell(Vector3 position,Color color)
{
position = transform.InverseTransformPoint(position);
HexCoordinates coordinates = HexCoordinates.FromPosition(position);
int index = coordinates.X + coordinates.Z * width + coordinates.Z / 2;
HexCell cell = cells[index];
cell.color = color;
hexMesh.TriangulateAll(cells);
Debug.Log("touched at " + coordinates.ToString());
}
}
A星寻路
需求
给定六边形网格的一个起点和一个终点,函数能够返回从起点到终点的通路经过哪些六边形。
实现
开启列表:需要考虑的节点都会被放到开启列表中,刚开始的时候开启列表只有起点一个节点,然后根据节点的相邻节点集,会逐渐把附近的节点都加到开启列表中。
关闭列表:所有不在考虑的节点的集合
估值:每个节点都做估值,估算值F = G + H:
G: 从起点,沿着产生的路径,移动到网格上指定方格的移动耗费。在这里,我们认为相邻的六边形,移动消耗是1
H:从网格上那个方格移动到终点B的预估移动耗费。这经常被称为启发式的,可因为它只是个猜测。这个H值的估算方式有很多种,我们暂时使用两个节点的直线距离
1 | public static List<Hexagon> searchRoute(Hexagon thisHexagon, Hexagon targetHexagon) |