In my little Java world, something like this (the wilderness problem, not the telnet thing or object discarding) would be best solved by using a pattern called the "flyweight" pattern. This would be where you re-use an object with certain properties over and over in place of creating new ones. An example would be reusing one instance of a circle object to draw different sized circles with different x,y coords on a 2D plane instead of creating a lots of different circle objects.

I would approach the room problem by working out how best to group my rooms in the wilderness (so which rooms I would want to reuse and how) and, when a player enters the co-ordinate, create a room with those attributes and store it in a hash map. When I needed a room with the same properties again, I would get the same room object out of the hashmap and reuse it.

If this were me, I would group (hash) each room by terrain type and exit types (eg, ROCKY_TERRAIN type and has exits n, s and e). My exit object would, by default, link to the x,y coordinate relative to the players current co-ordinate in the grid (e.g n: x + 0 y + 1, s: x - 0 y - 1, e: x + 1 y + 0, w x - 1 y + 0). You could even add a z coord by using up and down to do z +/- 1 respectively.

I would then keep a separate inventory for each co-ordinate location (but only when required) - possibly storing those in a hashmap that keys a co-ordinate hash to the inventory, but maybe in an array depending on performance factors.

The map can be pre-determined and stored by any means. I could create a loader to load the wilderness from a database or a text file, or whatever. All I need to know is what room properties I need to group by, so I can create a set of unique room types.

I hope this is helpful to someone, and if you want me to explain further just ask.

[edit to clarify my context]

Why even save the room at all? It's simply a container, and is only needed while something is inside it.

This is the full approach I used in my old mud:

The basic world was created from an array of 512x512 8bit integers, each containing a tile ID. Each of the 256 tiles provided the terrain types for 10x10 rooms, and each terrain type had its own rules for height. Thus I was able to represent a world 5120x5120x40 = 1048576000 rooms using 256K of RAM. The default world was then put together with tiles rather like a jigsaw puzzle, using admin tools to ensure that each tile matched its neighbouring tiles (so that rivers didn't suddenly flow back on themselves, oceans didn't exist alongside lakes, etc).

Of course I also wanted staff and players to be able to modify individual rooms, so I then added a 512x512 array of pointers to lists of tiles (ordered by height, with the array pointing to the last requested height), initialised from the tile IDs. This added an additional 1MB overhead for the array, and further overhead for the additional tiles (which were stored in a move-to-front heuristic list, with the least used element flushed to disk when the list grew too long), but it allowed individual rooms to be customised. These could be mapped over 'traditional' room vnums, and have other modifications made (such as walls and doors). This approach was also used for digging holes and mines, chopping down or burning forests, etc.

The physical Diku/Merc-style room structures were then simply generated and reused as needed, so that while wandering around you would usually leave and re-enter the same physical room, which would have its attributes modified each time you moved. This worked fine apart from the object persistence issue I mentioned previously, which I never resolved in the end (I lost interest in the project over time, and eventually gave up on it about 8 years ago).

Because (specifically) in Java object creation is relatively expensive compared to object instance re-use, and I'm guessing in C++ allocating a lump of memory for an object over and over can take a (relatively) long time too.



Great solution, however I get the feeling that programmatically it would involve many implied conventions about what the arrays actually store, and how the arrays are indexed and may rely on knowing implicitly what each integer means. Maintenance nightmare!! I'm sure the admin tool helped immensely when creating the virtual area so not many creators even had to look at the source. But I bet if I looked at your source code I would have a hell of a time trying to work out what it was going on about (probably). But I'm not here to criticise any implementation I haven't even seen.

The pattern I talked about is a well accepted industry tool for helping you think about object instance reuse, and was for OO programmers rather than specifically talking about any type of solution. I have never had to actually solve this problem yet, but I was trying to express how I would go about solving it.

Additionally, apart from the pattern, if you stop thinking as rooms as containers and start thinking of them as locations, the whole object inventory thing can be managed separately from rooms and goes away entirely. If your room is always implicitly a container and your mud doesnt allow you to override that and insists objects MUST be in a room, then I guess you are going to be a little stuffed for a good solution…


[Edit]

Re-reading your solution has definitely given me some great insights in to the problem and a feeling I may have been over-simplifying the solution (in my head). Although I dont think the actual flyweight pattern is wrong, certainly my ideas about hashing are being expanded to include some kind of tile system… intreaguing ideas KaVir :)

[Edit again - mistalking a lot]

You'd likely find with testing that for your purposes the benefits far outweigh any potential thrashing on modern architecture. Someone correct me if I'm wrong.

edit:

Otherwise there'd be a strong argument against much instantiation off of the stack. It would make libraries like boost::pool in C++ much more popular than it already is.

