Attention | Topic was automatically imported from the old Question2Answer platform. | |
Asked By | batmanasb | |
Old Version | Published before Godot 3 was released. |
I’m trying to generate terrain using this cellular automata tutorial and need pretty large double for loops of at least 1000 x 1000 or preferably much higher. 10k x 10k would be perfect. However, as I found out the hard way at Ludum Dare 34, large loops stall the game for way too long and often cause crashes on Windows exports. How can I improve/optimize my loop speeds?
The process requires a large double for loop for generating a 2D array, and then I have to generate a new one for every step. Here’s my code so far:
#map config
var mapSize = 1000
var birthLimit = 4
var deathLimit = 3
var initialChance = 0.4
var numSteps = 4
func _ready():
var map = generateMap():
#generate map over several steps (generations)
func generateMap():
var map = initializeMap()
#run the simulation for a set number of steps (generations)
for i in range(numSteps):
map = doSimulationStep(map)
return map
#make a map where every cell has the same chance to spawn alive
func initializeMap():
var map = []
for x in range(mapSize):
map.append([])
for y in range(mapSize):
map[x].append(randf()<initialChance)
return map
#map a new map based on the old map
func doSimulationStep(oldMap):
var map = []
for x in range(mapSize):
map.append([])
for y in range(mapSize):
#count Neighbors in the old map
var numNeighbors = countLivingNeighbors(oldMap, x, y)
#if cell is alive
if(oldMap[x][y]):
if(numNeighbors < deathLimit):
#kill cell
map[x].append(false)
else:
#keep cell alive
map[x].append(true)
#if cell is dead
else:
if(numNeighbors > birthLimit):
#revive cell
map[x].append(true)
else:
#keep cell dead
map[x].append(false)
return map
#returns the number of cells in a ring around (x,y) that are alive
func countLivingNeighbors(map, x, y):
var count = 0
for i in range(-1,2):
print(i)
for j in range(-1,2):
var nX = x+i
var nY = y+j
#ignore middle point
if( not(nX == 0 and nY == 0) ):
#if the neighbour if off the edge of the map
if(nX < 0 or nY < 0 or nX == mapSize or nY == mapSize):
#count it anyways
count += 1
#if neighbour is alive, count it
elif(map[nX][nY]):
count += 1
return count
Some ideas I think might work are:
- Spreading the generation over several frames (to at least prevent crashes… maybe)?
- Threads? But the process is sequential so it can’t be broken up, but maybe a background thread so the main thread isn’t stalled?
- Background loading??? Haven’t looked too far into this to know exactly how it works.
- Maybe
append()
is the issue and I need to figure out how to initialize a [1000][1000] 2D array? - Maybe I need to go into C++ and make a module to do it?
- Maybe I need to just give up on large loops and run several small 100 x 100 loops as the player moves around… although this will affect the way the terrain generates and probably wouldn’t be suitable for my game…
Edit 1: moving the generateMap()
function call to _init()
instead of having it in _ready()
will probably make it more stable… so it loads before the game starts and not during.
Edit 2 (aka someone beat me to it): I found another cellular automata project in Godot that uses it for it’s more intended purpose (caves). Although his doesn’t seem to handle large areas any better than mine
Please look at this two issues For loop with true iterators instead of arrays and Game crashes on range(0,100000000)
puppetmaster- | 2016-04-11 09:20
I took a look but I’m still not sure if they fixed range()
or not (commit reverted?). However, I converted all the double for
loops into double while
loops it now generates about 5% - 10% faster. But the generation rate is still way too slow…
batmanasb | 2016-04-11 10:31
GDScript optimization is still mostly nonexistent, I guess this should be improved before 3.0/3.1/4.0… maybe you can try writing it as C++
?
Bojidar Marinov | 2016-04-11 10:59
Terrain generation should be easy to parallelize, unless you need to randomly access to any cell of space at any time. Using a thread is fine, but it would still take forever. Maybe you can find a way to break it up in chunks so you can generate smaller portions of the world (like Minecraft), and prioritize those the player can see. In case you have to deal with neighboring, data duplication is an option (increases memory usage but also increases performance because you can spawn more threads).
You can also pick another algorithm, Simplex/Perlin noise should do the trick pretty well too
Zylann | 2016-04-11 17:01
I think I figured out a way to hide it from the user. I moved the generation process to its own thread, and when it finishes it saves it to a nextMap
variable. This way it can generate the nextMap
while the user is playing, and then simply swap to the new map when they restart. Also, I can save the nextMap
variable to a file in case the user quits, so that it loads into it when the user launches the game, and save one of my own maps for the first time someone runs the game.
Also, I didn’t realize it was possible, but after a quick google search I now think cellular automata can be parallelized, or at least parts of it. I’m going to do a bit more research on this right after I improve how the tilemap loads the map tiles.
batmanasb | 2016-04-12 12:52