[Lua] Cellular automaton cave generator

16 replies [Last post]
KoBeWi
KoBeWi's picture
User offline. Last seen 15 min 24 sec ago. Offline
Joined: 2010-12-25
Posts: 499

While I was searching for something for my presentation about procedural generation, I found this article: https://gamedevelopment.tutsplus.com/tutorials/generate-random-cave-levels-using-cellular-automata--gamedev-9664

Out of boredom, I also tried to implement it and, wow, it really works. So I thought: why shouldn't I try it with Hedgewars?

And did it (with some help).
Get it here: http://www.mediafire.com/file/364dmc49j6bd472/Script_CellurarCaves_v1.hwp

Credits to sheepluva for fixing it.

Some images:

Quote:

Here are some archived versions, which don't work that nice:
https://pastebin.com/238xPFme
https://pastebin.com/4T2nz4UK
https://pastebin.com/01CCZ0GF

sheepluva
sheepluva's picture
User offline. Last seen 1 week 1 day ago. Offline
Joined: 2009-07-18
Posts: 530

Interesting.

Could try with 2 passes:

First pass with very very very very low resolution to generate the general shape of the landscape.
Second pass to add detail.

  sheepluva <- me  my code stats -> 
a Hedgewars Developer


   <- where I'm from  what I speak -> 

KoBeWi
KoBeWi's picture
User offline. Last seen 15 min 24 sec ago. Offline
Joined: 2010-12-25
Posts: 499

sheepluva allegedly wrote:
Could try with 2 passes:

First pass with very very very very low resolution to generate the general shape of the landscape.
Second pass to add detail.

Um... how? >_>

What I do right now is use the algorithm to generate 2-dimensional array of bools, then use it to fill map with points. However, quality is unexpectedly low. This might be because the map is much bigger than the examples given in the article, but...

sheepluva
sheepluva's picture
User offline. Last seen 1 week 1 day ago. Offline
Joined: 2009-07-18
Posts: 530

How...? Well, that's the trick to find out Big Grin

And hm.
Did you also get that crash when starting the map?
Is that why you asked about GDB in IRC-Chat?

Anyway, the crash is in engine, in a function that I personally wrote to fix "dirty" looking edges on texture.

That should never happen, so I'll look into it.

  sheepluva <- me  my code stats -> 
a Hedgewars Developer


   <- where I'm from  what I speak -> 

KoBeWi
KoBeWi's picture
User offline. Last seen 15 min 24 sec ago. Offline
Joined: 2010-12-25
Posts: 499

sheepluva allegedly wrote:
And hm.
Did you also get that crash when starting the map?
Is that why you asked about GDB in IRC-Chat?
No, it didn't crash for me. Maybe it's broken if you are using newer release or different system D:

The crash I had was connected with secret project I'm working on. I just thought that maybe GDB could help me, like it did with the SDL thing.

sheepluva
sheepluva's picture
User offline. Last seen 1 week 1 day ago. Offline
Joined: 2009-07-18
Posts: 530

Ah ok.

It doesn't crash for me on dev, only on .22, so I guess it's fine.

And hm, playing with the values can give interesting results:
E.g.

local CHANCE_TO_START_ALIVE = 500
local BIRTH_LIMIT = 16
local DEATH_LIMIT = 5
local STEPS = 5

local distance = 64
local pointSize = 24

For cave mode it's probably makes sense to always place those at the border, and for non-caves map to never place anything at the edge. hmmm

  sheepluva <- me  my code stats -> 
a Hedgewars Developer


   <- where I'm from  what I speak -> 

KoBeWi
KoBeWi's picture
User offline. Last seen 15 min 24 sec ago. Offline
Joined: 2010-12-25
Posts: 499

sheepluva allegedly wrote:
local CHANCE_TO_START_ALIVE = 500
local BIRTH_LIMIT = 16
local DEATH_LIMIT = 5
local STEPS = 5

local distance = 64
local pointSize = 24

Fine enough ¬_¬

Although birth/death limit above 8 (or 9?) doesn't make sense, because algorithm uses them to compare with number of neighboring cells, and there can be only up to 8 of them.

sheepluva
sheepluva's picture
User offline. Last seen 1 week 1 day ago. Offline
Joined: 2009-07-18
Posts: 530

I just looked at the link.

The closest I could get to similar results was

local CHANCE_TO_START_ALIVE = 450
local BIRTH_LIMIT = 5
local DEATH_LIMIT = 5
local STEPS = 6

local distance = 64
local pointSize = 22

Results are playable and sometimes remind of what it /should/ look like.

I couldn't find anything wrong with your implementation of the algorithm, btw.

I think the problems is that the algorithm requires low, but not too low resolutions to deliver fast/good results.
distance of 64 seems to big of a resolution, 32 too small, so maybe we should adjust the code to allow values other than powers of 2.

To go with my first (2-passes) suggestion:
Maybe it could work to use above parameters, do 3 or 4 simulation steps, then double the resolution of the cells after, so that each cell becomes a cluster of 4 cells, then apply 1 or 2 more simulation steps and draw the final result (with a pointSize smaller than 22 though).

