Perlin Hunter Algorithm (PH3)

The Delta Project is aimed at creating multimedia editing tools and other utilities for bringing to life the dreams and inspirations of game creators around the globe.

Perlin Hunter Algorithm (PH3)

Postby Simion32 » May 4th, 2018, 12:16 pm

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:

Image

More images:
0000 0001 0002 0003
0004 0005 0007 0008
0009
Sage of Discovery
Bananas received 332
Posts: 2738
Joined: 2008

Re: Perlin Hunter Algorithm (PH3)

Postby OneOf99 » May 5th, 2018, 4:39 am

>sees O(n^4) :shakehead:

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)
Treasure Hunter
Bananas received 23
Posts: 383
Joined: 2015

Re: Perlin Hunter Algorithm (PH3)

Postby Kingizor » May 5th, 2018, 8:01 am

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. :headache:

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.
Trailblazer
Bananas received 77
Posts: 247
Joined: 2010

Re: Perlin Hunter Algorithm (PH3)

Postby Super Luigi! » May 6th, 2018, 8:35 am

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.
Sage of Discovery
Bananas received 301
Posts: 3697
Joined: 2012

Re: Perlin Hunter Algorithm (PH3)

Postby Simion32 » May 6th, 2018, 1:43 pm

Kingizor wrote: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.
Sage of Discovery
Bananas received 332
Posts: 2738
Joined: 2008

Re: Perlin Hunter Algorithm (PH3)

Postby riki2321gamer » May 8th, 2018, 8:17 am

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.
Trainee Trekker
Bananas received 6
Posts: 50
Joined: 2016

Re: Perlin Hunter Algorithm (PH3)

Postby rainbowsprinklez » May 8th, 2018, 11:12 am

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

***EDIT***
However, I am VERY good at rearranging objects and various resources.
Veteran Venturer
Bananas received 108
Posts: 568
Joined: 2016

Re: Perlin Hunter Algorithm (PH3)

Postby OneOf99 » May 8th, 2018, 1:11 pm

riki2321gamer wrote: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
Treasure Hunter
Bananas received 23
Posts: 383
Joined: 2015

Re: Perlin Hunter Algorithm (PH3)

Postby Simion32 » May 9th, 2018, 1:34 pm

riki2321gamer wrote: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.
Sage of Discovery
Bananas received 332
Posts: 2738
Joined: 2008

Re: Perlin Hunter Algorithm (PH3)

Postby rainbowsprinklez » May 10th, 2018, 5:14 am

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 :)
Veteran Venturer
Bananas received 108
Posts: 568
Joined: 2016

Re: Perlin Hunter Algorithm (PH3)

Postby Simion32 » May 10th, 2018, 10:22 am

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. ;)
Sage of Discovery
Bananas received 332
Posts: 2738
Joined: 2008

Re: Perlin Hunter Algorithm (PH3)

Postby Thriceroy » March 25th, 2021, 3:44 pm

Someone do this with Wave Function Collapse.
Newcomer
Posts: 4
Joined: 2011

Re: Perlin Hunter Algorithm (PH3)

Postby Simion32 » October 9th, 2021, 5:42 am

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. ;)
Sage of Discovery
Bananas received 332
Posts: 2738
Joined: 2008

Re: Perlin Hunter Algorithm (PH3)

Postby Simion32 » May 18th, 2023, 10:16 am

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
0001.png (120.71 KiB) Viewed 16460 times

Spoiler!
0009.png
0009.png (86.93 KiB) Viewed 16460 times

Spoiler!
0019.png
0019.png (92.45 KiB) Viewed 16460 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. ;)
Sage of Discovery
Bananas received 332
Posts: 2738
Joined: 2008

Re: Perlin Hunter Algorithm (PH3)

Postby WesternTanager794 » May 18th, 2023, 4:33 pm

I'm jumping up and down with excitement! Is this what you said you were working on, but couldn't discuss? :parry:
Sage of Discovery
Bananas received 127
Posts: 2392
Joined: 2022

Re: Perlin Hunter Algorithm (PH3)

Postby Simion32 » May 19th, 2023, 3:17 am

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


Part of it, yes. ;)
Sage of Discovery
Bananas received 332
Posts: 2738
Joined: 2008

Re: Perlin Hunter Algorithm (PH3)

Postby WesternTanager794 » May 19th, 2023, 3:42 am

Ok. Good luck with the rest! :parry:
Sage of Discovery
Bananas received 127
Posts: 2392
Joined: 2022

Re: Perlin Hunter Algorithm (PH3)

Postby rainbowsprinklez » May 20th, 2023, 7:54 am

Wow! This looks amazing! Great job! I'm still a bit noobish on big O :oops: My idea (maybe you thought of this already... :scratch: ) 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.

Image
Veteran Venturer
Bananas received 108
Posts: 568
Joined: 2016

Re: Perlin Hunter Algorithm (PH3)

Postby Simion32 » May 20th, 2023, 10:30 am

rainbowsprinklez wrote: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.
Sage of Discovery
Bananas received 332
Posts: 2738
Joined: 2008

Re: Perlin Hunter Algorithm (PH3)

Postby WesternTanager794 » May 20th, 2023, 11:17 am

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. :parry:
Sage of Discovery
Bananas received 127
Posts: 2392
Joined: 2022

Re: Perlin Hunter Algorithm (PH3)

Postby rainbowsprinklez » May 20th, 2023, 12:04 pm

Simion32 wrote: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?
Simion32 wrote: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 :D
Veteran Venturer
Bananas received 108
Posts: 568
Joined: 2016

Re: Perlin Hunter Algorithm (PH3)

Postby WesternTanager794 » May 20th, 2023, 12:06 pm

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. :parry:
Sage of Discovery
Bananas received 127
Posts: 2392
Joined: 2022

Re: Perlin Hunter Algorithm (PH3)

Postby rainbowsprinklez » May 20th, 2023, 12:07 pm

Simion32 wrote: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?
Veteran Venturer
Bananas received 108
Posts: 568
Joined: 2016

Re: Perlin Hunter Algorithm (PH3)

Postby WesternTanager794 » May 20th, 2023, 12:09 pm

That gets rid of the extra rotational solutions (that’s not the correct term). :parry:
Sage of Discovery
Bananas received 127
Posts: 2392
Joined: 2022

Re: Perlin Hunter Algorithm (PH3)

Postby Simion32 » May 21st, 2023, 8:16 am

rainbowsprinklez wrote: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.
Sage of Discovery
Bananas received 332
Posts: 2738
Joined: 2008

Re: Perlin Hunter Algorithm (PH3)

Postby rainbowsprinklez » May 21st, 2023, 11:35 am

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 :D

Veteran Venturer
Bananas received 108
Posts: 568
Joined: 2016



Return to The Delta Project

Who is online

Users browsing this forum: No registered users and 1 guest

cron