Mudlet Mapper

hempa
Posts: 48
Joined: Sat Jan 02, 2010 1:07 pm

Re: Mudlet Mapper

Post by hempa »

I'm an avid user of the Mudbot mapper, and I'm very much used to aliases and commands, so the least thing would be a manual way of editing the map without having to click and do stuff like that. I find it a hundred times easier to change stuff with commands than menus and clicking. The only reason I would like some sort of click is moving around rooms and perhaps hiding/showing exits.

A direct api to change stuff on the map, from triggers or aliases, would be necessary of course. It's necessary to track areas and rooms, and setting colors/styles. On the screenshot you linked you have icons as rooms, would it be possible for things like icon packs or similar?

Just a few thoughts...

Jeremy
Posts: 12
Joined: Wed Dec 30, 2009 7:09 pm
Location: Bellingham, WA, USA
Contact:

Re: Mudlet Mapper

Post by Jeremy »

One thing I would like to be able to offer users, as a developer, is the ability to be able to download a map db from our servers with the click of a button.

davidk
Posts: 13
Joined: Wed Dec 09, 2009 7:01 pm
Location: avalon.mud.de

Re: Mudlet Mapper

Post by davidk »

Vadi wrote:Alright. How about we follow an MVC model - with the viewer being a 3d one, or a 2d one, or an ascii one if you'd like. The model will be shared, just the views will take care of handling the display and visual navigation. Controller would be the same for them all too.
Oh, I fear I wasn't quite clear, when I talked about ASCII-maps. I don't really want them as the main representation but as an export option.

User avatar
Vadi
Posts: 4852
Joined: Sat Mar 14, 2009 3:13 pm

Re: Mudlet Mapper

Post by Vadi »

Ah, yeah, that makes more sense.

We can also start on the mapper already - we were planning to do it in Lua, so while heiko is busy on the 1.1 display/mxp, it's feasible to start creating it within Mudlet.

One thing that needs to be decided first is the map storage model... so it can work both on muds where you have an exit in every direction and the limited once. Also, an algorithm for pathing.

IMappers works quite well on the limited direction muds, but I'm not sure how would it work with tens of thousands of rooms (mostly because it's room detection isn't designed for that and it gets lost horribly easy).

Iocun
Posts: 174
Joined: Wed Dec 02, 2009 1:45 am

Re: Mudlet Mapper

Post by Iocun »

Vadi wrote: One thing that needs to be decided first is the map storage model... so it can work both on muds where you have an exit in every direction and the limited once.
Yeah, I think finding a balance between optimizing it for limited-exit-muds and all-exits-muds may be a challenge, especially when it comes to pathfinding. Limited-exit-muds have the advantage of, well, fewer exits, so there are fewer paths you have to consider. All-exit-muds, usually have the advantage of having geographically very "logical" connections, which allows you to estimate distances between rooms for pathfinding (particularly, when the rooms follow a strict coordinate system). So in the latter kind, some heuristic pathfinding algorithms may be advantageous, whereas in a mud with few exits (and optimally few rooms), a "just compare every possible path" approach may work fine. We'll probably have to find something in between there.

But unless the plan is to implement two different storage models, one for limited-exit-muds and one for the others (which may be an efficient, but also cumbersome approach), I guess it should be based on the model of limited exits, since that's the more general case. (Since muds of the other kind also have a finite number of exits, just a larger one.)

A storage model somewhat similar to IMaps may therefore still be the best option. (I.e. store a unique room id, a room name, all exits along with the room ids they lead to, and possibly further information). Personally, I'd love it if the kind of further information you wish to store was customizable, to some degree. I.e., some muds may have the concept of "areas" or "environments", whereas others have entirely different room properties.

One question is also whether it might be worth it storing some data several times, in slightly different forms, to increase processing time. For instance, a room might be stored somewhat like this:

Code: Select all

roomlist =	{
		
			{
			name="Someroom",
			connects={{id=15,dir="east"},{id=252,dir="southeast"},{id=352,dir="south"}},	
			exits={east=15, southeast=252, south=352},	
			--further room properties
			}		

		}
Here, the information of which exits exist and where they lead are actually stored thrice. Once, as a list "connects", which would probably be the most useful format for pathfinding routines. Once as a dictionary, where you can look up where each exit leads to (useful for tracking manual movement, etc.).

