Mapping - Pathing

Posted by Indoum on Sun 27 Aug 2006 09:31 PM — 66 posts, 238,270 views.

Indoum Sweden Sun 27 Aug 2006 09:31 PM #0

So, I've decided to try and make a mapper in a MUSHclient plugin, for educational purposes. I've never done or really read anything on pathing before and the topic seems a tad more advanced than I first thought. Despite this, I've managed to write some LUA code to calculate a path between two rooms of a MUD. While it doesn't take the shortest route (only the one it finds first) it always does find a path, if one exists. The code isn't very clean because of my attempts back and forth to get it working, but I hope you get the idea.

--[[ EXAMPLE MAP
1 - 2 - 3
|   |   |
4 - 5   6   7
]]

map = {
    { vnum = 1, name = "Entrance", exits = { south = 4, east = 2 } },
    { vnum = 2, name = "Kitchen", exits = { west = 1, east = 3, south = 5 } },
    { vnum = 3, name = "Garden", exits = { west = 2, south = 6 } },
    { vnum = 4, name = "Livingroom", exits = { north = 1, east = 5 } },
    { vnum = 5, name = "Bedroom", exits = { north = 2, west = 4 } },
    { vnum = 6, name = "Toilet", exits = { north = 3, west = 5 } },
    { vnum = 7, name = "Nowhere", exits = {} },
}

function mapPath(room1, room2)
    -- VALIDATE
    if not map[room1] or not map[room2] then
        print("\n[ Invalid vnums for pathing ]\n")
        return
    end
    -- INITIALIZE
    print("\n[ Calculating path between '" .. tostring(map[room1].name) .."' and '" .. tostring(map[room2].name) .. "' ]")
    local success, next_room = false, room1
    local path, visited_rooms, unexplored_rooms = {}, {}, {}
    -- BUILD PATH
    while true do
        -- CHANGE ROOM
        current_room = next_room
        next_room = false
        visited_rooms[current_room] = true
        print("\n[" .. map[current_room].name .. " (" .. map[current_room].vnum .. ")]")
        if current_room == room2 then
            local pathing = {}
            for _, v in pairs(path) do
                table.insert(pathing, v.dir .. "(" .. v.vnum .. ")")
            end
            print("\n*** SUCCESS ***")
            print("[ " .. table.concat(pathing, ", ") .. " ]")
            return
        end
        -- DECIDE ON AN EXIT
        step = (step or 0) + 1
        local exits, room = {}, map[current_room].name
        for k, v in pairs(map[current_room].exits) do
            if not next_room and not visited_rooms[v] then
                print(".. " .. k .. " *")
                next_room = v
                table.insert(path, { vnum = v, dir = k })
            elseif visited_rooms[v] then
                print(".. " .. k .. " -")
            else
                print(".. " .. k)
                table.insert(unexplored_rooms, current_room)
            end
        end
        -- DEAD END
        if not next_room then
            if table.getn(unexplored_rooms) > 0 then
                next_room = table.remove(unexplored_rooms)
                local tmp = {}
                for _, v in pairs(path) do
                    table.insert(tmp, v)
                    if v.vnum == next_room then
                        break
                    end
                end
                path = tmp
            else
                break
            end
        end
    end
    print("\n*** FAILURE ***")
    print("[ No path could be found ]")
end

mapPath(1, 6)

Now, I'm looking for feedback and suggestions to this. You have experience in this field? Please do share it.

Indoum Sweden Sun 27 Aug 2006 09:32 PM #1

Ohh, and here's the output from that example map:

C:\lua>lua5.1.exe pathing.lua

[ Calculating path between 'Entrance' and 'Toilet' ]

[Entrance (1)]
.. east *
.. south

[Kitchen (2)]
.. south *
.. east
.. west -

[Bedroom (5)]
.. west *
.. north -

[Livingroom (4)]
.. east -
.. north -

[Kitchen (2)]
.. south -
.. east *
.. west -

[Garden (3)]
.. south *
.. west -

[Toilet (6)]

*** SUCCESS ***
[ east(2), east(3), south(6) ]

C:\lua>

Nick Gammon Australia Forum Administrator Sun 27 Aug 2006 10:39 PM #2

Yes, that is interesting. Just a side-note, currently MUSHclient has Lua 5.0.2 in it, not 5.1, so be cautious if you develop scripts that rely on features in 5.1.

I tried something like that a while back, and for me the tricky part was handling something like this:

In particular, if I took the route shown with the purple line, it seems to the mapper that the way to get from room 16 to room 17 is quite lengthy (w n 3e s 2w) whereas once you walk one more square (west from 17 to 16) the mapper can now deduce that it can go back (16 to 17) with a single east, rather than the much longer route around the block.

It can also deduce that 16 to 18 is now simply 2e rather than around the block again.

I think it would be a fascinating project, to make something like this work for the more general case. For example, in the map above to find a route from room 21 to room 23.

A simple "try all possibilities" algorithm may soon become very slow, as it considers 1000s of possibilites, many ridiculous.

There are "shortest path" algorithms around, I think one that is used nowadays in graphical games is called B* (b-star) and is apparently very efficient. However one problem I see here is that there is no innate reason to know that to go from room 21 to room 23 you gradually need to head north and west, unless you assign some sort of geographical location to each room.

Shadowfyr USA Sun 27 Aug 2006 11:41 PM #3

Hmm. Too bad I don't know what the algorythm used in something called TradeWars Helper used. That could find the shortest path, with the information available to it, within maybe 2 seconds, even on an old 386. And the "sectors" in that game consisted of nothing but 100% random connections and random rooms:

Sector 453
Planet: Galbesh (spacedock)

Jump points: 4, 6, 10, 54, 120

This is not that different from what muds use. And no, you are still storing the rooms using an index (if you tried using the name, instead of simply incrementing the index, you would get one room erasing the prior unrelated room), so the only real difference isn't the way the data is tracked, just how it is percieved. At worst, a mud might have data like:

[453],Galbash sector,Galbesh,Y,10,5,_,4,120

or

[index],room name,planet,is_this_a_dock,<exit list>

One exit is simply "unknown" and thus disgarded from the search algorythm. If you are doing a path search, you are not going any place anyway *yet*, so a slight delay isn't going to heart anything, unless the algorythm is blindingly slow and inefficient. All your really asking is, "If I am in the room whose index is 453, how do I get to the one whose index is 195?" All the algorythm needs to know is which other indexed rooms are connected to by 453, and how those rooms connect. You don't even need to know what the room is named, what it contains, etc. Though.. You could set up "blocks" or "weighting", so that dangerous rooms can either show up as "there are no connections from this room", or, "this path is more dangerous, and thus less acceptable, than others", based on some threshold settings. All your doing is sort of this:

Room 4 - Nasty unkillable aggro mob? Then ignore all exits from here, as though there where none.

Room 5 - Aggro mobs, traps, quicksand, etc. which might make it harder to get there? Add 10 to the "apparent" path length using that route.

Room 10 - Empty of threats? Just add 1 to the path length using this one.

Its just in how you think about it. I believe Tradewars and its helper client both used a binary tree, and a search system that kept the last path found and the current one, then disgarded the prior found path, if the current one turned out to be shorter. I think it may have also somehow marked each sector, to show that a prior path aready got there or something similar, like marking "each" room with the path that was shortest to get to "it", every time it came across the same one, then automatically rejecting the current path if it got there by a longer method.

Lets say the best path is 1-2-3-4-5-6. The first try gets it 9-25-16-12-3-4-5-6. The next attempt would "automatically" end any search and return to the last branch, if it got to three using 9-29-45-57-123-17-3, since obviously the path to get there is "longer" than the previous one. This way, you chop entire sections of "possible" paths off right from the start, instead of exhaustively looking through all of them. The draw back is, you have to use a bit more memory, to keep track of how you got to that room the last time, so you know when to simply give up on that path. Obvious, if you suddenlt find a much shorter/equal path to 3, 1-2-3, you instead keep looking on that path and replace the list of rooms you went through to get there with the current one (or maybe just keep the old one, if its the same length anyway).

The real trick is making sure your "map" is accurate, and your database contains only "unique" rooms, so that you don't have the same room with two different indexes. That wouldn't prevent it from working, but it might create some issues with finding the best path.

Ked Russia Mon 28 Aug 2006 02:01 AM #4

I've come up with a similar algorithm a while back, and I even think I posted it here. Your algorithm is similar, but is more linear, as it walks a single path until it hits a deadend, then resumes with a different path. It also isn't optimal, as it isn't guaranteed to always find the shortest path. By changing it a little, you can easily ensure that it does.

All you have to do is make the algorithm walk all available paths at the same time. The best description of this that I've seen goes like this:

Two people are standing at different exits from a maze and they need to get the person standing at exit A to the person standing at exit B. In other words - they need to find a path through the maze. To do that, person A releases a coloured gas into the maze and yells for person B to start watching his exit. The gas particles fill the entire maze and as soon as person B sees the first particle appear at his exit, he grabs it and "interrogates" to find out what path it took to get there.

Disregarding the fact that gas particles can't talk, doing it that way always ensures that you have the shortest path, since if all particles move at the same speed - the one that travelled the shortest path will exit the labirinth first. You can also find all paths through the maze by waiting for all particles to exit and inspecting them all to find the shortest path (or paths). That would make the algorithm both optimal and complete.

There's also a simple optimization that makes that algorithm run pretty fast: you just disallow particles to travel down paths already explored by other particles.

The actual implementation of that algorithm is pretty simple and similar to yours. To represent particles, you use objects that store their current location and already travelled path:


function make_particle(curr_loc, prev_path)
  local prev_path = prev_path or {}
  return {current_room=curr_loc, prev_path=prev_path)
end

And then you have something like this:


local explored_rooms, particles = {}, {}
-- create particles for the initial room
while true do
  exits = current_room.exits
  new_generation = {}
  for i, part in ipairs(particles) do
    exits = part.current_room.exits
    for _, dest in pairs(exits) do
      if not explored_rooms[dest] then
        table.insert(part.path, part.current_room)
        table.insert(new_generation, make_particle(dest, part.path))
      end    
    end
  end
  particles = new_generation
end

The code above won't actually work, as it doesn't perform any checks to see if the final destination was reached, and requires a slightly different map setup than yours, but demonstrates the general idea: for each exit in a room you create a new particle and place it in a "new generation" of particles. So you are making each particle "give birth" to a bunch of new particles - one for each exit in the old particle's room. After all particles in the old generation have been processed, you replace that generation with a new one. Particles that are doomed to walk down already explored paths are simply discarded from the "population", which keeps its size trim and your memory uncluttered.

The beauty of that algorithm (beyond the fact that it can find the shortest path if such path exists) is its generality. One conclusion that I came to is that the actual path finding algorithm needn't be extremely fast - it needs to be general enough to work reliably for a wide range of different map types. Most existing algorithms I've seen while researching this issue are pretty specialized, which makes sense when choosing one for use in a particular game. Especially if the people making that choice are the same people who design the game world. So they can go with an algorithm tailored for a particular kind of map and build all their maps to fit that algorithm perfectly. But as soon as you try to apply that algorithm to a different map, it slows down to almost a complete stop, since the presumptions made when designing that algorithm don't work for this map.

Another advantage is simplicity and extensibility. For example, it is fairly trivial to adjust so that it accounts for exit weights: simply make particles pause (place a new particle into a separate table and merge that table with the main one a generation or two later) on exits with large weights.

And it runs fairly fast and can be fitted for very large maps, by breaking them up into smaller chunks and preprocessing those chunks to find paths through them into neighbouring chunks, so that when looking for a path between distant rooms you find a path between the chunks that contain those rooms, extract the path from room1 to chunk1's exit to adjacent chunk on the path, extract the path from chunk2's entrace from adjacent chunk on the path to room2, extract all paths through intermediate chunks and concatenate those paths in correct order. That way the algorithm will run almost instantly even on huge maps.

So, to summarize, I think your algorithm is the best thing you'll find. It just needs a small correction to make it find shortest paths, instead of a random one.

Nick Gammon Australia Forum Administrator Mon 28 Aug 2006 07:51 AM #5

Very inspirational! I have got it to work, there were some kinks to iron out. First I mucked around producing a table of rooms for testing purposes. I used the New Darkhaven zone in SMAUG, and converted the rooms and exits into a table. If you want to try the code out, save this as room_stuff.lua.


rooms = {}
rooms [21013] = { name = "Hawk Street",
   exits = {s=21014, n=21012, } }
rooms [21021] = { name = "Law Avenue",
   exits = {e=21020, w=21022, n=24800, } }
rooms [21029] = { name = "Falcon Road",
   exits = {s=21028, n=21030, } }
rooms [21037] = { name = "Horizon Road",
   exits = {e=21038, s=21126, w=21036, } }
rooms [21045] = { name = "Market Street",
   exits = {s=21052, e=21046, w=21026, n=21051, } }
rooms [21053] = { name = "The Darkhaven Courier",
   exits = {s=21409, e=21056, w=21052, n=21046, } }
rooms [21061] = { name = "The Dairy Tent",
   exits = {s=21050, w=21060, } }
rooms [21069] = { name = "The Darkhaven Inn",
   exits = {w=21068, n=21040, } }
rooms [21077] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21076, w=21078, } }
rooms [21085] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21084, n=21086, } }
rooms [21093] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21092, n=21094, } }
rooms [21101] = { name = "On a Trail East of the Northern Gate",
   exits = {e=21102, w=21099, } }
rooms [21109] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21110, n=21108, } }
rooms [21117] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21118, n=21116, } }
rooms [21133] = { name = "The Court of the Conclave",
   exits = {se=21073, sw=21380, d=21132, n=21072, } }
rooms [21141] = { name = "The Guild of Thieves",
   exits = {e=21142, s=21064, n=21144, } }
rooms [21149] = { name = "A Plain Room",
   exits = {n=21148, } }
rooms [21157] = { name = "A Plain Room",
   exits = {n=21155, } }
