Projecting MUD maps

[Diez B. Roggisch]

BJörn Lindqvist wrote:

> 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?

It depends - it is complicated and very sophisticated and generally
considered a hard, even unsolvable problem. However, a good general
solution is written in the graphviz toolkit. Which is the reason I
suggested it.

But there is no cookbook-algorithm that will produce perfect MUD-maps. For
such a beast, you have to cough up one on your own, with things like
constraint solvers and the like. Certainly over _my_ head, at least without
deep studies of planar graph representation problems.

Diez