Gammon Forum : MUSHclient : Python : Automapper

Log on

Gammon Forum

Entire forum

MUSHclient

Python

Automapper

Automapper

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

Posted by

LupusFatalis (154 posts)

bio

Date

Wed 24 May 2006 11:06 PM (UTC)

Message

Alright... First things first. I'm thinking of programming an automapper for Python. For a mud called Dartmud. So I guess the first question is, has anyone successfully done this for another mud and they wouldn't mind helping me out. My idea is quite simple, I database all the rooms, linking them to one another, each time a direction is taken, it will take into account your old room, add a new room in that direction. With a trigger for directions that were false, delete the room. Of course if this direction that already contains a room it will not add it, but move the current room location. Anyway, thats just a starting idea. Later, I may write a little program to take the database and create a JPG or something from it. But, until then I want it as a database. Mainly so I can generate pathings between rooms. This particular mud has thousands of rooms in Underdark, and it would be quite valuable to be able to go through them quickly. In any case, I'd appreciate input from anyone who has taken on such a project already. Or if anyone is familiar with the mud and would like to program it with me, thats cool too. The pathing is probably the most difficult part of the project, I've been thinking for a while, and can't figure out how I'd do it... So I'd appreciate input on that end.

top

Posted by

Ked Russia (524 posts)

bio

Date

Reply #1 on Thu 25 May 2006 09:33 AM (UTC)

Message

I've taken several stabs at it and never got too far, but can offer a couple of suggestions.

For the db, I'd advise sqlite, as the most portable and simple one to work with. You could use ADO but that would require dealing with what datasources your users have available locally (if any). Sqlite has a good Python (as well as Lua) binding, and is even going to be bundled with Python in future versions.

For pathfinding I can only offer a prototype script that uses a naive genetic-like algorithm (basically a stripped down version of A*). It's fairly well optimized and runs pretty fast on small maps (I've tested it on a map with about 60 rooms and over 200 links). But execution time varies depending on the map layout, so it would require further tweaking for larger maps. I was thinking about using some sort of a clustering technique to break up the map and run the pathfinder on individual pieces, as well as pre-computing some data about the map and storing it in the db. Problem is that this is a pet project to such a degree that unless I can come up with a _very_ fancy solution, I won't come up with any :)

The script in the next post has that pathfinder, as well as an idea for an object hierarchy that should translate well to SQL and be usable from Python.

top

Posted by Ked Russia (524 posts) bio

Date

Reply #2 on Thu 25 May 2006 09:38 AM (UTC)

Amended on Thu 25 May 2006 09:50 AM (UTC) by Ked

Message

The mapper/pathfinder script:


from types import IntType

class Room(object):
    def __init__(self, name, id):
        self.name = name
        self.id = id
        self.from_links = []
        self.to_links = []

    def __repr__(self):
        return "Room '%s' (%d)" % (self.name, self.id)


class Link(object):
    last_id = 0
    def __init__(self, orig):
        self.orig = orig
        self.dest = None
        self.id = self.getId()

    def getId(self):
        self.__class__.last_id += 1
        return self.__class__.last_id - 1

    def __repr__(self):
        return "%d -> %d" % (self.orig.id, self.dest.id)


class Rooms(dict):
    def __init__(self, parent):
        super(Rooms, self).__init__()
        self.parent = parent


class Links(dict):
    def __init__(self, parent):
        super(Links, self).__init__()
        self.parent = parent
    
    
    def __setitem__(self, key, val):
        assert type(val) == Link, "A Links dictionary may only contain values of type Link."
        super(Links,self).__setitem__(key, val)
        self.parent.rooms[val.orig.id].from_links.append(val)
        self.parent.rooms[val.dest.id].to_links.append(val)
    
    def getFromRoom(self, room):
        assert type(room) == Room, "Argument to Links.getFromRoom() method must be" + \
        "an instance of class Room, got %s instead" % str(type(room))
        return room.from_links
    
    def getToRoom(self, room):
        assert type(room) == Room, "Argument to Links.getToRoom() method must be" + \
        "an instance of class Room, got %s instead" % str(type(room))
        return room.to_links
    
    def isDirectLink(self, from_room, to_room):
        for link in self.getFromRoom(from_room):
            if link.dest == to_room:
                return link
        return False
    
    def hasToLinks(self, room):
        if len(self.getToRoom(room)) > 0:
            return True
        return False
    
    def hasFromLinks(self, room):
        if len(self.getFromRoom(room)) > 0:
            return True
        return False
    
           
   
class Walker(object):
    def __init__(self, current_room, goto_room, path=[]):
        self.path = path
        self.goto_room = goto_room
        self.current_room = current_room

    def __repr__(self):
        return "[%d->%d]" % (self.current_room.id, self.goto_room.id)

    def __eq__(self, other):
        if (self.goto_room.id == other.goto_room.id) and (self.current_room.id == other.current_room.id):
            return True
        return False
    
    def __hash__(self):
        return self.goto_room.id ^ self.current_room.id
    