rooms [21165] = { name = "A Forested Path",
   exits = {e=21163, w=21166, } }
rooms [21181] = { name = "Inside the Cathedral",
   exits = {s=21168, n=21182, } }
rooms [21205] = { name = "A Forested Path",
   exits = {w=21204, se=21207, } }
rooms [21213] = { name = "Tracking the Prey",
   exits = {sw=21208, } }
rooms [21237] = { name = "The Sparring Circle",
   exits = {w=21236, n=21239, } }
rooms [21293] = { name = "Entrance to the Graveyard",
   exits = {s=3600, n=21291, } }
rooms [21301] = { name = "Under the Southern Bridge",
   exits = {e=21300, w=21302, } }
rooms [21309] = { name = "Atop the Battlements",
   exits = {s=21308, } }
rooms [21325] = { name = "Atop the Battlements",
   exits = {e=21321, w=21326, } }
rooms [21333] = { name = "Atop the Battlements",
   exits = {n=21332, } }
rooms [21437] = { name = "The Hall of Repose",
   exits = {u=21432, d=21430, nw=21439, e=21438, } }
rooms [21006] = { name = "Justice Road",
   exits = {e=21007, w=21005, } }
rooms [21014] = { name = "Intersection of Market Street and Hawk Street",
   exits = {w=21050, s=21015, n=21013, } }
rooms [21022] = { name = "Law Avenue",
   exits = {e=21021, w=21023, n=21066, } }
rooms [21030] = { name = "Falcon Road",
   exits = {s=21029, n=21031, } }
rooms [21038] = { name = "Horizon Road",
   exits = {e=21012, s=21280, w=21037, } }
rooms [21046] = { name = "Market Street",
   exits = {s=21053, e=21047, w=21045, n=21054, } }
rooms [21054] = { name = "The Alchemist's",
   exits = {e=21055, s=21046, w=21051, } }
rooms [21062] = { name = "Weaponry Shop",
   exits = {w=21059, n=21050, } }
rooms [21078] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21077, w=21079, } }
rooms [21086] = { name = "On a Trail South of the Western Gate",
   exits = {s=21085, n=21087, } }
rooms [21094] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21095, s=21093, } }
rooms [21102] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21103, w=21101, } }
rooms [21110] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21111, n=21109, } }
rooms [21118] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21119, n=21117, } }
rooms [21126] = { name = "Outside the Tower of Sorcery",
   exits = {s=21127, n=21037, } }
rooms [21134] = { name = "Foyer of an Abandoned Mansion",
   exits = {d=21135, s=21353, } }
rooms [21142] = { name = "The Art of Profit",
   exits = {w=21141, } }
rooms [21150] = { name = "A Plain Room",
   exits = {s=21148, } }
rooms [21158] = { name = "A Plain Room",
   exits = {n=21159, } }
rooms [21166] = { name = "A Fork in the Path",
   exits = {e=21165, w=21185, n=21167, } }
rooms [21174] = { name = "Public Notices",
   exits = {e=21194, } }
rooms [21182] = { name = "Inside the Cathedral",
   exits = {s=21181, e=21192, w=21193, n=21194, } }
rooms [21190] = { name = "The Trial of Lore",
   exits = {n=21187, } }
rooms [21294] = { name = "Beneath the Elm Tree",
   exits = {w=21292, } }
rooms [21302] = { name = "On the Darkhaven River",
   exits = {e=21301, w=21303, } }
rooms [21318] = { name = "Atop the Battlements",
   exits = {e=21314, w=21319, } }
rooms [21326] = { name = "Atop the Battlements",
   exits = {e=21321, w=21327, } }
rooms [21390] = { name = "The Gold Room",
   exits = {} }
rooms [21430] = { name = "The Guild of Augurers",
   exits = {ne=21435, s=21434, u=21437, w=21433, } }
rooms [21438] = { name = "The Niche of Convergence",
   exits = {w=21437, } }
rooms [21007] = { name = "Justice Road",
   exits = {e=21008, w=21006, } }
rooms [21015] = { name = "Hawk Street",
   exits = {s=21016, n=21014, } }
rooms [21023] = { name = "Law Avenue",
   exits = {e=21022, w=21024, n=21353, } }
rooms [21031] = { name = "Falcon Road",
   exits = {s=21030, n=21032, } }
rooms [21039] = { name = "Horizon Road",
   exits = {e=21000, s=21335, w=21040, } }
rooms [21047] = { name = "Market Street",
   exits = {s=21056, e=21043, w=21046, n=21055, } }
rooms [21055] = { name = "The Wizard's Tent",
   exits = {s=21047, w=21054, } }
rooms [21063] = { name = "Thieves Alley",
   exits = {e=21064, w=21025, } }
rooms [21071] = { name = "A Chamber Covered with Runes",
   exits = {ne=21127, } }
rooms [21079] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21078, w=21080, } }
rooms [21087] = { name = "Outside the Western Gate",
   exits = {s=21086, e=21088, w=6000, n=21089, } }
rooms [21095] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21096, w=21094, } }
rooms [21103] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21105, w=21102, } }
rooms [21111] = { name = "On a Trail North of the Eastern Gate",
   exits = {s=21112, n=21110, } }
rooms [21119] = { name = "On a Trail Rounding Darkhaven",
   exits = {w=21120, n=21118, } }
rooms [21127] = { name = "Within the Tower of Sorcery",
   exits = {se=21129, u=21131, sw=21071, w=21128, n=21126, } }
rooms [21135] = { name = "Lair of the Vampires",
   exits = {ne=21138, s=21136, se=21162, u=21134, nw=21139, e=21137, } }
rooms [21151] = { name = "A Plain Hallway",
   exits = {s=21153, e=21154, w=21148, n=21152, } }
rooms [21159] = { name = "A Plain Hallway",
   exits = {s=21158, e=21155, w=21161, n=21160, } }
rooms [21167] = { name = "Outside the Cathedral",
   exits = {s=21166, n=21168, } }
rooms [21191] = { name = "A Room of Silence",
   exits = {e=21187, } }
rooms [21207] = { name = "Before a Steep Hill",
   exits = {u=21208, nw=21205, } }
rooms [21239] = { name = "A Silent Corner in the Hall",
   exits = {s=21237, w=21240, } }
rooms [21295] = { name = "The Young Adventurer's Necessities",
   exits = {w=21280, } }
rooms [21303] = { name = "Under the Crumbling Bridge",
   exits = {e=21302, } }
rooms [21311] = { name = "Atop the Battlements",
   exits = {e=21312, w=21307, } }
rooms [21319] = { name = "Atop the Battlements",
   exits = {e=21318, } }
rooms [21327] = { name = "Atop the Battlements",
   exits = {e=21326, } }
rooms [21335] = { name = "The Western Hall",
   exits = {n=21039, } }
rooms [21439] = { name = "The Cubiculum of Lore",
   exits = {se=21437, } }
rooms [21000] = { name = "Darkhaven Square",
   exits = {ne=21200, s=21042, u=21337, e=21036, w=21039, nw=21163, n=21001, } }
rooms [21008] = { name = "Meeting of Hawk Street and Justice Road",
   exits = {u=21321, w=21007, s=21009, } }
rooms [21016] = { name = "Meeting of Hawk Street and Law Avenue",
   exits = {u=21314, w=21017, n=21015, } }
rooms [21024] = { name = "Meeting of Falcon Road and Law Avenue",
   exits = {u=21307, e=21023, n=21025, } }
rooms [21032] = { name = "Meeting of Falcon Road and Justice Road",
   exits = {e=21033, s=21031, u=21328, } }
rooms [21040] = { name = "Horizon Road",
   exits = {e=21039, s=21069, w=21041, } }
rooms [21048] = { name = "Market Street",
   exits = {s=21058, e=21049, w=21043, n=21057, } }
rooms [21056] = { name = "Quills and Parchments",
   exits = {w=21053, n=21047, } }
rooms [21064] = { name = "Thieves Alley",
   exits = {e=21065, w=21063, n=21141, } }
rooms [21072] = { name = "The Court of the Red Robes",
   exits = {s=21133, } }
rooms [21080] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21079, w=21081, } }
rooms [21088] = { name = "Inside the Western Gate",
   exits = {e=21028, w=21087, } }
rooms [21096] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21097, w=21095, } }
rooms [21112] = { name = "Outside the Eastern Gate",
   exits = {s=21114, e=3503, w=21113, n=21111, } }
rooms [21120] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21119, w=21121, } }
rooms [21128] = { name = "The Library",
   exits = {e=21127, } }
rooms [21136] = { name = "A Stone Grotto",
   exits = {n=21135, } }
rooms [21144] = { name = "Chamber of the Loot",
   exits = {e=21145, s=21141, } }
rooms [21152] = { name = "A Plain Room",
   exits = {s=21151, } }
rooms [21160] = { name = "A Plain Room",
   exits = {s=21159, } }
rooms [21168] = { name = "Entry of the Cathedral",
   exits = {s=21167, e=21170, w=21177, n=21181, } }
rooms [21176] = { name = "Before the Altar to Evil",
   exits = {w=21170, } }
rooms [21192] = { name = "Eastern Donation Room",
   exits = {w=21182, } }
rooms [21200] = { name = "A Forested Path",
   exits = {ne=21201, sw=21000, } }
rooms [21208] = { name = "The Guild of Rangers",
   exits = {ne=21213, s=21212, e=21210, d=21207, } }
rooms [21240] = { name = "Armor Dump",
   exits = {e=21239, s=21236, } }
rooms [21280] = { name = "Entrance to the Academy",
   exits = {e=21295, d=10300, n=21038, } }
rooms [21296] = { name = "Crossing the Precarious Bridge",
   exits = {s=21290, n=21081, } }
rooms [21312] = { name = "Atop the Battlements",
   exits = {w=21311, } }
rooms [21328] = { name = "Atop the Battlements",
   exits = {e=21329, d=21032, s=21332, } }
rooms [21432] = { name = "The Vault of Contemplation",
   exits = {d=21437, } }
rooms [21001] = { name = "Vertic Avenue",
   exits = {s=21000, n=21002, } }
rooms [21009] = { name = "Hawk Street",
   exits = {s=21010, n=21008, } }
rooms [21017] = { name = "Law Avenue",
   exits = {e=21016, w=21018, n=21339, } }
rooms [21025] = { name = "Falcon Road",
   exits = {e=21063, s=21024, n=21026, } }
rooms [21033] = { name = "Justice Road",
   exits = {e=21034, w=21032, } }
rooms [21041] = { name = "Horizon Road",
   exits = {e=21040, s=21068, w=21028, } }
rooms [21049] = { name = "Market Street",
   exits = {s=21059, e=21050, w=21048, n=21060, } }
rooms [21057] = { name = "The Butcher's Shop",
   exits = {e=21060, s=21048, } }
rooms [21065] = { name = "Thieves Alley",
   exits = {e=21044, w=21064, } }
rooms [21073] = { name = "The Court of the Black Robes",
   exits = {nw=21133, } }
rooms [21081] = { name = "Before the Precarious Bridge",
   exits = {e=21080, s=21296, n=21082, } }
rooms [21089] = { name = "On a Trail North of the Western Gate",
   exits = {s=21087, n=21090, } }
rooms [21097] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21098, w=21096, } }
rooms [21105] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21106, w=21103, } }
rooms [21113] = { name = "Inside the Eastern Gate",
   exits = {e=21112, w=21012, } }
rooms [21121] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21120, w=21122, } }
rooms [21129] = { name = "The Chamber of Meditation",
   exits = {nw=21127, } }
rooms [21137] = { name = "The Chamber of Discipline",
   exits = {w=21135, } }
rooms [21145] = { name = "A Darkened Back Room",
   exits = {w=21144, } }
rooms [21153] = { name = "A Plain Room",
   exits = {n=21151, } }
rooms [21161] = { name = "A Luxurious Room",
   exits = {e=21159, } }
rooms [21177] = { name = "The Cleric's Guild",
   exits = {e=21168, w=21180, n=21178, } }
rooms [21185] = { name = "A Forested Path",
   exits = {e=21166, sw=21186, n=21435, } }
rooms [21193] = { name = "Western Donation Room",
   exits = {e=21182, } }
rooms [21201] = { name = "A Forested Path",
   exits = {e=21202, sw=21200, } }
rooms [21233] = { name = "Stone Tunnel",
   exits = {s=21204, n=21236, } }
rooms [21297] = { name = "On the Darkhaven River",
   exits = {n=21275, w=21300, se=21298, } }
rooms [21321] = { name = "Atop the Battlements",
   exits = {d=21008, w=21326, s=21323, } }
rooms [21329] = { name = "Atop the Battlements",
   exits = {e=21330, w=21328, } }
rooms [21337] = { name = "In the Air",
   exits = {u=21338, d=21000, } }
rooms [21353] = { name = "A Corridor in the Abandoned Mansion",
   exits = {s=21023, n=21134, } }
rooms [21401] = { name = "Plunging through the brambles",
   exits = {e=21090, sw=21402, } }
rooms [21409] = { name = "A Silent Corner of the Courier",
   exits = {n=21053, } }
rooms [21433] = { name = "The Plank of Musing",
   exits = {e=21430, } }
rooms [21002] = { name = "Vertic Avenue",
   exits = {s=21001, n=21003, } }
rooms [21010] = { name = "Hawk Street",
   exits = {s=21011, n=21009, } }
rooms [21018] = { name = "Law Avenue",
   exits = {e=21017, w=21019, } }
rooms [21026] = { name = "Intersection of Market Street and Falcon Road",
   exits = {e=21045, s=21025, n=21027, } }
rooms [21034] = { name = "Justice Road",
   exits = {e=21035, w=21033, } }
rooms [21042] = { name = "Vertic Avenue",
   exits = {s=21043, n=21000, } }
rooms [21050] = { name = "Market Street",
   exits = {s=21062, e=21014, w=21049, n=21061, } }
rooms [21058] = { name = "The Blacksmith's Tent",
   exits = {e=21059, n=21048, } }
