Data Structures & Grid-based MUDs

 
Post new topic   Reply to topic    mudlab.org Forum Index -> Coding
View previous topic :: View next topic  
Author Message
Blaidd



Joined: 08 Mar 2006
Posts: 7
Location: Arkansas

PostPosted: Mon Apr 03, 2006 2:13 pm    Post subject: Data Structures & Grid-based MUDs Reply with quote

Since my last post here, I've been giving a lot of thought to MUDs. I'm currently in the process of writing a single player demo to show my team what the MUD might look like and so I can get some suggestions on the interface before I get too far into the code. I'm using C++ for this and will probably end up using C++ for the actual MUD Server.

As part of the demo, I'm implementing a coordinate based system. It works great but the snag I'm running into is how to store the data efficiently.

The traditional "two-dimensional array" approach to map storage might work ok for a single player game with a lot of retangular maps, but if you store a discrete location in each cell you're right back to having arbitrary sized "rooms".

Plus, an array would be completely unsuitable for large distances with small increments (ie one foot squares) or dungeons that have more "blank space" than actual content. Can you imagine the waste from something like Diablo II's Arcane Sanctuary? (Which being isometric was quite likely stored in an array, but that's ok for single player games where only one area is loaded at a time).

One thing that's crossed my mind is you really don't need the whole map, just the coordinates of objects on it. That makes me wonder though how to figure out what objects are close to the viewer without going through a list of every object on the map and looking at its coordinates.

3D games generally store such relational information in trees. I'm thinking a simplified version of that is probably the way to go, but I'm just curious to see how other people have tackled this problem incase I'm overlooking something obvious.

The two issues here are:

How to know which hand-written description to display depending on the player's location on the grid. (That's fairly simple and should really only requires a single pair of coordinates)

How to know which objects on the map are near enough for the player to see and/or interact with them without having to cycle through every object in the zone to check it's coordinates.

A relational tree sounds pretty good, but what would be the root node? Can't use the player since there could be any number of players in the same zone. Hrm.

Blaidd
Back to top
View user's profile Send private message AIM Address MSN Messenger
Author Message
Kjartan



Joined: 13 May 2005
Posts: 110

PostPosted: Mon Apr 03, 2006 4:56 pm    Post subject: Reply with quote

How big a world are you talking about? It seems that it's not really necessary to have a life-sized world, because players won't be able to explore it all and you won't be able to generate decent content for it all either. If you can't even STORE the contents, you're never going to be able to build the contents in the first place.

But let's say you could: here are some solutions I have seen and/or tried.

1. tiles. Arena: the Elder Scrolls did this. You define some standard 10x10 or 50x50 or whatever terrain tiles, and the world map is an array storing tile ids. This means, in the case of A:ES, that when you walk cross-country you keep going through the same graveyard over and over. Kinda lame.

2. quadtrees, detail expanded as necessary, using a fractal-like function driven by pseudorandom numbers seeded from the coordinates. This is insanely complicated, but I like it. Some work I have done with those can be found at http://www.outgribe.com/jason/tep/index.html

As to the question you actually posed, which I paraphrase "How do I store a bunch of points in 2D space so that I can quickly answer a range listing query, 'which points are within radius R of X, Y'?" this is something that can be done in I think O(M (log N)^2) time where you have N total objects and M objects within range. The algorithm is a little complicated, so people other than the original poster feel free to stop reading now.

First, let's consider 1D: put the objects in a binary search tree (see wiki). Store also an Euler tour of the tree (see wiki). (Here you can't make a true Euler tour, I mean to make one that passes each edge once going each way). At each node in the tree store the offset of that node in the Euler tour. Now, say you want to return the objects in the range (a,b): just do the binary search algorithm on a, and do it on b, and you will get two pointers into the Euler tour - the set of objects you want is that range from the array.

EDIT: I oversimplified that - you need to store, in each node, the pointer to the first and last occurrence of each object in the Euler tour. Use the "last" pointer for a and the "first" pointer for b when extracting the range.

Next, let's extend this to a 2D rectangle: consider the tree from the 1D case; put all the objects in 2D space in such a tree based on their x coordinate, ignoring their y coordinate for now. At each node of that tree, think about the subtree, that is, that node and all of its descendents. Take the set of objects represented by those nodes, and stick it into a new binary-search-tree-plus-Euler-tour organized this time by y coordinate that hangs off of that node. This takes N log N total storage for N objects. Then do the search as in 1D, but for each highest-level-node-totally-inside-the-range-in-X, do the range search in Y on the associated Y tree referenced by that node.

You may be satisfied now; you can do rectangular searches, which may be good enough. If you really want to do circular searches you can do it, though, by adding a third dimension.