And cause memory fragmentation, but I'm not suggesting literally 'free'ing the rooms each time - in fact my solution never freed the memory allocated for rooms. When you left a room it would remain in memory, and when you entered a new room the mud would first look for an empty room to reuse, only allocating memory for a new one if there were no empty rooms available. The room then had some quick adjustments made to it (such as terrain type), and it was ready to reuse.

This meant that in the majority of cases, walking around would simply move you out of room X, make some quick adjustments to room X, then move you back into room X (i.e., exactly the same memory-allocated room). Technically it could have skipped the whole moving out/in and just left you in the room, but as my solution was hacked into the Diku/Merc code it proved much easier to handle in this way.


Well the array elements were of specific data types, and there was a selection of functions serving as an interface for manipulating the data. I'm not sure why you feel that that would make it inherently worse than any other solution for that particular programming problem, but I'm sure there are other approaches.


Sure, but you pick the right tool for the job - not every problem is a nail. I needed a huge virtual world, and it was neither desirable nor feasible to store every single room.

As an aside, I've reused the tile concept for my current mud as well, although (because my new mud is roomless) the tiles don't represents 10x10 rooms, but 10x10 patches of terrain. Unlike my previous mud, individual tiles can't be customised, although I may add such functionality in the future.

Please read this:

http://www.javaworld.com/javaworld/jw-07...


Even so it's certainly a memory efficient way to do it and I don't have to jump through too many hoops to achieve it. If I want 5000 rooms and have 256 tiles, I only have to represent the 5000 rooms with < 256 real objects. Heck even 1,000,000,000 rooms can still be represented by those < 256 unique objects (depending how i group em). All those rooms can 'exist' at once, and I even dont have to worry about the contents (because it will be maintained separately).

[EDIT]

Actually, looking at past the numbers at what KaVir was actually describing, it could be interpretted as a kind of flyweight. He just seems to of had a bit of an obsession with keeping the room usage down to one room for whatever reason. If, perhaps, he had added rooms (in which items were dropped) into a list and substituted that room for his virtual room when players or mobs returned back to those coords, he could perhaps have solved his problem…