rooms [21066] = { name = "Annir's Clothing",
   exits = {s=21022, } }
rooms [21074] = { name = "Inside the Southern Gate",
   exits = {s=21075, n=21020, } }
rooms [21082] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21081, n=21083, } }
rooms [21090] = { name = "On a Trail Rounding Darkhaven",
   exits = {w=21401, s=21089, n=21091, } }
rooms [21098] = { name = "On a Trail West of the Northern Gate",
   exits = {e=21099, w=21097, } }
rooms [21106] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21107, w=21105, } }
rooms [21114] = { name = "On a Trail South of the East Gate",
   exits = {s=21115, n=21112, } }
rooms [21122] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21121, w=21123, } }
rooms [21138] = { name = "A Room Covered with Blood",
   exits = {sw=21135, w=21139, } }
rooms [21146] = { name = "A Plain Hallway",
   exits = {e=21148, s=21147, w=21155, } }
rooms [21154] = { name = "A Luxurious Room",
   exits = {w=21151, } }
rooms [21162] = { name = "A Shadowy Room Covered With Blood",
   exits = {nw=21135, } }
rooms [21170] = { name = "The Cleric's Guild",
   exits = {s=21172, e=21176, w=21168, n=21171, } }
rooms [21178] = { name = "The Chamber of Charity",
   exits = {s=21177, } }
rooms [21186] = { name = "A Clearing in the Forest",
   exits = {ne=21185, d=21187, } }
rooms [21194] = { name = "The Cathedral Altar",
   exits = {s=21182, w=21174, } }
rooms [21202] = { name = "A Forested Path",
   exits = {ne=21204, w=21201, } }
rooms [21210] = { name = "The Clearing of Comrades",
   exits = {w=21208, } }
rooms [21290] = { name = "The Ruins of the Concourse",
   exits = {e=21291, n=21296, } }
rooms [21298] = { name = "On the Darkhaven River",
   exits = {e=21299, nw=21297, } }
rooms [21314] = { name = "Atop the Battlements",
   exits = {d=21016, w=21318, n=21315, } }
rooms [21322] = { name = "Atop the Battlements",
   exits = {s=21323, n=21321, } }
rooms [21330] = { name = "Atop the Battlements",
   exits = {w=21329, } }
rooms [21338] = { name = "In the Air",
   exits = {u=800, d=21337, } }
rooms [21402] = { name = "On a forest trail",
   exits = {ne=21401, w=21403, } }
rooms [21434] = { name = "The Chamber of Bounty",
   exits = {n=21430, } }
rooms [21003] = { name = "Vertic Avenue",
   exits = {s=21002, n=21004, } }
rooms [21011] = { name = "Hawk Street",
   exits = {s=21012, n=21010, } }
rooms [21019] = { name = "Law Avenue",
   exits = {e=21018, w=21020, n=9850, } }
rooms [21027] = { name = "Falcon Road",
   exits = {s=21026, n=21028, } }
rooms [21035] = { name = "Justice Road",
   exits = {e=21004, w=21034, } }
rooms [21043] = { name = "Intersection of Vertic Avenue and Market Street",
   exits = {s=21044, e=21048, w=21047, n=21042, } }
rooms [21051] = { name = "The Scribe's Tent",
   exits = {e=21054, s=21045, } }
rooms [21059] = { name = "Armory",
   exits = {e=21062, w=21058, n=21049, } }
rooms [21067] = { name = "Companions and Mounts",
   exits = {} }
rooms [21075] = { name = "Outside the Southern Gate",
   exits = {s=3504, e=21124, d=7030, w=21076, n=21074, } }
rooms [21083] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21082, n=21084, } }
rooms [21091] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21090, n=21092, } }
rooms [21099] = { name = "Outside the Northern Gate",
   exits = {e=21101, s=21100, w=21098, } }
rooms [21107] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21108, n=21106, } }
rooms [21115] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21116, n=21114, } }
rooms [21123] = { name = "On a Trail Rounding Darkhaven",
   exits = {e=21122, w=21124, } }
rooms [21131] = { name = "On a Stone Stairway",
   exits = {u=21132, d=21127, } }
rooms [21139] = { name = "Hoard of the Undead",
   exits = {e=21138, se=21135, } }
rooms [21147] = { name = "A Luxurious Room",
   exits = {n=21146, } }
rooms [21155] = { name = "A Plain Hallway",
   exits = {s=21157, e=21146, w=21159, n=21156, } }
rooms [21163] = { name = "A Forested Path",
   exits = {w=21165, se=21000, } }
rooms [21171] = { name = "The Chamber of Prayer",
   exits = {s=21170, } }
rooms [21187] = { name = "The Guild of Druids",
   exits = {s=21190, u=21186, w=21191, n=21188, } }
rooms [21275] = { name = "The Darkhaven Marina",
   exits = {s=21297, n=21124, } }
rooms [21291] = { name = "Among the Ruins of the Concourse",
   exits = {s=21293, e=21292, w=21290, u=7914, } }
rooms [21299] = { name = "On the Darkhaven River",
   exits = {w=21298, } }
rooms [21307] = { name = "Atop the Battlements",
   exits = {e=21311, d=21024, n=21308, } }
rooms [21315] = { name = "Atop the Battlements",
   exits = {s=21314, n=21316, } }
rooms [21323] = { name = "Atop the Battlements",
   exits = {s=21324, n=21321, } }
rooms [21339] = { name = "Companions and Mounts",
   exits = {s=21017, } }
rooms [21403] = { name = "On a forest trail",
   exits = {e=21402, w=21404, } }
rooms [21435] = { name = "Along the forested path",
   exits = {sw=21430, s=21185, } }
rooms [21499] = { name = "Final room",
   exits = {} }
rooms [21004] = { name = "Intersection of Vertic Avenue and Justice Road",
   exits = {s=21003, e=21005, w=21035, n=21100, } }
rooms [21012] = { name = "Intersection of Horizon Road and Hawk Street",
   exits = {s=21013, e=21113, w=21038, n=21011, } }
rooms [21020] = { name = "Intersection of Vertic Avenue and Law Avenue",
   exits = {s=21074, e=21019, w=21021, n=21044, } }
rooms [21028] = { name = "Intersection of Horizon Road and Falcon Road",
   exits = {s=21027, e=21041, w=21088, n=21029, } }
rooms [21036] = { name = "Horizon Road",
   exits = {e=21037, w=21000, } }
rooms [21044] = { name = "Vertic Avenue",
   exits = {w=21065, s=21020, n=21043, } }
rooms [21052] = { name = "The Shining Emerald",
   exits = {e=21053, n=21045, } }
rooms [21060] = { name = "The Darkhaven Bakery",
   exits = {e=21061, s=21049, w=21057, } }
rooms [21068] = { name = "The Tavern",
   exits = {e=21069, n=21041, } }
rooms [21076] = { name = "On a Trail West of the Southern Gate",
   exits = {e=21075, w=21077, } }
rooms [21084] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21083, n=21085, } }
rooms [21092] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21091, n=21093, } }
rooms [21100] = { name = "Inside the Northern Gate",
   exits = {s=21004, n=21099, } }
rooms [21108] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21109, n=21107, } }
rooms [21116] = { name = "On a Trail Rounding Darkhaven",
   exits = {s=21117, n=21115, } }
rooms [21124] = { name = "On a Trail East of the Southern Gate",
   exits = {e=21123, s=21275, w=21075, } }
rooms [21132] = { name = "On a Stone Stairway",
   exits = {u=21133, d=21131, } }
rooms [21148] = { name = "A Plain Hallway",
   exits = {s=21149, e=21151, w=21146, n=21150, } }
rooms [21156] = { name = "A Plain Room",
   exits = {s=21155, } }
rooms [21172] = { name = "The Chamber of the Scriptures",
   exits = {n=21170, } }
rooms [21180] = { name = "Before the Altar to Good",
   exits = {e=21177, } }
rooms [21188] = { name = "A Spacious Room",
   exits = {s=21187, } }
rooms [21204] = { name = "A Fork in the Path",
   exits = {e=21205, sw=21202, n=21233, } }
rooms [21212] = { name = "A Silent Building",
   exits = {n=21208, } }
rooms [21236] = { name = "The Guild of Warriors",
   exits = {e=21237, s=21233, n=21240, } }
rooms [21292] = { name = "Near the Elm Tree",
   exits = {e=21294, w=21291, } }
rooms [21300] = { name = "On the Darkhaven River",
   exits = {e=21297, w=21301, } }
rooms [21308] = { name = "Atop the Battlements",
   exits = {s=21307, n=21309, } }
rooms [21316] = { name = "Atop the Battlements",
   exits = {s=21315, } }
rooms [21324] = { name = "Atop the Battlements",
   exits = {n=21323, } }
rooms [21332] = { name = "Atop the Battlements",
   exits = {s=21333, n=21328, } }
rooms [21340] = { name = "Petshop Stables",
   exits = {} }
rooms [21380] = { name = "The Court of the White Robes",
   exits = {ne=21133, } }
rooms [21404] = { name = "A turn in the forest trail",
   exits = {e=21403, nw=2074, } }
rooms [21436] = { name = "The Tomb of Rectification",
   exits = {} }
rooms [21005] = { name = "Justice Road",
   exits = {e=21006, w=21004, } }

Nick Gammon Australia Forum Administrator Mon 28 Aug 2006 08:29 AM #6

Now assuming you have your rooms in a file similar to that, this will find the path for you:


-- Path finding algorithm, inspired by Ked and Indoum
--
--  28 August 2006

dofile "room_stuff.lua"  -- room definitions

particle_count = 0

function make_particle(curr_loc, path)
  particle_count = particle_count + 1
  local path = path or {}
  return {current_room=curr_loc, path=path}
end

-- we want a copy of the table, not just a copy of the pointer
function dup_table (t)
local new_t = {}
  table.foreachi (t, 
     function (k, v) 
       table.insert (new_t, v) 
     end )
  return new_t
end -- dup_table

function find_path (start, destination)

  local explored_rooms, particles = {}, {}
  
  -- create particle for the initial room
  table.insert (particles, make_particle (start))
    
  while table.getn (particles) > 0 do
  
    -- give birth to new lot of particles, based on where the existing ones lead
    new_generation = {}
    
    -- consider each active particle, see where it goes
    for i, part in ipairs(particles) do
    
      -- if room doesn't exist, forget it
      if rooms [part.current_room] then
      
        -- where this one can go (gives birth to one per exit)
        exits = rooms [part.current_room].exits
        
        -- make one per possible exit
        for dir, dest in pairs(exits) do
                
          -- if we have been there before, drop it, don't need to reconsider
          if not explored_rooms[dest] then
              explored_rooms[dest] = true
              new_path = dup_table (part.path)
            table.insert(new_path, dir)
            
            -- if the destination is where we want to go, we now know how to get there
            if dest == destination then
              return new_path
            end -- found it!

            -- make a new particle in the new room
            table.insert(new_generation, make_particle(dest, new_path))
            
           end    
        end
      end -- if room exists in table
      
    end -- doing each existing particle
    particles = new_generation
  end -- looping until path found

end -- function find_path

-- test it

starting_point = 21057
destination = 21142

path = find_path (starting_point, destination)

if path then
 print (string.format ("Found path from room %i (%s) to room %i (%s).\r\n The path is: %s",
                     starting_point,
                     rooms [starting_point].name,
                     destination, 
                     rooms [destination].name,
                     table.concat (path, ",")))
else
 print ("No path to room")
end -- if
       
print ("Made", particle_count, "particles to do that")

Example output:


Found path from room 21057 (The Butcher's Shop) to room 21142 (The Art of Profit).

 The path is: s,w,s,w,w,n,e
Made	62	particles to do that

(and another)

Found path from room 21006 (Justice Road) to room 21339 (Companions and Mounts).

 The path is: e,e,s,s,s,s,s,s,s,s,w,n
Made	128	particles to do that

(and for a non-existant room, say 21999)

No path to room
Made	246	particles to do that

So it certainly seems to work, and with a reasonably small amount of processing. There are things you could do to improve it, I wanted to keep it fairly simple:

Convert the output into a proper speedwalk string
Handle locked and/or closed doors (perhaps simply delete the exit from the list)
Handle rooms with aggressive mobs (perhaps delete the room from the list)
Make it exit after generating (say) 1000 particles with a message "destination too far away" or some such thing, to stop large amounts of CPU being consumed generating the path.

Still, pretty impresssive, thanks Ked and Indoum for the ideas. It is interesting to see that it damps down reasonably quickly when I try to find a room that doesn't exist - 246 particles isn't too bad in that case.

Ked, there were a few things I needed to tweak to get it to work. One thing that was confusing me was that the results were initially much longer than I expected (a huge lot of walks to get from one room to one next to it). This was because when you do something like this in Lua:


a = {}  -- make a table
table.insert (a, 42)
b = a  -- assign it
table.insert (b, 55)

You don't have two separate tables, one with 42 in it, and one with (42, 55) in it. The assignment copies the pointer to the table, it doesn't create a new one.

Thus the paths were getting very long, as the table.insert was really adding to one very long table.

I made the function dup_table to work around that. It takes a table as an argument and returns a copy of it.

Nick Gammon Australia Forum Administrator Mon 28 Aug 2006 09:45 AM #7

There is an interesting asymmetry to this. For example:


Found path from room 21057 (The Butcher's Shop) to room 21142 (The Art of Profit).

 The path is: s,w,s,w,w,n,e
Made	68	particles to do that


(going backwards)

Found path from room 21142 (The Art of Profit) to room 21057 (The Butcher's Shop).

 The path is: w,s,e,e,n,e,n
Made	31	particles to do that

Effectively, the reverse path is the same as the forward path (if you read it backwards, and convert w to e and so on), however it was reached in under half the number of iterations.

Ked Russia Mon 28 Aug 2006 03:51 PM #8

As for tweaking - yeah, when doing it in Python I had to muck around a bit to get rid of the ghost particles. If I remember correctly, sets took care of them.

And the number of steps needed for each path depends mostly on the map's layout. In your example, if there was lots of branching in the part of the map where room 21057 is located, but not so much of it near 21142 then the particles would spend much more time in the branches when searching 21057->21142, but would die quickly on the reverse walk.

Imagine a map like this:


        *-*-*-*-*-*-*-*-*-*-3
       /
1-*-*-*-*-*-*-*-*-*-*-*-*-*-2

When calculating a path from 1->2, already on the third step a separate branch of the population will be created to explore the path to 3, and it'll stay alive until room 2 is finally reached by the "winning" particle's decendant. But from 2->1 that branch will only exist for 3 generations, after which it'll be promptly killed as room 1 will be reached by then. But the maximum life length of any population branch is obviously limitted by the length of the winning branch.

This can become a serious problem (one that various heuristic algorithms try to solve with a varying degree of success or failure) on large maps, which is why I mention breaking up the map into medium-sized chunks and using preprocessing. That way, branches will never go deep enough to bog the whole thing down considerably. That was the main thing that I was meaning to do after settling on this algorithm but got distracted by other things.

David Haley USA Mon 28 Aug 2006 04:38 PM #9

Search algorithms are indeed very interesting. For these purposes, a breadth-first search is guaranteed to find the shortest path (in terms of steps). A breadth-first search is that you explore all depth-1 children of the start node, then all depth-1 children of those children (hence all depth-2 children of the first), and so forth.

The algorithm used in a lot of games is A*, which constructs paths taking the shortest one at each step. It's sort of like a greedy algorithm. A purely greedy algorithm, however, where you always take the shortest step, will break; consider:

A --> B (cost of 3)
A --> C --> B (each step with cost of 2)

The greedy algorithm will pick C then B, ending up with a total cost of 4 which is one more than the optimal 2.

A* helps get around this by taking not the shortest step at each node but the shortest total path so far. It will initially pick C, but then it will note that A to C to B is 4 and it can go from A to B with 3. The actual algorithm is a lot more complicated, though. A* is more memory heavy than the purely greedy algorithm; this is fairly apparent when you consider that you need to keep all this stuff in memory. A* is also generally associated with heuristics, where in addition to keeping track of movement cost, you take guesses at how "good" a particular node is. (Of course, it's not always obvious what makes one node "better" than another!)

What Nick and Ked observed actually gives rise to an interesting alternative search, called bi-directional search, where you start from the beginning and go forward, and also start from the end and go backwards. (Of course, this only works if edges are bi-directional.) This is, in general, quite memory heavy because you store more of the tree than you might otherwise need. However, it can save you a great deal of time in cases where the destination is down a "single path" with lots of branches that could otherwise get in the way.

Searching is a very interesting topic; I could go on for a while so I should stop now. :-) (And as a disclaimer allow me to note that I've presented things in a fairly simplified way, and so have not necessarily been fully precise.)

Shadowfyr USA Mon 28 Aug 2006 07:53 PM #10

I think you misunderstood how what I described works. Lets say you have:

1 - 2345
2 - 16
3 - 1279
4 - 19A
5 - 347
6 - 28B
7 - 3B
8 - 6
9 - B
A - 4B
B - 679

You want to get from 1 to B.


        _2*
  _2-6-<-8-6*
1<      -B
Path = 1268B

  _2+(1268b)
1<-3-2*
  -4-1*
    \9-B
Path = 149B

1-5-3-2*
     \7*
     \9*

Final Path = 149B

Well, with some minor adjustments, but that's basically how I "think" they did it. Frankly, I don't know how close that is to what your version does Nick. I still haven't sat down and really worked with Lua yet. lol

Shadowfyr USA Mon 28 Aug 2006 07:57 PM #11

Hmm. Actually, its simpler than that.. You only need to mark a room, so you know if you have been there before, then throw out any paths you find that are longer than the last one that got you there. So, you just need a table for the total rooms, which in the best case, would just be a binary flag (yeah like that's going to happen), and the table/string used to store the current path being walked and last successful path found.

David Haley USA Mon 28 Aug 2006 08:16 PM #12

Breadth first searching solves this very easily. You don't need to do anything complicated like throwing out longer paths; the algorithm structure does that for you. (A* has the same advantage.) The only complexity is needing to mark if you've been to a room before (to deal with cycles in the graph), and that can be accomplished fairly easily by passing a table around in the recursion and flagging rooms when you expand them.

Nick Gammon Australia Forum Administrator Mon 28 Aug 2006 09:25 PM #13

Quote:

What Nick and Ked observed actually gives rise to an interesting alternative search, called bi-directional search, where you start from the beginning and go forward, and also start from the end and go backwards.

Yes I thought of that, however I was not convinced that this would be a great idea because:

The saving would not be that great - you might save a bit of time, but say they met in the middle you still have to do half of double the processing. That is, one way in my example it was 68, and the other way it was 31. If we halve each of those (34 + 15) you get 49 steps, compared to 68. A saving, but not a great saving.
I am not convinced they would happen to meet at the optimal path. Two branches that wandered off at a tangent might meet first, however the shorter path might be about to be reached by a more direct route.
There is the possibility that the paths are not symmetric. For example, one-way exits, like a room with a hole in the floor you can jump down, but not get back up. Thus going from start to finish is safer than finish to start.

Shadowfyr, I was initially thinking along the lines of what you described. Finding a whole series of routes and choosing the shortest. However I like Ked's algorithm more as the shortest route is implied as being the one that finds the exit first.

You could add weightings to his algorithm by adding a counter to a particle, so that it "sits there before giving birth" while the counter decrements. I think that could work quite nicely.

Just for curiosity I ran a test on calculating every possible path in New Darkhaven. That is, every room to every other room, excepting itself. Since there are 257 rooms, it had to run the algorithm 257 * 256 times, which is 65,792 iterations. The whole thing took 275 seconds, so that is 239 path finds per second. The total number of particles used was 8,178,551. If you want to try it, replace the "testing" code near the bottom of my post with this:


paths = {}

-- find all paths

count = 0

print "Starting ..."
io.flush ()
t1 = os.time ()

for from_room in pairs (rooms) do
  count= count + 1
  paths [from_room] = {}  -- table of all paths from this room
  print ("Doing room", count, "vnum", from_room)
  io.flush ()

  for to_room in pairs (rooms) do
    if from_room ~= to_room then  -- don't do to ourself
       paths [from_room] [to_room] = find_path (from_room, to_room)
    end -- not same room
  
  end -- for each path from this room
  
end  -- for each room

print ("rooms = ", count)

print ("Made", particle_count, "particles to do that")

t2 = os.time ()
print ("Time taken = ", os.difftime (t2, t1), "seconds")

I had to put the io.flush in, or I got no output, and was getting a bit worried after a couple of minutes elapsed with no obvious activity, hence the debugging displays. It actually took 4.58 minutes to run (275 seconds).

Nick Gammon Australia Forum Administrator Mon 28 Aug 2006 09:39 PM #14

To make a pather from the client viewpoint you need to solve other problems, such as:

Uniquely identifying each room.

Unless the MUD happens to pass down a unique room number (which some might), you have cases of rooms that look the same, but are different, for example in New Darkhaven the following rooms' names are repeated (count on right):


On a forest trail	2
On a Stone Stairway	2
Inside the Cathedral	2
Market Street	6
On the Darkhaven River	5
Thieves Alley	3
Justice Road	6
Companions and Mounts	2
On a Trail Rounding Darkhaven	33
A Luxurious Room	3
In the Air	2
Horizon Road	6
A Forested Path	7
Atop the Battlements	22
A Plain Room	8
The Cleric's Guild	2
Falcon Road	5
A Plain Hallway	5
Vertic Avenue	5
Law Avenue	6
Hawk Street	5
A Fork in the Path	2

Code to generate this was:


descs = {}

for k, v in pairs (rooms) do
  descs [v.name] = (descs [v.name] or 0) + 1
end -- for

for k, v in pairs (descs) do
  if v > 1 then
    print (k, v)
  end
end

One possibility would be to hash together the:

Name of the room
Room description
Exits list

And hope that gave a unique signature for each room.

Building the list of rooms and exits

Say this is your first visit to New Darkhaven, you need to build up your knowledge of where everything is. You could make a "bot" that walks everywhere, similar to the path finder, except that as there is only one bot (only one player) you would have to work a bit differently. Perhaps just take the first exit from every room, and add unvisited exits to a list. Then when you hit a dead-end, find the closest room with an unvisited exit, and take that. Then keep doing that until the list of unvisited exits is empty.
Knowing where you are

Clearly to get somewhere you need to know your current location. Hopefully you could establish that by doing a "look" and identifying your current place.

David Haley USA Mon 28 Aug 2006 10:15 PM #15

Quote:
The saving would not be that great - you might save a bit of time, but say they met in the middle you still have to do half of double the processing. That is, one way in my example it was 68, and the other way it was 31. If we halve each of those (34 + 15) you get 49 steps, compared to 68. A saving, but not a great saving.

Yes, bi-directional search is only really a good idea when you know a fair amount about the structure of your graph. It's very useful when the branching is very heavy in the start-to-end direction, and less heavy in the start-to-front direction.

Quote:
I am not convinced they would happen to meet at the optimal path. Two branches that wandered off at a tangent might meet first, however the shorter path might be about to be reached by a more direct route.

If you use breadth-first search, I believe it is a proven result that it will in fact be optimal. Of course all bets are off with depth-first search without heuristics.

Quote:
There is the possibility that the paths are not symmetric. For example, one-way exits, like a room with a hole in the floor you can jump down, but not get back up. Thus going from start to finish is safer than finish to start.

Well, I did mention that all exits had to be bi-directional; nonetheless it would be fairly easy to modify the algorithm such that it only picked exits into the current node when going backwards. To be efficient a room would have to know about all exits to it, in addition to all exits from it.

I'm a bit perplexed as to why you would want to generate every possible path and pick the shortest. Generating all paths is a very large problem (in terms of big-O complexity) whereas a simple, straightforward breadth-first search depends only on the branching factor of your graph and the distance from start to finish -- and in any case this will be far smaller than all possible paths. Furthermore breadth-first search has been proven to be optimal in cases like this, where all transitions have uniform cost.

As a matter of fact, you don't even need to worry about cycles in your graph if you know for sure that there is a path from place A to place B. The breadth-first search algorithm will waste a fair amount of time, yes, but it will still find a solution. If however there is no path from A to B then you will loop forever if you do not account for cycles.

Nick Gammon Australia Forum Administrator Mon 28 Aug 2006 10:57 PM #16

I thought I would do a more extensive test. I loaded up all rooms I found in stock SMAUG Fuss, and tried to find a long path. I guessed from 1587 to 7918, however if someone knows a longer one I would be pleased to hear it. Anyway, this was the result, in under a second:



Found path from room 1587 (A guard post) to room 7918 (The Mighty Chain of Naris).



 The path is: nw,n,e,d,s,w,n,n,n,w,w,nw,n,ne,nw,w,s,s,s,s,s,s,w,w,w,w,w,w,w,w,w,w,w,w,s,s,e,u,u,u



Made	845	particles to do that



rooms = 	1547

Nick Gammon Australia Forum Administrator Mon 28 Aug 2006 11:32 PM #17

In case you want to try this at home, I'll describe how I generated the room data. I decided to use the admin command "rlist" which lets you list a range of vnums. However the default behaviour is just to list vnums and names, not the exits, like this:


 1500) The chief guard   
 1501) A bend in the trail   
 1502) A distant sound   
 1503) Breaks in the trees

A small change adds the exits as well. Near the bottom of do_rlist in build.c change the code to do the actual listing to:


 for( vnum = lrange; vnum <= trange; vnum++ )
   {
   EXIT_DATA *pexit;
   static char *dir_text[] = { "n", "e", "s", "w", "u", "d", "ne", "nw", "se", "sw", "?" };
     
      if( ( room = get_room_index( vnum ) ) == NULL )
         continue;
      pager_printf( ch, "%5d) %s Exits: ", vnum, room->name );
      
    for(pexit = room->first_exit; pexit; pexit = pexit->next )
        pager_printf( ch,
                   "%s:%-5d ",
                    dir_text[pexit->vdir],
                   pexit->to_room ? pexit->to_room->vnum : 0 );
      
    pager_printf (ch, "\r\n");
   }
   return;

Now the output looks like this:


 1500) The chief guard Exits: n:1576  s:1575  
 1501) A bend in the trail Exits: e:1502  nw:3588  
 1502) A distant sound Exits: n:1503  e:1520  w:1501  
 1503) Breaks in the trees Exits: n:1510  e:1506  s:1502  w:1505

To generate the rlists, I needed to break them down to avoid buffer overflow. This did the trick:



for i = 0, 25 do 

  what = string.format ("rlist %i %i", i * 1000, (i * 1000) + 999)

  DoAfterSpecial (i * 5, 'Send ("' .. what .. '")', 12) 

end

Now I used some Lua code to read in that rlist output, and convert it into the rooms table. In my case I wrote it to disk so I could run tests on the saved data, but you could omit that step and just preprocess the lines before doing the path find.


roomslist = [[
 1500) The chief guard Exits: n:1576  s:1575  
 1501) A bend in the trail Exits: e:1502  nw:3588  
 1502) A distant sound Exits: n:1503  e:1520  w:1501  
 1503) Breaks in the trees Exits: n:1510  e:1506  s:1502  w:1505  
 1504) Storage Exits: e:1505  
 
... and so on for hundreds of lines ...

24896) 223 Rasche Hall Exits: u:24899 
24897) Forrester and Cox's Room Exits: w:24898 
24898) The Third Floor Miles Hallway Exits: e:24897 s:24895 w:24899 
24899) Grant and Seguin's Room Exits: e:24898 d:24896 
 ]]

-- getlines iterator - iterates over a string and returns one item per line

