Hex Grids Framework

pdate 04/03/2018 - Hex Grids is available on the Unreal marketplace. Hex Grids V10.0 in Code Plugins - UE Marketplace

Promo Video:

Upcoming Map Builder System:

I have a discord where I give updates, advice, and happily help with any questions or issues. It’s meant to be about the HexGrids plugin, but honestly, I’m happy to help with any Unreal questions.

**Discord **

The Hex Grids plugin is a C++ plugin, with full blueprint implementation. No C++ knowledge is required to use the plugin, I use the C++ to get the maximum performance out of a very maths heavy system, and expose everything you might need to blueprints. 56 blueprint exposed functions do the heavy lifting of generating a hex-based grid and allow you to perform various queries on the grid (full list below). The blueprints included show setups for static meshes, instanced static meshes, and a multi-instance static mesh setup. It also includes examples of animating the grid and getting coordinates from line traces and mouse positions. The system also includes two powerful pathfinding solutions. an A* pathfinding, and a flood fill pathfinding that makes navigation easy. The A* pathfinding at its core is powered by Epic’s own A* pathfinding as used in Paragon, which is incredibly optimized for fast performance.

This looks really cool.

Keep up the good work!

Great job.

You may need to handle the height of the hex in your A* path. This might be interesting.
Blocking hex is also something valuable.

Will you share it to the community or is it for the MarketPlace?

You shouldn’t need to dip into C++ to optimise this; most of the generic functions should be perfectly able to avoid the need for more than a few loops. Which functionality is impacting your performance the most?

Yeh there’s certainly a lot of scope for optimising in blueprints. I have taken a very mathematical approach to it, using formulas from research papers and guides, but since I have the full power of Unreal I could start to use more clever tricks for many of the functions. I mean the purist approach is certainly a good way to go, but equally I could be doing collision checks, sphere traces and other such methods for far simpler and cheaper solutions.

I managed to get my pathfinding a lot cheaper now by spreading the iterations across a few frames, technically still takes just as many computations, but the fps hitch is basically gone. The pathfinding in particular could benefit from C++ though as I could take advantage of the PriorityQueue rather than the array sorting im currently using. Im also struggling with the movement radius, once it moves past about 8 tiles the fps hit is extreme. I have an idea for optimising that, it just keeps going wrong on odd rows. If it works though a 8 radius for example will go from 512 loops down to 64, so its a big improvement.

The C++ argument in general is a tricky one though, i’m up to 40 functions making this work, and just for pure tidiness, C++ would allow me just to expose the finished functions without all the internals, and whilst it takes away flexibility, many of the more mathematical functions are the type you wouldn’t be changing anyway. On the other hand, flexibility to iterate quickly, and If i do decide to marketplace this or give it away, it’s much simpler for people to just add it to their project rather than messing with plugins and the potential for having to compile it.

Great point! I had been planning to do some tests with the FastNoise plugin to try generating interesting landscapes with it, or animated floors, and also some random Z values just to get some unique looks, but I have not yet thought about how I might adapt some of the systems to work with it. They still exist on the same grid framework, I don’t count height in the calculations, so I will probably add support for a height in which you can step up too, and if so, how much more expensive is that in terms of movement. Anything higher than that will just be treated as an obstacle, which I am in the process of adding. Should be as simple as removing all blocking hex’s from the calculation array, which is how I already treat the boundary edges.

As for giveaway vs marketplace, I am not sure yet. Im very picky with quality when it comes to sale, so if it reaches a place where I feel there’s a rock solid product that will help people, I will probably look into the marketplace, but if it never reaches a stage i’m confident in, i will probably just provide a download. Currently I think it would be useful, but its nowhere near ready. Certainly one of the big features I think will appeal is getting the wraparound support in, it will make it far more viable for world generation. Im probably not going to include seeding systems to actually form biomes, but I would love to get some base framework for it, I just don’t want it to only become a Civ style mapper, it’s not what I need for my project, and I want to keep it really general and usable for lots of concepts. When I looked into other alternatives, Unreal has very little, but Unity has many, and they are used for so many things besides just land grids, that I want to achieve the same level of flexibility.

In you go to the C++ route, you might use Task to get your pathfinding. It will allow you to send a parralel task that can last for fews frame and be notified when you can look for the result. As a consequence, you won’t impact your FPS as if you are in the main thread.

