[Home] [Downloads] [Search] [Help/forum]

Gammon Forum

See www.mushclient.com/spam for dealing with forum spam. Please read the MUSHclient FAQ!

[Folder]  Entire forum
-> [Folder]  MUSHclient
. -> [Folder]  Lua
. . -> [Subject]  Mapping - Pathing
Home  |  Users  |  Search  |  FAQ
Username:
Register forum user name
Password:
Forgotten password?

Mapping - Pathing

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


Pages: 1  2 3  4  5  

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #15 on Mon 28 Aug 2006 10:15 PM (UTC)
Message
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.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Reply #16 on Mon 28 Aug 2006 10:57 PM (UTC)
Message
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

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Reply #17 on Mon 28 Aug 2006 11:32 PM (UTC)

Amended on Tue 29 Aug 2006 05:04 AM (UTC) by Nick Gammon

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

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Ked   Russia  (524 posts)  [Biography] bio
Date Reply #18 on Tue 29 Aug 2006 12:10 AM (UTC)
Message
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.
[Go to top] top

Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Reply #19 on Tue 29 Aug 2006 03:42 AM (UTC)
Message
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

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Reply #20 on Tue 29 Aug 2006 04:20 AM (UTC)

Amended on Tue 29 Aug 2006 05:14 AM (UTC) by Nick Gammon

Message
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

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Reply #21 on Tue 29 Aug 2006 05:13 AM (UTC)

Amended on Tue 29 Aug 2006 05:16 AM (UTC) by Nick Gammon

Message
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



- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Shadowfyr   USA  (1,783 posts)  [Biography] bio
Date Reply #22 on Wed 30 Aug 2006 02:44 AM (UTC)
Message
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
[Go to top] top

Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Reply #23 on Wed 30 Aug 2006 05:27 AM (UTC)
Message
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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #24 on Wed 30 Aug 2006 02:58 PM (UTC)
Message
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.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Reply #25 on Wed 30 Aug 2006 10:38 PM (UTC)
Message
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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Ked   Russia  (524 posts)  [Biography] bio
Date Reply #26 on Thu 31 Aug 2006 03:22 AM (UTC)
Message
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.
[Go to top] top

Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Reply #27 on Thu 31 Aug 2006 06:35 AM (UTC)
Message
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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #28 on Thu 31 Aug 2006 05:07 PM (UTC)
Message
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.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Shadowfyr   USA  (1,783 posts)  [Biography] bio
Date Reply #29 on Thu 31 Aug 2006 06:50 PM (UTC)
Message
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.
[Go to top] 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.


45,135 views.

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

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

Go to topic:           Search the forum


[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

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

[Home]


Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at FutureQuest]