function getlines (str)

  local pos = 0
  
  -- the for loop calls this for every iteration
  -- returning nil terminates the loop
  local function iterator (s)
  
    if not pos then
      return nil
    end -- end of string, exit loop
    
    local oldpos = pos + 1  -- step past previous newline
    pos = string.find (s, "\n", oldpos) -- find next newline
  
    if not pos then  -- no more newlines, return rest of string
      return string.sub (s, oldpos)
    end -- no newline
    
    return string.sub (s, oldpos, pos - 1)
    
  end -- iterator
  
  return iterator, str
end -- getlines

-- table of rooms and their exits

rooms = {}

for l in getlines (roomslist) do
  _, _, vnum, name, exits = string.find (l, "(%d+)%) (.+) Exits%: (.*)")
  if vnum then
    vnum = tonumber (vnum)
    rooms [vnum] = { name = name, exits = {} }
    string.gsub (exits, "(%a+)%:(%d+) ", 
             function (dir, where) 
                rooms [vnum].exits [dir] = tonumber (where) 
             end )
  end -- vnum found
end -- for

--------------- This part saves it all to disk ------------

f = io.output ("room_stuff.lua")

f:write ("rooms = {}\n")

for vnum, data in pairs (rooms) do
  exits = ""
  for k, v in pairs (data.exits) do
    exits = exits .. k .. "=" .. v .. ", "
  end -- for each exit  
  f:write (string.format ("rooms [%i] = { name = %q,\n   exits = {%s} }\n", vnum, data.name, exits))
end -- for loop

f:close ()

I used the getlines iterator (described elsewhere in this forum) to break the text into lines. You could omit that by saving the the raw room data as a disk file and then use the Lua io.lines function, which reads a file line by line.

Ked Russia Tue 29 Aug 2006 12:10 AM #18

Here's a modification of Nick's function that will take a list of destinations and return a table of found paths. I did this to see how fast Nick's heavy-duty test could go, but it's also applicable in a general case (for example for finding all paths through an area into another area):


function find_paths (start, destinations)
	
	local dest_length = table.getn(destinations)
	local new_dest = {}
	for i,room in pairs(destinations) do
		new_dest[room] = true
	end
	destinations = new_dest
	
	local explored_rooms, particles = {}, {}
	
	-- this is where we collect found paths
	-- the table is keyed by destination, with paths as values
	local paths = {}
	
	-- create particle for the initial room
	table.insert (particles, make_particle (start) )
	
	while table.getn(particles) > 0 do
	
		-- create a new generation of particles
		new_generation = {}
		
		-- process each active particle
		for i,part in ipairs(particles) do
		
			-- if room doesn't exist, forget it
      		if rooms [part.current_room] then
			
				-- get a list of exits from the current room
				exits = rooms [part.current_room].exits
				
				-- create one new particle for each exit
				for dir, dest in pairs(exits) do
				
					-- if we've been in this room before, drop it
					if not explored_rooms[dest] then
						explored_rooms[dest] = true
						new_path = dup_table (part.path)
						table.insert(new_path, dir)
						
						-- if this room is in the list of destinations then save its path
						if destinations[dest] then
							paths[dest] = new_path
							dest_length = dest_length - 1
						end -- found one!
						
						-- make a new particle in the new room
	            		table.insert(new_generation, make_particle(dest, new_path))
					end
				end
			
			end
		end
		
		-- check if all destinations have been reached
		if dest_length == 0 then
			return paths
		end
			
		particles = new_generation
	end	
	return paths			
end

And here's the test code:


destinations = {}
paths = {}

-- find all paths

count = 0

print "Starting ..."
io.flush ()
t1 = os.time ()

for from_room in pairs (rooms) do
  count= count + 1
  print ("Doing room", count, "vnum", from_room)
  io.flush ()

  for to_room in pairs (rooms) do
    if from_room ~= to_room then  -- don't do to ourself
    	table.insert(destinations, to_room)
    end -- not same room
    -- if destinations table isn't empty

  end -- for each path from this room
  if table.getn(destinations) > 0 then
	paths[from_room] = find_paths(from_room, destinations)
	destinations = {} 
  end

end  -- for each room

print ("rooms = ", count)

print ("Made", particle_count, "particles to do that")

t2 = os.time ()
print ("Time taken = ", os.difftime (t2, t1), "seconds")

This will run in about a second, compared to the 200+ seconds that the original function gives.

Nick Gammon Australia Forum Administrator Tue 29 Aug 2006 03:42 AM #19

Excellent! I have confirmed that your version takes around 2 seconds on my PC compared to 275 or whatever the figure was.
Of course your efficiency is in that my version recalculated lots of the paths, while yours saves each one as it is found, which is much faster.

Nick Gammon Australia Forum Administrator Tue 29 Aug 2006 04:20 AM #20

Now I worked out what is the longest path in New Darkhaven. A bit of extra code worked it out:


max_length = 0

for from_room, dests in pairs (paths) do
  for to_room, how in pairs (dests) do
    if table.getn (how) > max_length then
      max_length = table.getn (how)
      long_from = from_room
      long_to = to_room
    end -- if longer
  end -- of each to room

end -- each from room


print ("Longest path (", table.getn (paths [long_from] [long_to]), "nodes) was from", 
       long_from, "to", long_to)
print ("From ", rooms [long_from].name, "to",  rooms [long_to].name)
print ("Path = ", table.concat (paths [long_from] [long_to], ","))



Starting ...

rooms = 	257



Made	58333	particles to do that



Time taken = 	2	seconds



Longest path (	28	nodes) was from	21294	to	21324

From 	Beneath the Elm Tree	to	Atop the Battlements

Path = 	w,w,w,n,n,e,e,e,e,e,e,n,n,e,e,e,e,n,n,n,n,n,n,n,n,u,s,s

Then for a bit of fun I ran Ked's algorithm over all the rooms in SMAUG FUSS (1547 of them anyway), and got these results:



Starting ...

rooms = 	1547



Made	1442853	particles to do that



Time taken = 	383	seconds



Longest path (	87	nodes) was from	3469	to	1577

From 	The Gilded Hallway	to	The treasure room

Path = 	n, n, n, n, n, w, n, w, s, w, u, w, s, e, e, s, e, e, e, w, u, s, w, n, n, e, e, n, u, n, n, n, n, n, n, n, w, n, n, e, e, e, e, e, e, e, e, e, e, e, e, n, n, n, n, n, n, e, se, sw, s, se, e, e, s, s, s, e, n, d, w, s, w, w, w, n, w, w, sw, s, sw, n, w, w, n, n, w

During execution of this my copy of lua50.exe peaked at over 1 Gb of virtual memory usage, so it was pretty intensive.

So, the longest walk you can take in SMAUG is from room 3469 (chapel.are) to room 1577 (srefuge.are).

I converted that to a speedwalk string by replacing "," by ")(" and then adding a "(" to the start and an ")" to the end. Then running RemoveBacktracks over the resulting string gives me this:



5n w n w s w u w s 2e s 2e u s w 2n 2e n u 7n w 2n 12e 6n e (se) (sw) s (se) 2e 3s e n d w s 3w n 2w (sw) s (sw) n 2w 2n w

Nick Gammon Australia Forum Administrator Tue 29 Aug 2006 05:13 AM #21

Interestingly, I then redid the test with only unlocked exits, that is ones with a key of -1.

I got somewhat faster results, not exactly sure why:



rooms = 	1549



Made	379566	particles to do that



Time taken = 	48	seconds



Finding longest path ...



Longest path (	79	nodes) was from	2487	to	1547



From 	The Labyrinth	to	A bridge over the river

Path = 	e, n, n, e, e, n, n, nw, n, w, w, n, w, u, u, s, s, s, d, s, sw, s, s, s, s, se, e, e, ne, e, n, n, n, n, e, e, e, e, e, e, e, e, e, e, s, s, s, s, s, s, e, se, sw, s, se, e, e, s, s, s, e, n, d, w, s, w, w, w, n, w, u, nw, w, w, d, sw, w, u, n

As a speedwalk string that is:



e 2n 2e 2n (nw) n 2w n w 2u 3s d s (sw) 4s (se) 2e (ne) e 4n 10e 6s e (se) (sw) s (se) 2e 3s e n d w s 3w n w u (nw) 2w d (sw) w u n

Shadowfyr USA Wed 30 Aug 2006 02:44 AM #22

lol That's kind of funny. One of the tricks that the Tradewars helper let you do was find the logest path of "unexplored" sectors, then fire a probe to the sector at the end of it. Of course, the helper used a download of the database, (one of the features of the ship computer in the game), to first find the exits that all rooms had in the game. You still needed to send the probe, since it only told you where they connect to, not what was actually in them.

This will definitely be helpful, if we even manage to impliment the rest of a mapper in Mushclient. Though, technically, we could now, we just need wxLua and, maybe, LuaCOM (wxLua might have some sort of event bridge in it already, for its own supported controls). I just wish the documentation of the wx libraries was a little less of a, "What are you using this for, if you don't already know how it works?", and instead a tad clearer about making it work right. lol

--
With something like the wx libraries, we could do nearly any GUI stuff we wanted to "if" we coded everything, including the layout, entirely by hand. My own intent had been to make the coding of the layout and design simple, even if I can't do much about behaviour. Not impossible still, but not "quite" as dynamic as I intended. Basically.. It would involve making a function to take the size of every control, produce handles for it, disable/hide the real control, then let you move the handles. This is basically what the designers already do, except that the implimentation of the handles+outline is built into the control, and the window basically executes something telling it, "Ok, now you are in design mode, hide yourself (if you need to), show the handles, and stop recieving any other input, etc., if you plan to stay visible."

Their own "internal" event systems probably look something like this:

if not design
  select case event
    on click
      fire_event click
    ...
  end select
else
  if event = drag then
    fire_event drag
  end if
end if