Of course, it would work just as well with just a single one of these subtables and it would save storage space (plus slightly increase mapping time), but processing the map after it has been mapped would in turn be faster and simpler, since it saves you to loop through tables to find certain values, in contrast to just directly indexing them.

Also, an algorithm for pathing.
Here again, one question is probably whether we can take into account heuristic guesses (such as the remaining distance from a certain room to the desired end room), or whether that's not possible. Also: Whether it's absolutely required to find the shortest path, or just a relatively short path, respectively: How much processing time we're willing to offer in favour of a shorter path.

If it's just about finding -any- path, the task is rather easy. I came up with a little crude lua demo for something like that:

Code: Select all

function resetRoomlist()

	roomlist =	{
				{connections={2,3,4}, parent=nil},
				{connections={1,3}, parent=nil},
				{connections={1,2,5,6}, parent=nil},
				{connections={1,5,7,8}, parent=nil},
				{connections={3,4}, parent=nil},
				{connections={3,7,8,9,10}, parent=nil},	
				{connections={4,6,10}, parent=nil},
				{connections={4,6,11}, parent=nil},
				{connections={6}, parent=nil},
				{connections={6,7,12}, parent=nil},
				{connections={8,13}, parent=nil},
				{connections={10}, parent=nil},
				{connections={11,14,15,16,17}, parent=nil},
				{connections={13,15,16,17}, parent=nil},
				{connections={13,14}, parent=nil},
				{connections={13,14,17}, parent=nil},
				{connections={13,14,16,18,19}, parent=nil},
				{connections={17,19}, parent=nil},
				{connections={17,18,20}, parent=nil},
				{connections={19}, parent=nil}
				}
end

