DKC Atlas Forum

[Simion32]

Perlin Hunter 3

Perlin Hunter 3 is an automatic tile layout generator that I'm working on. It will be able to produce random levels (tile layouts) with one click.

There hasn't been much progress up until now (late April 2018).

The most recent progress involves a version of the algorithm that picks tiles by scanning to see which tiles are possible before each choice is made. Unfortunately, this means that the algorithm can fail to find a solution to the tiles grid -- sometimes the choices that it makes lead to a "zero" in the search graph.

Not only does the current version have failures, it's also EXTREMELY SLOW. The computation takes multiple (width x height) scans for each tile in the level, resulting in O(n^4) complexity. This means that, while a 16x16 tile level takes around 20 seconds to generate a full solution, anything bigger (say, a 20x40) starts to take hours instead of minutes. Adding to the slowness, the time of each scan goes up the more tiles are in the input tileset.

The current version of Perlin Hunter 3 has been tested on Factory, Jungles, and Temples tilesets. Factory and Temples seem to work OK, but Jungles have a super-high-complexity matching graph, resulting in the algorithm not being able to find a solution nearly 100% of the time.

The algorithm will require a heavy redesign before it will be ready for regular use. Right now it's far too slow/clunky.


Here are a few good examples generated from the Temples tileset:



More images:
0000 0001 0002 0003
0004 0005 0007 0008
0009

[OneOf99]

>sees O(n^4)

Yeah.... that's a rip. Have you considered letting the user draw the entire level first, and then add filler with a basic algorithm instead of doing it all in one go? (Which seems to be the case right now, but of course I don't know your code so you already be doing that and I am just beating a dead horse)

[Kingizor]

I'd maybe think about making connections based on corners.

Imagine you're placing some tile g:

Code: Select all

a b c
d e f
g h i

When you're scanning for valid connections during setup, ensure that there are valid solutions for each corner based on the adjacent tiles. So if for example you have some tile d that can be placed above g and some tile h that can be placed to the right of g, this combination of d-h relative to g is only valid if there is some tile that can fit in the resulting space e and is also part of a valid connection to the right of d and above h, otherwise discard. You'd only need to store each valid corner-combo for a given tile and then look do minimal lookups when doing placement.

In my head it should knit rather cleanly, but I'm sleepy and maybe (probably) there are eventualities I haven't taken into consideration. Building the combo table might require a few passes, but I think I'm on the right track, maybe.

Or if none of that is any good, maybe someone out there has done their own research or written a paper on jigsaws or sliding block puzzles or something that might be applicable.

[Super Luigi!]

Overall, I think Perlin Hunter 3 shows promise. My favorite picture is 0002, but 0009 is also interesting. Well done, Simion32, and I wish you the best as you continue.

[Simion32]

I'd maybe think about making connections based on corners.
(...)
When you're scanning for valid connections during setup, ensure that there are valid solutions for each corner based on the adjacent tiles. (...)

The current code is basically a brute-force version of attempting to pick tiles that are valid, simply by eliminating all of the ones that aren't.

This O(n^4) code is the first time I've ever gotten somewhat-working results.

Basically what happens is that every tile slot has listed a bit array of possible tiles, and it uses the matching data to ensure that each possible tile in the level has valid connections in all 4 directions. The ones that don't have valid connections for all 4 directions are removed by zeroing out those bits. After this is done, the algorithm then chooses a tile to go into the next tile slot (there's no special ordering to the choices, it just linearly goes through the array). Rinse and repeat until the entire level has picked tiles.

The problem with even this extreme brute force approach is that, sometimes (or all of the time like with Jungle levels), the tile that was last picked causes some other part of the tile grid to have zero possible tiles. Once this zero occurs, the code stops running as there's no way to finish the level.

I could add in explicit corner based detection, but the complexity of that information would take up too much memory -- there are an extreme number of possible "corner combos" that could appear. Furthermore, if I simply used corner combos (sets of valid 2x2s), I'd still be using matching data, just more complicated, to put together valid combos in a grid. The same problem of finding valid matches applies to this "corner combo" approach.

[riki2321gamer]

How is it slow? Does it have a wait x seconds (or frames) or something? or is it doing way too much calculations? Are you doing multithreaded or single core?

It looks pretty awesome though, wonder what it'd be like with long levels.

[rainbowsprinklez]

This would be incredible! I always said I lacked imagination for tiles!

***EDIT***
However, I am VERY good at rearranging objects and various resources.

[OneOf99]

How is it slow? Does it have a wait x seconds (or frames) or something? or is it doing way too much calculations? Are you doing multithreaded or single core?

It looks pretty awesome though, wonder what it'd be like with long levels.

When determining runtime, O(n^4) is pretty much considered terrible because of how much time each new element adds to the runtime. Essentially doubling the amount of elements makes the program take 16 times as long to run (and if you know exponential functions, you know how severe of a slope change that is).

Example: If it takes 8 minutes to run a program with 5 elements, it will take a bit more than two hours to run it with 10 elements. At 20 elements that becomes almost a day and a half.

*Made edit because I was wrong in my math

[Simion32]

How is it slow? Does it have a wait x seconds (or frames) or something? or is it doing way too much calculations? Are you doing multithreaded or single core?

What OneOf99 said.

The algorithm takes some amount of time before it finishes. A 16x16 in Temple levels, assuming it doesn't fail, takes around 20-30 seconds.

I'm not sure the current approach can be easily multi-threaded. I'll only consider building a multi-threaded version once the algorithm has been improved beyond the horrible O(n^4) time complexity. Until the algorithm is faster, multi-threading won't really help.

And just to be sure, there's no such thing as "too much calculations" -- the code has to do lots of hard calculations to output a valid result.

[rainbowsprinklez]

So I'm guessing this is a ways away? Not that I'm rooting for failure, it's just I'm making a tedious hack and don't want to restart

[Simion32]

It'll take a while before I have anything concrete, to be sure.

Perlin Hunter 3 is currently on hold for a while so that I can get back into DELTA development.

[Thriceroy]

Someone do this with Wave Function Collapse.

[Simion32]

It took me some time until recently that I actually looked up Wave Function Collapse.

Basically, my previous builds of PH3 are actually doing the same thing as Wave Function Collapse, just with more complicated matching rules.

The true Perlin Hunter Algorithm will be more advanced than that algorithm, as the PH problem is a superset (IE bigger category) of the problem area that WFC deals with.

The problem with PH so far has basically been that it is extremely easy for the algorithm to fail (WFC calls this "reaching a contradiction").

I will be working on Perlin Hunter sometime in the future but regular DELTA development comes first.