# Re: Projecting MUD maps

On 11/5/06, Diez B. Roggisch <deets@xxxxxxxxxxxxx> 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()
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
.

## Relevant Pages

• [QUIZ][SOLUTION] Re: Sokoban (#5)
... I know that the Sokoban quiz was posted a long time ago. ... # GAME is the name given to a saved game. ... # Given a level's map, return the position of the token representing ... def Sokoban.find ...
(comp.lang.ruby)
• Re: A dungeon generator
... rooms will not fit in the map, so your algorithm will fail. ... each level has 16 possible starting templates. ...
(rec.games.roguelike.development)
• Re: one sentence proof of 4 Color Mapping Problem; direct method
... for you to determine whether you can color this map with THREE ... So an algorithm for this machine would look ... building the algorithm in P to solve the NP-complete problems, ... Perhaps the equivalency is the idea that Eucl geom is what is ...
(sci.math)
• Re: A dungeon generator
... then it automatically turns in the former kind of algorithm. ... If it fails to generate a map ... rooms, then after a hundred more fails, five rooms, etc. ... each level has 16 possible starting templates. ...
(rec.games.roguelike.development)
• Re: A* (#98)
... It produces this path on the large map: ... In response to Martin about the quiz being "spoiled" - I don't come ... def initialize ... raise "Either position or goal tile are not set" ...
(comp.lang.ruby)