To do what I wanted, would require I impliment something like above to override the code in every standard control needed. The alternative is to just hide the object, create a fake ghost of it to move around, then reposition the original, when you go back to "run" mode. This is what a number of people have done in VB to solve the same issue. Imho, its an annoying hack. :(

Point is though, we have all the tools we need to build almost anything at this point. Well, with 1-2 additional libraries. Its just a pain in the rear to do so. lol

Nick Gammon Australia Forum Administrator Wed 30 Aug 2006 05:27 AM #23

I agree that our goal of some sort of mapper has moved a step closer. I was thinking that the pathing information could probably be used to work out where each room is. For example, taking Darkhaven Square as a reference point, and pathing to each other room in the city, you could then cancel out matching n/s and e/w directions, leaving a total of the distance away in n/s e/w terms. For example:

s,w,s,w,w,n,e

We have a s/n pair, so we can eliminate them, and an e/w pair, so what remains is:

s, 2w

Thus we could say that this room is 1 square south, and 2 squares west, of the reference point.

David Haley USA Wed 30 Aug 2006 02:58 PM #24

I think that it is unfortunately very dangerous to make assumptions about geographical layout based on the directions taken. This is something we have wrestled with for a while on Darkstone. We have several areas where things should behave as you say but simply do not; this is because not all exits represent the same change of distance.

Even if builders try to respect some notion of scale, things go to hell when you change scale reference. For instance if you go inside a building, the rooms will be "smaller" because the space is more interesting; similarly if you venture into the wild, you don't care as much so rooms are "bigger". So even assuming scale is kept in each reference size, things get very broken when you change from one reference to another.

I think it would be safer to treat the graph of rooms simply as a graph, and give "hints" to the layout engine according to the direction of the exit. It would stretch exit lines as necessary to make things fit as best possible, so things would still look right. But I don't think we can assume that the rooms are laid out on a rational coordinate system.

Nick Gammon Australia Forum Administrator Wed 30 Aug 2006 10:38 PM #25

Absolutely, which is why I have been reluctant to try in the past. However I agree you can probably get a hint that, say, one zone is to the East of Darkhaven, by the fact that there are 20e walks to get there.

A smart algorithm might work out stretch amounts by trying to first identify outdoor paths (like roads, which might even be flagged as outdoor rooms) and then stretch the length of them to accomodate indoor paths, like the contents of a castle.

However it only takes something like a "teleport door" to completely throw out an automated system.

Ked Russia Thu 31 Aug 2006 03:22 AM #26

A perfect solution to that problem probably doesn't exist, but nothing prevents one from calculating distances based on directions and number of steps, stretching links where needed and possible and pushing rooms the hell out of the way where impossible, and then just handing off that graphical representation to a specialized "map designer" application, where a user can employ his creativity to arrange rooms in a saner fashion.

I think that's the general approach Zmud+Zmapper take. I'd give a Zmapper analog a shot, but I really want to solve another puzzle: how to track player's current position on the map, and how to use that tracking for automapping.

Nick Gammon Australia Forum Administrator Thu 31 Aug 2006 06:35 AM #27

Well, as I suggested earlier, a hash of the room name, description, and available exits would hopefully give a unique id for each room.

In some MUDs, determining what is the room name/description may not be all that easy. I think in SMAUG the room name is one colour, the description another and the exits a third. Plus, the exits line start with "Exits:".

Once you have done that, an interesting exercise is to make a bot that walks around and establishes all the rooms and exits, using a similar algorithm to your earlier one.

David Haley USA Thu 31 Aug 2006 05:07 PM #28

A hash on name/description/exits would probably work for almost all cases, I agree. It wouldn't be that hard to make a specialized trigger setup for a particular MUD if it happens to lay things out differently.

However I can think of three cases off the top of my head that would break this:

MUDs where descriptions include the contents of the room, in some more or less obfuscated format
MUDs that have large outdoor areas where room names and descriptions can be recycled. [1]
Rooms in which exits are sometimes visible, and sometimes not. If an exit were to appear (after being found by a search, for instance) it could really throw off the automapper's sense of position.

[1] Darkstone, for example, has a 'random description' system where you can label a whole stretch of rooms as "forest" and it will assign a description to each chosen randomly from a pool of forest descriptions for that area. This is used to generate a sense of size for large, uncivilized terrain, like deserts, vast forests, etc.

Shadowfyr USA Thu 31 Aug 2006 06:50 PM #29

Yes, you are better off storing the room description, etc. in a database, where each room has simply been given a new, incremental, index number, then when running the path algorythm, you only have to do a search on the room you are moving to, to get its index, and the one for the room you are in. The path algorythm is only using the index number, which refers to the rooms, and the exits in it. Note, if you want to add weighting, like for locked doors, traps, mobs, etc., you do need to read in some extra info for each, but the point is, using a numeric index will work. A hash, quite simply won't, since a) there is no certainty that a room "won't" be identical, and b) any hashing method can generate duplicate hashes, even if the rooms are entirely different (unless I am missing something, but I don't see how producing a hash that is shorter than the original text "can't" produce duplicates). An algorythm that produces 100% unique ones for mud A might generate 1-2 non-unique hashes on mud B, even without the problem of completely duplicate rooms.

David Haley USA Thu 31 Aug 2006 07:23 PM #30

If the hashing algorithm is good, then your chances of getting duplicates are fairly small. Of course, it depends on how big your hash key is; a four-character hash will have lots of duplicates, but a 128-character hexadecimal hash will have a whole lot fewer duplicates.

The real problem here is that neither hashes nor indices can solve the fundamental problem, which is uniquely identifying and distinguishing rooms. If you enter a room, you need to find some way to tell which room it is; Nick's hash method would give you a pretty good idea, in almost all cases. The index issue is slightly separate; the index is not used to determine which room you're in, and is rather an internal unique representation of the room. You still need a mapping from room name/description/etc. to an index number, and that is the million dollar question.

You could probably use some heuristics to make fairly educated guesses. For instance if you come across a room that hashes to the same as one you've seen before, but it is highly unlikely that it is the same (because it is, say, 20 steps east from the first) the mapper could either assume that it's a different room or tell the player that it's confused and ask what it should it.

This issue is very, very complicated... Frankly, it would be so much nicer if players could just see the MUD's internal method of distinguishing rooms. :-) Either that, or give the players more ways to tell if two rooms are different. Of course, sometimes you might *want* the players to feel lost, if for instance you are in a big desert. (That is one reason why we use the random descriptions: making things look somewhat similar, to give a feeling of being in a very large, mostly non-descript segment of terrain.)

Nick Gammon Australia Forum Administrator Thu 31 Aug 2006 09:27 PM #31

These are all issues I have been thinking about, and I admit that the solution is not totally simple.

First, the hashing idea. Certainly you could store the room descriptions, but I think that the hash is shorter, especially if you also have to store the name, the exits, and maybe nearby descriptions.

The whole idea of a well-designed hash is that it is very, very unlikely that you can get duplicates. A major reason for this is that hashes are used to "sign" documents digitially.

Say, for example, Shadowfyr gave me a digitally signed document in which he promised to pay me $100, and I could change that to read $100,000 and then make minor changes (like adding spaces, or slightly rewording it) and keep re-hashing it until I got the same hash, then the signature would not be very useful.

In fact, the MD5 hash is a 128-bit hash, and therefore has 2^128 possible combinations (340,282,366,920,938,463,463,374,607,431,768,211,456 combinations), so you can see that for a few thousand rooms, a collision is not that likely.

If you were worried, you could do a 256-bit hash (SHA256 which is provided in the MUSHclient Lua libraries) which gives you 2^256 combinations (115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 possibilities)

Even the 256-bit hash only requires storing 32 bytes (maybe 64 if you stored them in "hex" format).

The problem with duplicate descriptions is hard to solve as far as I can see. I agree that maybe hashing (or storing) the exits is not a great idea, and in any case something like "a path around darkhaven" could easily fail both our tests. My test of the exits might not help (the path might have various entries that are east and west) and Ksilyan's idea of proximity might also fail, as the paths are likely to be adjacent.

The only (fairly) certain test I can think of is to look into nearby rooms, using Ked's algorithm, and stop after getting one or 2 rooms away (and then going back, if we are able).

Here is an example of what I am talking about. Say there is a long north-south road in Darkhaven, where every room is called "Vertic Avenue".

Now as we enter each room we take all possible exits, and add their descriptions to our hash (or append them to the master description).

Now we have something like this:



Vertic Avenue -> east -> butcher -> west -> baker

This gives us a different hash from:



Vertic Avenue -> east (no room) -> west -> (no room)

or:



Vertic Avenue -> east -> arms supplier -> west -> cooking trainer

However the case of:



Vertic Avenue -> east (no room) -> west -> (no room)

might have multiple occurrences, which is why you probably have to try further afield. Using the terminololy from the algorithm above, you might need to generate 10 or so "particles" to guarantee uniqueness.

I can forsee other difficulties, though. For one thing, one-way exits might make it hard to go back to the room under investigation.

Maybe there is a more elegant solution?

Shadowfyr USA Sat 02 Sep 2006 12:50 AM #32

Well Ksilyan, to be honest, the biggest issue with, "if the program could see the way the mud sees a room", is that some "don't" have such a thing. The closest where I play would be something like:

./Simon/My_City/GenericRoom_1.c

The problem being, there might be several of those rooms, and they might be 100% identical, right down the the individual exits. There is no internal ID number, quite possibly identical exits and no way to even produce a useful hash as a result. A hash is imho, completely worthless, except as a quick check to see if there might be a similar room, and warning the player if something seems odd. For the purposes of pathing, its totally poinless, since you are only interested in the room you are in, the room you are going to, and what it takes to get there. A hash is unlikely to be useful in seeing if an exit is locked, blocked, etc, without making the hash more complicated. It is probably just as easy and more accurate to check the original data for that room, than rely on a hash to figure that out. This means, you are adding a X-bit hash, that is useless for "anything" other than making it "maybe" marginally faster to check an apparently new room against those already known, and thus warn that player of a possible problem. The only advantage I can see is that keeping the hash table in memory is probably "cheaper" memory wise and in terms of speed that doing a series of retrievals from a database.

This is likely a rare enough case that you could let the player do it themselves when "they" realize there is a problem, and only adjust the data "after" they do something like- Click to select first room, click to select second room, click a "Merge" button. And its probably less complicated to let the user fix the problem, than have the mapper constantly whining at them, in something like overland maps especially, that the mapper "thinks" a problem exists. I tend to suspect that the problems possible when trying to use hashes and help the player too much may outway the benefits, but that's just a guess.

Oh, and one ***really*** big problem I see, is that its not totally impossible for someone to create a mud, at least with a real driver, instead of one of these "modern" ones, where the rooms "location" stays the same, but there is no certainty that the name, description and/or exists will *always* be the same.

David Haley USA Sat 02 Sep 2006 02:02 AM #33

I think that what this comes down to is that there simply is no general, perfect solution. The huge variety of more or less different setups precludes that. So, I think the problem worth solving here is targeting a specific sub-class of mapping problems and tackling that. Not to be pessimistic but I think it is basically hopeless to try to make a completely general mapping program that will work across all games. Even if it's possible, it would probably be much less effort anyhow to sub-divide the games into categories and tackle them one at a time.

To be honest, I would find it very useful to have a tool in which I create rooms myself, and I take care of linking them; and from that point all the mapper does is move me from room to room along with my movements. For example if I have mapped rooms A and B, and B lies west of A, and I'm in A and go west, it will know to put me in B. Simple as that. This would be a very big help already. From there it should be pretty simple to automatically detect which exits are present in a room, and ask the user to manually link them to their destinations.

Nick Gammon Australia Forum Administrator Sat 02 Sep 2006 04:03 AM #34

Quote:

A hash is imho, completely worthless, except as a quick check to see if there might be a similar room, and warning the player if something seems odd.

Let's assume for the sake of argument that the hashes will not collide if the data being fed into them is different. From the figures I gave earlier, where there are trillions of trillions (is that gazillions?) of possible hashes I think we are fairly safe there.

The real issue is the data (hashed or not). If we are collecting things like room name/description/exits we can either hash them or simply concat them together and store the resulting string. I only mentioned the hash as it could be a reasonable "key" for indexing into the room data. You could also do what you suggested and simply generate a numeric key (1, 2, 3 ...) and assign a new one when you think you have a new room.

If you know in advance that the room descriptions will be unique then your problem is largely solved, of course. However if not, then it may be very hard to solve. An automated "mapping bot" could easily get confused in this situation:


---> Winding Passage ---> Winding Passage --|
                              |             |
                              ^             v
                              |             |
                              ----<----------

The bot keeps going east, thinking it is finding new rooms, but actually keeps revisiting the last one without realising it.

In fact, even checking nearby rooms won't help because it will find a "Winding Passage" to the east and to the west of it.

Ked Russia Sat 02 Sep 2006 04:04 AM #35

Here's what I finally came up with. The actual code is in the next post.

This uses room name and exits (without the description) for the room signature. The Locator object has move(), look(), undo_move(), and room_display() methods, which are called when making a move, entering a command that will result in a room description but doesn't move you anywhere, receiving a failed move message from the MUD, and receiving a room description, respectively.

Upon initialization, the Locator object searches the map for all rooms with the given signature, for each match it creates a Tracker object, that supports the same methods listed above.

Tracker objects try to match the player's moves to the contents of the map. They do this by storing each move in an internal queue. A move is removed from this queue when either undo_move() or room_display() methods are called. The Trackers' room_display() method returns either true or nil. The former is returned in one of 3 cases:

1) A move direction queued by the Tracker doesn't exist in the current room.
2) A queued move is a "look" command.
3) There was a match between signatures for the expected room and the room being actually displayed. In this case the expected room is set as the Tracker's current room.

In all other cases, the main one of these being absence of a match between signatures, it returns nil.

Locator, when its' room_display() method is called, iterates through its Trackers, calling their corresponding methods. All Trackers that return nil are removed from the Locator's list of trackers. The Locator re-initializes itself when it runs out of trackers.

The Locator can return the current location with its getCurrentRoom() method. It will do so only if there is exactly one tracker left in the list, in any other case it should return nil to signal that the current position is unknown.

So far I can see one advantage of this system and two large shortcomings.

The advantage is that the system is fairly simple and will work on both the MUDs that display unique room IDs and those that don't.

The first shortcoming is that it is very sensitive to the order of commands sent and received. Right now, failing to notify it of a single failed move will break it immediately. This is a big deal because keeping track of failed move messages is not always an easy task. For example, being prone could prevent you from moving in a direction, but also from doing any other numbers of things, and filtering out those prone messages that prevented movement from those that prevented picking your nose is difficult.

The second shortcoming is that the system requires the map to be complete, exits and rooms missing on the map will cause constant failures to pin down the current position. Not sure how this can be helped at this point.

And of course, it requires plenty of refactoring. For instance, I am unhappy with the way exits are represented on the map - they don't allow for hidden exits, coupling what is show in room descriptions with what is really there. I think that a separate Link object would be a better idea.

Ked Russia Sat 02 Sep 2006 04:07 AM #36




dofile "room_stuff.lua"  -- room definitions

function sortExitsTable(exit_tab)
  local labels = {}
  for label,_ in pairs(exit_tab) do
    table.insert(labels, label)
  end
  
  table.sort(labels)
  return labels

end

function sortExitsList(exit_list)
  local exit_list = exit_list
  table.sort(exit_list)
  return exit_list
end



-- a map object that implements all methods for
-- getting rooms, etc.
map = {}

map.rooms = rooms

map.getRoomSignature = function (vnum)
  local room = map.rooms[vnum]
  if not room then
    return nil
  end
  
  local sig = room.name
  sig = sig .. " Exits: " .. table.concat(sortExitsTable(room.exits), ",")
  return sig
end


map.makeRoomSignature = function(room_name, room_exits)
  local sig = room_name
  sig = sig .. " Exits: " .. table.concat(sortExitsList(room_exits), ",")
  return sig
end

map.getRooms = function(room_name, room_exits)
  local sig = map.makeRoomSignature(room_name, room_exits)
  local rooms = {}
  for vnum,room in pairs(map.rooms) do
    if map.getRoomSignature(vnum) == sig then
      table.insert(rooms, vnum)
    end
  end
  
  return rooms
end

map.getRoom = function(vnum)
  return map.rooms[vnum]
end

-- An object implementing all movement-related methods
function Tracker(init_room_id)
  local t = {}

  -- An attribute holding the current room's presumed ID
  t.current_room = init_room_id

 
  -- Holds a history of moves
  t.moves = {}
  
  -- This is called on each move
  t.move = function(dir)

    local room = map.getRoom(t.current_room)
    -- add target room and move to history
    table.insert(t.moves, dir)
      
  end
  
  -- This is called when doing a LOOK command, or any other command
  -- that results in a room display without actual movement
  t.look = function()
    table.insert(t.moves, "look")
  end
  
  t.room_display = function(room_name, room_exits)
    local exit_taken = table.remove(t.moves, 1)
    
    local room = map.getRoom(t.current_room)
    local targ_rsig = map.getRoomSignature(room.exits[exit_taken])
    local this_rsig = map.makeRoomSignature(room_name, room_exits)
    
    if not room.exits[exit_taken] then
      return true
    elseif exit_taken == "look" then
      return true
    elseif targ_rsig == this_rsig then
      t.current_room = room.exits[exit_taken]
      return true
    else
      return nil
    end
  end
  
  -- Call this when a failed move is encountered
  t.undo_move = function()
    table.remove(t.moves,1)
  end
  
  
  return t
end 


-- Call to start searching for the current location when lost
function findCurrentLocation(room_name, room_exits)
  
  -- search the map for any rooms with the given signature
  local rooms = map.getRooms(room_name, room_exits)
  
  -- create a separate Walker for each room returned by the map
  local trackers = {}
  for _, vnum in ipairs(rooms) do
  	table.insert(trackers, Tracker(vnum))
  end
  
  -- return the list of generated Walker objects
  return trackers

end



