Member Discussions

I'd like to make my world 5000 rooms wide and tall (we're talking 25 million rooms). Only a few areas are zones, but every room has to be represented in some way and obviously they can't (or, at least, I don't consider it an option for them) all be held in memory at the same time.

I've had a few thoughts on how this could be done.

1) Define a 50x50 matrix of area (one area = 100x100 rooms) pointers. All non-wilderness areas are 'permanently' stored in this matrix, but wilderness areas are generated for the matrix as needed (for instance, some player comes within 10 rooms of where the area would begin) and unloaded when free. This method allows generation based off a bitmap image or radial distance from other areas with given environmental affects(each area could have some given weather pattern that influences the algorithm and the orc nest might kill all the trees around them for a distance of a mile or two).

Pros: 'efficient' allocation
Cons: With lots of players, every zone might be loaded
Room states, mobiles, etc stays for as long as a zone is loaded

2) Generate a map for each player with an algorithm that produces the same output for a given room all the time. This is preferable, even though it eats up cycles, because the memory usage is far smaller (I already have a minimap).

Pros: Little memory eatten
Cons: CPU usage grows with players in wilderness zones
Room states don't save, a player going north then south finds a new room from before they left it (could be a real problem with players dying in wilderness zones)

3) #1, but store the result in an area for a while. Generate the entire zone when it is 'loaded' then keep it there for a dozen ticks after players have moved a certain distance away. After unloading, anything left behind vanishes. This isn't totally unrealistic in a wilderness though; maybe something wandered by and took it.

Pros: Not storing all the mud rooms, but potentially...
Cons: Creating a 10,000 rooms on the fly

As a side note, I would like to have room descriptions for each of these that is, obviously, generated by some type of algorithm.

Kelson

4) Load a room (and possible its one exit neighbors) into memory as players enter them. Keep an LRU of the rooms with its max size that is adjustable at run time (even perhaps dynamically based on available memory/CPU). Add new rooms to the top of the LRU as they are created. Aka lazy loading.

4b) Where/how to store the room data and read it effectively?

.

Why so big? 1000x1000 should already do unless you have over 150 areas.

I do agree with Teelf,

store your world in a good sql (i did choose MySql),
and upload/download rooms dynamically when players enter the rooms. Add a room garbage collector which uploads inactive rooms in your sql (inactive for long enough).
You could add another low priority thread that will load areas close to the active ones, thus when the server is not busy it will populate your memory with "likely to be used soon" areas and those rooms would be accessed faster than a download from the sql. (but the mysql is very fast so u may not need that at then end).

(there is a discussion about that i think "asynchronous access data" or something like that, -of course the sql access have to be async).

actually in mud codebases, how is the world stored and recreated after a crash ?

Generally, ROM muds only write rooms when an OLC save command is executed. Otherwise, they remain the way they were when the mud was first loaded up.

The rooms are stored in .are files that are loaded at bootup and written when the save command is executed, no other times. When the mud crashes, it just forgets about all those rooms. After rebooting, it just loads them from the files again; the same as if the mud had been reset or shutdown and turned back on.

My mud saves rooms periodically since my mobs can change various rooms in order to expand their civilization, but most items aren't saved (to reflect things taking them).

Kelson

I was reading through the various wilderness, asynch loading, and large area holding threads on the forum and I think I've found what amounts to a nice solution.

I have far too many rooms to store statically in memory, but not so many that they can't all be saved on the disk. So, I think it might not be a bad idea to use a database to hold all rooms by index (although with some gaps for true areas which may or may not match any type of grid [for the sake of my builders, I'd like to allow them to create a 50x130 area (with non-linear borders) to fit in a 100x100 block; there are only certain rooms that can be walked into in the area, so it all does work out with a bit of extra work]). All 'real' areas will be stored either in a RealArea section of the database, or more likely statically, and all wilderness rooms will be located in the database. When a player enters a wilderness room it loads all the data for that room for the player. When they leave the room, it saves the state of that room in the database, including all objects and mobiles (though this could lead to a problem with damaged mobiles healing, etc...can be handled by keeping the room longer in memory maybe). On mud shutdown/reboot/area save command, these wilderness rooms are written to disk without the mobs or items in them (basically, just room descriptions, maybe with some natural resources).

This allows for generic wilderness rooms to be created one time and then updated to match certain variations the staff would like. They can also be updated in the future to match new 'real' areas being added.

Kelson

I'm actually curious to hear if you're still using the 16mb of memory you spoke about in another post for a 4k matrix of rooms.