You can imagine how to extend it to a 3D rectangle. But why go to 3D, you ask, when my world is only 2D? You need to create a synthetic third dimension where a point at X, Y, has Z = X^2 + Y^2. Now let's consider that we want the contents of some circle of arbitrary radius about an arbitrary center: you can write that as A X + B Y + C ( X^2 + Y^2 ) < R. That's a half-plane in the extended space, thus you have reduced the circular search back to a rectangular search in one more dimension.

I am not a computational geometer, and so there may be errors in these algorithms, but I think I got the basic idea right. You can read more about it on the web. There may be faster algorithms.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Blaidd



Joined: 08 Mar 2006
Posts: 7
Location: Arkansas

PostPosted: Mon Apr 03, 2006 7:02 pm    Post subject: Reply with quote

Quote:
How big a world are you talking about? It seems that it's not really necessary to have a life-sized world, because players won't be able to explore it all and you won't be able to generate decent content for it all either. If you can't even STORE the contents, you're never going to be able to build the contents in the first place.


I'm not talking about storing the whole world in one array. I'm talking about standard "zones" which are interconnected on the edges (or at specific points, ie a doorway). It's not a matter of not being able to store the contents, it's just a matter of efficiency because at this point there is no way of knowing how many zones may need to be in memory at once. On a large game, you'll eventually run into the problem of having more areas than you can keep in memory.

My point was that arrays strike me as being terribly inefficient because not all zones are nice squares. Twisty dungeons may have as many "blank" cells as they have actual content. Even if you use NULL pointers to represent "blank" space, you're still devoting quite a bit of memory to saying "There's nothing here."

All I really want to do is overlay a grid on top of a zone so that distance is measurable between rooms (for ranged combat and line of sight checks). My first thought for doing that was to get rid of the idea of arbitrary "rooms" entirely and just using a grid. That may not be the best idea.

I'll have to do a lot of reading before I can respond to the rest of the post, but that seems to be similar to what I was thinking.
Back to top
View user's profile Send private message AIM Address MSN Messenger
Author Message
Kjartan



Joined: 13 May 2005
Posts: 110

PostPosted: Mon Apr 03, 2006 7:13 pm    Post subject: Reply with quote

Scratch all that stuff about the Euler tour and replace it with "ordered list". Whoops.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Kjartan



Joined: 13 May 2005
Posts: 110

PostPosted: Mon Apr 03, 2006 7:21 pm    Post subject: Reply with quote

Quote:
I'm not talking about storing the whole world in one array. I'm talking about standard "zones" which are interconnected on the edges (or at specific points, ie a doorway). It's not a matter of not being able to store the contents, it's just a matter of efficiency because at this point there is no way of knowing how many zones may need to be in memory at once. On a large game, you'll eventually run into the problem of having more areas than you can keep in memory.