function Locator()
  local t = {}
  
  t.trackers = {}
  
  
  t.init = function(room_name, room_exits)
    t.trackers = findCurrentLocation(room_name, room_exits)
  end

  t.move = function(dir)
    if table.getn(t.trackers) == 0 then
      return nil
    end
    
    for _, tracker in ipairs(t.trackers) do
      tracker.move(dir)
    end
    return true
  end


  t.room_display = function(room_name, room_exits)
    if table.getn(t.trackers) == 0 then
      t.init(room_name, room_exits)
    end

    local new_trackers = {}
    for _, tracker in ipairs(t.trackers) do
      if tracker.room_display(room_name, room_exits) then
        table.insert(new_trackers, tracker)
      end      
    end
    
    t.trackers = new_trackers
    
    
    if table.getn(t.trackers) == 0 then
      t.init(room_name, room_exits)
    end
  
  end
        
  
  t.undo_move = function()
    for _,tracker in ipairs(t.trackers) do
      tracker.undo_move()
    end
  end
  
  t.look = function()
    for _, tracker in ipairs(t.trackers) do
      tracker.look()
    end
  end
  
  
  t.getCurrentRoom = function()
    
    if table.getn(t.trackers) == 1 then
      return t.trackers[1].current_room
    else
      return nil
    end
  
  end
  
  
  return t

end


loc = Locator()

Ked Russia Sat 02 Sep 2006 04:08 AM #37

And a few simple tests using Nick's map:


function checkPosition(pos)
  if loc.getCurrentRoom() == pos then
    print ("Position correct: " .. tostring(pos))
  else
    print ("Test was failed! Position: " .. tostring(loc.getCurrentRoom()) )
  end
end


-- Do a short walk to ensure that it works at all
--
-- start at 21013
loc.init("Hawk Street", {"s", "n"})

-- move 'n' to 21012
loc.move('n')
loc.room_display("Intersection of Horizon Road and Hawk Street", {'s','e','w','n'})

-- move 's' back to 21013
loc.move('s')
loc.room_display("Hawk Street", {"s", "n"})

checkPosition(21013)


-- Simulate three moves in correct directions with one failure
--
-- start at 21013
loc.init("Hawk Street", {"s", "n"})

-- move 'n' to 21012
loc.move('n')

-- move 'n' to 21011
loc.move('n')

-- move 'n', presumably to 21010
loc.move('n')

-- arrive message received for 21012
loc.room_display("Intersection of Horizon Road and Hawk Street", {'s','e','w','n'})

-- a move failed, so one room display is missing
loc.undo_move()

-- arrive message received for 21011
loc.room_display("Hawk Street", {'s','n'} )

-- current position should be 21011
checkPosition(21011)


-- Three moves, one in a non-existant direction
--
-- start at 21013
loc.init("Hawk Street", {"s", "n"})

-- move 'n' to 21012
loc.move('n')

-- move 'ne' - direction doesn't exist
loc.move('ne')

-- move 'n' to 21011
loc.move('n')

-- arrive message received for 21012
loc.room_display("Intersection of Horizon Road and Hawk Street", {'s','e','w','n'})

-- move failed
loc.undo_move()

-- arrive message for 21011
loc.room_display("Hawk Street", {'s','n'} )

-- current position should be 21011
checkPosition(21011)

Onoitsu2 USA Sat 02 Sep 2006 02:08 PM #38

Ksilyan has got somewhat of the right idea, as zMud's mapper (one built into zmud, not zMapper) uses MS Access databases, so that it will always have a unique key for each room, and that key is created automatically by the DB engine, it is not made from anything, no hash, no concat, just automatic. I remember using the mapper in version 6.something and it had an option of keypad creation (allows manual creation of room layout via the keypad, and sets a flag on said room to say "I am new, capture whatever Room Name, Descriptions, and Exits you see while 'inside' me", then from there you could right click the room in the mapper, and in the game send 'look' and then it would go to work, and unset the afore mentioned flag, so that next entry into the room (whether successful or otherwise will NOT change the info stored for it)

I suggest looking for a zMud map file, and opening it in MS Access, ones from version 6.5- will guarenteed open in MS Access 2000(XP), and that should give a general layout I am describing. Also the mapper would, when you would move in the game (send any direction) would create a virtual room in the previous method, send whatever direction was used, and then retrieve whatever info the mud sent back (meaning the automatic room entry info, can be Name and Exits, may be Name Descrip and Exits, may just be Name). Then from whatever info retrieved, whether all or some it would populate the appropriate info for that room, and toggle the previously mentioned flag. A Portal exit/entrance to a room, can be manually created, there is no real point in trying to match this automatically, it will only mess up the map layout, as you have no set direction where the room the portal exits into's direction is, so a special exit room can be created MANUALLY, say "north east" of the starting room, and the portal link was designated as a red dot in the bottom right (or left, I don't remember 100%) and then once the room is set, you can set the portal entry command, for the starting room, and then the portal exit command to go back (if any, or even if diferent) for the 2nd room. From there in order to monitor for said command it creates a temporary trigger ,matching on the command box imput, so in essence it is an alias '^(.*?)$' and keep evaluating is enabled, and within it it checks if the command entered is EQ to the command already set to enter the portal, if so it moves you to the 'linked' room previously created, otherwise it does pretty much nothing.

The exits, rooms are not created based upon the output of the exits information, only 'link directions' (the room you are in could be surrounded by exits, before even getting the room information for them) and from knowing there is an 'link' existant already the mapper can create a room in that direction if it is sent, and start the whole matching process over again.

I think we already have more than enough combined intellect on these forums, from how quickly entire scripts are posted, and the complexities of some of them. The mapper is basically a bunch of triggers, and the numbering system needing to be used in the mapper is needed to be complete uniqueness, same as used by the Access DB Engine for unique key entries, think of a company's order invoice technique, sure there may be an invoice number, but you do not use that as the unique key, you use a 32-bit short 'positive only' number, and have an invoice number field, and 'link' the tables 'Order Summary' and 'Customer' based on that 'Order Id' field and the 'Customer Id' one as well.

It is all in the layout of the data, you keep trying to create the unique number based on actual information, and concat'ing it or hashing it, but that is the wrong approach to allow such ease of creation of new rooms.

Just my 2 Cents, I may be completely and utterly wrong on this idea, but in my beliefs and experience using the mapper in zMud, this would be the optimal way of thinking, and enacting such a task.

Laterzzz,
Onoitsu2

Shadowfyr USA Sun 03 Sep 2006 01:24 AM #39

Yeah, that was basically what I thought. Why reinvent the wheel, when most databases you are likely to employ already have unique keys? You could make the code smart enough to notice obvious oddities, or let the user handle manually merging the rooms (or more likely both).

Ked Russia Sun 03 Sep 2006 03:26 AM #40

Well, a database is implied, since how else are you going to store and retrieve room and link data? Serializing to disc could work for a while, but reading large maps into memory and searching them by iteration is a bad idea.

A database backend also opens up a score of various possible uses for a map. For example, you could allow users to define their own "objects", creating for each object a table according to the defined schema with a foreign key into the rooms table, thus attaching objects to rooms. Users could then search the map for all rooms containing a certain type of object, a certain type of object with a certain set of properties matching specified values, etc.

These objects could be anything, mobs are one example. Another example involves the Concoctions skillset in Achaea that lets you harvest herbs, with different kinds of herbs growing in different kinds of areas. Different herbs could be defined as object types and then placed in rooms that actually contain them, allowing the user to get a list of rooms (or areas, if the mapper allows them in a sense of collections of rooms) that contain a certain herb. Or all rooms with herbs in them, which would give all natural locations in the world. Or, if the mapper allows for "object type inheritance" all herbs growing in forests could be created as members of the "forest herb" type, which in turn would be of type "herb", so searching for rooms with forest herbs would give all forest locations :)

Then of course, rooms can have shops, which have wares, which have prices... And so on. So a db is a must.

Nick Gammon Australia Forum Administrator Sun 03 Sep 2006 04:09 AM #41

Quote:

... uses MS Access databases, so that it will always have a unique key for each room, and that key is created automatically by the DB engine, it is not made from anything, no hash, no concat, just automatic ...

There is no big problem finding a unique key. Access just adds 1 to the previous highest key when you create a new record. I can achieve that by starting at 1 and adding 1 each time.

The problem is, tying this unique key to rooms in such a way that we are sure the same key is used once, and once only.

For example, if I wander around a city and find "a butcher shop", and store that in my database/table/variable/whatever with key number 5.

Then I wander around for another half an hour, taking many twists and turns. Eventually I find "a butcher shop". Now is that the same butcher shop, and therefore key number 5, which I already have in my database, or another butcher shop at the other end of town, in which case I have to make a new key for it?

Maybe both shops have the same description - the room designer might have copied and pasted. They might both have an east exit. They both might sell the same stuff.

Deciding if they are the actual same room, or two different rooms, is the non-trivial problem we are trying to solve here.

Ked Russia Sun 03 Sep 2006 06:01 AM #42

Quote:
Maybe both shops have the same description - the room designer might have copied and pasted. They might both have an east exit. They both might sell the same stuff.

I think it will be safe to presume that while an individual room may have exact duplicates, duplicate collections of linked rooms are going to be much rarer. And their rarity will increase together with the size of collections.

So if you have added 20 rooms that you believe are new, you can tell which of them are and which aren't by searching for those 20 rooms and links between them on the existing map. Then you can decide whether to merge any or all of those rooms with the existing map based on the results of that search.

Then there's also the question of where to add those new rooms exactly, but that's a different issue.

Shadowfyr USA Mon 04 Sep 2006 12:41 AM #43

And of course, if all you do is inform the user that such a duplication may exist, and let them specify the merge, you have a lot less of the problem. We are trying to make a tool here, not something that can play the game for someone.

Nick Gammon Australia Forum Administrator Tue 12 Sep 2006 07:41 AM #44

To tie this thread to an earlier one, see this:

http://www.gammon.com.au/forum/?id=3970

That thread actually solves (partly at least) knowing where you are, so making something that combines that with the pathing algorithm, should give a pretty good result.

Nobody Fri 22 Dec 2006 06:45 AM #45

Sorry for the thread resurrection but I was working on my own mapper when I stumbled across this thread. I love the algorithm presented earlier (the gas particle thing) which is both efficient and elegant.

Being a perl guy rather than lua, I converted everything to perl and ran the same code/benchmarks that you did. While the results are practically the same, there are a few that are different, which means either I screwed up (most likely) or there's some really subtle trick that I'm missing.

The 'check all paths' versio n(the first one without optimisations) gave me the following output:

Rooms = 257
Made 8,168,729 particles to do that
Time taken = 498 secs

