-
Notifications
You must be signed in to change notification settings - Fork 2
/
fill_3d.lua
53 lines (49 loc) · 1.61 KB
/
fill_3d.lua
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
-- Algorithm created by sofar and changed by others:
-- https://github.com/minetest/minetest/commit/d7908ee49480caaab63d05c8a53d93103579d7a9
local function search(go, p, apply_move, moves)
local num_moves = #moves
-- We make a stack, and manually maintain size for performance.
-- Stored in the stack, we will maintain tables with pos, and
-- last neighbor visited. This way, when we get back to each
-- node, we know which directions we have already walked, and
-- which direction is the next to walk.
local s = {}
local n = 0
-- The neighbor order we will visit from our table.
local v = 1
while true do
-- Push current pos onto the stack.
n = n + 1
s[n] = {p = p, v = v}
-- Select next node from neighbor list.
p = apply_move(p, moves[v])
-- Now we check out the node. If it is in need of an update,
-- it will let us know in the return value (true = updated).
if not go(p) then
-- If we don't need to "recurse" (walk) to it then pop
-- our previous pos off the stack and continue from there,
-- with the v value we were at when we last were at that
-- node
repeat
local pop = s[n]
p = pop.p
v = pop.v
s[n] = nil
n = n - 1
-- If there's nothing left on the stack, and no
-- more sides to walk to, we're done and can exit
if n == 0 and v == num_moves then
return
end
until v < num_moves
-- The next round walk the next neighbor in list.
v = v + 1
else
-- If we did need to walk the neighbor, then
-- start walking it from the walk order start (1),
-- and not the order we just pushed up the stack.
v = 1
end
end
end
return search