Module to procedurally generate a map of islands

Question

It chooses for each chunk some points inside that chunk that work as the center of each island. Then for each tile on the map it calculates the distance from the points in the 9 chunks around the tile's chunk and subtracts the value from a Perlin noise (as described here).

The "problem" came when trying to reduce the time taken to generate a chunk: each chunk has a random number of points that it can contain, which can be either 0, 1 or 2.

To choose this number I previously used a separate function, then I tried including the choosing in the chunk generation function, but it turned out that doing it all in one function is 2 / 100 of second slower than getting the number from another function.

--Requires the perlin module, which returns a class table
--Then it creates a perlin object, basically a random permutation of the 0 - 255 array with a noise function inside
local p = (require"perlin")()
--Here's the separated function to choose the number of points
local function n()
 local n = math.random()
 if n < .7 then
 return 0
 elseif n < .8 then
 return 1
 end
 return 2
end
--2D array used to store the points
local chunk = setmetatable({}, {
 __index = function(xtab, x)
 local ytab = {}
 xtab[x] = ytab
 return ytab
 end})
--Function to create a new piece of the chunkmap, holding some points
local function newchunk(x, y)
 local xs, ys = x * 32, y * 32
 --Here's the piece of code that trys replacing the n function, which results in a loss of time
 --[[local n = math.random()
 if n < .7 then
 n = 0
 elseif n < .8 then
 n = 1
 else
 n = 2
 end--]]
 local points = {}
 for i = 1, n() do --for i = 1, n do for the slower version
 points[i] = {x = math.random(xs, xs + 31), y = math.random(ys, ys + 31), l = math.random(26, 32)}
 end
 chunk[x][y] = points
end
--Actual tilemap
local map = setmetatable({}, {
 __index = function(xtab, x)
 local ytab = {}
 xtab[x] = ytab
 return ytab
 end})
--function to generate a new 32 x 32 portion of the tilemap
local function newmap(x, y)
 local xs, ys = x * 32, y * 32
 for xm = xs, xs + 31 do
 for ym = ys, ys + 31 do
 local total = 1
 for xc = x - 1, x + 1 do
 for yc = y - 1, y + 1 do
 if not chunk[xc][yc] then
 newchunk(xc, yc)
 end
 local c = chunk[xc][yc]
 for i = 1, #c do
 local p = c[i]
 local d = math.min(math.sqrt((p.x - xm) ^ 2 + (p.y - ym) ^ 2) / p.l, 1)
 total = total * d
 end
 end
 end
 map[xm][ym] = (p:noise(xm / 64, ym / 64) + 1) / 2 - total
 end
 end
end

So basically if I replace this piece of code:

local function n()
 local n = math.random()
 if n < .7 then
 return 0
 elseif n < .8 then
 return 1
 end
 return 2
end
local function newchunk(x, y)
 local xs, ys = x * 32, y * 32
 local points = {}
 for i = 1, n() do
 points[i] = {x = math.random(xs, xs + 31), y = math.random(ys, ys + 31), l = math.random(26, 32)}
 end
 chunk[x][y] = points
end

with this one (which should in theory be faster because one less function call is involved):

local function newchunk(x, y)
 local xs, ys = x * 32, y * 32
 local n = math.random()
 if n < .7 then
 n = 0
 elseif n < .8 then
 n = 1
 else
 n = 2
 end
 local points = {}
 for i = 1, n do
 points[i] = {x = math.random(xs, xs + 31), y = math.random(ys, ys + 31), l = math.random(26, 32)}
 end
 chunk[x][y] = points
end

the computational time required to do one newmap(x, y) call goes from about 0.05 seconds to something like 0.07 seconds.

I already asked the question on Stack Overflow and they answered what I expected: the second method should be faster, and maybe I was doing something wrong with calculating the time taken, so I thought of posting the whole code here so that you can maybe try it yourself.

Answer 1

It is probably effects of CPU caches and CPU frequency scaling. You should run same test multiple times to get plausible results.

But if you really want to minimize times, then first of all you should stop accessing global variables in inner loops. Copy math.random in local variable just once before declaring functions that repeatedly call it. Getting function from upvalue is faster than from global table.

To make CPU cache's life easier, try to group similar actions. For example, try to calculate all three values before putting it in table.

Also avoid modifying external tables within functions. Say, don't modify chunk[x][y] within newchunk() function, just return new points you've generated.

You should end up with something like this:

local random = math.random
local function newchunk(x, y)
 local xs, ys = x * 32, y * 32
 local n = random()
 if n < .7 then
 n = 0
 elseif n < .8 then
 n = 1
 else
 n = 2
 end
 local points = {}
 for i = 1, n do
 local x,y,l = random(xs, xs + 31), random(ys, ys + 31),random(26, 32)
 points[i] = { x=x, y=y, l=l }
 end
 return points
end
-- put some load for testing purposes
local chunk = {}
for x=1,1000 do
 local column = {}
 for y=1,1000 do
 column[y] = newchunk(x, y)
 end
 chunk[x] = column
end

• user6245072: Nope. Storing the points in a table is necessary to get coherent result. When a piece of map is generated, it takes in consideration the nine chunks around it, so storing what the chunks look like is important.
• Vlad: Result is identical, no matter if you assign points as the last statement within newchunk(), or immediately after returning points from newchunk(). But implementation details will make it slower if you assign inside of newchunk. You'll have to read 'chunks' table from some global variable, or pass it explicitly to newchunk. Let calling side manage recieved points. Chunks will be local, most likely.
• Vlad: That test loops at the end is only to get newchunk() code running to measure time. It's not the replacement for your toplevel loops. Though there's still one point highlighted - save returned result, and don't alter chunks within newchunk()
• user6245072: I guess you're right. Anyway I replaced the "modify n to an integer, then loop n times and create a new table each time" to a faster "if n is great enough, create one table, and if it's even greater, create another table".