Also I'd recommend getting a different visualisation of the code (the round points aren't too good for seeing anything happen tbh), e.g. outside the game or in-game using PlaceSprite or what it's called and generate an image in the map with health crate sprites or something square.

  sheepluva <- me  my code stats -> 
a Hedgewars Developer


   <- where I'm from  what I speak -> 

KoBeWi
KoBeWi's picture
User offline. Last seen 15 min 24 sec ago. Offline
Joined: 2010-12-25
Posts: 499

sheepluva allegedly wrote:
Also I'd recommend getting a different visualisation of the code (the round points aren't too good for seeing anything happen tbh).
I already implemented it outside the game, then I thought it'd fun to try in Hedgewars. I just get a completely different results here Sad Smiley
Such visualizations are useless now, because I need to know how will it look in the game.

I'll try your suggestions.

EDIT:
k, done: https://pastebin.com/01CCZ0GF

I'm not sure if I did the 2-pass part good, but distance don't need to be power of 2 now, and I made it customizable with in-game slider.

sheepluva
sheepluva's picture
User offline. Last seen 1 week 1 day ago. Offline
Joined: 2009-07-18
Posts: 530

Um, actually I just noticed by accident, that the original script posted in this post works quite well with

local distance = 64
local pointSize = 9

Best played on Bath theme ;p

EDIT: if you double both values you also get nice caves (with less detail)

I'm working on the multipass-version btw.
I looked at your version but I think it does it the other way around than what I meant xD

  sheepluva <- me  my code stats -> 
a Hedgewars Developer


   <- where I'm from  what I speak -> 

sheepluva
sheepluva's picture
User offline. Last seen 1 week 1 day ago. Offline
Joined: 2009-07-18
Posts: 530

Okay, I implemented dual-pass generation.
Also I added a spawn bias that will force cells to be at the border initially.

https://pastebin.com/mj0mQw8N

I also preferred big spaces, so current settings lead to more cavern-style maps. Which I find nice to play on though.

You can probably adjust parameters to get more tunnel-like caves.

  sheepluva <- me  my code stats -> 
a Hedgewars Developer


   <- where I'm from  what I speak -> 

KoBeWi
KoBeWi's picture
User offline. Last seen 15 min 24 sec ago. Offline
Joined: 2010-12-25
Posts: 499

Wow, thanks D:

I'm going to update the topic with HWP, but first I'd like to make distance customizable with slider (it needs to customize something to make it complete, right?). However, for some reason if I modify the distance inside functions, I get weird results.

EDIT:
Nevermind, found why. Although maybe point size should be customizable :?

sheepluva
sheepluva's picture
User offline. Last seen 1 week 1 day ago. Offline
Joined: 2009-07-18
Posts: 530

Make sure that updateLastXY() gets called after changing distance.

I cache lastx and lasty instead of having a lot of division operations based on distance in each function Smile

EDIT: Hm, yeah, maybe just make a table of slider positions -> distance -> pointsize that looks good with chosen distance

EDIT2 : Would be nice to have a version of this in HW engine 0.9.24
Possible tweak: Generate in square area and squeeze vertically into half size, in order to have more platforms and to make them more horizontal.

  sheepluva <- me  my code stats -> 
a Hedgewars Developer


   <- where I'm from  what I speak -> 

KoBeWi
KoBeWi's picture
User offline. Last seen 15 min 24 sec ago. Offline
Joined: 2010-12-25
Posts: 499

I updated the HWP with table of harcoded values. Luckily, nobody downloaded it, so I went with v1 again Hellish Hand Grenade

It uses "best" values at the default position, and gets weird otherwise. It's super-sparse on the left and almost fully covered on the right.

Thanks for the help, sheepluva!

Wuzzy
Wuzzy's picture
User offline. Last seen 11 hours 56 min ago. Offline
Joined: 2012-06-20
Posts: 1084

Can you please upload your HWPs to hh.unit22.org?

MediaFire has a history of burning files. You can of course keep your MediaFire link as an alternative, but if MediaFire is the only place where you upload stuff, this is dangerous because files on MediaFire are unlikely to still be there after 1 year or so.

Hi, I am a Hedgewars developer. Smile I accept personal donations in bitcoin. Heart 17fsUywHxeMHKG41UFfu34F1rAxZcrVoqH

KoBeWi
KoBeWi's picture
User offline. Last seen 15 min 24 sec ago. Offline
Joined: 2010-12-25
Posts: 499

Not sure what you mean by "history of burning files", because I use MediaFire for like 10 years and it never caused me any problems.

Anyways: http://hh.unit22.org/addons/Script/Cellular_Caves_v1/

Wuzzy
Wuzzy's picture
User offline. Last seen 11 hours 56 min ago. Offline
Joined: 2012-06-20
Posts: 1084

Thanks. Smile

Hi, I am a Hedgewars developer. Smile I accept personal donations in bitcoin. Heart 17fsUywHxeMHKG41UFfu34F1rAxZcrVoqH

Copyright © 2004-2017 Hedgewars Project. All rights reserved. [ contact ]