Projecting MUD maps

[BJörn Lindqvist]

On 11/5/06, Diez B. Roggisch <deets at nospam.web.de> wrote:
> BJörn Lindqvist schrieb:
> > Hello, I'm looking for an algorithm to project "MUD maps" such as the
> > following map: http://www.aww-mud.org/maps/MUD_Maps/Caerin-colour.jpg
> >
> > MUD:s consists of rooms, each rooms has up to four orthogonal edges
> > (north, east, west and south) that connects it to another room. So it
> > is very easy to model a MUD as a directed graph. But projecting the
> > graph on a surface is very complicated. For example, Room A:s North
> > edge may connect it to Room B. But Room B:s South edge may connect it
> > to Room C. Or another tricky example: Room A:s East edge connects it
> > to Room B, whose East edge connect it to Room C, whose North edge
> > connects it to Room D, whose West edge connects it to Room E, whose
> > South edge connects it to Room A. In that example, there would be a
> > "hole" between Room D and E.
>
>
> try graphviz. You can also annotate some compass information ther, I
> guess it should make for a better placement.

Sorry, I think everyone misunderstood what my problem is. Which is not
very strange since I see now that I didn't explain it very well.

In the code below, I have created a simple Room class. It has up to
four edges; north, east, west and south. The Room class also has the
method get_projection() which recursively traverses through all
reachable rooms in the graphs and gives them x,y coordinates and
returns a dict containing x,y-coordinates and rooms. The function
project_dict() simply plots the dict on stdout.

The main() function demonstrates how a map consisting of nine rooms
should be plotted. All well so far. But if there had been an east-west
edge from G to I, then that edge would have overlapped C:s position.
That would have been wrong and I want the algorithm in
get_projection() to detect such overlaps and automatically fix them.
In this case, the fix would have been to add 2 to G and I:s
y-coordinate. Then the east-west edge from G to I wouldn't overlap any
room.

So I wonder if there is any algorithm that can do what I'm asking for?

----------------------- mudgraph.py -----------------------
# -*- coding: utf-8 -*-
import sys

class Dir:
    dirs = ['n', 'e', 's', 'w']
    @classmethod
    def opposite(cls, dir):
        """
        Return the opposite direction, i.e Dir.opposite('n') => 's'.
        """
        opp_idx = (Dir.dirs.index(dir) + 2) % 4
        return Dir.dirs[opp_idx]

class Room:
    """
    A Room is a node in a mud map. Each room can have up to four
    connections (edges) to other rooms in the cardinal directions;
    north, east, south and west.
    """
    def __init__(self, name = None):
        self.name = name or "+"
        self.n = None
        self.s = None
        self.e = None
        self.w = None

    def connect(self, dir, room):
        """
        Create an edge dir from self to room. Also create an edge in
        the opposite direction from room to self.
        """
        setattr(self, dir, room)
        setattr(room, Dir.opposite(dir), self)

    def north(self, room):
        self.connect('n', room)

    def east(self, room):
        self.connect('e', room)

    def west(self, room):
        self.connect('w', room)

    def south(self, room):
        self.connect('s', room)

    def get_projection(self, x = 0, y = 0,
                       proj_dict = None,
                       visited = None):
        """
        Return a dictionary containing all Rooms in the map as
        values. Each key is the projected x and y position of the
        room.
        """
        if proj_dict is None:
            proj_dict = {}
        if visited is None:
            visited = set()
        visited.add(self)
        proj_dict[x, y] = self
        if self.n and not self.n in visited:
            self.n.get_projection(x, y - 1, proj_dict, visited)
        if self.e and not self.e in visited:
            self.e.get_projection(x + 1, y, proj_dict, visited)
        if self.w and not self.w in visited:
            self.w.get_projection(x - 1, y, proj_dict, visited)
        if self.s and not self.s in visited:
            self.s.get_projection(x, y + 1, proj_dict, visited)
        return proj_dict

def project_dict(dict):
    coords = dict.keys()

    max_x = 0
    max_y = 0
    min_x = 999
    min_y = 999
    for x, y in coords:
        if x > max_x:
            max_x = x
        elif x < min_x:
            min_x = x
        if y > max_y:
            max_y = y
        elif y < min_y:
            min_y = y

    max_x += 1
    max_y += 1
    for y in range(min_y, max_y):
        x_range = range(min_x, max_x)
        for x in x_range:
            if dict.has_key((x, y)) and dict[x, y].n:
                sys.stdout.write(" | ")
            else:
                sys.stdout.write("   ")
        sys.stdout.write("\n")
        for x in x_range:
            if dict.has_key((x, y)):
                room = dict[x, y]
                if room.w:
                    sys.stdout.write("-")
                else:
                    sys.stdout.write(" ")
                sys.stdout.write(room.name)
                if room.e:
                    sys.stdout.write("-")
                else:
                    sys.stdout.write(" ")
            else:
                sys.stdout.write("   ")
        sys.stdout.write("\n")
        for x in x_range:
            if dict.has_key((x, y)) and dict[x, y].s:
                sys.stdout.write(" | ")
            else:
                sys.stdout.write("   ")
        sys.stdout.write("\n")

def main():
    a = Room('A')
    b = Room('B')
    c = Room('C')
    d = Room('D')
    e = Room('E')
    f = Room('F')
    g = Room('G')
    h = Room('H')
    i = Room('I')

    a.east(b)
    b.south(c)
    b.east(h)
    c.south(d)
    a.north(e)
    a.west(f)
    f.south(g)
    i.north(h)


    dict = a.get_projection()

    project_dict(dict)

if __name__ == "__main__":
    main()


-- 
mvh Björn