I'm just saying that aside from near constant instantiation and destruction it won't bring your mud to its knees. On most muds it would all still happen between pulses. And if the decision is expending a lot of ram instead of the slower alternative then I disagree with that design decision. (slow being a subjective term, I've been using Ruby and Python for a while for muds.)

As I mentioned previously, my rooms were simply containers - that was their one and only purpose. If you're maintaining their content elsewhere then we could scrap the concept of rooms (from a memory allocation perspective) entirely.

So…I've got over a billion separate locations in the world, each of which contains 0 or more objects. How and where would you store them?

I'm guessing not as a billion allocated empty containers. :P

haha no. And neither was I suggesting that you would ;D The obvious answer is you would not store a billion rooms, only < 256 template rooms with swappable contents.

I had supposed that you had descriptive data and had different methods to call stored (for actions that might be performed) for each room? I was assuming, probably incorrectly, that your "room object" would do this sort of thing for you along side your inventory. Not having seen your implementation, as I said, it is very hard to comment on what you did.

However, only creating one room for each existing player (even if it is just an inventory slot) seems a bit minimalist for my taste. I'm not saying its wrong but it obviously has its flaws, whereas storing a little more than just one room that a player exists in these days probably wouldn't break the bank either. For example, keeping a track of all the different rooms that the user has dropped things in probably wouldnt use much more memory than your system can cope with? I mean, with object decay, how many of those 1 billion locations are actually going to be accessed and have things dropped in them over an objects lifetime? 10% ? less than that?

(As I said before, your solution does sound very very good btw, and as I mentioned I'm thinking about how my own version would work so its all food for thought)

The way I set up my wilderness, rooms containing items in them remain in memory when the player leaves, with a check to hash the room whenever the last item in it decays. I'm not concerned about memory fragmentation (which I think is mostly an issue with linked lists) since I'm using a 1 dimensional array for the grid. The advantage of a 1 dimensional array is that I can use index 1 to 100.000 for normal area stuff, and 100.001 to 4.099.999 for a 2000x2000 map, with some routines to translate coordinates to vnums.

Remember the context we're talking about here, namely a ROM/RaM/Diku environment. Because the coding of these systems is very complex and intertwined, the solution that has the smallest impact and allows the most re-use of existing solutions is probably the best, even if it's not technically as "perfect" as it could be.

Since DikuMUD is designed around the idea of rooms as containers, and many of the combat, communication, and inventory systems assume that things in the same room are adjacent, and things in different rooms are not, I suspect you'll get the most mileage from something that places people in their own rooms if they're at different grid coordinates, and moves them into the same room when those coordinates overlap.

How you handle reusing/reallocating the rooms matters, but not as much as you might think unless you have thousands of NPC's wandering around your wilderness system (or, I suppose, hundreds of players running around like maniacs). What you do with dropped items is a question, but you can either keep them in a list with coordinates so you can populate as needed, or just assume things that get dropped go away when you take your eyes off them.

One thing that might be useful is an efficient way to map coordinates to rooms. Pathfinding algorithms in most Diku's tend to walk the path of exits (BFS, DFS, A*, however) to find out how close or far away something is, and to handle pursuit/tracking/etc. In a wilderness where rooms get reused and only the coordinates change, this system will need to be modified to understand coordinates as well as room connections.

If ALL your rooms ended up with coordinates, it would be simpler, but this isn't likely to be the case unless your world is euclidean, and most are not. So, the question is… if a mob is tracking you from a real-world non-wilderness vnum'd room, and you're also in a non-wilderness room, but you walked across 12 steps of wilderness to get there, how can we determine the distance?

I expect thats where polymorphism would help to some degree, where you would "fake" the objects "distance" from another by providing overridden methods to give correct "real" data one players distance from another, no matter what co-ordinate system was in use.

I must admit to being entirely clueless when it comes to specific mud bases. I only speak from personal programming experience.

lol i guess this isn't what a vnum is…

http://en.wikipedia.org/wiki/VNUM


error id10t.. search bar selection failure

But that doesn't help with the container issue - if I'm fighting a goblin in a 'dense forest' room, and he disarms me, I don't want to run west into the next 'dense forest' room only to see that same goblin (and my sword lying on the ground).


No, that was generated - everything I stored was initialised from 32 bits of data taken from the tile. And, of course, the contents of the room (mobiles and objects).


Probably not (although it could increase your hosting costs, which might concern some people). I developed this solution around 12 years ago though, sharing a server with several other muds, on a machine that was considered pretty substandard even back then. I had to 'nice' my compilations, because they took nearly an hour, and would impact everyone else on the server.


Well that would still be a problem even today, for the reasons I outlined previously - many items simply never vanished. My goal was to create a truly persistant world. However the clutter was really due to a design flaw, and would need to be addressed there rather than in the implementation.





Most muds with a separate wilderness system patch area entrances over specific x/y locations, so that entering the area moves you to a traditional area. That's the approach I used for my first wilderness system, and it's a pretty reasonable approach if you want to keep all of your old areas without too much work.

My second wilderness approach (which is the one I'm describing here) allowed individual rooms to be patched over specific x/y locations. You could use old-style areas still, but you had to patch them over one room at a time (which obviously meant that some areas required padding, as 'north, east, south, west' would always take you back to your starting point). This approach also scrapped exists, so that old-style areas were no longer possible, and an interesting side-effect was that if you patched the same room over multiple coordinates, people on different sides of the world could meet up (although it wasn't actual teleporting, because they'd still retain their coordinates).

No of course, but why would you get that from what I was saying? I suppose if your room was purely a container and nothing else then I guess so, but I wasn't really suggesting that at all. It only works if your "room" is not just a "container" and you can maintain a list of contents separate from the fact that the object is a "dense forest".



Very very cool btw. Would never have thought of that. Ahh the constraints of memory size and how it makes you think :D I almost forgot those days.

[edit] as i mentioned before, i think we are grabbing a different end of the same stick, you were probably using the flyweight pattern even if you didn't know it at the time!

Because the question I asked (which you were replying to) was "So…I've got over a billion separate locations in the world, each of which contains 0 or more objects. How and where would you store them?"


Okay, but how and where do you store this list of contents?

Your templates use shared data so that you can represent the entire world with a maximum of 256 allocated rooms - I understand that, it's a nice approach, and is conceptually similar to the way I created the default world layout. But while your solution is certainly elegant, it's not actually addressing the problem (rooms generated on the fly also work perfectly fine).

The problem is maintaining, storing and retrieving the contents of a room, particularly in regard to persistant objects which may potentially have a very long lifespan. Your solution doesn't address that problem, instead it shifts the responsibility to some "separate" list of contents. It's that list that I'm interested in, rather than the management of the rooms (which in my case, at least, were simply containers).

I'm not seeing a real issue with maintaining your lists in memory assuming the list is actually unique and not empty. Using ram is the price of maintaining that much data. Another solution might be databasing these lists and caching access to them. This obviously presents its own set of difficulties to overcome.

vnum is short for virtual number.

And here I was thinking it stood for Volcano Number. :)