正六边形网格化(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 条评论
登录 后参与评论

相关文章

来自专栏机器人网

图像识别:微信跳一跳机器人

准备 IDE:VisualStudio Language:VB.NET/C# GitHub:AutoJump.NET 本文将向你介绍一种通过图像识别实现“跳一跳...

2735
来自专栏何俊林

OpenGL ES总结(一)OpenGL 初识

导读:OpenGL是在图形图像中,非常优秀的渲染库,文中Demo下载地址:https://github.com/hejunlin2013/OpenGL31,看下...

2627
来自专栏清墨_iOS分享

OpenGLES-04 绘制带颜色的立方体

前面几篇文章都只是绘制了平面图形,接下来我们开始绘制一个真正的3D立方体图形。代码在前一篇文章基础上修改。 绘制立方体之前,我们需要知道这个立方体的各个顶点坐...

3499
来自专栏数据小魔方

sparklines迷你图系列7——Comparision(+/-Variance)。

今天跟大家分享sparklines迷你图系列的第七篇——Comparision(+/-Variance)。 该图表用于表现指标增长率波动情况,波动范围-100%...

2395
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[06-1]:基础纹理

Texture 在 OpenGL 里面有很多种类,但在 ES 版本中就两种——Texture_2D + Texture_CubeMap;

1032
来自专栏机器人网

别让接线这件小事,拉开你与工程师的差距

导线与导线的连接、线头与接线桩的连接,事情小,责任大。本文图文并茂,让你清清楚楚看懂! 导线与导线的连接 导线的连接情况有:单股铜芯导线的直线连接、T字形连接;...

3237
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

简单探讨可牛影像软件中具有肤质保留功能的磨皮算法及其实现细节。

     在几年前写的一篇关于BEEP的文章时,我曾经说过Beep的去噪作用可以用于磨皮,并且给出了结论BEEP比可牛和美图等的效果要更为好,现在看来,那个结论...

2096
来自专栏章鱼的慢慢技术路

用OpenGL进行曲线、曲面的绘制

1747
来自专栏数据小魔方

sparklines迷你图系列12——Composition(Pie)

今天分享sparklines迷你图系列13——Composition(Pie)。 大家看到名字就肯定知道是饼图了。借助sparklines迷你图工具,我们可以通...

2467
来自专栏企鹅号快讯

opencv是Python处理图片的利器!Python大牛教你玩转opencv!

opencv作为我最常用的图像处理库,当然第一个介绍,并且介绍得比较全面。毋庸置疑,opencv是今天介绍得所有图像库中最全面也最强大的库,如果我们只想掌握一个...

3415

扫码关注云+社区