Recursively created linked lists with a class, C++

Question

I'm using C++ to recursively make a hexagonal grid (using a multiply linked list style). I've got it set up to create neighboring tiles easily, but because I'm doing it recursively, I can only really create all 6 neighbors for a given tile. Obviously, this is causing duplicate tiles to be created and I'm trying to get rid of them in some way. Because I'm using a class, checking for null pointers doesn't seem to work. It's either failing to convert from my Tile class to and int, or somehow converting it but not doing it properly. I'm explicitly setting all pointers to NULL upon creation, and when I check to see if it still is, it says it's not even though I never touched it since initialization. Is there a specific way I'm supposed to do this? I can't even traverse the grid without NULLs of some kind

Here's some of my relevant code. Yes, I know it's embarassing.

Tile class header:

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 Initialization:

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;
    }
}

Creation of neighboring tiles:

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);
    }
}

And finally, traversing the grid:

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);
        }

}

The key line is "if(inputTile->neighbor[x])" and whether I make it "if(inputTile->neighbor[x]==NULL)" or whatever I do, it just isn't handling it properly. Oh and I'm also aware that I haven't set up the list fully. It's only one direction now.

Answer 1

If you want to create a hexagonal grid you should remember that it easily can be simulated using a normal grid!

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

This will make life MUCH simpler :)

Hence the easiest way would be

1. set up a temporary square grid m*n
2. fill it with tiles
3. traverse the grid and connect properly

Now the connections, based on the diagram above:

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]

... and you have all desired connections (just remember to check bounds to decide if the tile isn't on the edge) -- if you hold the tiles in another way, you can even remove the grid :).

Answer 2

I'm only guessing at what MakeNeighbors() does, but instead of blindly doing InputTile->neighbor[x]=new Tile();, you could check to see if neighbor[x] is non-NULL before creating a new one and initializing it. E.g. if its parent creates it and sets all of its neighbor information, then it shouldn't go and create its parent.

When the parent creates the children, it should also define the children's other neighbors appropriately, as far as it knows them. So, it should make sure that child[i] also is neighbors with child[i-1] and child[i+1].

Answer 3

I actually did the same thing but my pattern was more like this:

00   01   02   03   04

   10    11   12   13   14

      20    21   22   23   24

         30   31   32   33   34

This makes it pretty easy to figure out what can be reached, but forces a strange offset pattern. I just got rid of (in the above example) 00,01,10 and 20 to make it more of a hex pattern like this:

            02   03   04   05   06

         11   12   13   14   15

            21   22   23   24   25

         30   31   32   33   34

So if you look at the pattern above, reachable is always the same:

from 23 (call 2 "a" and 3 "b") you can get to:

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)

This pattern should hold correct for the entire grid.

EDIT:

I was going to do this in a comment but it got too long. I can see two approaches.

1) Allocate the array of nodes (null, don't allocate them). Whenever you need to allocate a node, just do so, but use the array address whenever you need to reference a node, if it's null populate it, if it has a value use that value. Huge empty arrays shouldn't take up that much memory, but if they do...

2) Create a HashSet to hold your nodes where the Hash value of the node class is calculated like this: (a << 32 || b). In this way you can instantly look up to see if a previous node existed or not. Remember to overload "equals" as well (it should return true only if the compared object is the same type and a and b are equal).

In a mostly populated system where bounds are known, 1 will save memory, but if your system is sparse (as you claim) then #2 could save a LOT of memory with no cost to efficiency.

Answer 4

In the class declaration there is a second constructor Tile(char *Filename);. Maybe this constructor is used to create the main node, but doesn't initialize neighbor properly? (Its implementation isn't shown.)

And on an unrelated node, you have a duplicate strcpy() in the constructor that doesn't serves any purpose and might only lead to problems:

strcpy(Filename, strcpy(Filename, "Data/BlueTile.bmp"));

Answer 5

Creation. Recursion is a neat and elegant way to solve some problems, but it isn't perfect for every problem. I suspect that a purely recursive solution to creating the nodes would be much more complicated (i.e. less elegant) than Kornel Kisielewicz's straightforward iterative solution. That's because the Tile constructor needs to know the layout of all tiles in its immediate vicinity, in order to avoid recreating nodes that are already there.

Traversal. The main problem in your node-traversal code is similar in that you will wind up with an infinite loop and blow the stack because every node will eventually "traverse" back to its parent, beginning the cycle again. I presume you're trying to visit every tile exactly once, right? In that case TraverseGrid() needs to have a parameter telling it which direction we are entering the node from, so that we avoid traversing back that way.

But that's not enough -- you also need more discipline in deciding which directions to go. Simply spreading out in all directions except the direction we entered from will still wind up in an infinite loop and stack overflow, since any three adjacent tiles will cycle endlessly. In order to do this recursively you need to really think about which strategies will wind up visiting each node once and only once.

One possibility would be changing the signature of TraverseGrid() to TraverseGrid(Tile *inputTile, int fromDir, bool leftmost) and then using the following rules:

• If we entered from above-left, traverse only to above-right, passing leftmost = false.
• If we entered from below-left or above-right, traverse only to below-right, passing leftmost = false.
• If leftmost, and there is a node to our lower left, then also traverse to that node, passing leftmost = true.

Of course fromDir and leftmost could be combined into a single parameter, but this gives the general idea.

Another alternative would be keeping a visited flag in each tile which is checked before traversing to that tile. Then your traversal will be a flood fill. But again, a simple iterative traversal is likely to be much simpler and easier to understand, and has the additional benefit of using constant stack space.