function findPath(startnode, endnode)
	local closedlist = {startnode}
	local openlist = {}
	local currentnode
	local revpath = {}
	local path = {}

	resetRoomlist()
	roomlist[startnode]["parent"] = 0

	while(not roomlist[endnode]["parent"]) do
		currentnode=closedlist[#closedlist]

		for i, node in ipairs(roomlist[currentnode]["connections"]) do
			if not roomlist[node]["parent"] then
				openlist[#openlist+1] = node
				roomlist[node]["parent"]=currentnode	
			end	
		end
		if #openlist > 0 then
			closedlist[#closedlist+1]=openlist[1]
			table.remove(openlist,1)
		else
			return false							--no path found
		end
	end
	revpath[#revpath+1]=endnode
	while(roomlist[revpath[#revpath]]["parent"] ~= 0) do		--tracing back
		revpath[#revpath+1]=roomlist[revpath[#revpath]]["parent"]
	end
	for i = #revpath,1,-1 do							--reverse the path
       path[#path+1]=revpath[i]
    end
	return path	
end
(I'm totally inexperienced with pathfinding stuff, so excuse the primitive approach here.)
Example: findPath(6,17) returns the following path between room 6 and room 17: {6, 8, 11, 13, 17}

This does something like a "spiral search" around the starting room; i.e. it adds all adjacent rooms to a list, then it adds the rooms adjacent to those rooms to the list, and so on, until it hits the target room. Then it traces back the path according to which rooms were called from which other rooms.

I think this will always find the shortest path (as long as there are no differing "costs"/durations by taking different exits), but it won't be very efficient on huge numbers of rooms. It would have to be optimized a lot for that, by adding heuristic guesses.

P.S. I did some testing with randomly generated "worlds" consisting of up to a million rooms, with 2-8 exits each and some rather large distances between starting and ending rooms (up to several thousand steps), and the algorithm posted above performed surprisingly well. I can't really say if it actually did find the shortest possible path in all cases (but it may very well have), but it always found one within a few milliseconds. (With three or four exceptions that took a bit longer than a second to calculate - but very often it took less than 10 milliseconds.) Of course that may have to do with the way I generated the room list - it may be somewhat different with room lists from an actual mud, I don't know. I'd have to get hold of a large map of a mud to test this with.

User avatar
Vadi
Posts: 4852
Joined: Sat Mar 14, 2009 3:13 pm

Re: Mudlet Mapper

Post by Vadi »

The two different map storage formats does make sense, however, I don't think it'll work too efficiently when you have MUDs that combine them both (like IRE even) since when your path takes you from an infinite to finite exit areas, that all would need to be calculated in a rather complex way.

So perhaps the dual model as you suggested would be the best.

I talked to Whyte (creator of IMapper) some, and here's what he had to say:
  • analyze all (popular) mud drivers, see what they have in common (if anything)
  • create smart room autodetection (ie recognize the different parts of the room message)
  • no change in the imappers pathing algorithm
  • as for data storage, suggested different models since that's how MUDs have it too, although I don't think pathfinding between them was considered

User avatar
Vadi
Posts: 4852
Joined: Sat Mar 14, 2009 3:13 pm

Re: Mudlet Mapper

Post by Vadi »

Iocun wrote:
P.S. I did some testing with randomly generated "worlds" consisting of up to a million rooms, with 2-8 exits each and some rather large distances between starting and ending rooms (up to several thousand steps), and the algorithm posted above performed surprisingly well. I can't really say if it actually did find the shortest possible path in all cases (but it may very well have), but it always found one within a few milliseconds. (With three or four exceptions that took a bit longer than a second to calculate - but very often it took less than 10 milliseconds.) Of course that may have to do with the way I generated the room list - it may be somewhat different with room lists from an actual mud, I don't know. I'd have to get hold of a large map of a mud to test this with.
Oh, that's good. You know, I think Larkin wrote a Lua parser for the IMap (to sort of add mapping integration that way) - perhaps you can modify it to output some real IMaps in this format and do some work on them, and compare to the IMappers result. That would be good finite-room testing.

Thylacine
Posts: 28
Joined: Sun May 10, 2009 5:04 am

Re: Mudlet Mapper

Post by Thylacine »

I'm generally agreeing with everything said here, but as for the storage why not use map,x,y,z coords instead of an arbitrary vnum?

That way you can use a hash map for each room that lists a 'command' to send and its resultant modification to each of the exits.

This way heuristics become one hell of a lot easier; if the desired room's x < current room's x then find the exit that reduces the x coordinate. That can be done for y, z and map as well.

Of course it will be a little more complicated to code and I'm not sure if it will be any faster or otherwise, but it would allow for both normal and 'multi dir' muds to function on the same base code.

Iocun
Posts: 174
Joined: Wed Dec 02, 2009 1:45 am

Re: Mudlet Mapper

Post by Iocun »

That may work perfectly in some muds, but others behave rather illogically regarding "geographical directions". E.g. you might find stuff like this in a mud: Room A connects east to B, which connects east to A again. (Often it's of course much less extreme than this, but even the above appears enough.) Also, the distances between room, when seen in actual X/Y coordinates aren't always the same. You might have a setup like this:

Code: Select all

[]------[]
|        |
[]--[]--[]
When you're just mapping the above two rooms, it seems like they're one step to the X direction apart. But as soon as you map the lower ones, you see that it's actually two steps. And these distances might continuously change while mapping like this, not even to mention different kinds of exits (up, down, in, out, "enter house", "climb wall", whatever). So, while coordinates may be the most suitable storage option for some muds (and some areas), I don't think they would work very well for others. You're right of course that they're the easiest way of implementing heuristical methods. Otherwise we have no means of measuring distances easily. (But we also have to take into account that X/Y distances do not actually always determine travel times either. In the graphical example above, you would travel as fast between the above two rooms, as between the room to the lower left and lower middle, even though the above two rooms have twice the distance coordinate-wise.)

But since there probably will be X/Y coordinates anyways (for the map display), we might use them in -combination- to vnums. I.e. use vnums as the technical basis, but take into account X/Y coordinates to some degree for heuristics.

User avatar
Vadi
Posts: 4852
Joined: Sat Mar 14, 2009 3:13 pm

Re: Mudlet Mapper

Post by Vadi »

Taking IRE into example, not everything is laid out in geographically logical manner... especially Ashtans bog. Too lazy to go to it atm to take a screenshot, but here's the zmud map.

In Iocuns example though, by default, the 2 rooms would be faster than 3, because of the 2 rooms/sec speed limit in IRE. Unless you're using a sprinting command like gallop, at which point it would be the same travel time.

So maybe we could try storing the x,y coordinates also, for the muds that use a logical geographical sense... but not rely on them if they aren't available.

Post Reply