Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.
 Entire forum ➜ MUSHclient ➜ Lua ➜ Mapping - Pathing
Mapping - Pathing

It is now over 60 days since the last post. This thread is closed.     Refresh page

Pages: 1 2  3  4  5  

Posted by Indoum   Sweden  (17 posts)  Bio
Date Sun 27 Aug 2006 09:31 PM (UTC)

Amended on Sun 27 Aug 2006 09:33 PM (UTC) by Indoum

Message
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.
Top
Posted by Indoum   Sweden  (17 posts)  Bio
Date Reply #1 on Sun 27 Aug 2006 09:32 PM (UTC)
Message
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>
Top
Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Reply #2 on Sun 27 Aug 2006 10:39 PM (UTC)
Message

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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Shadowfyr   USA  (1,788 posts)  Bio
Date Reply #3 on Sun 27 Aug 2006 11:41 PM (UTC)
Message
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.

Top
Posted by Ked   Russia  (524 posts)  Bio
Date Reply #4 on Mon 28 Aug 2006 02:01 AM (UTC)
Message
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.
Top
Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Reply #5 on Mon 28 Aug 2006 07:51 AM (UTC)

Amended on Mon 28 Aug 2006 08:50 AM (UTC) by Nick Gammon

Message
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

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Reply #6 on Mon 28 Aug 2006 08:29 AM (UTC)

Amended on Mon 28 Aug 2006 08:51 AM (UTC) by Nick Gammon

Message
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

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Reply #7 on Mon 28 Aug 2006 09:45 AM (UTC)
Message
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.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Ked   Russia  (524 posts)  Bio
Date Reply #8 on Mon 28 Aug 2006 03:51 PM (UTC)

Amended on Mon 28 Aug 2006 03:53 PM (UTC) by Ked

Message
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.


Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #9 on Mon 28 Aug 2006 04:38 PM (UTC)
Message
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.)
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Shadowfyr   USA  (1,788 posts)  Bio
Date Reply #10 on Mon 28 Aug 2006 07:53 PM (UTC)
Message
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
Top
Posted by Shadowfyr   USA  (1,788 posts)  Bio
Date Reply #11 on Mon 28 Aug 2006 07:57 PM (UTC)
Message
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.
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #12 on Mon 28 Aug 2006 08:16 PM (UTC)
Message
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.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Reply #13 on Mon 28 Aug 2006 09:25 PM (UTC)
Message
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

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Reply #14 on Mon 28 Aug 2006 09:39 PM (UTC)
Message
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.


- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

165,932 views.

This is page 1, subject is 5 pages long: 1 2  3  4  5  [Next page]

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum

[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

Home