2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user6245072 May 27 '16 at 11:18
  • \$\begingroup\$ 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. \$\endgroup\$ – Vlad May 27 '16 at 11:34
  • \$\begingroup\$ 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() \$\endgroup\$ – Vlad May 27 '16 at 11:49
  • \$\begingroup\$ 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". \$\endgroup\$ – user6245072 May 27 '16 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.