2

我正在使用 C++ 递归地制作六边形网格（使用多重链表样式）。我已经将它设置为可以轻松创建相邻的图块，但是因为我是递归地执行它，所以我只能为给定的图块创建所有 6 个邻居。显然，这会导致创建重复的瓷砖，我正试图以某种方式摆脱它们。因为我正在使用一个类，所以检查空指针似乎不起作用。它要么无法从我的 Tile 类转换为 int，要么以某种方式转换它但没有正确执行。我在创建时明确地将所有指针设置为 NULL，当我检查它是否仍然存在时，它说它不是即使我自初始化以来从未接触过它。有没有我应该这样做的特定方式？如果没有某种 NULL，我什至无法遍历网格

这是我的一些相关代码。是的，我知道这很尴尬。

瓦片类头：

class Tile
{
public:
    Tile(void);
    Tile(char *Filename);
    ~Tile(void);

    void show(void);
    bool LoadGLTextures();
    void makeDisplayList();
    void BindTexture();
    void setFilename(char *newName);

    char Filename[100];
    GLuint texture[2];
    GLuint displayList;
    Tile *neighbor[6];
    float xPos, yPos,zPos;
};`

瓷砖初始化：

Tile::Tile(void)
{
    xPos=0.0f;
    yPos=0.0f;
    zPos=0.0f;
    glEnable(GL_DEPTH_TEST);
    strcpy(Filename, strcpy(Filename, "Data/BlueTile.bmp"));
    if(!BuildTexture(Filename, texture[0]))
        MessageBox(NULL,"Texture failed to load!","Crap!",MB_OK|MB_ICONASTERISK);

    for(int x=0;x<6;x++)
    {
        neighbor[x]=NULL;
    }
}

相邻瓦片的创建：

void MakeNeighbors(Tile *InputTile, int stacks)
{
    for(int x=0;x<6;x++)
    {
        InputTile->neighbor[x]=new Tile();
        InputTile->neighbor[x]->xPos=0.0f;
        InputTile->neighbor[x]->yPos=0.0f;
        InputTile->zPos=float(stacks);
    }
    if(stacks)
    {
        for(int x=0;x<6;x++)
            MakeNeighbors(InputTile->neighbor[x],stacks-1);
    }
}

最后，遍历网格：

void TraverseGrid(Tile *inputTile)
{
    Tile *temp;
    for(int x=0;x<6;x++)
        if(inputTile->neighbor[x])
        {
            temp=inputTile->neighbor[x];
            temp->xPos=0.0f;
            TraverseGrid(temp);
            //MessageBox(NULL,"Not Null!","SHUTDOWN ERROR",MB_OK | MB_ICONINFORMATION);
        }

}

关键是“if(inputTile->neighbor[x])”，无论我是“if(inputTile->neighbor[x]==NULL)”还是我做的任何事情，它都没有正确处理它。哦，我也知道我还没有完全设置列表。现在只有一个方向。

4

5 回答 5

10

如果你想创建一个六边形网格，你应该记住，它可以很容易地使用普通网格进行模拟！

    __    __    __
\__/2 \__/4 \__/6 \
/1 \__/3 \__/5 \__/
\__/8 \__/10\__/12\
/7 \__/9 \__/11\__/
\__/  \__/  \__/  \

这将使生活更简单:)

因此，最简单的方法是

  1. 设置一个临时方格m*n
  2. 用瓷砖填充它
  3. 穿越网格并正确连接

现在连接，基于上图：

A) Connect to previous and next [x-1,y], [x+1,y]
B) Connect to row above and row below [x,y-1], [x,y+1]
C) Connect to row above previous and next [x-1,y-1], [x+1,y-1]

...并且您拥有所有所需的连接（只需记住检查边界以确定瓷砖是否不在边缘）-如果您以另一种方式握住瓷砖，您甚至可以删除网格:)。

于 2010-05-25T01:09:31.637 回答
1

创建。 递归是解决某些问题的一种简洁优雅的方法，但它并不是对所有问题都完美。我怀疑创建节点的纯递归解决方案会比Kornel Kisielewicz 的直接迭代解决方案复杂得多（即不太优雅）。这是因为构造函数需要知道其附近所有图块的布局，以避免重新创建已经存在的节点。Tile

遍历。 节点遍历代码中的主要问题是类似的，因为每个节点最终都会“遍历”回其父节点，从而再次开始循环，因此您最终会陷入无限循环并破坏堆栈。我想您正试图只访问每个图块一次，对吗？在这种情况下，TraverseGrid()需要有一个参数告诉它我们从哪个方向进入节点，这样我们就可以避免往回走。

但这还不够——你还需要更多的纪律来决定去哪个方向。简单地向所有方向展开，除了我们输入的方向之外，仍然会陷入无限循环和堆栈溢出，因为任何三个相邻的图块都会无限循环。为了递归地执行此操作，您需要真正考虑哪些策略最终会访问每个节点一次且仅一次。

一种可能性是更改 to 的签名，TraverseGrid()然后TraverseGrid(Tile *inputTile, int fromDir, bool leftmost)使用以下规则：

  • 如果我们从左上角进入，只遍历到右上角，通过leftmost = false.
  • 如果我们从左下或右上进入，只遍历到右下，通过leftmost = false。
  • 如果leftmost，并且我们的左下角有一个节点，那么也遍历该节点，传递leftmost = true。

当然fromDir，leftmost也可以组合成一个参数，但这给出了总体思路。

另一种选择是visited在每个图块中保留一个标志，在遍历该图块之前对其进行检查。那么你的遍历将是一个洪水填充。但同样，简单的迭代遍历可能更简单、更容易理解，并且具有使用恒定堆栈空间的额外好处。

于 2010-05-25T01:52:02.190 回答
1

我只是猜测 MakeNeighbors() 做了什么，但不是盲目地做InputTile->neighbor[x]=new Tile();，您可以在创建新邻居并初始化它之前检查邻居 [x] 是否为非 NULL。例如，如果它的父级创建它并设置它的所有邻居信息，那么它不应该去创建它的父级。

当父母创建孩子时，它还应该适当地定义孩子的其他邻居，只要它知道他们。因此，它应该确保 child[i] 也是 child[i-1] 和 child[i+1] 的邻居。

于 2010-05-25T01:18:15.777 回答
0

我实际上做了同样的事情，但我的模式更像是这样的：

00   01   02   03   04

   10    11   12   13   14

      20    21   22   23   24

         30   31   32   33   34

这使得很容易弄清楚可以达到什么，但会产生一种奇怪的偏移模式。我刚刚摆脱了（在上面的例子中）00,01,10 和 20，使它更像是这样的十六进制模式：

            02   03   04   05   06

         11   12   13   14   15

            21   22   23   24   25

         30   31   32   33   34

所以如果你看上面的模式，reachable 总是一样的：

从 23（调用 2“a”和 3“b”）您可以到达：

NW(a-1, b), NE(a-1, b+1), W(a, b-1), E(a, b+1), SW(a+1, b-1), SE(a+1,b)

这种模式应该适用于整个网格。

编辑：

我打算在评论中这样做，但它太长了。我可以看到两种方法。

1）分配节点数组（null，不分配它们）。每当您需要分配一个节点时，就这样做，但是当您需要引用一个节点时使用数组地址，如果它为空，则填充它，如果它有一个值，则使用该值。巨大的空数组不应该占用那么多内存，但如果他们这样做......

2) 创建一个 HashSet 来保存节点，其中节点类的哈希值计算如下：(a << 32 || b)。通过这种方式，您可以立即查看以前的节点是否存在。记住也要重载“equals”（只有当比较对象是相同类型并且 a 和 b 相等时，它才应该返回 true）。

在一个已知边界的人口最多的系统中，1 将节省内存，但如果您的系统是稀疏的（如您声称的那样），那么＃2 可以节省大量内存而不会降低效率。

于 2010-05-25T01:25:16.977 回答
0

在类声明中有第二个构造函数Tile(char *Filename);。也许这个构造函数用于创建主节点，但没有neighbor正确初始化？（未显示其实现。）

在不相关的节点上，构造函数中有一个重复项strcpy()，它没有任何用途，可能只会导致问题：

strcpy(Filename, strcpy(Filename, "Data/BlueTile.bmp"));
于 2010-05-25T01:25:57.650 回答