在具有负坐标的三角形/六边形网格上实现 A*
遵循使用这个问题作为新问题基础的明显传统，我也有我希望尽可能优雅地解决一个问题：
我已经实现了这样的六角形地图：（
想在此处插入图像..但由于是新的而不允许我...请参阅上面的链接）
但是现在想知道如何（优雅地）使用这些类型的坐标为此类地图实现 A*。 我有在典型的方形网格（我认为是笛卡尔网格？）上使用 A* 的经验，并且我在那里处理它的方式似乎与这个坐标系不兼容。
通常我会生成一个二维字节数组。数组的索引将对应于网格坐标，并且所述索引处的值将给出该节点的“权重”。 （0 表示不可移动，较高的数字比较低的数字“权重”更多）。
例子： sbyte[,] pathGrid = 新 sbyte[5, 5] { {0,0,1,0,0}, {9,5,1,3,0}, {9,5,1,3,0}, {9,5,1,3,0}, {0,0,1,0,0} };
如果 0 是不可通过的，那么 1 就可以很容易地遍历，并且数字越大，遍历的“成本”就越高。 （对格式感到抱歉......我是一个堆栈溢出新手：P） 该数组将根据我的地图的组成生成，然后输入到我的路径查找算法中，该算法将依次输出节点列表（路径），或者如果未找到路径则返回 null。
然而，使用这种类型的网格，这是不可能的（至少乍一看），因为负坐标（这显然不适用于数组）以及网格不遵循与 ' 相同的规则。典型的网格。
我认为有一些方法可以使用我的 A* 方法来解决这个问题，但它们都相当草率（转换网格坐标并使用空节点），我想知道是否有人想到了一种方法来优雅地做到这一点。
无论如何，感谢您的阅读:) （顺便说一句，我在 C#/.net 中这样做是为了它的价值）
Following the apparent tradition of of using this question as the basis of new questions I too have a problem I am looking to solve as elegantly as possible:
I have implemented a hexagonal map as such:
(Wanted to insert image here.. but I'm not allowed due to being new... Please see above link)
But am now wondering how to (elegantly) implement A* for this type of map with these types of coordinates.
I have experience with using A* on typical squared grids (cartesian grids I think?) and the way I handle it there seems incompatible with this coordinate system.
Typically I would generate a 2D array of bytes. The indices of the array would correspond to a grid coordinate and the value at said index would give the 'weight' of that node. (0 being impassible and higher numbers 'weighing' more then lower numbers).
Example:sbyte[,] pathGrid = new sbyte[5, 5]
{
{0,0,1,0,0},
{9,5,1,3,0},
{9,5,1,3,0},
{9,5,1,3,0},
{0,0,1,0,0}
};
Where the 0's would be impassible, the 1's would be easily traversable, and higher numbers would 'cost' more to traverse. (sorry about formatting.. I'm a stack overflow newb :P )
This array would be generated based on the composition of my map and then fed into my path finding algorithm which would in turn spit out a list of nodes (the path) or return null if no path was found.
However, using this type of grid, that isn't possible (at least at first glance) due to negative coordinates (which obviously do not work in an array) and the fact that the grid doesn't follow the same rules as a 'typical' grid.
There are ways to solve this using my A* method I think but they are all rather sloppy (converting grid coordinates and using empty nodes) and I was wondering if anybody has thought of a way to do this elegantly.
Thanks for reading in any case :)
(Btw I am doing this in C#/.net for what it's worth)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
即使数组的索引从 0 开始，您的程序也不需要在概念上以这种方式处理数组。例如，如果您总是在使用索引在数组中查找之前将 3 添加到索引中，那么您实际上拥有一个索引从 3 开始的数组。为了以这种方式简化数组的使用，您可以创建一个类例如称为
ArbitraryBaseArray，它包装了一个数组和一个指定所需基索引的数字。然后，您可以创建一个
HexGrid类，其中包含一个ArbitraryBaseArray数组，每个数组都有自己的基本索引（取决于十六进制区域的左边缘的外观）。该类可以有一个索引器，让您可以根据两个十六进制坐标查找特定元素。它还可以有一个静态方法，给定十六进制网格中的坐标，返回一个包含六个相邻坐标的数组； A*可以使用此方法。 （请注意，虽然您链接到的问题中的插图对每个六角形图块使用三个坐标，但两个坐标就足够了。）Even though the indices of an array begin at 0, your program doesn't need to conceptually treat the arrays that way. For instance, if you always add e.g. 3 to your indices before using them to look up in an array, you effectively have an array where the indices begin at 3. In order to simplify working with arrays in this way, you could create a class called e.g.
ArbitraryBaseArraythat wraps an array and a number that specifies the desired base index.Then, you could create a
HexGridclass that contains an array ofArbitraryBaseArray, each with their own base index (depending on how the left edge of your hex area looks). The class could have an indexer that lets you look up a specific element based on two hex coordinates. It could also have a static method which, given a coordinate in the hex grid, returns an array with the six neighbouring coordinates; this method could be used by A*. (Note that while the illustration in the question you linked to uses three coordinates for each hex tile, two coordinates are sufficient.)您可以将坐标存储在字典中：
这样您就不再局限于正坐标，而且也不受每个节点的路径数量的限制
You could store your coordinates in a dictionary:
This way you're not limited to positive coordinates, and you're also not limited on the number of paths from each node