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 228
Posts: 2591
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 22
Posts: 321
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.
Jungle Explorer
Bananas received 51
Posts: 189
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.
Expedition Leader
Bananas received 196
Posts: 1863
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 228
Posts: 2591
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.
Tourist
Bananas received 3
Posts: 46
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.
Jungle Explorer
Bananas received 5
Posts: 148
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 22
Posts: 321
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 228
Posts: 2591
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 :)
Jungle Explorer
Bananas received 5
Posts: 148
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 228
Posts: 2591
Joined: 2008


Return to The Delta Project

Who is online

Users browsing this forum: No registered users and 0 guests