class Map(object):
    def __init__(self):
        self.links = Links(self)
        self.rooms = Rooms(self)
    
    def loadMap(self, rooms_ary, links_ary):
        self.loadRooms(rooms_ary)
        self.loadLinks(links_ary)
        
    def loadLinks(self, links_ary):
        for i in links_ary:
            nlink = Link(self.rooms[i[0]])
            nlink.dest = self.rooms[i[1]]
            self.links[Link.last_id] = nlink

    def loadRooms(self, rooms_ary):
        count = 0
        for i in rooms_ary:
            self.rooms[count] = Room(i[0], i[1])
            count += 1

    def getShortestPath(self, from_room, to_room):
        from_room = self.rooms[from_room]
        to_room = self.rooms[to_room]
        # make sure that the rooms aren't immediate neighbors
        adj = self.links.isDirectLink(from_room, to_room)
        if adj: return [adj]
        
        # check  whether the from and to rooms are linked to anything,
        # absence of links to/from either means inability to find the path
        # TODO: raise a descriptive error if either room is not linked to anything
        if not self.links.hasFromLinks(from_room) and not self.links.hasToLinks(to_room):
            return None
        
        walked_rooms = set()
        current_gen = set([Walker(i.orig, i.dest, [i]) for i in self.links.getFromRoom(from_room)])
        next_gen = set()

        #gen_count = 0
        while True:
            # if all the walkers are dead then we failed to find the path
            #gen_count += 1
            #print current_gen, "\n"
            if len(current_gen) == 0:
                return None
            for wlk in current_gen:
                #print "  ", wlk.path
                for i in self.links.getFromRoom(wlk.goto_room):
                    if i.dest == to_room:
                        return wlk.path+[i]
                    walked_rooms.update(set([wlk.current_room, wlk.goto_room]))
                    # weed out the unfit - backward or loop walkers
                    if (i.dest == wlk.path[-1].orig) or (i in wlk.path) or (i.dest in walked_rooms):
                        continue
                    nw = Walker(i.orig, i.dest, wlk.path+[i])
                    next_gen.add(nw)
            current_gen = set(next_gen) 
            next_gen = set()

top

Posted by Ked Russia (524 posts) bio

Date Reply #3 on Thu 25 May 2006 09:43 AM (UTC)

Message

A test map for the script above:


all_rooms = []

for i in range(68):
    all_rooms.append((str(i), i))


all_links =((0,1),(1,0), (1,2), (2,1), (1,3), (3,1),
    (2,3), (3,2), (2,7), (7,2), (2,8), (8,2), (3,7), (7,3),
    (3,4), (4,3), (3,5), (5,3),(5,4), (4,5),(4,6), (6,4),
    (6,9), (9,6), (6,7), (7,6), (7,8), (8,7), (8,9), (9,8),
    (9,10), (10,9), (6,11), (11,6), (11,12), (12,11), (12,13), (13,12),
    (12,6), (6,12), (12,4), (4,12),(13,14), (14,13), (13,5), (5,13),
    (13,19), (19,13),(14,15), (15,14),(14,16), (16,14),(14,17), (17,14),
    (14,5), (5,14),(15,5), (5,15),(15,16), (16,15),(16,17), (17,16),
    (17,18), (18,17),(18,19), (19,18),(18,22), (22,18),(22,20), (20,22),
    (22,53), (53,22),(22,21), (21,22),(21,23), (23,21),(23,24), (24,23),
    (24,25), (25,24),(25,26), (26,25),(26,48), (48,26),(48,49), (49,48),
    (49,50), (50,49),(50,51), (51,50),(51,52), (52,51),(53,27), (27,53),
    (27,28), (28,28),(28,29), (29,28),(28,31), (31,28),(28,30), (30,28),
    (31,30), (30,31),(30,29), (29,30),(30,32), (32,30),(30,34), (34,30),
    (29,33), (33,29),(31,33), (33,31),(30,33), (33,30),(34,33), (33,34),
    (31,32), (32,31),(29,34), (34,29),(34,35), (35,34),(32,35), (35,32),
    (33,35), (35,33),(35,38), (38,35),(35,37), (37,35),(35,36), (36,35),
    (36,37), (37,36),(37,38), (38,37),(37,40), (40,37),(38,41), (41,38),
    (36,39), (39,36),(39,40), (40,39),(40,41), (41,40),(40,43), (43,40),
    (39,44), (44,39),(41,42), (42,41),(42,43), (43,42),(43,44), (44,43),
    (44,45), (45,44),(45,46), (46,45),(46,47), (47,46),(43,46), (46,43),
    (47,42), (42,47),(46,54), (54,46),(54,55), (55,54),(54,56), (56,54),
    (55,56), (56,55),(56,57), (57,56),(57,58), (58,57),(58,59), (59,58),
    (57,60), (60,57),(59,60), (60,59),(60,56), (56,60),(56,61), (61,56),
    (61,62), (62,61),(62,63), (63,62),(63,64), (64,63),(64,65), (65,64),
    (64,67), (67,64),(66,67), (67,66)
    )


