Nngvd1Gt

1function find_paths (uid, f)
2
3  local function make_particle (curr_loc, prev_path)
4    local prev_path = prev_path or {}
5    return {current_room=curr_loc, path=prev_path}
6  end
7
8  local depth = 0
9  local count = 0
10  local done = false
11  local found, reason
12  local explored_rooms, particles = {}, {}
13
14  -- this is where we collect found paths
15  -- the table is keyed by destination, with paths as values
16  local paths = {}
17
18  -- create particle for the initial room
19  table.insert (particles, make_particle (uid))
20
21  while (not done) and #particles > 0 and depth < config.SCAN.depth do
22
23    -- create a new generation of particles
24    new_generation = {}
25    depth = depth + 1
26
27    SetStatus (string.format ("Scanning: %i/%i depth (%i rooms)", depth, config.SCAN.depth, count))
28
29    -- process each active particle
30    for i, part in ipairs (particles) do
31
32      count = count + 1
33
34      if not rooms [part.current_room] then
35        rooms [part.current_room] = get_room (part.current_room)
36      end -- if not in memory yet
37
38      -- if room doesn't exist, forget it
39      if rooms [part.current_room] then
40
41        -- get a list of exits from the current room
42        exits = rooms [part.current_room].exits
43
44        -- create one new particle for each exit
45        for dir, dest in pairs(exits) do
46
47          -- if we've been in this room before, drop it
48          if not explored_rooms[dest] then
49            explored_rooms[dest] = true
50            rooms [dest] = supplied_get_room (dest)  -- make sure this room in table
51            if rooms [dest] then
52              new_path = copytable.deep (part.path)
53              table.insert(new_path, { dir = dir, uid = dest } )
54
55              -- if this room is in the list of destinations then save its path
56              found, done = f (dest)
57              if found then
58                paths[dest] = { path = new_path, reason = found }
59              end -- found one!
60
61              -- make a new particle in the new room
62              table.insert(new_generation, make_particle(dest, new_path))
63            end -- if room exists
64          end -- not explored this room
65          if done then
66            break
67          end
68
69        end  -- for each exit
70
71      end -- if room exists
72
73      if done then
74        break
75      end
76    end  -- for each particle
77
78    particles = new_generation
79  end   -- while more particles
80
81  SetStatus "Ready"
82  return paths, count, depth
83end -- function find_paths