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.
--
mvh Björn 6 1882
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.
Diez
BJörn Lindqvist wrote:
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.
--
mvh Björn
I'm working on a text adventure where if the player types in n, w, e or
s he/she gets something back like "You go north, then turn around, then
look left, right . . . finally you realize that you have no idea in
which direction North is." It makes mapping more tedious, but also
simplifies it and gives you more freedom.
Or you could do something like this.
>>rooms = [class instance, class instance, 0 (because there's no room here),
.. . . . . . . . . . .0, , class instance]
But that would still only get you the mapping and not the
implimentation, and it's untested by me because I chose not to do it.
And for my closing remark:
You know the game Zork? The people who made that game never made a grid
or anything. I'd bet that in the class, they had a variable for NW, N,
NE, E, SE, S, SW and W, and they probably even had a U and D for
defining what rooms would be in those directions..
On 2006-11-05, BJörn Lindqvist <bj*****@gmail.comwrote:
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
Check out the Ruby project IFMapper for a mature project that
might accomplish your goal. You can write a new back-end for it
to produce MUD code (so you can design your maps graphically), or
you can write a new front-end to interpret MUD code (so you can
make IF-Mapper draw maps for you game in progress). http://ifmapper.rubyforge.org/
--
Neil Cerutti
On 11/5/06, Diez B. Roggisch <de***@nospam.web.dewrote:
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
BJörn Lindqvist wrote:
On 11/5/06, Diez B. Roggisch <de***@nospam.web.dewrote:
>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
Diez B. Roggisch wrote:
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.
To convince yourself of this, here is a small problem
that does not flatten to any simple 2-D solution.
Consider :
A, B, C
a, b, c
A.south, B.South, C.south = a, b, c
a.north, b.north, c.north = A, B, C
A.east, B.east, C.east = a, b, c
a.west, b.west, c.west = A, B, C
a.east, b.east, c.east = A, B, C
A.west, B.west, C.west = a, b, c
--
--Scott David Daniels sc***********@acm.org This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Jeff Sandys |
last post by:
I'm trying to write a mapping function for genealogy.
I want to read a gedcom database and plot an icon at
a geographic location based on a user's query.
Can you help me find:
1) A python...
|
by: Stanimir Stamenkov |
last post by:
I have this kind of construct:
http://www.geocities.com/stanio/temp/usemap01.html
(an IMG element using MAP described with AREA elements)
I'm trying to make it more accessible and currently...
|
by: Old Monk |
last post by:
Hi all,
Say I have two maps m1 and m2. Both have key as std::string and value
as long.
m1 could hold entries like
"abc" 123
"def" 456
m2 could have entries like
|
by: Steven T. Hatton |
last post by:
Now that I have a better grasp of the scope and capabilities of the C++
Standard Library, I understand that products such as Qt actually provide
much of the same functionality through their own...
|
by: Sean |
last post by:
Have you ever wanted to add the great features inherent in Google Maps?
Here is how you do it.
==============
== STEP ONE ==
==============
Create a new MS Access form called frmGoogleMap....
|
by: Philadelphia XML User Group |
last post by:
NEXT MEETING: March 8th, 6:00 to 8:00 pm
A Definitive Introduction to Topic Maps
with Michel Biezunski and Roger Sperberg
To sign up, please visit http://www.xmlphilly.org/signup.asp
...
|
by: Sam Carleton |
last post by:
Ok, over the years I have read about doing web programing and I have
done some real basic stuff. Now I am digging into some real ASP.Net
2.0 and am totally lost some things.
I have a master...
|
by: rn5arn5a |
last post by:
I am not sure where I should have posted this question in this
newsgroup. Please excuse me if I am wrong.
Nowadays, a lot of websites have come with Maps (Google Maps being an
example). Can...
|
by: Phil Stanton |
last post by:
I have a button on a form which when pressed displays a google map of the
address.
Code is
Private Sub Googlemap_Click()
MakeURL ("")
End Sub
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
| |