When the possibility of making an ARPG came to be (aka. FLD), from start to finish (as a solo developer), I've had this idea of using semi-random generated maps (massive ones), to adhere to the rules of roguelikes. Knew right from the get-go that was possible to do (with visual scripting, on a slow/old PC), however wasn't convinced that it would be suitable for a commercial release. Hence, I started to further explore said idea in practice.

The limitations that make you stronger

Initially, I hoped to use simple White noise, or other variations of generation, such as the Perlin noise (or others), but I had to quickly realize that in this case, it wasn't a viable option: Despite the fact that I read up on all kinds of literature for procedural generation, the end result just wasn't even close enough (you can see that as the ground floor of my next attempt).

Then came the idea of hoping to create a path, between the entry and the exit of a level, and somehow weld everything to it. Sort of making sure that the level is playable and valid to use (meaning that the player can traverse it, from start to finish). This was the brief moment of me using splines, for such occasion: https://youtu.be/x8pkoXh7C4U

All these attempts were made in the hopes that I could–somehow–avoid using arrays; as they are notoriously expensive in blueprints*. Also, I'm still having some PTSD just thinking about this, even though I have created a working A*–using an array based grid system–before.

*[Worth to note that in Unreal Engine, currently there's no option to use Matrices, or Data tables that are generated at runtime. And as such, a workaround has to be made, for each application, so that it can be utilized with a 1D array. Which is a pain in a the rear to use. Especially, knowing the fact that such arrays, working with those that is, tanks the FPS, if the length is over a couple of hundred (as calculation time increases exponentially). ]

Off to hexagons, 'cos why not?

Instead of relying on the good ‘ol rectangles (which would’ve made it 100x easier), I slowly-but-surely opted out, and started to use Hexagons instead (although, in a way, hexagons ARE just rectangles, ahem, rhomboids). My reasoning was simple: Hexagons offered more variety as to how they were placed. Thus ultimately giving more options for layout design. So my next attempt was to make a workable solution for such an idea. It more or less worked, despite the fact that I've went over-the-top with it, with features such as:

• Goal based pathfinding
• Randomly placed, dynamics obstacles
• Static, actor based grid-generation (instead of using “data” tables)*

*[Pathfinding was traversed backwards, from an initial point, where the “Seeker” was placed, so that it would need to find a Yellow goal. Which will came in handy later, when assessing failed maps.] https://youtu.be/x8pkoXh7C4U

In practice, as you can see, it worked quite well (although getting to this point took some time). However, there were numerous issues with generation, as there were times that the map was simply too clogged and couldn't be solved, or other situations where the pathfinding would bug out; not speaking of the fact that this map was tiny in scale, and lacked numerous visible features. There were also issues with unnecessary overhead, that just simply didn't scale, and wasn't pleased with the overall layout of said maps. As the goal was to create a one-rule-them-all generator, that would be able to generate, somewhat natural landscapes, such as:

• caves/mazes
• semi-open areas (think canyons)
• wide open fields
• and anything in-between

Moving onto random fields

To improve the system, I've changed the way the base grid was generated, by using all kinds of projections/generation ideas. This resulted in a much more eye pleasing map, but coincidentally introduced the more sever problem of failed maps. https://youtu.be/J45bIU5RHWY

For quite some time, I tried and tried to fix this, by introducing more and more restrictions, as to how the code worked; kinda like how an overly-protective parent would act towards their children. And as such, as the problems kept on mounting, I decided to change parts of the code (often times rewriting in from scratch), and (temporarily) drop the use of dynamic obstacles; as making the grid work in the first place was top priority (as everything else is just an icing at that point).

Grid en masse

Turned out, one of the problems the generator suffered from, had to do with precision (that hunted me later). You see, when I switched from using a static square grid, I hoped to create random polygons instead; to mitigate the presence (creation) of a semi-natural landscape. However, making . . . ahem, detecting of said polygons (n-gons to be precise), had numerous approach alone, all with their own caveats: Some worked better then others, but most of them were impossible to implement in visual scripting. Days and days went by searching, and finding out that the reason why it didn't quite work the way it was supposed to (as to there were times when the hexagons simply didn't connect), was solely blamed of the imprecise application of said approaches and my knowledge on the topic. Turns out, calculating N-gons (concave ones, where you can “hide” inside) often requires some high level math.

Furthermore, as I tried to path the problem, the code started to slow down, bit-by-bit as a result of:

• having to double check each cell
• having to check each cell's surrounding (a total of 6 sides)
• making sure all info is read numerous times (wave effect for pathfinding)
• and all info is kept in order for further calculations

The results were sub-optimal, to say the least, and forced my hands to think of a different approaches. That was around when this was born: https://youtu.be/heQGRCqKFTg

Not the fastest (had to speed up the footage), but managed to create a much larger, more open map (both in terms of space and design), that was coming to be closer to what I envisioned in the first place. The only thing I didn't know, at this point, that how this system performed when scaled, and how could it be re-used later; despite the fact that sometimes it worked, sometimes it didn't. The new, “improved” and simplified generator also gave me the ability to adjust how it worked, essentially delivering all my previous requirements of such generator. I just needed to tweak how each cell was placed, and bam: got me-self a field, or a cave system. I was also surprised as how well it worked, judging by the fact that each cell is tiny (around a feet in size*).

