正六边形网格化(Hexagonal Grids)原理与实现

 在路径规划、游戏设计栅格法应用中,正六边形网格不如矩形网格直接和常见,但是正六边形具有自身的应用特点,更适用于一些特殊场景中,比如旷阔的海洋、区域或者太空。本文主要讲述如何对正六边形进行几何学分析、网格化环境建模、坐标系转换以及正六边形间的关系求解等。六边形的具体代码实现可以参见github: https://github.com/wylloong/HexagonalGrids .

几何学分析:正六边形的边长相等,内角都是120度,其它性质可以参见百度百科。在正六边形网格化布局设计中,典型的正六边形方向有水平方向(pointy topped,图1)和垂直方向(flat topped,图2)两类,两者性质类似。篇幅所限,本文主要讨论pointy topped类型的正六边形网格化布局。

图 1. pointy topped

图 2. flat topped

如图3所示的正六边形布局,针对pointy topped型的正六边形,设其边长为size,则六边形的宽width=sqrt(3)/2*size,和相邻六边形的水平距离hori=sqrt(3)/2*size,六边形的高是height=size*2,和相邻六边形的垂直距离是vert=1.5*size。

图 3. pointy topped型的正六边形几何示意图

坐标系选择:假设实现六边形网格化,那么六边形位置关系的表达有很多方式,有Offset coordinates、Cube coordinates、Axial coordinates等。本文推荐使用Cube coordinates作为主要的展示方式,Axial coordinates作为网格存储单位和显示坐标系。

  Offset coordinates:最常用的坐标系,以左上角为坐标系原点,以横向为column轴,以纵向为roe轴,对行和列进行偏置。其中,针对flat topped型的正六边形,具有奇和偶两种表示方式,如下图所示。

  Cube coordinates:一种全新的看待正六边形的方式,它把正六边形看作具有三个轴,并且满足x+y+z=0的性质,并且我们可以使用标准的方法实现坐标系的加减乘除和求距离。Cube坐标系的原理和其它性质可以参见文献。

  因为我们已经有针对方形网格和cube网格的计算方法,使用cube坐标系允许我们对六边形采用这些算法。当这个算法要和其他坐标系交互时,我会把其他坐标系转换为cube坐标系,然后计算结束后在转换为其他坐标系。

  Axial coordinates:该坐标系是由cube坐标系中三个轴中的两个组成的。因为在cube坐标系有x+y+z=0的限制,所以第三个轴是多余的。Axial coordinates主要应用于地图存储和对用户的显示。Axial coordinates相比offset grids的优点是坐标系更清楚,劣势是当存储一个长方形地图时显得有点怪异。

  总结:Offset coordinates因为符合square grids通用的笛卡尔坐标系,是我们最容易想到的坐标系,但是因为两轴中的一轴必须跟随变化,是一件复杂的事情;Cube and axial systems随着增长而变化并且具有相对简单的计算方法,但是在存储时具有一定的复杂度。

Coordinate conversion:我们通常在项目中使用axial or offset coordinates,但是很多算法使用cube坐标系更容易去表达,所以我们需要在坐标系之间转换。

  Axial coordinates和cube coordinates联系紧密,所以转换公式相对简单。

  Offset coordinates和cube coordinates转换有点复杂。本文主要针对even-q offset和odd-q offset进行研究。

邻近网格:cube coordinates容易求出相邻的6个邻近正六边形网格,但是offset坐标系却比较复杂。

  Cube coordinates:在正六边形上移动一个网格,涉及到改变cube坐标系中两个轴,一个+1,另一个-1,所以共有六种可能性,每一种可能性对应于六边形的一个方向。

  Axial coordinates:如前所示,我们以cube为起点,由cube转换为axil坐标系即可,如下图所示。

Distance: 在cube坐标系中,每一个六边形是一个在cube里面的3d空间。在六边形中相邻的六边形距离是1,但是在cube grid里面距离是2,这会让距离求解变得简单和快速。在square grid中,Manhattan distances are abs(dx) + abs(dy). In a cube grid, Manhattan distances are abs(dx) + abs(dy) + abs(dz).

所以,在cube坐标系中,距离可以表示为

  在Axial coordinates,第三个坐标系是缺省的,所以通用的做法是先转变为cube坐标系,再求距离。

  在offset坐标系中,正如Axial coordinates坐标系,我们把offset转变为cube坐标系再求取距离。

 路径规划:如果使用基于图论的A*或者Dijkstra算法,在六边形中寻找最短路径和正方形网格并没有太多不同。其中,不同的是邻近网格位置获取方法不同,需要用到前面的方法获取临近网格。

启发函数:A*算法使用heuristic功能求出两个位置的距离。可以使用距离公式求出距离,乘以移动代价。

  参考文献和资料:

1、http://www.redblobgames.com/grids/hexagons/

2、Her I. Geometric transformations on the hexagonal grid[J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 1995, 4(9):1213-22.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT派

一份数学小白也能读懂的「马尔可夫链蒙特卡洛方法」入门指南

IT派 - {技术青年圈} 持续关注互联网、大数据、人工智能领域 大多数时候,贝叶斯统计在结果在最好的情况下是魔法,在最糟糕时是一种完全主观的废话。在用到贝...

3565
来自专栏AI2ML人工智能to机器学习

基于深度学习的文本分类?

曾几何时, SVM一统江湖, Lecun见证的Vapnik和Larry Jackel的世纪之赌, 从95年坚持到2000年依然岿然不动。 但是再过10年, 到2...

632
来自专栏LET

球心坐标与本地坐标

1416
来自专栏IT派

二十六条深度学习经验,来自蒙特利尔深度学习

【前言】2016年8月初的蒙特利尔深度学习暑期班,由Yoshua Bengio、 Leon Bottou等大神组成的讲师团奉献了10天精彩的讲座,剑桥大学自然语...

2947
来自专栏新智元

【谷歌大脑力作】RNN最新技术:注意力增强 RNN,四大模型

【新智元导读】谷歌大脑团队的Chris Olah & Shan Carter 整理了 2016 年递归神经网络(RNN)的发展,总结了神经图灵机、注意力界面、自...

3365
来自专栏机器学习算法全栈工程师

一种简单有效的网络结构搜索

这篇文章主要介绍了一种方法用于解决网络结构搜索中,搜索空间过大且训练时间过长,算力要求过高的问题。运用了爬山算法来搜索优秀的网络结构,主要是用了一个很nb的技术...

761
来自专栏WOLFRAM

用 Mathematica 玩转环面

1484
来自专栏新智元

【资源】17个最受欢迎的机器学习应用标准数据集

【新智元导读】学好机器学习的关键是用许多不同的数据集来实践。本文介绍了10个最受欢迎的标准机器学习数据集和7个时间序列数据集,既有回归问题也有分类问题,并提供了...

50214
来自专栏机器之心

专栏 | 大漠孤烟,长河落日:面向景深结构的风景照生成技术

机器之心专栏 上海交通大学电子工程系 作者:杨蕊 简介 2014 年以来,生成对抗网络(Generative Adversarial Networks)已经在各...

2728
来自专栏AI研习社

谷歌发布TensorFlow Lattice:得益于先验知识,提升模型泛化能力

AI研习社消息,近日,谷歌科学家发布TensorFlow Lattice,这是一套预建的TensorFlow Estimators,易于使用,它相当于是Tens...

3739

扫描关注云+社区