DKC Atlas Forum

[Simion32]

Simion's Search Algorithm

This is a new algorithm to auto-generate levels and provide partial fill-ins for level designers.

Currently only the base algorithm is done; there will be more advancements in the future as well as speed optimizations.

The most recent progress involved getting the base algorithm done which I completed around May 11th 2024 (Mother's Day weekend).

I won't be regularly editing this post so you will need to check back for new progress update posts!

The image here displays the capability of Simion's Search to give you an idea of what kind of output to expect:



OLD POST:

Spoiler!

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:

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.

[Simion32]

Progress Update:
Perlin Hunter 3 is Working, and it's FAST!!

I've been secretly toiling away at PH3 given some new ideas on how to make the algorithm work.

Now, the algorithm is O(T x N x W x H) where T is the tile usage count, N is the number of checking passes per round within a "level", and W,H are the level dimensions.

Even though the core algorithm is complete it is still technically possible for the searches to fail.

But almost all of the time it succeeds, usually in under a handful of seconds:

Spoiler!

0001.png (120.71 KiB) Viewed 87347 times

Spoiler!

0009.png (86.93 KiB) Viewed 87347 times

Spoiler!

0019.png (92.45 KiB) Viewed 87347 times

I will be working on extensions to PH3 at some point to integrate the functionality into DELTA.

I'm going to leave the rest up to your imaginations.

[WesternTanager794]

I'm jumping up and down with excitement! Is this what you said you were working on, but couldn't discuss?

[Simion32]

Is this what you said you were working on, but couldn't discuss?

Part of it, yes.

[WesternTanager794]

Ok. Good luck with the rest!

[rainbowsprinklez]

Wow! This looks amazing! Great job! I'm still a bit noobish on big O My idea (maybe you thought of this already... ) is somehow using collision data to match... idk, I didn't think it out. All I have is an autofill 1 tile at a tiime based on connections in a single direction... this is just, wow. Impressive.

[Simion32]

somehow using collision data to match... idk, I didn't think it out

The algorithm is based on matches for each direction for every "compressed tile" (abstracting away flipped tiles so that the only thing to worry about is tile indexes).

PH3 will include a tile zone autocomplete mode as well as a mode that generates a tile grid. There will additionally be another mode that edits the tiles as you add platforms, but is a more advanced thing to implement and will require heavy level layout structure research.

As of present PH3 is only able to generate tiles -- it doesn't have any sense of platforms or etc in the "level" it generates. A lot of the results favor large expanses of walls and the sort, since they are more common than platforms. Walkways for example like to generate large empty space due to there being a lot of empty space in the real levels.

As to the actual method used, it's basically a superset (bigger category) of the same type of algorithm as Wave Function Collapse. There are several advanced methods I had to design to get things going smoothly.

Only the Jungles tileset requires the longest wait for results, coming in at roughly 850 compressed tiles if I recall correctly. The Temples and Factory tilesets are much quicker, usually in under a second.

[WesternTanager794]

Thanks for providing some insight into how it works! I don't remember how wave function collapse works in programming. This is a very silly question, though. Surprisingly, I'm growing rusty in everything coding related. I'll have to brush back up at some time. But luckily I'm probably not going to do a C++ engine immediately. Perhaps that is the final product or something.

[rainbowsprinklez]

it doesn't have any sense of platforms or etc in the "level" it generates.

That was one thing to me at least that seemed impossible without human input... Maybe a way to tell the program how many + how long each is platform sections to use?

Walkways for example like to generate large empty space due to there being a lot of empty space in the real levels.

That could be cool too! People could use those levels for wide expanses of objects, like the original's 4-1 barrel section!

Either way, I seriously love this. Level designing was always particularly hard for me. Thank you so much for all you do! If you need someone to produce a hack to show off what it can do, lmk

[WesternTanager794]

Maybe a neural network? I mean, AlphaZero learned chess and played itself for four hours and then beat the worlds top chess computer Stockfish 22-0 with the rest of the hundred game match being draws. Maybe it could learn that.

[rainbowsprinklez]

The algorithm is based on matches for each direction for every "compressed tile" (abstracting away flipped tiles so that the only thing to worry about is tile indexes).

That is seriously surprising to me. I thought you'd use the 32x32 meta tiles.... do you make your own instead? increasing connections?

[WesternTanager794]

That gets rid of the extra rotational solutions (that’s not the correct term).

[Simion32]

I thought you'd use the 32x32 meta tiles.... do you make your own instead? increasing connections?

It is actually using 32x32s to do the pattern generation, just that it doesn't use the raw tile values to do the matching work.

I could actually implement an 8x8 version if I wrote an advanced tile scanner that took into account the individual 8x8s in relation to their positions in levels. However, doing so would make generating actually-playable levels even more difficult than it is with 32x32 tiles.

[rainbowsprinklez]

That makes more sense to me. I had a project a few years ago that took an image, generated the tiles needed, and allowed you to draw the physics in. Nothing ever came of that though. With that, I would've had the detail rare's levels provide. The only thing to consider, is it only works with expanded roms because so many levels share assets! Generating meta maps is ez. Doing what you have done.... Not something I'm good with. It's magic to me

[WesternTanager794]

That’s cool!

[Simion32]

Perlin Hunter is now
Simion's Search 3

Why the name change?
I decided that since I'm the sole developer of this new search algorithm, I might as well name it after myself.
Additionally there were several iterations of Perlin Hunter behind the scenes -- technically speaking, the current code would be considered to be Perlin Hunter 4, not 3.

About The Algorithm:
I've redesigned the logic and completely revamped the tile handling so that it is now impossible for the algorithm to fail when generating a level from scratch.

What does this mean? Well, for example, it will now be possible to provide fill-in solutions for partial level grids - if the algorithm fails doing a partial fill, it means your tiles do not match up properly. Another capability of the algorithm is that I will be able to design extra layers of code that calculate levels based on platform pattern recognition, but only once I have researched and developed such features.

--------------------------------------------------

The outputs for this version of Perlin Hunter are not really all that different from the old version, just that it is impossible to have the search fail.
So hopefully I don't need to provide any generated level PNGs here.

Oh, and the algorithm is reasonably fast but is still not quite as quick as the old Perlin Hunter 3 code - the extra steps required to make failures impossible adds some extra time to the computations.

I've already got the new code set up with seeded randomness based on a running SHA256 buffer that provides well-rounded random numbers for the selection code.

I'll be working on optimizing this new version over the course of time and will begin researching level layout pattern recognition stuff.

[Simion32]

Well guess what I found out trying to generate a 20x20 Jungles level:

it is actually possible that... given a set of tile wave functions, a tile in the level will not have any possible tile that can intersect the graph and be selected.

This appears to be some sort of complex wave function effect that will make it impossible to generate levels beyond a certain size because the tile wave effects don't actually go as far as the algorithm needs to be able to complete a level.

For example treetowns and several of the other archetypes don't have any issues generating tall/wide levels. I'd really love to be able to test SS3 on DKC2/3 levels but I don't have that data available.

I'm not going to count this as a failure/contradiction -- it's more like an after-effect of the matching rules.

I'll research this some more, but I'm unsure whether there is a way to correct for this type of thing.

[Simion32]

A quick update on that: This appears to happen due to a logic bug in my implementation of the actual algorithm.

It should NEVER be possible for from-scratch levels to fail given the logic the algorithm is supposed to be following.

The issue stems from the fact that it is failing to check to ensure that each chosen tile actually has a fully intersecting wave function as opposed to just checking to see if tiles/matches are not zeroed out inside that wave function. Extra checking will be required to fix the problem.

It will take me some time to develop the code to fix this, but I can assure you I'm on the case!

[Simion32]

Progress Update: Explaining the Error!!

So I've done some heavy research on the problem that needs to be fixed, and it goes something like this:

After selecting the first tile, the tiles that are marked possible by the algorithm can end up not having a fully intersecting grid with the tiles that are already marked as being possible (even though the logic I designed says otherwise). If this happens with all of the tiles for a particular location, the algorithm errors out (effectively giving up).

If I set the algorithm to just use one of the tiles that were checked during the current pass, it will produce bad results but shows how this problem behaves.

My task will be to design and implement an advanced approach to deal with this no-back-intersection issue.

This could take a while for me to iron out, as the algorithm is already very computationally complex to begin with. Wish me luck!

[rainbowsprinklez]

This is perhaps my favorite thing. This is truly amazing. My way, of course, was a lot more primitive than yours and less robust. Mine only worked on a single tile at a time. Wow. Just wow.