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

相关文章

来自专栏一个会写诗的程序员的博客

java.sql.SQLException: connection holder is null

java.sql.SQLException: connection holder is null

1341
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5866
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9664
来自专栏封碎

Android中Broadcast的Intent大全 博客分类: Android小技巧 Android.netWAPGoogle

952
来自专栏JMCui

MongoDB系列五(地理空间索引与查询).

Volvo Today, Volvo announced i...

2712
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1272
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2169
来自专栏菩提树下的杨过

linq to sql取出随机记录/多表查询/将查询出的结果生成xml

在手写sql的年代,如果想从sqlserver数据库随机取几条数据,可以利用order by NewId()轻松实现,要实现多表查询也可以用select * f...

2196
来自专栏项勇

[Android笔记7]之通过DatePickerDialog,TimePickerDialog调用系统时间设置

2753
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2232

扫码关注云+社区