Help with Hex grid generator

[OpticalShadows]

I’m working on an adaption of a board game I made a while back that used a hex based grid map with a select paths drawn on it (not all tiles used) that the player can move across. I have a basic grid generator (I’ve adapted Epic’s blueprint puzzle template) and it works, however I’ve been reading around on the forms and they seem to be doing things a bit differently. I’m a bit confused as to the use of the vector arrays I’ve been seeing in other examples. I’ve looked at this page as well and I couldn’t grasp it that well. Here is the generator that I have so far. (large image try open in new tab)

The main concern is eventually getting this to work with a path finding system to create paths through the grid from a start point to end point. Ideally it would be based on a seed so the seed can be passed over network to get the same map. The question I have is if this is a valid way to create tiles so it can be used with the systems found on that site I listed above (Path Finding, getting neighbors etc)? Just as an example this is what the graph produces. I have the tiles alternate color based on even odd. The size of the grid is 16x16 and each tile is labeled with its number.

Any feedback / tips would be greatly appreciated!

[Zeustiak]

So you have the basics down, which is to create and spawn the grid, and then adding your tiles to an Array.

Everything you want to do with your grid can be done by referencing a large set of arrays that all have mirrored indexing.

If every map is 0-255, then every array that has anything to do with your entire map is also 0-255. If Index 0 is Vector X/Y, then affecting any of your arrays at index 0 should affect/reference the tile at Vector X/Y. I use dozens of arrays for my map generator, and they are all indexed in a similar fashion to your grid. Here is what that looks like on a spreadsheet:

I put the formulas for neighbor checking using indexes on that spreadsheet, which should give you an idea of what you need to do to create similar formulas that match your index.