*[As I also looked into the possibility of generating larger hexagon tiles, then breaking those up. The reason why I opted out from that, had to do with terrain: Originally, no further functions would've been implemented between two points (cells), resulting in unrealistic edges, even with subdivision implied; as all static mesh were planned to be positioned based on a cell's location. The workaround would've been troublesome (to further refine said connections, essentially making each connection jagged), and chose not to go that route.]

Streaming levels and world compositions (ugh)

The next task was to save each map (after generation), and load them up on a need-to-know basis. At first, I hoped to use world composition, but then reverted to using streaming levels, as they offered me the option to placing them at a random location, to fit the needs of any map (as there are no fix points to anchor to). Unfortunately, this also didn't go as planned*, as there are still limitations as to how you can use or place these level instances, and how they interacted with the player. This meant that often times, parts of the map would become unloaded, before "asking" permission. Luckily, as FLD is meant to be a top-down game, this would've not been that big of an issues, but was still concerning. And there was still the problem of scaling up the production.

*[Currently there's no way to assign an individual blueprint to a level instance, which technically crushed the idea of using this method.] https://youtu.be/weh8CPFJXEQ

Aside everything, the issue of inconsistency towered above, and sooner, rather then later, I decided to use world composition after all (for now), as I just couldn't find the solution that I was looking for (using blueprints), namely:

• generate level instances, at any given location
• be able to save these levels into a map file
• be able to not use collision detectors, for level loading (or expensive map to player calculations)
• being able to set static boundaries for each map
• and be able to reference each map, to know which cell goes where (and how to save it)

After some more time and research, I came to the lame conclusion of using world composition after all (one that is based on distance from the player), which is cumbersome to use, set up and have technically no way of alteration (opposed to the relative freedom of manually streaming levels). This meant a hard cap in the size of the map, unless you painstakingly made it larger (by placing more maps on the persistent level, by hand). Which is fun, when you're doing a 3x3 map, but becomes almost impossible when you wish to utilize a far greater space. Nevertheless, I pushed through and made the change, so technically one can use all 20x20Km map, if they choose so (to put in a couple of extra hours to make that happen): https://youtu.be/x8pkoXh7C4U

It started to work much better . . . better than expected. Although, still suffered from the fact that over a certain amount, the system would just break down, and would take for-e-ver to create; no joke, once I set down for an hour or so, to see a map to be generated. Also, there were some issues where the bits of the map would be missing (later realized that was due to the fact how Unreal loads assets, initially, as not all components of the engine start up equally: e.g., Your main controller starts to pump fuel, before the map loads). So there were some issues to fix: Like the issue with floating point precision. Namely, again not sure why as I hope there's a programming/math explanation to it, but Unreal cannot use precise (exact) numbers when working with floats. E.g., when you wish to use 15.07, there is a chance that your number will be converted (by the engine) to 15.0700003. Which, obviously isn't much of a big deal in the real world. However, when you rely on point (integer like) precision, having this small of a difference can break the code. So often, I ran into the issue that the majority of the cells weren't able to be detected as hoped. Which took me quite the few days to figure out; as to why this was a thing.

[And there was the major issue of detecting all the individual edges, which added to the slow time of cell calculation, which made it impossible to bear.]

Weeks of optimizing, and back to using arrays, and my biggest pet-peeve with Unreal and Blueprints: Iterations

Yes. I gave up on using my previous methods, and caved in on using arrays instead. Which gave me another headache, as the more cells were on the map: namely the hard limit of any given ticks. I know that there's a way to increase iteration limits (needed for cell data), but increasing the limit did F all (also has a hard cap on the number, thinking it being 32bit related). I'm not sure why this is a thing, but if there's no infinite loop in the code, let the program run its course–please. Maybe this would be the time to use C++ instead . . . Figuring out a way to go around this problem, whilst making it faster was a challenge in itself (on top of now working with arrays). But eventually, again surprisingly even, the code became lightning fast at generating and calculating each cell's location. Also, because of how I couldn't fully go around the issue with precision (as sometimes one-or-two cells were missing, especially on the edges), I had to revert using a form of brute force, when rendering the walls of the map. Which coincidentally takes the longest to do. All-in-all, I'm happy that making such a large, random generated map, only takes a couple of minutes, and can be easily utilized in games (at loading), Oh, and not mentioning the fact that by using maps, I've eliminated the issue of sharing said maps, in multiplayer, if there were more then one player wanting to play the same level*. See the result below.

*[For a split second I looked into using deterministic RNG methods (so that each game would generate the same map, based on a few initial keys), but then chose not to go that route. Sharing files is more convenient I find, and less prone to failure. Especially, in a multiplayer scenario, where precision (synchronization) is extremely important.] https://youtu.be/x8pkoXh7C4U

Thais concludes my brief history with working with Hexagon based grids. See you next time. Take care.

theaaronstory