I think storing them in arrays is probably actually ok. Say that you have 10 bytes per square (probably you'll actually have far less) and each zone is 100 x 100 squares, which is several x several screens across (at least in a standard-sized telnet window). That's 100k per zone. Now say you have 1000 such zones; that's 100 Mb which is still no big deal. Even 1 Gb is bearable these days, and it will probably be a very long time before you have 1000 zones.

Quote:
My point was that arrays strike me as being terribly inefficient because not all zones are nice squares. Twisty dungeons may have as many "blank" cells as they have actual content. Even if you use NULL pointers to represent "blank" space, you're still devoting quite a bit of memory to saying "There's nothing here."


I would say (1) don't worry about it until it becomes a problem and (2) if you find you're running out of memory, store each row with run-length encoding. Although SSI had an interesting solution to this in Pool of Radiance and sequels: they used teleports to cheat, so if you were running down a really long corridor, every 20 squares or so you'd pass through an archway that mapwise teleported you back 20 squares left and one square up, so the corridor was actually stacked.

As far as whether you should have rooms or grids, I don't think you'll find a definitive answer to that one. There are many threads about it here and on TMC as well.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Nornagest



Joined: 08 Jan 2006
Posts: 12
Location: California

PostPosted: Tue Apr 04, 2006 1:49 am    Post subject: Reply with quote

Blaidd wrote:
All I really want to do is overlay a grid on top of a zone so that distance is measurable between rooms (for ranged combat and line of sight checks).


I might be misinterpreting your wishes, but, leaving aside both the rooms-vs-grids debate and which you should choose, this doesn't seem especially difficult in a traditional room-based MUD.

My MUD manages similar things by referring to a map server that also clones most of the rooms involved, but that involves writing a lot of extra code. If you don't want to deal with a map server, or already have a map server of an unsuitable design, you have other options; you can, for example, assume all your rooms are equidistant and just figure out offsets with some sort of short-distance search, or attach the distance between rooms to your exits and use some slightly more complicated math. It's just geometry either way, though.

If you want line-of-sight that doesn't just propagate along direct paths, without manually inserting lists of visible rooms, it gets a bit more difficult. Offhand, I think you'd need to figure out which sides of which rooms are transparent, then filter the list of rooms in the zone according to some relational criterion as discussed above. This would probably require maintaining coordinates for each room, though these could be calculated in any number of ways.
Back to top
View user's profile Send private message
Author Message
Kelson



Joined: 18 May 2005
Posts: 71
Location: SC

PostPosted: Thu Apr 06, 2006 2:05 am    Post subject: Reply with quote

Have you considered using a fully 3D world with the player-level abstractions of grids existing as finite-sized volumes (for example, 10x10 floor and 20' height)? What I mean is that your whole world is set up using 3D coordinates, but the player experiences it as though it were a grid (in terms of movement, descriptions provided, and targetting). The one issue that comes up in that case is movement within a 'room' (I've seen some nasty interfaces for in-room locations...and some cool ones, AweMUD's relational location model is a favorite - as long as the location is linked to a coordinate, solving player positions should be relatively easy).

Nornagest is talking from the other side of the debate - fully room-based system that simulates full 3D-ness. Either way could work, though I'd suggest the more detailed (3D) model be the foundation for the abstract (room) model.
Back to top
View user's profile Send private message Send e-mail AIM Address
Author Message
Lindahl



Joined: 29 May 2005
Posts: 56

PostPosted: Thu Apr 06, 2006 3:00 pm    Post subject: Reply with quote

Keep in mind that directional (n,e,s,w - grids) systems are also cumbersome for players, not just for storage and building. A region-based system with target-based movement is much more suitable to all three. However, it's more difficult to implement.
Back to top
View user's profile Send private message
Author Message
Kelson



Joined: 18 May 2005
Posts: 71
Location: SC

PostPosted: Thu Apr 06, 2006 10:19 pm    Post subject: Reply with quote

Lindahl wrote:
Keep in mind that directional (n,e,s,w - grids) systems are also cumbersome for players, not just for storage and building. A region-based system with target-based movement is much more suitable to all three. However, it's more difficult to implement.


What about the nesw system is cumbersome for players? It is predictable, easy-to-understand, and flexible; demonstrated by its extensive use throughout the mudding community. I'd also argue a nesw system doesn't rely on a grid at all - perhaps it is simply a linking system where a large number of exits are (for ease of navigation) named nesw.

And, when put as a linking system between abstract rooms, the room-based system is no different from the region-based system with 'target-based movement' except in semantics and "region/room" size. Toe-may-toe, too-mat-o
Back to top
View user's profile Send private message Send e-mail AIM Address
Author Message
kelson76



Joined: 27 Jun 2005
Posts: 30

PostPosted: Fri Apr 07, 2006 3:31 am    Post subject: Reply with quote

Lindahl wrote:
Keep in mind that directional (n,e,s,w - grids) systems are also cumbersome for players, not just for storage and building. A region-based system with target-based movement is much more suitable to all three. However, it's more difficult to implement.


I have to agree with Kelson on this. I don't find the n/e/s/w to be cumbersome at all.

I think of a room as an interaction context, with the n/e/s/w providing an easily distinguishable form to the landscape, and path to other interaction contexts.

I personally do not like target-based movement. It makes more sense obviously in a graphical mud, but in a text based mud, I think the n/e/s/w system is cleaner conceptually for a player.

- Kelson76
Back to top
View user's profile Send private message AIM Address
Author Message
Lindahl



Joined: 29 May 2005
Posts: 56

PostPosted: Fri Apr 28, 2006 3:28 pm    Post subject: Reply with quote

It's cumbersome because it requires the user to half-remember a sequence of nesw to move themselves through a multi-room region. It's much simpler to follow a windy path by typing 'follow path', or something to that effect - and this is just one simple example of it's usefulness (there are plenty more). It's much more natural to type 'enter kitchen' than it is to figure out which nesw is the kitchen from outside the inn, as well as from within the inn. And how many times have you had to type 'e' three times to get to the end of a hallway, the whole time, not being able to see whats at the end of it - just because the builder wanted to add a sense of length? There is a lot left to be desired from such systems.
Back to top
View user's profile Send private message
Author Message
KaVir



Joined: 11 May 2005
Posts: 565
Location: Munich

PostPosted: Fri Apr 28, 2006 6:15 pm    Post subject: Reply with quote

I agree with you to a point - but it can be equally cumbersome for the user to try and remember the sequence of landmarks needed to move across the landscape.

There's no need for the two systems to be mutually exclusive though - you can let players mix and match between the two. Real life explorers will certainly use landmarks to navigate, but they wouldn't get far without a compass as well.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Vopisk



Joined: 22 Aug 2005
Posts: 99
Location: Golden Valley, Arizona, USA

PostPosted: Sat Apr 29, 2006 4:53 pm    Post subject: Reply with quote

I have to agree with KaVir here.

I used to play on a game which used a diku-style system for its buildings, but a coordinate system for the game-world at large, so as you travelled the outside, you would see buildings and could ENTER them, from there you would use n,s,e,w to navigate through the building. You would also use the cardinals to navigate the world, but if you were going a long way you would just WALK, RUN or RIDE w to keep moving to the west until you wanted to stop.

I suppose that if you are using a coordinate grid system, you could assign a specific "terrain type" to each coordinate in order to create things such as paths which could be followed logically until they arrive at a fork, and giving some rooms "hotkey" names such as kitchen, living room, et al can make navigation easier, but what about that hallway? What if it is long and I can only see six doors lining it, three on either side, I may know that there must be a master bedroom somewhere down there, but how does my character if all of the doors are closed?

This is probably bad mud design (having six doors exiting from a single hallway) because as suggested, I should be able to see all the way to the end of the hallway and it would become rather cumbersome to have to look through six doors to try and find which way I want to go. Then again, it's also a pain to have to glance n, e, s, w, sw, nw, ne, se in order to figure out which way I want to go too.

Perhaps it really describes the true difficulty of creating a system that is fun to explore before you know exactly where you are going. I suppose you could always LOOK THROUGH FIRST DOOR and the like, moving your character progressively or regressively further as she approaches each individual door. However, having played with the idea of "facing <directions>" and moving forward and backward and turning left left me with the only conclusion being hopelessly being lost for the majority of players, as it's easy enough to discern your relative direction in the real world, but when you're getting the information as text and generally being inundated by the flood, only breezing through, you'd most likely soon end up walking in large circles.

I think the north, south, east and west cardinal direction interface allows players to easily navigate just like they would if reading a map, north is up, etc... It doesn't necessarily mean that they want to move cardinally north, merely up, to something that they know lies in that direction, you could as easily use up, down, left and right to navigate the world, but MUDders are familiar with n,s,e,w so why change the old and familiar feel just for the sake of doing something different and increasing the learning curve?

Edit: On the subject of landmarks as navigational aids, I like the idea, if I can see a city, or mountain or totem pole on the horizon, I would (in the real world sense) walk towards it if I knew that's where I wanted to go, so something akin to WALK TOWARDS TOTEM POLE would probably make things easier for navigation without having to redundantly type n,s,e,w constantly, however, outside of visible landmarks, I don't really like the idea of WALK TOWARDS <CITY ON OTHER SIDE OF THE GLOBE>. Following roads and paths may get you there, but you still need a system in place to handle if the character happens to be a woodsman or ranger type and wants to get from point A to point B by going straight through the wilderness and seeing what sort of trouble they can get themselves in.
Back to top
View user's profile Send private message AIM Address MSN Messenger
Author Message
shasarak



Joined: 29 Jun 2005
Posts: 134
Location: Emily's Shop

PostPosted: Tue May 02, 2006 10:46 am    Post subject: Reply with quote

I prefer a "landmark" system myself ("enter house", "walk towards hill", etc.) But such a system wouldn't eliminate compass directions as concepts, it would simply eliminate the idea that there is only one possible distance once can travel in any one direction, and that this happens instantaneously.

The key, I think, is to understand that beginning to move and stopping may be two separate actions, and that a certain amount of real time will pass in between them. During that time the character is moving continuoously through the game world.

If you want to travel along a road, that's easy: type "follow road" and you begin moving. When you reach a fork, type "fork left", etc. But you might well want to stop half way along the road. So, rather than complete the move with a single typed action, you type "follow road", and your character begins to move. Wait till you reach the necessary landmark (a milestone, say). When you reach it you type "stop", or "walk to milestone" - the latter overriding your previous instruction. If you don't type anything else, you keep on moving along the road till the road ends.

In the middle of the countryside you could move in compass directions in the same way as moving along the road. If you want to approach a specific object or landmark that is in sight, then "walk to hill", "walk to oak tree", etc. If the place you're going is out of sight then you "walk north" - and your character continues to walk northward until the place you're going comes into view, at which point you can direct motion more precisely ("walk towards village").

This allows all sorts of interesting developments. For example, you can model how fast someone is moving by how much real time it takes them to get to places. A character on horseback would therefore be genuinely able to outrun a character on foot, regardless of typing speed. Or you could model different fatigue rates for a character who is running rather than walking.

This system also allows a really neat way for players to get lost. "Walk north" is interpreted not as "walk north" but as "walk in the direction that I think is north". How close that direction is to actually being north will depend on things like the character's wilderness survival skills, whether they have a compass, and what the terrain is like: it's much easier to walk the wrong way in a desert or deep forest than in fields with hedgerows. So you can model the player travelling in roughly the right direction, but still not ending up quite where they thought they'd be.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    mudlab.org Forum Index -> Coding All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2002 phpBB Group
BBTech Template by © 2003-04 MDesign