介绍

后端基于偏移坐标系odd-q实现六角格地图，并提供获取邻居，两格子连线经过的格子等相关功能。且提供html可视化界面。

1.后端代码有些是基于ai 生成，然后自己进行调整，处理相关问题。

2.前端可视化界面基本都是由ai生成(当然有些大模型改不动的还是得自己调整)

3.六角个地图的几个核心算法介绍可以看Hexagonal Grids。有些功能链接中没有的，那就是我自己想的，比如基于两点获取连线。

4.测试案例不够多，可能会有bug

源码地址

https://github.com/g5zhu5896/hexgame

相关资料链接

下面地址需要翻墙

六角格地图整体介绍

Bresenham原版算法

Bresenham 增强版

功能介绍

1.获取邻居

如下图所示，用于获取指定格子周边的六个格子。

2.两格子连线

如下图所示,是用于获取选中的两个格子连直线中间穿过的格子。

3.范围查询

如下图所示，下图为查询(3,4) 距离为2的周边的所有格子,

4.距离计算

如下图所示，用于获取两个格子之间距离了多少个格子.也是最短路径需要结果的格子数

5.方向查询

如下图所示，用于查询第二个格子相对于第一个格子在哪个方向。这个方向索引是我自己定义的，0表示正南南,逆时针旋转,以此类推,5表示西南。

限制

选中的两个格子必须时邻居

6.两点连线

如图所示,可以指定两个格子,并分别指定格子上各一个点,然后就能得到这两个点连线后会在哪个格子上面的哪个方向。

限制

1.两格子可相同，可不相同，但必须是邻居
2.两格子的点连线必须至少可以作为其中一个格子的一条边,否则连线失败
2.如果是两格子的共线,则会返回连线在结束点格子上的方向

可调整逻辑

两格子连线获取穿过格子

可以通过调整 HexMap 如下红框地方的代码切换实现方法

方法1：线性插值

介绍

通过线性插值的方式获取连线穿过的格子。适用于精度要求不高，对性能有要求的情况。实现类为 LerpHexLine

        优点:性能快,只要循环两格子距离的次数就可以获取结果

        缺点:会存在偏差，获取的结果并不是连线穿过的所有格子,存在边缘的时候会出现一些偏差。虽然可以通过 调整采样次数(后续会介绍)来减少偏差，但是却不治本。

偏差问题

如下图所示,连线应该要穿过(3,3),但实际没用。默认返回的格子数为两格子的距离

上述情况可以通过调整采样次数( LerpHexLine 中的 k 值),减少偏差。采样次数越多，偏差应该越小，同时循环次数变多，性能越差。采样次数为 【两格子距离*k】

如下为 k=3 时的效果,覆盖到 (3,3) 了

但是在k=3时,下图却不包含 (5,0)

所以，提高采样次数，只能减少偏差，但不治本(也可能会存在一个值可以让偏差几乎为0,但是多少不知道，但性能得降低很多)

共边问题

两格子连线经过共边时(同行或斜向)的时候会出现问题(应该也是偏差问题，只是这种偏差可以通过其他方法解决)，正常情况如下图所示

目前可过 LerpHexLine.getLineBetween 中如下代码将共边的两个格子都会包含在结果集(这个方法也会用于方法2,感觉处理共边性能更好)

共边有三种情况,效果如下所示

同行

左斜

右斜

可以选择修改 HexLine.hexLineSameRow、HexLine.hexLineRightSameEdge、HexLine.hexLineLeftSameEdge 中相关代码自己控制结果集在共边的时候需要如何处理。如下面图修改红框注释的逻辑即可

方法2：几何学方式

介绍

通过几何学的方式获取连线穿过的格子。适用于精度要求高的场景。实现类为 GeometryHexLine

        优点:没bug的话返回结果准确不会出现偏差。

        缺点:性能不如线性插值,需要判断多个六角格多边形是否和直线相交等相关逻辑

减少判断六角格数量优化

如果不做任何优化,直接取全地图的进行判断，那计算量就太大了,所以考虑通过一些方式减少需要参与计算的格子数。目前提供两种优化方法,通过修改 GeometryHexLine.getLineBetween 中如下红框代码调整

方法一：获取外包围盒内的格子

就是基于两格子的最大行、列和最小行列，获取最大的外包围盒内的所有格子，这样计算的格子数就会在两个行列的周边。对应 GeometryHexLine.getBoundaryHexes 的代码

        优点:我只能想到比获取所有格子好

        缺点:获取的格子数会比方法二多，所以个人感觉性能比方法二差，当然没验证过。

获取格子的效果如下图所示

这个方法还可以进行优化，就是提前对整个地图切片，分成多个区域且分多层,这样就不需要每次都要计算边界,然后获取起点格子和终点格子所在的层级区域的所有格子,理论上性能应该能更好点。

方法二：通过类似线性插值的方式

类似线性插值的方式，只是插值的时候选择更大的范围，而不是最接近的几个格子。对应 GeometryHexLine.getLerpCloseHex 的代码

        优点:获取的格子数会比方法一少，所以个人感觉性能比方法一好，当然没验证过。

        缺点:我也不知道，我自己想的方法，目前我验证好像时没错的,但不保证百分百准确。只是我个人感觉时对的

获取的格子效果如下图所示.

方法三：bresenham增强版

介绍

后面基于 Bresenham 增强版 实现的,解决了 bresenham 原版是和 lerp 方法一样的偏差问题的。

        优点:感觉就是结合了方法一和方法二的优点，效率快加准确

        缺点:目前验证的例子好像都是对的，不确定是否存在某种情况不准确。

共边问题

这种方法在共边的时候的结果也是错误的，所以当共边的时候使用了方法一解决共边问题的代码

两点连线获取格子边

目前两点连线当存在共边时,只返回结束点所在格子该连线所在方向。如果想要拿到该连线在共边的两个格子的方向。可以调整 HexMap.getEdge  如下所示的红框代码.只要在共边的时候让红框的代码都执行，就可以拿到连线分别在两个格子中的方向