As you can see, this is slightly different from the lua version, which gave 8,178,551 particles in 275 seconds. While the time is considerably slower (roughly half as fast) I'm more concerned with why my version didn't build quite so many particles (10,000 or so less). This leads me to believe that something in my version is broken and is not finding all paths (I've had a few choices result in 'no path' for some reason, even though I think all rooms are accessible from each other. One area that was giving me problems is the 'plain hallway' rooms, when I was debugging one time it got caught in a loop somewhere around there. Trying to narrow down exactly where was practically impossible because of so many iterations and data to examine.

So, I'm wondering if there's a way to get more detailed output on both the lua version and my perl version to see what the difference is, and then hopefully I'll be able to figure out what mine isn't doing that it should be. Perhaps you could make it print out each path it discovers into a file, and then email that file to me? Then I can do a simple comparison to figure out which path is failing and then I can focus on that.

Nick Gammon Australia Forum Administrator Sat 23 Dec 2006 07:42 PM #46

I re-ran the test to make sure. The results I get this time are:


rooms =  257
Made 8176447 particles to do that
Time taken =  205 seconds

This is different from both my previous results, and your results.

Quote:

This leads me to believe that something in my version is broken and is not finding all paths (I've had a few choices result in 'no path' for some reason, even though I think all rooms are accessible from each other. One area that was giving me problems is the 'plain hallway' rooms, when I was debugging one time it got caught in a loop somewhere around there.

Well it is possible my version isn't perfect, however your comment about getting in a loop is a worry, as really the algorithm should check if it has been in a room before, and if so, drop the particle. Thus I can't really see how it can loop.

A possible problem is that we are not using identical room data, so the sensible thing is for me to email you my room definition file (in itself 23 Kb before zipping it).

It shouldn't take much effort to convert that in a Perl-compatible table, even if you write a small Lua program to do it. Then you can be sure we are using the same raw data.

Nick Gammon Australia Forum Administrator Sat 23 Dec 2006 07:53 PM #47

I have sent the room data to your forum email address.

Nobody Sun 24 Dec 2006 05:56 AM #48

Thanks Nick,

I got the file, and re-ran it and got the following output:

Rooms = 257
Made 8168729 particles to do that
Time taken = 507 secs

This is identical to my first reading (except for the time taken, this one took 30 seconds longer - the probable reason is because I had another process chewing up the other half of my CPU so it might have not swapped as efficiently as it should have).

I changed my code to add one extra line. After storing the data returned from find_path, it then prints it out, so I have a log of paths:

Path from room 21096 to room 21308: w,w,s,s,s,s,s,s,e,e,s,s,s,s,u,n
Path from room 21096 to room 21037: e,e,e,s,s,s,s,s,s,e,e

Obviously all 65792 iterations are in there. If someone could do the same with their lua version, perhaps I can figure out which rooms are giving me different results and then I can focus my debugging and analysis on those specific parts.

In the interests of my mudmapper, I converted the pathfinder script into one that retrieves the rooms from an Access db. In perl I use the Win32::ODBC module to access it and run queries. I gather the lua version is somewhat similar. I expected it to be slow, but not quite this slow.

Rooms = 257
Made 8956621 particles to do that
Time taken = 16996 secs

Yes, you read it right - 4 hours 43 minutes 16 seconds.

I figured that a map of a large number of rooms from a mud will be better stored in a db rather than a (hash) table. There are a few reasons why, which I wont get into. Hash tables of course are faster, and don't require as much disk access. However I think the expandability and other benefits from a relational db make this the preferred choice. The speed isn't that important if your mapper is going to be just tracking your location and/or searching for specific paths. If you intend to use it for listing *all* paths (as the benchmark code above did) then perhaps a hash is the way to go.

I'm toying with the idea of a hybrid. One that loads all data from a db to a hash on startup, and when adding a new room, adds it to both at the same time (thereby removing any problems with having to 'save' it constantly from the hash table to the database). I haven't thoroughly explored it yet, I'm still toying with ideas.

My next step is to use that optimised version above on the db version and see how much faster it is. Another thing I'd like to try is running a single path search on a db (both Access and hash table version) with a lot of rooms: 20,000+ would be a good start, my ideal would be 50,000+ or 100,000+ rooms to find out just how long it takes on a 'real' map.

Shadowfyr USA Sun 24 Dec 2006 09:41 PM #49

You're kidding right? That long? I think maybe we need to find out what algorythm the Tradewars Helper application used and figure out some way to adapt that. Seriously, one function it had was, "Use probes to find information about as many sectors as possible." This often took only 10-20 probes, to produce a complete map of 10,000 rooms and their contents. Mind you, the
"ship computer" had a map of how the rooms connected, so what it would actually do is:

1. Log into the computer.
2. List "every" sector (room) in the game, which provided the number ID, basic description and exits.
3. Do a "longest path" search for the first probe.
4. Send the probe to the end room and marking each returned room as it want.
4. Do a longest path search for the next probe, which automatically excluded all rooms seen already (it allowed cross overs, but not ones that ended in the same room that the last one did.
5. Send the probe, etc.
6. Repeat 4, until you have all rooms or you run out of probes.

Obviously a "longest path" search **must** be exhaustive. I.e., for it to find the longest path, it must check every "available" path to every un-identified sector, then send the probe to the one farthest away. Mind you, in that case the longest path was usually between 10-20 rooms. However, while it took (on a 386 processor) 20-30 minutes to read the computer data to "build" the database, the searches took all of about 30 seconds each. Now, we are talking about maybe double the rooms, with theoretically, lets just say, twice the path lengths, on a machine that is 1,000+ times *faster* than the Tradewars Helper ran on, and its taking nearly -5- hours to do what is basically a, "find all paths to see which is the longest one from X to Y"?!? Something is seriously wrong with that imho. But maybe I just don't understand how much greater the search time is for longer paths...

Nobody Mon 25 Dec 2006 04:43 AM #50

Just for further benchmarking information, I ran the optimised version (posted back on page 1 I believe) that runs in lua in about 2-3 seconds. In perl, using perl hashes, it takes 25 seconds. In perl, accessing everything through the Win32::ODBC and running an sql query to obtain room/exit data, took 137 seconds.

So a rough conclusion to be drawn is that perl is between 2 and 10 times slower than lua when using perl hashes. When comparing perl hashes to perl ODBC, it's between 5 and 30 times slower. I'd really like to find the bottleneck and see if it could be eliminated, but I suspect it's just that perl isn't fast at anything except regexps. Still, I think for a mapper it's reasonably fast, as long as you're not going to need to generate hundreds of paths a second you should be ok.

Nick Gammon Australia Forum Administrator Tue 26 Dec 2006 02:06 AM #51

Quote:

Obviously all 65792 iterations are in there. If someone could do the same with their lua version, perhaps I can figure out which rooms are giving me different results and then I can focus my debugging and analysis on those specific parts.

As discussed earlier in this thread it is possible to use less particles to discover the same path, I think, depending on the starting point. So it is possible you are generating the correct paths, but in a slightly different order.

Anyway, I am making a file of the generated paths as you requested, which I will zip up and email shortly. If you sort both yours and mine into sequence, and then run a "diff" on them, it should be easy to spot any differences.

Nobody Wed 27 Dec 2006 11:46 AM #52

Thanks Nick,

When I first checked the output, I noticed a few thousand lines of differences, and I groaned at the thought that I had royally screwed up. Then I started analyzing them an realised that the differences, while noticeable, were in fact different ways of getting to the same place - 4e4n instead of 4n4e. When I compared the length of each path, they were identical. So it seems that due to the order the exits are chosen, you can end up with a path the same length, but using less particles. Interesting.

My next step is to add a weighting to certain exits depending on other conditions: eg, damage rooms, exits that are locked, rooms that you have to kill a certain mob to access, and to factor them into the pathing algorithm. It shouldn't be a big deal, but I still think it would be useful. For example, a room that damages you might only be used if the alternate path is some huge length around. Another option is to return an array with the top 5 paths, so that the user can then choose which one they want.

Hmmm there's so much else I want to do, but baby steps, baby steps. Incidentally, is there a standard downloadable mud server that comes with a few ten-thousands of rooms already built in and linked? I might use that for testing the large-path speeds instead of trying to manually link all my own.

Nick Gammon Australia Forum Administrator Wed 27 Dec 2006 07:05 PM #53

This confirms what I said before, that the particle count depends a bit on the order on which rooms are visited.

As for the standard MUD, I just used SmaugFUSS, which is available as a download from this site.

Nobody Thu 28 Dec 2006 12:29 AM #54

Yeah I've used that so far, I just wanted something with alot more rooms to see if the finder chokes on extremely large paths when searching 30,000+ rooms. By 'chokes' I mean 'becomes too slow to be useful'.

Nick Gammon Australia Forum Administrator Fri 29 Dec 2006 02:57 AM #55

I think that to make large maps efficient you probably need to zone them somehow. For example, if you know the room you want is somewhere to the east, then checking each road that leads west is probably a waste of time.

Or, you might simply limit the pather, so that after it becomes (say) 30 rooms long it simply stops.

Thus, if I wanted to go from some city to some other city a long way away, I might first find the exit from this city - and go there. Then I find the next city. Then I go to the room.

Breaking down the problem like that could make the mapper useable, and be more practical anyway.

Nobody Fri 29 Dec 2006 05:40 AM #56

While that seems to work, I can think of a simple situation (and one that's likely to exist in alot of places on many muds) right off the top of my head that would screw it up.

Say, for example, you're at the north gate of a city, and you know you have to go north to get to your target. So (with some modifications) you can make the mapper ignore any exits that arent north. Sounds fine and dandy, but what about this: Somewhere north of this exit, there's a path that branches off to the east, and links up with the path that is sent out from the east gate of the city you're in. Now you're searching that entire east branch as well. And if there's one linking that east path to a south path, then again you're locked into exploring all those unnecessary paths.

The upside of course, is that maybe there's a secret hidden path that's actually quicker that you might not know about. Perhaps one featuring a portal or something.

I dunno, I still think with 50,000+ rooms the speed would be enough that it wouldn't be a hassle. Guess it's hard to test something like that though since there's not much chance of getting a workable test system with that many rooms on it.

Nick Gammon Australia Forum Administrator Fri 29 Dec 2006 06:13 AM #57

Well, I was thinking if you are in South City, and you want to go North City, and you are somewhere in the bowels of South City, then you choose a road you know leads you to North City (eg. Northern Highway) and ask for a route to that.

Even if your initial paths are south, you hopefully get the optimal route that takes you to the edge of the city. Then, following the main road north, you reach the gates of North City. From there you request a path to your final destination.

As for test data, you could just randomly generate heaps of rooms.

Shadowfyr USA Fri 29 Dec 2006 09:58 PM #58

Yeah, you can hope that you can pick such a path. Just to illistrate the problem with that hope though, I have been playing EQ2. Yeah, I know, its a graphical system, but there are clear areas and clear checkpoints along the way, like buildings, roads, etc. There is also an "underground" I stumbled across. The unique thing about it being that *every* part of the city of Qeynos is accessible through that underground, just by moving 2-3 rooms. Now, the "room" you want to get to, like the South Qeynos pet shop might be 20 rooms away, but if you are in the Willow Woods, for example, it might be, parsing the distance into text terms, 10 rooms to get to the underground, 3 rooms in there, then 20 to get to the shop, while the "alternate" route, that takes city zones into account, would take 15 to get to the boundary to High Castle View, 15 to get to North Qeynos, 30 to get through there, then another 30 to get to to shop.

The mapper needs to be smart enough, in other words, if you are going to do it that way, of "knowing" that a short path does exist and that it makes sense to go to the next city zone, instead of the underground, or like in EQ 1, running all the way from Qeynos to Freeport, instead of going the opposite direction to the Plane of Knowledge teleport book, then through there to the POK stone that links out to Freeport. A distance of 3-4 areas, each (again, projecting it into a text world) 30-40 rooms across, vs. going straight from outside the city walls of Qeynos to just outside West Freeport.

Mind you, one option, and one that makes sense imho, is to have something like quickpaths to "named" locations. A player could set specific places, as "always follow this path". That could include known crossroads. That way the "optimal" path know at that point could be stored (and rechecked later at the players option). Then, when you need to look for some place you could optimize things a bit by taking the "known" part of a path, then using its end point as the "start" when looking for a destination. Though, again, that means having some awareness of "Where" that endpoint is. Hmm... I suppose, one things you could do is use a base point, like initial login for most people, and store the data for rooms in a tree of sorts, so that the search can generate a rough estimate of distance from a known point that an end point is, then *guess* if its a good candidate to search off of. It kind of depends on how smart you a) want to make it and b) need to make it to work well.

Nick Gammon Australia Forum Administrator Sun 31 Dec 2006 03:22 AM #59

A simple limiter (eg. stop when path is 100 long) would at least stop lengthy CPU loops.

Then it could be up to the player to "manually" move closer to the destination. Assuming you have some idea of the topology of your world, you could generate a path to the exit from the city that you think leads to where you want to go, and take it from there.

Quote:

The unique thing about it being that *every* part of the city of Qeynos is accessible through that underground, just by moving 2-3 rooms.

The existing pather will discover those, because it does an exhaustive search. Assuming those rooms are known, it will take the shortest path, which in this case would be underground.

Shadowfyr USA Mon 01 Jan 2007 01:30 AM #60

Of course. My point is that an optimization that didn't "know" that the underground existed at all initially might look for the path to the area boundary instead, this being flawed, since once the underground is known, its no longer the most reasonable path.

Nick Gammon Australia Forum Administrator Tue 02 Jan 2007 06:49 AM #61

Exactly. An exhaustive search is probably the safest, and with a limiter, should not consume your CPU for 10 minutes.

Shadowfyr USA Tue 02 Jan 2007 07:28 PM #62

Mind you. Its probably a good idea to make it so that if "no" path is found with those limits, that it looks for one with a bigger limit, so you start with 30, then if not found, try 40, etc. Or, maybe even let the player specify, something like, "find orc shaman : far". Where that designates that it should use a bigger limit, or just ignore them. Its not impossible for some mud to have a path from the farthest corners to each other be 30+ rooms. Of course, if using this with a GUI, you could simply have a set of buttons to define if you want "near", "close", "distant", "far" or "unknown", as a search limit. And if previous successful searches where stored, so going from the bank to Zorg's Merchantile was already found, the "current" distance would be stored for those start/end locations, so that a new search only looks for something "shorter than or equal to" that.

In other words:

Near - 10
Close - 20
Distant - 30
Far - 40
Unknown - infinite

So, if the path from the Bank to Zorg's is "known" to have been 19 last time, it won't look for any path longer than "Close" the next time. The only issue is how many prior searches it stores, so you might want an option of "save this search", or even just throw out ones that haven't been used more than once after 10 active days. That way you don't have to look through 50,000 * 50,000 prior searches (in the worst case, like some moron going to every room, one at a time, and searching every other room in the game world...), just the "often used" and most recent ones.

Nobody Sun 07 Jan 2007 06:32 AM #63

Who wants to help me plan out some data structures for a mapping system that does everything above, but also has the ability to learn new rooms and add them (with appropriate linkage to other rooms) ?

It doesn't really matter much about which language is used - perl hashes are pretty much the same as lua tables in this case. The trouble I'm having is searching for a room by title. I was hoping to have a way to search for something quickly (I was thinking of somehow using a room title as a key, but that falls apart when multiple rooms with the same title occur) so I guess I'll have to do the old brute search method.

What I'm aiming for here is a mapper that can monitor your position and keep itself updated about which room you're in, and one that adds the room if it's not found. I'm not too concerned right now with things such as detecting rooms and making it all 'portable' for all muds. Right now I'm just focusing on the data structures for storing the data. Who has some ideas?

I'll be storing the following data: Room title, description, vnum (not given by the mud, generated by me), exits. Room title and description will be strings, vnum obviously will be int, and exits will be a hash (or table) of direction->vnum.

So far I have a hash with the vnum as key, and the text data as a sub-hash (with the exits data as a sub-sub-hash). Can anyone think of a better way ?

David Haley USA Sun 07 Jan 2007 08:19 AM #64

Well, there is a data structure called the multimap, which can store several values with the same key. That way you could keep very quick lookup, and when you have conflicts, you would resolve them however you would normally resolve them. (You have to resolve them somehow anyhow.)

One main difference with this data structure is that you wouldn't specify just a key to remove, but a key-value pair so that it leaves other values that might share the same key.

An easy but not optimal way of implementing this is to have every key point to a list of values for that key. (This is not optimal because most of the time the list overhead is useless. It might be better to only have a list if you actually need one, but that adds extra complexity.)

Onoitsu2 USA Wed 11 Apr 2007 11:09 AM #65

Since this WAS a very hot discussion, and is still more likely than not an idea in a lot of user's heads, I have tried to track down some things on it, and have located an Open Source Client, that HAS a MAPPER, so that such code can be examined, and perhaps a mapper can be built by the "Programming Community" since the release of mushclient's source.

http://www.mudmagic.com/mud-client/source_download.php

That is the URL to DL the source in a variety of archive types. The Windows Zip is 3769KB (roughly 3, nearly 4 MB)

I am unsure as to the Language used, as I have not DL'd the source as I am having connection difficulties (Dialup only wanting to connect at 26.6 for some odd reason)

Laterzzz,
Onoitsu2