Yeh I was thinking about looking into moving the calculation to a worker thread in one method or another. The task concept is fairly interesting, that attempts to farm each calculation out to a separate thread right? Well a kinda queue of calculations to get through. Generally good for lots of small calculations, which would certainly cover the pathfinding system. Before I do that though i’m taking a look at a buried away A* method already included in the engine. Epic have said they used it for paragon with good results, so going to see if it can be adapted for my use, and if there’s any benefits to it.

Yes, I’m doing something similar. I’ve put my path finding and navmesh updates (my world is dynamic and I group hexagons into convex polygons) in a separate thread. It is definitely the way to go. I used a “lockless” design so the impact is minimal to the game thread.

It seems hexagons and grids of them are pretty popular!
Either of you know of a good starting point for all of this?

I’ve had a few bad starts and can only reliably create a square grid of them (with offsetting).
By chance, are you creating a square grid of coordinates then just not spawning any that are outside of a given set of angles?

Just an update to how things are going. I have updated the whole project to C++. It is a lot more tidy, more efficient, and far less breakable. While I wanted to keep with blueprint originally for flexibility, I decided that so many of the functions are a fixed mathematical method, that there’s really no need to provide easy access to tweaking the internals of the core functions. Instead I have taken the approach that all functions are exposed to blueprints, and require all variables to be fed in, so there’s no hidden variables driving the system that you need to know. So to get it to work you still need to use blueprint to wire it all together in whatever use case you need, but you have a library of functions to call upon. I have found a fairly large performance gain with the heavier maths functions, so I think it’s worth it.

I have gotten pathfinding working by utilising epics framework for AStar pathfinding, it’s really nice and extremely well written as you might expect from epic, so the performance gains have been immense. I have yet to get any lag whatsoever from pushing it as hard as I can. It was not overly obvious how to integrate it, but I have the core features in now. I have integrating my coordinates system and neighbour code, and exposed the pathfinding as a blueprint node.

I have thoroughly tested the single ring selection, movement ranges,and line drawing. Pathfinding works, and if you check the main post, I have a video of a character running along a path now. I have since cleaned up the stop-start motion, by adding a custom acceptance range, so we update to the next target just before reaching the current one, that way he keeps running until he reaches the end. I still need to implement the blocked tiles into the grid spawner to block off the map boundaries, right now he can be a bit of a lemming when it comes to world’s end. The rest of the blocked positions and traversal cost is up to you, you would add to it when you add mountains or rivers or whatever you need.

I have added a screenshot of the current nodes I have exposed, all these ones are code nodes. I also use a bunch of blueprint functions that will be a bit more up to the end user, such as adding static or instance meshes, debug select methods, returning a tile reference at coords etc.

I also wanted to make a few notes. One of the key things to note is while you may see Vectors, these are in fact a cube coordinate system, which in my head is kind of like viewing a axis at 45 degrees looking straight down on the grid. It’s completely unusable for actual placement, and is used to perform the maths internally. Thankfully it’s easy to convert to offset coords, which is a struct of 2 ints, columns, and rows. I decided to use the struct rather than a vector2D, as it eliminates any pesky rounding errors with vector 2Ds floats, and works better in my head. If you need to do some normal maths, you can easily convert to a vector2D, do whatever, then convert back if required. For example the tiles are placed by taking the struct, performing a Scale and Offset (function provided but forgot to include in screenshot), then converting to a vector to drive the add instance / add static mesh component.

Lastly, I would love to know what anyone might want to use a hexagon grid for, obviously there’s a Civ like game, and i’m including functions for that, but would love to know other ideas someone might use it for, so I could write more functionality to support it.

Did a quick test during a lunch break, see if I could make something interesting looking quickly using the framework. Managed to knock this prototype up in about 5 mins start to finish. Its starting to feel like a very adaptable little setup.

I got flood fills in last week so will try to get a proper example of that in here soon. What’s really nice is you can use the flood fill to calculate paths as well, so if you were moving a character within a small radius, the flood fill would show you the move range, and could be used to get the path as well, without needing to run a A* calculation. In that case you would only bother with the A* if you were moving beyond a single turn limit. Over long distances A* will be cheaper, so it still has its use cases.

