So, I've been playing around with trying to get an absolutely massive world in BYOND and I have ideas on how it could be done, but they may not be the best.
Before I start, here are my definitions of the above.
1. Huge. Simply put, this is a minimum of 10,000x10,000 in size, or 100,000,000 tiles.
2. Seamless. This means the map only has 4 edges and a player can walk from one edge to the other without ever appearing to bump into an edge and then be taken to the edge of another map.
3. Dynamic. The world has to be changed by players, meaning it needs to be saved and loaded.
Anyway, there are a some major problems with doing this.
1. I don't think BYOND can handle a world of this size from a technical stand point. The largest I've successfully created is a 5000x5000 world, it took several minutes to initialize and used a whole lot of RAM.
2. Saving and loading a world of this size is not an easy task. Using BYONDs savefiles for this is simply not feasible. Saving a 1000x1000 world can take as long as 20-30 minutes and it can reach inexcess of 700mb+. Loading it takes just as long.
A world 100x bigger would by this logic take 2000-3000 minutes (that is 33 to 50 hours) to save and exceed 70GB in size.
My current solution is to slice the world up, a 1000x1000 world might be made up of 400 50x50 slices.
On top of this, I have written my own code that saves the world as a very simple raw text file, where each turf is represented by nothing but a number.
Doing this, I have managed to save a 1000x1000 world in as little as 25 seconds and it requires just under 2MB of space. This means an individual slice of this map takes 0.06 seconds to save and load, and around 4-5kb.
Anyway, my method works, but it has it's own problems.
First, the world is not technically seamless. This can be solved, but the method is not easy.
It would require loading the map a player is on, as well as the 9 surrounding maps, then taking the edges of these 9 surrounding maps and stitching them onto the map the player is presently on to give the illusion that the map is seamless.
This picture makes it easier to understand.
http://files.byondhome.com/TheMagicMan/stiched%20map.png
The black is the map the player is on, blue are surrounding maps and green is the maps stitched onto the map the player is on from the surrounding ones.
Doing this is not only harder than it sounds, but it has also increased both the physical size of the world significantly (just using maps with seams means 20 players use 20 maps, this system means 20 players could use 180 maps as well as the edges of 160 maps), as well as increased the time it takes to load the world.
The second problem is the entire world needs to be synchronized. What this means is, if a player stands at the edge of their map, a copy of them needs to appear on the edge of another map. People may need to be able to interact with this copy in exactly the same was as they interact with the player.
This picture explains it.
http://files.byondhome.com/TheMagicMan/stiched%20map%202.png
If the red dots are two different players, then the purple dots are copies of these players that appear on another map.
Not only is making a system like this hard, but I suspect it will require a lot happening in the background as it is entirely possible for 1 player to appear on as many as 4 different maps (1 person in a corner will appear on 3 other maps).
(PS. Technical help on implementing a system like this would help)
The next problem is again with saving and loading a world like this. As I said, it can be done using my method, but this method saves nothing other than a single number. This number is converted into a turf when the world is loaded.
Mobs and objects are not saved, infact nothing about the turf other than it's type is saved either. Mobs may not need saving and saving objects isn't difficult but would probably significantly increase both the time it takes to save a world and the size of saved files.
The problem however is saving two different versions of one thing. This might be easy for objects as they probably do not reach insanely high numbers like turfs can and do.
But for turfs there is only one, ever so slightly feasible way of doing this, and that is using a whole lot of different turfs.
Anyway, the final problem with making a sliced up world like this is making it persistent. If a slice is unloaded when a player leaves it, nothing on that slice continues anymore as it doesn't exist. If a player lights a fire on a slice that will burn for 10 minutes, then leaves that slice, what happens to the fire?
There are two solutions to this, neither is a great solution. The first is to not immediately unload a slice when a player leaves it, but wait for a while. This presents a problem in that if a lot of players are in a world and move around a lot, you end up with a lot of maps being loaded into memory, and this system was suppose to prevent this kind of situation.
The second is have some kind of timer keeping track of things even as they're unloaded. The most obvious choice in most cases is when the fire is lit, have the time it was lit recorded, when this slice is saved this time is saved, when the slice is loaded a check is made and if the time passed since the fire was lit is more than 10 minutes, the fire is extinguished. The problem with this is once again saving and loading even more data, which results in it taking longer to save/load and bigger save/load times.
ANYWAY. These are some of the problems I have encountered so far, and potential solutions for them. Has anyone else here experimented with making worlds like this in BYOND, if so how did you go about it and what problems and solutions did you discover into?
ID:1450705
 Dec 22 2013, 8:41 am