I just posted the other reply about using a database, but then I'd also need a database table of mobiles that are autonomous so they could go about their way building on my world. Which, as I think about it, may not be such a bad idea. However, the part that would be an annoyance would be for autonomous mobile created buildings in the wilderness. At first run, the areas are all going to be close to their original cities (which are smaller than the area blocks) which means I'll just be able to store them there. However, after a bit, they're going to be building in other zones which means a lot of checking on wilderness zones. Makes me question the efficiency of leaving rooms unloaded then...

Kelson

Still using that system, 4 bytes per room. An index either points to a default room (1 per sector) or to a real room that is created when a mob or object is put in it, and deleted when it is empty again.

A bit of an unusual approach but it works to my liking =]

I'm responding to a post Tyche made on mudmagic.com to this issue with a link to the post (http://www.mudconnector.com/discuss/discuss.cgi?mode=MSG&area=adv_code&message=9998)

I thought about the tree idea before, but it isn't so much a question of computational efficiency that I'm worried about right now (which would relate to the tree being more efficient than a linked list, although still less efficient than my proposed matrix). Rather, it is a question of memory. I don't want to have so much of it eaten up with rooms.

However, I was thinking about your abstraction from a room and I think I've found a possible solution. Unfortunately, it means I'll have to scrap individualized rooms, but I'm willing to take that.

Basically, form room descriptions from room-description-segments that will have to be specially made to fit together without a problem. This makes 4-6 line descriptions without a problem and still allows for descriptions that describe 'where' the player is without killing my computer. Just store all players, mobs, and objects in the wilderness zones in a big array (resize-able, or maybe even hashed) then scan through it for which ones are in the same room. Maybe generate a room for a player when they enter so that commands don't have to be re-written (for example, get all looking for all objects in a room).

Keep the abstract-talk coming, Tyche :) Sometimes I forget there is no spoon.

Kelson

Remindes me of an idea I have on my "list of things to try." You have a set of xy coordinates and at each point there is a one line description. As the player walks around it combines all the point around him to make up a paragraph description and lists all the objects/mobs close to them. I have gotten around to putting much thought into the coding yet but I don't think it would be that hard. You just have to make sure that no two points close together have the same description. Kinda like trying to color all 50 states with only 4 colors and the same color can't touch itself (sometimes I miss the simplicity of elementary school).

(Comment added by Maxxus on Thu Jun 3 11:06:28 2004)

should be haven't gotten around

Scrapping individualized rooms isn't necessary, provided the two systems co-exist. What I was trying to figure out is a clean way to do coordinate lookup into the big ugly hash system that already exists for rooms (diku family). If the lookup finds an existing room, just use that (hand-crafted description and all), if it fails, look on the map grid to see what kind of room *should* be there, and generate a stitched-together description as described in previous posts.

The key is, how to efficiently determine these coordinate overlaps? I believe many coordinate-based FPS games use R-Trees (or a spherical version of them), but how can you build a R-Tree from a set of rooms with coordinates attatched? More memory management, of course! Fortunately, google does provide a few examples of such code.

Along a slightly different topic... a discussion from some time ago wandered around the nature of rooms. Of late, I've come to think of a 'room' as a set of coordinates upon which a common description hangs. Implementing in pure coordinate space, but only displaying a new 'room' when the player moves out of the current one, and allowing sensory data to overlap rooms (the smell of a campfire might have a radius of several hundred yards, even if the descriptions of the dense forest rooms were only 20 feet), seems quite flexible and easier to maintain than fixed room relationships.

By that, I mean if you decide to add a small pond south of an existing grassy field, instead of making several more grassy field rooms to fill in the space, you just extend the room description to reach further south.

If an efficient way to handle coordinate overlaps exists, encounters can be decoupled from the 'room' structure, although line-of-sight rules will have to come into play in indoor settings. I think the default might be that 'indoor' rooms have edges that block LOS.

Food for thought anyways.

As I said before, with 25 million rooms, it's inevitably expensive to store them all. Even if you use a simple pointer, it is 25 million pointers * 4 bytes/pointer...lots of memory.