map = Map()
map.loadMap(all_rooms, all_links)
from time import clock

print "========"
start = clock()
path = map.getShortestPath(0,66)
timing = clock() - start
print timing
print path
print "========"

Additionally using Psyco gives about a 40% improvement in speed. I find that psyco.proxy()'ing just the Map.getShortestPath() method (as opposed to psyco.full() on the whole script) yields the best result with Psyco.

top

Posted by

Heliomance (5 posts)

bio

Date

Reply #4 on Thu 06 Sep 2007 04:41 PM (UTC)

Message

If you're any good at understanding C, then one guy has written an incredibly awesome automapper in C for a different MUD called Imperian. You can find a link to his one at www.freewebs.com/heliomance, you might like to take it apart and have a look at how he did it.

top

Posted by

Shadowfyr USA (1,786 posts)

bio

Date

Reply #5 on Thu 06 Sep 2007 07:21 PM (UTC)

Message

Hmm. If we want a cross-platform database, why not one like MySQL? It uses TCP/IP to talk to it, in both systems. Mind you, there is a OBDC wrapper for it, but that just hides the TCP/IP under the hood. Any client that needs to be cross platform also needs to use a database that works in both places. Obviously, relying on ADO is therefor not going to work. Mind you, MySQL has limitations, not the least of which it not being an open source project. We might be able to find one that is, has a smaller profile, and works the same way, thus making it easier to use with the client. In fact, as nice as tables and stuff are in Lua, some people may want a more "stable" and transferable method of tracking some things, like a true database, so having one available for storing the map data would logically mean you also have one available for player databases. In any case, if we go the path of, "well, lets store it our way, not someone else's.", we invariably limit the usefulness of the mapper to anyone that might want to run its data through something else, as well as possibly the usefulness of any database structure we might be inclined to support for other data.

And, as I said before, while the "display" may need to be handled using a scripted plugin, its might not be practical to have the data storage handled that way, or even some of the general retrieval/storage. Some of that may need to be handled under the hood, just to keep things from hanging the client while busy trying to retrieve data or search paths, etc. Now, a "interface plugin", which **only** reacts to inbound data and some GUI elements, but *never* sends text to the main output, or commands "directly" to the mud, and which could thus run "parallel" to the main processes, might work. This would mean we could have functions that other plugins could call, exposed as part of the interfaces, which could retrieve the path, etc. when we need to use that. For that matter, there could even be events described in the system, like, "Search_Complete", which could then fire all "OnSearchComplete" functions in plugins requesting the data. Mind you, this would need to be a true event, not the ones we have now, which is to say, we want to tell the interface plugin, "We need you to inform function X in plugin Y of this event.", or "Stop informing me." That way, if you have two plugins with events sinks for searches, only the one "actively" watching for that event will see it. If you see my meaning. Otherwise, every plugin would have to check to make sure it was "supposed to" get an event, which would work, but is more complicated, and only works for that interface. If someone makes a new interface, you have the same problem over again, only worse, since someone else could have made a "OnGotBag" function *for their own script*, a new interface could add a "GotBag" event, and then the client would be calling "OnGotBag", when that was
never intended to receive such events in the plugin. Real event sinks/broadcasters are needed for this reason, so that the function name is the option of the "user" for those not explicitly built into the client (and thus static). Extended events need to be non-static, and use the event sink the plugins coder wants them to use, not a fixed name, which someone else might have already used some place else. If you see what I mean.

Mind you, another solution is to *restrict* the names, so that any function that begins with "OnPlugin" is **presumed** to be a client/extension event, thus making its use for anything else "illegal". This may even be better, since it means you can clearly see which event sinks connect to client/extension events. VB does much the same. Most languages do too, *if* you use the wizard libraries to build your application. But, in most cases this is the convention of the library used, and you could, on the most basic level, use any name you want. In scripts, like those running in IE, this is also the case. There is no "requirement" that the name start with, or look like, anything specific, you just make up a name, get the internal entry point reference, then tell the event source to start firing to the entry point. Allowing this may actually be a bad idea, from a readability standpoint, now that I think of it.

top

Posted by

Isthiriel (113 posts)

bio

Date

Reply #6 on Fri 07 Sep 2007 02:50 PM (UTC)

Message

Quote:
Shadowfyr wrote:
If we want a cross-platform database, why not one like MySQL?

The advantages of SQLite are:

Python's (and presumably Lua's) SQLite API is the actual database driver, not merely an interface to a separate program
Faster to develop for
SQLite can be converted to a MySQL database later very easily

MySQL is a better db in general, but you don't need to install SQLite, creating a new db is trivial and backing the db up is just as easy.

top

Posted by

Shadowfyr USA (1,786 posts)

bio

Date

Reply #7 on Sat 08 Sep 2007 03:59 AM (UTC)

Message

Ok, I can see that. As long as the database format is stable and compatible, it certainly makes sense to use one with a smaller foot print. In fact, I even said so, but that I thought it might be hard to find one. Guess I didn't look at your post close enough. :p

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.

28,684 views.

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

Go to topic: Search the forum

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.