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?
----------------------- 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
--
http://mail.python.org/mailman/listinfo/python-list
