BJörn Lindqvist wrote: > On 11/5/06, Diez B. Roggisch <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