For my work, I first create a Vector Array because I use the distance between vectors to determine what Seed is closest to the current tile I am setting. If a Water Seed is closer than a Land Seed, then the tile is set to Water. (I wrote an article about this here: http://www.epicallytech.com/articles/sculpting-believable-world-maps-and-other-uses-for-voronoi-diagrams.32/)

You are probably going to want the vectors of each tile stored in an array because you are going to want some kind of reference telling you where each tile is. If you want to move a unit to Tile 4, you get the Vector of Tile 4 from your Vector Array, and set the unit on it’s way.

Other notes:
If you stick to 16x16, then using static meshes is fine. If you want to do anything significantly bigger, such as 50x50 or bigger, then you are definitely going to want to switch to InstancedStaticMeshes. For examples of why/how, see my first Map Generator thread in my sig.

Accounting for World Wrap can be a major pain, if you use it. I suggest working out an efficient way of handling that as one of the first things you do.

Really work out solid Neighbor Checking functions early on. It will save you a lot of time later on. Here is a pic of one of mine:

Basically, you are going to be doing something on a tile and you are going to want to know what is happening in nearby tiles, and getting that tile’s index is how you do that. Notice how I am taking into account Offset, Edges, and World Wrap using the same function. Work that out now because it is key. I had 3-5 clunky, buggy systems before I finally nailed that down.

If you choose to use Axial coordinates, here is how you could fill your array with matching Axial Coordinates:

I made this generator but never needed to use it. If you can get good neighbor checking functions down, that take into account your Offset grid and other needs, then you don’t need axial. Especially on a small 16x16 grid. I might move to Axial later for performance reasons, but only maybe.

Anyway, that is all I have for now. There is a lot of information in my Map Generator threads and some of it is extremely complicated, but I pretty much worked through all the issues you are about to face and I outlined a lot of that starting in my first Map Generator thread. Let me know if you have any more specific questions.

[OpticalShadows]

Thanks for the quick response! I’ve been looking at your generators for quite some time now and the challenge has been trying to figure out what parts applied to my project. I don’t need to generate different biomes or anything and I’m planning on keeping my map at one size (probably 22x22 not sure yet). Basically what I want to do (behind the scenes before the player actually see’s the board) is:

• Generate the grid
• Pick a start point and end point near corners of the grid
• Block out parts of the grid that wont be used (perhaps look into the Voronoi diagram you posted about) and set those as obstacles
• Generate paths from the start point to end point 1 tile wide
• Hide all tiles except the paths that were generated

Here is an example of a generator I was working on before this. It places tiles individually based on the last one put down and randomizing its directional offset (North NW NE etc) based on what I set as preferred. So with this it will only choose N, NW, or NE so it only moves bottom left to top right. At the end of the generation it places another large pad of tiles similar to the starting area.

This wasn’t a good solution at all because it couldn’t be done in a for loop (I had to fake my own with a delay) because it calculates collisions with invisible boxes at each offset (N NW NE etc) and it got really expensive updating each tiles isTouching array. But this is a good visualization of what I’m hoping to achieve in the end. A simple path with random tiles (bases on percentage chance) from start to finish.

Another quick question. When you’re talking about storing each tile in a vector array, do you mean its actual world location?

Quick update:

I went ahead and built in a Get neighbors function. I tried using the math you had in your table but it didn’t line up. I’m guessing that’s because you created your grid differently. Either that or I got everything wrong and should just quit now :P. EDIT of my EDIT: I realized that you are using a flat top grid and I’m using a pointy top grid so that may have been the reason why our math didn’t match.

The picture is on an angle with north up, or how I think / want north to be. Not sure how north translates in your grid. I also need to put in a check for top and bottom border tiles because getNeighbors wraps around the grid. But here is what I got for “math” for neighboring tiles
North

NW

NE

South

SW

SE

Here is the wrapping I was talking about:

[Zeustiak]

Looks good. Your neighbor functions should be fine as long as they work for you grid(which is aligned indexed differently as you said, but same concepts).

One thing I would say about your neighbor checking function would be that they seem overly complicated for what they need to do. You know the max grid size of your map, whether it is 16x16 or whatever, so use that as M and set it at the beginning of the blueprint if you have multiple sizes. Have a variable set to be your Current index and that will be your reference. Then it should be as simple as +/- 1 and +/-M.

Also, make the base formulas into pure functions that simply outputs the index for whatever tile. Then, when you have the pure functions, make functions that are again only dealing with the index, but taking into account the wraps, edges, etc. Then that function will have the index as an output, and you can put that function in front of any Get Array node that you have. At that point, you should never have to think about your neighbor checking functions again.

Yes the world location of the tile. Just fill that vector array up and you can use it later to spawn tiles or as references for any location related action you take in regards to the grid(moving units, adding props, etc). Then you could have an array that represents whether a tile is an obstacle or not, whether a tile costs more to move through, etc. In your case, you probably want an array that says whether a visible tile is spawned there or not. You can zip through that array with a ForEachLoop and on the indexes that say yes, it leads to the spawn node which has your vector array pulling indexes from the ForEachLoop.

[OpticalShadows]

Quick update. I decided to scrap the grid generation method I had previously and built something, which I think, is much closer if not exactly the same as shown on the site I mentioned in my first post.

As you can see, each tile has 2 numbers corresponding to their index in the tile array. Now I need to rework all of the neighboring functions and get that working again. I’m using 2 for loops instead of one. I don’t have any of the array adding set up yet but that shouldn’t be hard at all.

Update:
I have implemented neighboring functions yet again following this page’s offset coordinates. I then converted each tiles’ neighbors’ 2D index [x,y] to index number in the tile array (one number 0 - gridsize^2). I did this by taking its X and adding its Y multiplied by gridsize. So Index = X + Y * gridsize

Much cleaner implementation

Another Quick Update: Added a check for border tiles so wrapping isn’t a problem. I simply checked to see if a tiles’ neighbors’ X index was < 0 or > gridsize -1

[Zeustiak]

Looks pretty good! I would be interested to see how you implement things using the axial coordinate system going forward.

What does your Convert Tile 2D To Index function look like inside? For my own work I had come to the conclusion that using axial would add too many steps to the Index conversion process to be worth switching my project from Offset to Axial, but since you are just starting out it shouldn’t matter for you.

[OpticalShadows]

Here is what my Tile 2D to Index looks like. It takes the tiles (x,y) index and converts that to its index in the Master Tile Array.

Note: For my pathfinding, I am using cube coordinates converted from offset for path finding.

[OpticalShadows]

I thought that I should also post an update since it’s been a while stating that I’ve figured out A* path finding and have a path manager for each path it finds. Right now, this is not on automation because I have no way to generate random obstacles yet. Below are 3 paths that I generated manually (I have it set to find a path when i press “F”) shown in green, calculated from the start (Silver) to end (gold). Black tiles are set as obstacles and pink are unprocessed. I did rearrange them while generating each path to make the results look like they do. I also have a system to “break” out of the path finding loop when its run into another path already, which is what you can see happening with the middle path.

It is a very complicated, though simple at the same time, system that took a lot of tweaking. It’s still not perfect, but for now, I am going to work on a system for drawing paths manually by selecting tiles so I can get working on gameplay and player movement. Below is the A* Algoritm, sorry I’m not good at comment boxes

Once a path is found, it runs a separate function that builds the path based off the parent tile starting from the end point.

The key to A* is managing an “Open List” of which I have a function for. My open list is an array of Vector2D. The X is the tile’s FScore (calculated in a function right before) and the Y is the tile’s Index in the master tile array. Another important note, with A* you are looking for the tile with the lowest FScore when searching for this, I needed to sort the Open list so finding the lowest score would be as simple as grabbing index 0 from the array. That unfortunately, had to be done in C++ using QuickSort (google).

[anonymous_user_dd537c6e]

Did you ever post more about your hex grid generation? I’ve been studying concepts and examples for some time now and have not gotten as far as your most basic structure. Getting lost and confused attempting to trace actions and info through advanced toolkits. Your basic grid with position identifiers is… simple. Are the structures also relatively simple?

[fandangoflip]

I’m really struggling with hex tile grids. I’m trying to implement something similar but it’s blowing my mind!

[LuisAlaguna]

Did you finish this project?