Nice work! I will have to look into this more in the near future. My personal project is small cities that can be connected together and share resources (like simcity) with some rpg flavorings and small armies. Could this be adapted for a real time game where the player can float from section to section of a larger scale map? Random map generating during runtime supported?

Thanks, thats a interesting sounding use case. Im super excited to hear ideas people might use it for, so I can work on features to support it. I believe in this case it would work quite well. I separate the grid generation from the map generation so there’s a lot of flexibility there, in your case, I would probably generate a very large coordinate grid to support all cities, then make a map gen that uses something like flood fills or radius expand functions to choose coords for cities,and place the blocks there, so you end up with x number of cities spaced out as required. Since they all share a single coordinate grid, you could then snap connections between them easily and place stuff however needed. I have a specialised roundings function to snap onto grids, but I still need to improve it to ensure it covers all use cases. I don’t support multiple grids, but since the grid is just a array of integer pairs, it’s cheap to just make it colossal, and then treat different sections as different grids which can all interact.

As for random map gen at runtime, the framework is basically all in now. I don’t provide any specific map gen designs, since everyone will have a different use case, so i’m trying to just built it very flexible, and Im going to make a bunch of example content to show some methods I can think of. Everything is generated at runtime currently, though I want to explore custom grid shapes and in-game designed map shapes, and if I get that working, Il look into how to save and load those custom maps.

Small update, I decided I wanted a nice way to debug instance grids, since color selections are out, and I didn’t want to use instance swapping for debugging. I decided to make tiles flip over. It turned out to be a lot more involved than expected, especially with decided the rotation axis. The nice thing is it forced me to expand A* to support diagonal movement, and add a few new functions for finding how a tile is related to another, returning neighbour/diagonal directionality. I also learned how to do blueprint autocasts which should be a nicer UX for everyone, so for example, you can drag a vector2D onto my OffsetCoords type and have blueprint add a auto-convert node for you.

Here’s a little gif of the tile flip using flood fill as the selection type:

So a quick post, hoping to get some feedback. I am writing the square grid framework now, and I have to separate it from the Hex grid stuff, and I see 2 options. Either I keep blueprint nodes generic, and add a input enum of “Hex”, “Square” so on every single node you have to set which grid type you’re working on. Thats kind of annoying, and junks up your blueprints. The other approach is making blueprint nodes specific, so you end up with twice the amount of bp nodes, ie GenerateTriangleGrid_Square, and GenerateTriangleGrid_Hex. That’s not idea either.

Most of my nodes apply to both types, but the actual implementation is different, so one way or another they need to have separate code bases. Does anyone have any preference or other approaches?

You might use a global parameter?
I don’t think people will mix square & Hex. So if you set a Global parameter, you can switch in all your function.
You can even set that “smart” with an optional parameter per function. So if you set it, your function will use it otherwise the global parameter. :smiley:

It’s more work to maintain, but I’d say implementation specific blueprints instead of trying to cram everything into one. The keeps the surface area smaller and makes it easier to learn. I think you can use inheritance to put the common functions into one blueprint and inherit specific ones for Hex/Square/Swan/whatever…

You were asking for use cases, I’m looking to port a wargame written in C++ into either Unreal or Unity. One thing I need to do is to have multiple textures. One hex might have a grass texture overlayed by a river running n/s , a road running ne/sw, a city and snow or mud. I could update the texture each time manually instead, but it would make more sense to be able to throw everything into the graphics card and let it sort it out through a shader :wink: I haven’t looked into it seriously yet, but that’s my use case.

I haven’t decided which engine I want to use yet, but the core logic will remain in C++ indefinitely and Unreal makes that process easier for me.

I need to render rectangle hex map but I need to hide some border tiles so the map is symetric. Is there any way to do this?
Edit: Ok, I think I can use empty tile. I hope it won’t affect performance.

Also I don’t know if it is a bug but it seems I can’t make rectangle map 5x5 when Center Map is checked. I get 4x4 map - it seems all even sizes work and odd ones are rounded down.

Hey Daniel - Got some feedback for you.

  1. Go for a global function that allows us to toggle between hex and square tiles.
  2. Is there any chance for Biomes in this framework?

I am looking at doing the same thing.