How I was planning to implement the wilderness was that if a room was not encapsulated in the range of any given area (assume that it is a valid room, then if it isn't located, make sure it isn't located in any area file) then it is a wilderness room. These can be generated based off two simple coordinates in a data structure common to all entities (objects/mobs/players). When a player walks around into a wilderness area, it bases their new coordinates from where the area they left 'is' in the world. When they move around the wilderness area, it just shifts their coordinates. Moving out would be similar (for simplicity, it'd probably be easiest to add a coordinate flag to border rooms and not a bad idea to add one to all rooms where it is convenient, though other systems could be used).

R-trees could definately be used for breaking the world map down into segments down to each room similar to what Tyche was talking about in another thread (I'd look it up, but...). Or any other methodology. The only problem I'd have with these is that it uses additional memory and less cpu...I'm aiming for the reverse, which I think my system has accomplished.

Kelson

I have been reading through this, and some of the other, threads about wilderness areas and ways to handle them.

But I have a few questions. First - how do you, Kelson, define a 'wilderness' area? Also, why would you want some areas stored statically (do you mean in a text file?), and others in a database? What advantages would this type of split system allow? Also, is the sized you stated including all areas - or only wilderness areas? Why such a big game, what are you looking to do with 25,000,000 rooms?

I am trying to make some decisions about this very thing - but I can't make up my mind. I originally thought storing ALL the areas, both important zone areas, as well as 'filler' wilderness areas (including rooms, obj, mobs, resets, etc.) in a database would be the most efficient. But as you stated, this would get cumbersome with mobs moving rooms, objects being dropped etc. Just looking for some more info and others ideas.

>But I have a few questions. First - how do you, Kelson,
>define a 'wilderness' area?

A wilderness is any zone the builders have not explicitly built themselves. I used the word beause the initial idea was to define all the voids between areas with forest-like wilderness, but it means any automatically generated room-wise generated content.

In it's present form, my wilderness generator is able to generate an entire (100 million room) world from nothing more than a seeding integer. Right now, it is still in a rather basic form though; only generating the height field and filling in some details. I plan to add some variables for weather and climate as well as soil quality and the viability of life in different regions to spice things up.

>Also, why would you want some areas stored statically (do
>you mean in a text file?), and others in a database? What
>advantages would this type of split system allow?

I think you're quoting on something I was pondering before my current implementation. Basically, I was going to hold "used" or "likely to be used soon" regions in memory while all "unused" regions would be sitting on the hard drive (accessed through a database system). This has the benefit of allowing me to define every single room in the world, populated once, and then change it as I see fit or have players modify the rooms. On the downside, it meant I'd be storing tons of unused rooms in memory just because they "might be used" and I would have to save 100 million rooms to the hard drive, which while not as bad as holding them in memory wasn't something I wanted to do.

I'm no longer using this approach.

>Also, is the sized you stated including all areas - or
>only wilderness areas? Why such a big game, what are you
>looking to do with 25,000,000 rooms?

The 25 million rooms was simple the base grid 5000 rooms wide and 5000 rooms tall. I wanted a world so large the players would be challenged to fully explore everything. Areas would be loaded "over" the algorithmically generated rooms and would be able to do things wilderness rooms could not (like room A can link to room B without a return link, wilderness rooms are all connected both directions by the limitation of a coordinate system [not coordinates are connected though...if there is a mountain next to you and you're on a plain, you might not be able to walk into it...you'd have to go up and over]). There are also several planes of existance for players to explore (these are infinite in size).


>I am trying to make some decisions about this very thing -
>but I can't make up my mind. I originally thought storing
>ALL the areas, both important zone areas, as well
>as 'filler' wilderness areas (including rooms, obj, mobs,
>resets, etc.) in a database would be the most efficient.
>But as you stated, this would get cumbersome with mobs
>moving rooms, objects being dropped etc. Just looking for
>some more info and others ideas.

I'd recommend generating the wilderness rooms on the fly. It actually isn't that hard to do (look the 3D usage of height fields and algorithms to generate them...then modify it to do that on one pass via a simple x,y, and seed value) and the memory savings are enormous. I'm not storing a single wilderness room in memory or on the hard drive (not completely true: when the mud generates a wilderness room for a player, it actually creates 'real' room so it doesn't have to generate it again every time the player types look...the room moves with the player though, so it is really just their memory of the surroundings), which allows me to have literally an infinite number of rooms.

I will be storing the builder-created areas on file through a database however. They will be loaded into memory and held in memory as long as the mud is up. 10,000 real rooms pose no memory issue on a modern computer and I see no point in taking a performance hit by trying to load each room through the database as a player enters it merely to save that memory.

As far as objects, mobs, and players...they will all be stored in a sparse array. I think this was commented on earlier in this thread (if not, it is in another one of the threads on generating worlds that I started). Basically, a sparse array is a vector of linked lists. So an object is added at coordinate 10052, 42322 it will go to location 10052 in the array and add a node, y=42322 to the linked list. When a player enters room 10052, 42322 it checks the sparse array to see if anything abnormal is present.

I'm not actually making an array of 10000 pointers...I have several layers for the main plane of existance. The inner square of 1000x1000 rooms is a sparse array as described. The rest of the world is a linked list of linked lists as I don't expect many things to exist out there for very long.

Overall, I quite like the whole system.

Kelson