|
|
http://files.byondhome.com/TheMagicMan/slices.zip
This is what I'm working on right now. It's similar in a way to your example. Except it uses multiple z levels, and when they're no longer needed it scraps them. Each z level is saved in a text file (you can even look at them and edit them) which the game loads when you enter the new z level. At the moment it's not seamless however, which is the next thing to work on. The demo is only a 200x200 world though, saved as 64 25x25 slices. But once this is done it'll probably allow for technically infinite sized worlds (or however long arrays can be in BYOND, at the moment I'm using maps[100][100] which would allow for 10,000 slices, which at 25x25 is a 2500x2500 world). | |
Here we go, one seamless world made up of a lot of smaller slices that are loaded and unloaded as needed.
http://files.byondhome.com/TheMagicMan/seamless.zip It works well but it's not as smooth as I was hoping and it'll need some optimization. EDIT: It's about as smooth as I could possibly get it. It looks and runs pretty well, not sure how it'd handle multiplayer mind you. | |
http://files.byondhome.com/TheMagicMan/seamless.zip
So, there we have it. An entirely seamless world made up of small slices, which also synchronizes all mobs/objects that might appear on multiple z levels. It doesn't look impressive yet and I'm not sure how efficient synchronizing everything would be on a larger scale, but potentially this allows for infinite sized worlds. | |
So, I've been playing around some more with this, and run into a problem.
BYOND has no function to split a string into a list. So you need to write this function yourself. The problem with this is when you need to split several strings tens of thousands of times, it's just not possible to do this fast. I've wrote my own function to try it, and tried every single library and demo on BYOND, it's just not possible to do this as fast as I need. What this results in, is a brief (only very brief, like 0.1 second) of lag when a map is loaded. This might not seem significant, but it ruins the illusion of a seamless world. The options I have available now are settle for this noticeable lag, but there is an issue with this. At the moment I only save/load turn files. When objects and mobs are saved/loaded, this 0.1 second of lag will double or even triple. Or I use very small files, such as 20x20 to minimize how often strings are split. The problem with this is, a 10,000x10,000 world split into 20x20 slices is 250,000 separate files. This is clearly not an option. The other option is to use an external dll to handle splitting strings into lists. This might be the only option at this point, except I have no idea how to do this. http://files.byondhome.com/TheMagicMan/seamless_src.zip This is what I've got so far, but unless I can somehow figure out C++ this is about the limit of what's capable with BYOND (using this method anyway). | |
I will just give you a hint, the trick to a seamless MASSIVE world is multiple daemons running multiple dmb's and using link to pass people around. It means you have to do external everything in terms of saving/loading/communication. Welcome to the reality! It simply isn't possible, no matter what language you're using, to have the whole world running on 1 logic brain (1 server).
Even if you came up with some magical binary solution to handling everything very quickly, you'd run into a brick wall with time spent initializing tiles, saving and loading those tiles to flat files (it won't be fast enough without a database), and many many more issues. | |
Take a look at how I implement things.
Technically, with my way of doing things, you can make a world of infinite size and it will use no more resources than 1 70x70 map. Because the whole world is not running at once, only one tiny section of it is. Naturally, as more people play this becomes a problem because each person may need their own 70x70 map. But I've had BYOND run a 1000x1000 map (which is 204 70x70 maps, and 204 is more players than almost every BYOND game gets) without any hassle. My problem is purely converting strings into lists. I have to convert strings into 427 lists everytime a map is loaded (technically 9 maps). Although this is done in a fraction of a second, for that tiny fraction of a second the game stutters, and this breaks the illusion of a seamless world. Unless I find a better method of saving and loading each map slice, or a better way of converting strings into lists, there is just nothing that can be done about this brief stuttering caused by converting so many strings into lists. The system I have set up is lag free and uses minimal resources (excluding potentially several hundreds of MB for saving the world) and is so flawless that if I disable converting strings into lists, there is no lag or stuttering and effectively an infinite sized world. But without converting these strings into lists, I cannot convert the saved map data into a usable format. Infact, the system works so well, that right now I have a 10,000x10,000 world set up, and BYOND is using about 17MB of ram. I can fully explore this entire world. | |
I actually made a feature request some time ago that would mitigate problems like what you've mentioned but I haven't heard a word on it as of late.
| |
My first instinct is that tiles isn't the best measurement of the size of the world. To give an example from BYOND, FFO is a well made game with what used to be a huge world. I remember spending upwards of two hours trying to go from one end of it to the other. When I visited the game recently they had changed the way shops work such that a slightly better speed enhancing item was sometimes available. This slight increase in speed, along with a couple other bits of power creep, allowed me to run across the world in a matter of a half hour. Also, they added a "world say". Suddenly the game world became tiny. I'd consider other metrics, such as time, in measuring your world.
| |
I actually did measure it in time. With the speed I had a player moving at, and the size of the world I was aiming for (10,000x10,000), it would have taken a player about 2660 seconds to walk across in a straight line.
That might seem big, but take a game like Haven and Hearth. It's world map is made up of something it calls "supergrids". The world is currently 10x10 super grids. A supergrid is 5000x5000 tiles in size. That's 50,000x50,000 tiles in size. That's probably bigger than every single BYOND game that's ever been made combined. That's the sort of size I wanted to aim for, but it's just not feasible with BYOND. | |
With procedural generation it can be infinite in size :P
| |
But it's just not feasible with BYOND. It is entirely feasible. Let's say we have a world that's approximately 50,000 by 50,000 tiles in size. BYOND's internal limitation on turfs is roughly 1024x1024x200 before you run into memory issues. That's approximately 14,500 tiles squared. Let's be conservative and say that we can support optimally at most 5,000x5,000 contiguous tiles on each layer before needing to transition the player to another z-layer or server. Now, the mistake you are making, is in assuming that Haven and Hearth runs on a single process with their server. It's highly unlikely that this is the case. In fact, I think it's entirely reasonable that they are splitting their world's loading/processing to exclusively what parts of the world are currently being interacted with. Thus, it's likely that they are splitting these regions and the clients contained therein into a series of separate processes. So, if we assume that we can manage 5,000x5,000 tiles, we can readily handle 4 z-layers of that size per-server node. In order to construct a server with 50Kx50K tiles, we're looking at around 100 distinct nodes, provided they are loaded all at once. Now, that's something of a problem, because 100 distinct copies of DS running on your shell is definitely going to burst your limits. So how do we get around this issue? Instead of focusing on each individual server being dedicated to one particular region, I'd suggest a more dynamic approach. Merely keep a central server in charge of keeping track of which parts of the world are loaded, and which server is housing that part of the world. If we reduce our chunk sizes to roughly 1000x1000, we can manage about 100 distinct z-layers at once on a single machine. Optimally, we are going to want to keep that number down, so we'll call it 50. That reduces our server load to just 50 segments. But we want to do it with 8-16 processes maximum. That means that we need to support 157 distinct regions per server node at peak if 100% of your world is going to have a unique client in it at once. My guess, though, is assuming an average online player count of 200 at most, and a monthly community of 1,000 players, you will have populations of 5-10 clustered in very small spots around the world. As such, we can depend on at most, 3 1Kx1K cells being loaded at any given time per group 5 players. This means that at peak, we'll have an upper bound of 120 cells loaded at any given time. That's about 5% of your map loaded at any given moment. Okay, but let's not be conservative. Let's aim to support 500 concurrent players on a single dedicated box with an 8 core machine and 1 server per core. In order to support this, we need to support approximately 100 unique locations with an average of 3 cells per location. Now, with an 8-server setup, we are distributing 300 cell grids loaded at the time. That's approximately 38 z-layers per server, with an average player distribution of 63 players per hosted node. This is exactly 12% of your world loaded at once. Basically, what I'm saying here, is don't plan on having 100% of your world loaded at any given time, because it's probably not going to EVER happen. If you are planning on having a world 50K tiles in size, and supporting 500 players at any given time, you are absolutely, irrevocably going to have to split your server up using a series of load-balancing distributed nodes controlled from a single central server. If you want a world 50K tiles in size supporting a maximum of 30-50 players, though?, BYOND is absolutely capable of this, you just need to dial in your map loading logic and get it optimized to a level where BYOND can quickly and seamlessly handle the load you are going to put on it by loading large areas from files on demand. Part of this is going to be achieved by designing an efficient and novel serialization approach (Read: Not stored in DMM format. Serialization of DMM data is going to take too long to be reliable for runtime loading.) The other part of this is going to be achieved by handling world loading in a sensible and well-thought-out manner. Optimization is going to be absolutely key here, and small operations and misplaced logic are going to add up very quickly in this arena. And before you throw your hands up and say this is too hard to do in BYOND? It's not going to be any easier in any other language or toolkit, because what I've said above is going to apply at least in part to any other environment regarding a 2D multi-player game. While yes, BYOND's server does keep track of a lot of stuff a standard tile-based game server doesn't really have to, it compounds the problems with this kind of a system only slightly. | |
Actually, what I have right now is a system that can handle an infinite sized world. There is absolutely no upper limit on the size of the world. I've had it theoretically run a world that was something like 1 million tiles wide and across.
This is the easy part. The world is just divided into small slices (say 100x100 tiles), only 1 z layer is loaded based on the players location, so if 1 player is in the world, no more than a 100x100 area of the map exists at a time. I even managed to make this (ALMOST) perfectly seamless. A player could walk from one end to the other and never appear to reach the edge of the map, they'd even see and be able to interact with things on other z levels. The problem I ran into was simple. Saving and loading these maps. I could do this easily, but doing this made a very brief, but very noticeable stutter everytime a new map was loaded. I eventually found out, the problem is actually BYONDs string handling. The maps were saved as a set of numbers in a text file and nothing more, a map file might look like this... 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 2 1 1 2 1 2 2 1 1 1 Obviously a lot bigger than this. The problem is when you get BYOND to read this data, you need to break it down into readable format. First you need to break this file down into 5 lines, and each of these 5 lines into 5 numbers. This might not seem like much, but now imagine having to do this with a map slice that is 100x100. Suddenly it becomes a much bigger issue. Now imagine you have to load upto 18 of these files everytime a map is loaded (1 the player is entering, the 8 surrounding maps to make the entire thing appear seamless, and then all of this again but for objects, since you're only saving a single number to represent each tile in the world you can't store very much data in a single file). What this meant was, everytime a map slice was loaded, it'd have to process tens of thousands of strings. This caused a tiny stutter which might not seem like much, but it was very noticeable and ruined the entire illusion of a seamless world. The problem wasn't handling a world of massive size. The problem was purely string related. And unless BYOND gets better native support for handling strings in a variety of ways, there just isn't much you can do about it outside of dividing the world into tiny slices (say 10x10, that produced a perfectly seamless world, the problem? Saving a 50,000x50,000 world in 10x10 slices results in 25,000,000 files for just the turfs and that many again for objects, windows does not handle that many files in a single folder well at all, like enjoy crashing your entire computer if you even try to access it). | |
Why bother with strings at all?
BYOND's savefile format is decently space-efficient if you learn to use it properly. Why not store your data in a format consisting of an explicit identifier per-type. Create a format, and cram it into a single linear buffer. [TILE ID token] [value 1] [value 2] [value3] [...] If you explicitly line out an expected series of arguments within the buffer, you can read them back in sequence: //writing to the buffer: Yeah, it's going to take some work on your part to get it right, but provided you set it up right, the format can be as flexible as you want, you can store versioning information, and you can keep all the linear data in a single structure, allowing reasonably structured files. | |
But again, you probably shouldn't blame the system when the approach was ill-suited to it.
Without seeing your loading/saving code, I can't really tell you what you can improve. But I know that loading a 1024x1024 area should be doable in about 9 seconds flat (with moderate breaks in processing to keep the server fluid) on a modern computer. --Considering that's what my current approach tests at. | |
I don't really see the need for this obsession with completely seamless play. Even AAA titles have loading screens, and they usually give the player a nice picture and a funny or informative piece of information while they wait.
Besides, nobody is going to come to your BYOND game expecting a virtual reality that makes them almost lose touch with reality. They expect to play a game, on a computer, and the most important question they will ask themselves is "Is this game fun to play?", not "Is this game impressive in the size of its seamless world?" The second question certainly would impress certain people who know something about programming, but I just don't think that should be a big concern for you as a developer. Now, having loading screens too often is definitely a problem. You obviously want your player to spend almost all of the time actually playing the game, with only a couple short delays when you change areas. I guess if you want there to be no obvious borders to the areas of your game, you have no other choice. But would your system work in multiplayer at all? If you had players on their own z-level, what happens when they get close enough to each other that they can both see some of the same map slice? Look at your numpad: Player A is on the 1, player B is on the 9. They should both be able to see and walk into section 5. But will you load two section 5's? Or will you only load one - but on which z level? | |
BYONDs savefile format is incredibly slow. Thousands of times slower than simply saving or loading raw text. It also results in files hundreds of times bigger. I've already tried using it, it's simply not fast enough for what I need.
Also, loading a 1000x1000 area in 9 seconds is incredibly slow. My system can do it in less than 0.09 seconds. The problem is purely that once the map is loaded, the thousand lines it loads need to be split into a thousand numbers each. This is just slow, I've tried my own function, and every single function to split a string with a delimiter in every library on BYOND. They are all simply too slow to do on the scale I need to do them on (I'm using 25x25 map sizes, meaning I need to split 450 lines of text into 11,250 strings, in such a small time that it's not noticeable to the player). If you need to see the exact code, go and download the libraries like deadron.texthandling, or forum_account.text, those two were the best two libraries in terms of speed. But neither is sufficient for what I need. Funnily enough, using my incredibly limited knowledge of C++, I managed to write a function to split a string into a series of numbers and it's incredibly fast. Infact it's fast enough for my needs. Too bad it's useless because BYONDs call feature can only make use of strings, which is the exact opposite of what I need. As for loading screens in massive, AAA games. Most of them are due to the data being read off of the disk. But what we are comparing here is a fully 3D world made up of 3D meshes and textures that are probably bigger than some BYOND games. Are you really going to compare loading these to a BYOND game? Also go and play something like Fallout or Skyrim. In these games, once you're outside, you can walk from one end of the map to the other without a single loading screen or even a brief delay. These worlds are bigger than what BYOND can support without making some kind of system for it like I have made. Also, my system handles multiplayer perfectly well. I've tested it with about 4 players (all me), if they're in the same area of the map, they're all placed on the same z layer. If one walks off, even though he's on another z layer he can see the other players and they can still see him (and even interact with him like he was still on the same z player). This was done ages ago and is no problem now. | |
Short answer here is simple, you only load what you need. And with BYOND, that's not exactly easy due to the entire collection of /turfs being initiated at runtime with no option to disregard unvisited turfs. What you can do though is make sure turfs always start out "stupid" and fill them in as players move around. You can get the processing time short enough that it can be sprinkled in as the players need to see more of the world based on location, as opposed to needing to load it all right now.
This is the approach I take in my demo "Massive" where I made a proof in concept of this idea working.
http://www.byond.com/developer/FIREking/Massive