ID:154442
 
I know that maps are up for improvements for Future BYOND, but I thought I'd bring it up a bit for discussion...

Whatever future model we end up using, it should support some robust form of handing reasonably large maps.

One thing the DDT is finding is that once you go with larger mobs, your sense of the map size shrinks dramatically. Areas that seemed huge before now seem tiny.

And playing Diablo, which uses mob sizes and graphics that are I think a pretty good model for Future BYOND, I realize that the space of ground I cover in a few seconds is the size of a large map in BYOND.

After much observation, including during times of lag when the seams show a bit, I've determined how Blizzard does their Diablo maps:

They create a number of large map chunks (you could think of them as areas) which can be rotated and connect to each other seamlessly, then they specify the map by just storing references to those chunks and displaying them when they come into view. Internally, a zone is probably stored something like this, assuming 50 different area types:

30 EAST  ||  43 SOUTH  ||  21 SOUTH  ||  15 WEST


In this manner, the area takes up no memory until you see a part of it, at which time it is displayed and populated, and often it's a duplicate of other areas you have in memory. It's as if they were treating each large area the same way we treat a turf.

All the places you've loaded stay loaded (including mobs and dead bodies).

It's possible to imagine how BYOND could be extended to load areas on demand similar to this...though I wonder, how to games like Diablo store all that data in memory? To store an equivalent amount of space in BYOND would be pretty huge...or maybe they are taking up a huge amount of memory and that's the basic answer?

Anyway, it seems like a robust ability to load portions of the map dynamically is important, and the ability to keep reasonably large amounts of map in memory at a time, possibly by supporting an "area definition" that is similar to a turf definition that can be displayed on demand, if there's any way we can swing it.

One interesting point: Even Blizzard doesn't try to have all their mobs be active all the time. Once an area has been loaded, the mobs stay in their initial location until you stumble on them.
Hmm, I was thinking about this today myself, not about Diablo, but how I would go about mapping a huge city containing possibly hundreds of NPCs without my computer grinding to a halt, the best I could come up with was multiple small maps which link seemlessly to each other, though this method would be both time consuming and, well, ugly. I can't see how you can have a seemless link between two maps becuase even when your on the very edge of one map, you wouldnt be able to see poeple on the adjacent edge on teh next map (if that makes sence).

Hmm.
I bet Diablo doesn't store as much data for each "turf". They don't have overlays in the way that BYOND does, nor icon_state, z coordinate, and a slew of other variables. I doubt if they even store the coordinates at all, instead referencing it as a 2 dimensional array. You can store a very large map if it's just an array of image pointers. Items and monsters are are stored too, but only one item and one monster per map space.

Your building blocks approach is a great idea, one I've been fascinated with since I bought a pack if dungeon geomorphs in the ancient days of D&D. For the most part, I think Diablo uses a map maker very similar to mine, but with variable cell sizes. (Something my map maker will support when I work on it again. Also, my map maker will build the map entirely in an array and not alter any turfs until it's finished. Part of the reason it's currently so slow is because of multiple turf deletions.)


I too have been wrestling with the idea of large maps. Mine is further complicated by being able to see traces of what lies one or two turfs under empty spaces. Calculating all those underlays brings my system to it's knees when a large world boots up. The best option I can think of for my game is buying a small server farm, placing each map in a separate server, and transferring players between them like the big games do. As soon as I win the lottery*, expect to see it happen ;)



<font size=-1>* Sadly I won't be winning the lottery, since I refuse to waste my money on it.</font>
I agree. Large maps are important, and the ability to load them dynamically in sections is equally important.

If dynamic map-loading is added to BYOND, I suggest it be done in the following manner:

- Each map or mob should have variables indicating the maximum in-memory size of a region, and the maximum size of any overlap. Say the max size is 40x40 and the overlap is 5. When you get to x=36 in your map segment, your segment shifts over by 30 (40-5x2) so now you're at x=6. Of course your position on the larger map is what really counts. When you teleport, it should be into the center of the region.
- Each mob must be specified map-active or map-inactive, to determine whether part of the map must be loaded for it. Some mobs may need smaller map sections loaded, so it makes some sense for the above variables to belong to the mob.
- Some commands and procedures may need access to parts of the map outside the currently loaded region. If necessary, it should be possible to use the whole map within a command, but made relatively easy at least to access a single location. Locations needed on a sporadic basis like this should be cached in small packets, perhaps 8x8.

Overall, the important thing is to keep track of which parts of the map are loaded and which aren't, and who's using which.
It's complicated, but workable.

Lummox JR
In response to Shadowdarke
Shadowdarke wrote:
I bet Diablo doesn't store as much data for each "turf". They don't have overlays in the way that BYOND does, nor icon_state, z coordinate, and a slew of other variables. I doubt if they even store the coordinates at all, instead referencing it as a 2 dimensional array.

Well each map section does have some unique geographical aspects...like chests you can check or rocks you can turn over...and sometimes a cave entrance or something.

It's possible, as you might be implying, that any differences are stored in a list that indicates where they are in the map area, rather than being mixed in with the map data.
In response to Deadron
Deadron wrote:
Shadowdarke wrote:
Well each map section does have some unique geographical aspects...like chests you can check or rocks you can turn over...and sometimes a cave entrance or something.

It's possible, as you might be implying, that any differences are stored in a list that indicates where they are in the map area, rather than being mixed in with the map data.

Since you can't place items in the locations of those objects, they might occupy the item slot for that space. Hard to tell without talking to their dev team.

I wonder how much of their design concepts Blizzard North would be willing to share with budding programmers.
In response to Shadowdarke
Shadowdarke wrote:
Since you can't place items in the locations of those objects, they might occupy the item slot for that space. Hard to tell without talking to their dev team.

Not quite sure what you mean here...you can drop items anywhere on the map and they will persist at that location...and opening a chest or something will add items to the map at that location.

Anyway, we probably don't want to exactly mirror the Diablo approach, but it is a good system to look at. I think if BYOND got to robustly supporting games that go from text to tile-based 32x32 to some form of Diablo-like free-ranging maps with arbitrary mob/obj sizes, it would be one of the most excellent all-around game engines.

As it is, it is probably one of the most excellent in terms of language, hub features, and easy networking...but graphics/maps are the obvious low points. Fortunately we can workaround much of that in the meantime.
In response to Deadron
Deadron wrote:
Shadowdarke wrote:
Since you can't place items in the locations of those objects, they might occupy the item slot for that space. Hard to tell without talking to their dev team.

Not quite sure what you mean here...you can drop items anywhere on the map and they will persist at that location...and opening a chest or something will add items to the map at that location.

Diablo appears to have a basic isometric map, which is just a specialized tile based map. You can never put two items in one tile in Diablo or Diablo 2. They can go to nearby tiles, but they won't stack one on another.

Off of Diablo and onto the topic of BYOND maps, You could store unused maps in an simplified array in 2 or 3 dimensions (whichever suits your needs) Each cell in the matrix contains only the turf type. If you have other values that must be persistant, you can add them to the cell datum.

For instance, walls have a damage variable in Tanks, so I'd have to store that as well. I don't have to store the overlays on the walls, because walls below a certain damage level always display the cracked overlay. A map for Tanks could be stored in as few as 4802 bytes (a 49 x 49 map, with 1 byte as an index to the turf type and 1 byte to indicate damage) if BYOND supported one byte data types. (Yes, I know you could cram more stuff in with bit operators, but I don't want to confuse the topic further.)

When a player moves to the level, you reconstruct the map of that level from the simplified map array.
In response to Shadowdarke
Shadowdarke wrote:
Off of Diablo and onto the topic of BYOND maps, You could store unused maps in an simplified array in 2 or 3 dimensions (whichever suits your needs) Each cell in the matrix contains only the turf type. If you have other values that must be persistant, you can add them to the cell datum.

I think this is how BYOND maps are stored now, and maps like 50x50 are no problem. But if you assume a reasonable mob size is 64x64, you quadruple your need for map space. And once you get past 200x200 turfs, especially if you have multiple map levels, things start getting dicy. At some point, as some have reported with large maps, BYOND basically stops working.
In response to Deadron
Deadron wrote:
Shadowdarke wrote:
Off of Diablo and onto the topic of BYOND maps, You could store unused maps in an simplified array in 2 or 3 dimensions (whichever suits your needs) Each cell in the matrix contains only the turf type. If you have other values that must be persistant, you can add them to the cell datum.

I think this is how BYOND maps are stored now, and maps like 50x50 are no problem. But if you assume a reasonable mob size is 64x64, you quadruple your need for map space. And once you get past 200x200 turfs, especially if you have multiple map levels, things start getting dicy. At some point, as some have reported with large maps, BYOND basically stops working.

I kinda asked this before, in a different thread in here, but Im gonna ask again, and hope that I get a bit more comprehensive answer, its kinda on topic..

How much can Byond handle? What can you throw at it before either the connection lags, or the client/server lags? How big maps? How many NPC? Players? that kinda thing.. I know itll have a lot to do with the power of the machine, and the quality of the coding, but its prolly a good thing for a lot of not so experienced people to know ^^;;

Elorien, who is now waiting for her programming class to start.
In response to Deadron
Deadron wrote:
I think this is how BYOND maps are stored now, and maps like 50x50 are no problem. But if you assume a reasonable mob size is 64x64, you quadruple your need for map space. And once you get past 200x200 turfs, especially if you have multiple map levels, things start getting dicy. At some point, as some have reported with large maps, BYOND basically stops working.

The map size isn't at issue. I just used Tanks because it was a handy example. What I was trying to say is that You could store it in a more compact way, with only two variables, instead of in a regular turf map.

Turfs have a lot of extra data that baloons the amount of memory required tremendously. Each atom has around 8 numeric variables at 2 to 4 bytes each, 6 string variables which can be 1 to 256 bytes long (maybe more), 5 pointers (to other data constructs like lists, icons or other atoms atoms) that are 2 or 4 bytes. (I'm being conservative on the variable counts and am not sure on the amount of memory allocated to each type requires, but you see how large the turf data object is.)

I can't find the reference now, but when we were discussing maximum map sizes one of the gurus estimated a turf was around 4Kb. It sounds a little high to me, but it's possible. If so, the method I presented earlier compresses an entire Tanks battlefield into the memory space of one turf, about as much memory as 4 32x32 256 color bitmaps.

Maps that require more complexity will take more memory, but you can strip away unnecessary variables when you "put a map away" to save your system considerable amounts of memory.
In response to Elorien
Elorien wrote:
How much can Byond handle? What can you throw at it before either the connection lags, or the client/server lags? How big maps? How many NPC? Players? that kinda thing.. I know itll have a lot to do with the power of the machine, and the quality of the coding, but its prolly a good thing for a lot of not so experienced people to know ^^;;

Elorien, who is now waiting for her programming class to start.

It has "a lot to do with the power of the machine, and the quality of the coding" as well as the network connection involved.

The BYOND software is currently limited to 65535 mobs and 65535 objs in any given world, but Dantom is going to change that. I think the turf limit is around 8 or 16 million, but you're not likely to have a computer that can digest that easily.
but that would be a little complicated and i think BYOND is made to be alot less complicated than c/c++ if you want to do that you should program a c/c++ game or dantom should make a seperate system for multiplayer c/c++.
In response to Shadowdarke
Shadowdarke wrote:
Elorien wrote:
How much can Byond handle? What can you throw at it before either the connection lags, or the client/server lags? How big maps? How many NPC? Players? that kinda thing.. I know itll have a lot to do with the power of the machine, and the quality of the coding, but its prolly a good thing for a lot of not so experienced people to know ^^;;

Elorien, who is now waiting for her programming class to start.

It has "a lot to do with the power of the machine, and the quality of the coding" as well as the network connection involved.

The BYOND software is currently limited to 65535 mobs and 65535 objs in any given world, but Dantom is going to change that. I think the turf limit is around 8 or 16 million, but you're not likely to have a computer that can digest that easily.

Hmm.. sounds like a lot, but realisiticaly, what can a system handle? *looks around the boards* Anyone out there (coders) notice that thier system chugs a little under some circumstances? Why not post your system specs, and what you were running <about how many mobs/areas/size of areas and such, I know that coding efficiancy is gonna make this not all that accurate but it still would be good) just so people out there who havent run into those kinda problems know a little better how far they can push thier games ^^;;

Ive said in other posts that I jumped right into a rather ambitious game, so I wouldnt mind knowing what some of my limits might be, so I can design around it before I run into problems during actual testing ^^;;;;

Elorien
In response to Shadowdarke
Shadowdarke wrote:
Turfs have a lot of extra data that baloons the amount of memory required tremendously. Each atom has around 8 numeric variables at 2 to 4 bytes each, 6 string variables which can be 1 to 256 bytes long (maybe more), 5 pointers (to other data constructs like lists, icons or other atoms atoms) that are 2 or 4 bytes. (I'm being conservative on the variable counts and am not sure on the amount of memory allocated to each type requires, but you see how large the turf data object is.)

I can't find the reference now, but when we were discussing maximum map sizes one of the gurus estimated a turf was around 4Kb.

Actually, if the turf has no unique values it takes up very little space. I believe Dan once said a non-unique turf takes up 12 bytes.
In response to Elorien
Hmm.. sounds like a lot, but realisiticaly, what can a system handle? *looks around the boards* Anyone out there (coders) notice that thier system chugs a little under some circumstances? Why not post your system specs, and what you were running <about how many mobs/areas/size of areas and such, I know that coding efficiancy is gonna make this not all that accurate but it still would be good) just so people out there who havent run into those kinda problems know a little better how far they can push thier games ^^;;

My system always chugs if I design something poorly. Otherwise, it runs very rapidly -- especially for an interpreted language. For example, if I loop through 1e+13 numbers one at a time, I get several seconds of freeze-time. Instead, I break that up into chunks -- I'll work with several thousand numbers simultaneously, and then further subdivide the remainder until I've executed them all.

Realistically, BYOND can handle a lot. Assuming you have very basic AI mobs, and objs that do nothing until used, you can easily reach the object limits without any major problems. The lag in BYOND is not due to the amount of objects, but rather, when people check a list of every object in the world and work with them.

Assuming you do what I do and pay lots of attention to detail, you have to design your game to be very efficient -- not doing AI operations on mobs that aren't in range of anyone, not having one mass-initialisation where you set and randomise all of the variables of every mob in the world, etc.


Ive said in other posts that I jumped right into a rather ambitious game, so I wouldnt mind knowing what some of my limits might be, so I can design around it before I run into problems during actual testing ^^;;;;

People have reported their games working just fine with 500x500x5 maps. People have reported problems, both in the map editor and in the game itself, running 500x500x50 maps.

Since 1000x1000x1 is just a little smaller than 500x500x5, it is your call. 500x500 is extremely huge, especially if it takes you time to cross the map (i.e. your movement is delayed) -- assuming, of course, you aren't underexaggerating (oxymoron of the day!) the size of the map by making things look big.


In Haven (ack, I mentioned it again!) my maps are 79x79 areas that interconnect to each other (my initial plans include a single island-continent that covers 30 areas in total). Maps at that size seem much bigger than they really are when you use small creatures, and it removes the necessity for tons of wasted space, like vast fields of grass and stuff... anything on the map can be meticulously designed.
Since I love Ultima VII so much, I'm more than happy to point out a very nifty trick that The Black Gate uses to store information.

Though UO is a step up from the latter versions of the RPG-oriented Ultima (or down, depending on how you look at it), I'm fairly sure it works in the same way.

What it does is it keeps a FIFO (for non-programmer types, that means file-in-file-out) constantly running. You drop an item, it is immediately written to the file. You pick it up, it is removed from that file and added to your character, and so on.

The world is divided into 256 (16x16) megachunks. Each of these megachunks is subdivided into 256 superchunks. And each superchunk is subdivided 256 chunks, each of which contains 256 tiles.

When the game starts, the entire world -- the whole thing -- is generated from the code, and saved to the megachunk savefiles that govern the world.

Whenever your Avatar moves, he moves tile by tile. Each superchunk the Avatar enters is then loaded from the file and initialised. Anything in the Avatar's previous superchunk, save the bordering chunks which are still visible, is then unloaded from memory.

Thus, the game works with up to four megachunk files open (sitting near the cross of the four borders), and will have up to four superchunks loaded into memory.

As you can hopefully tell, this means that anything in the world that isn't within the superchunk, which is a 256x256 tile area, is processed behind-the-scenes -- NPCs will arrive instantly at their destinations during that time, monsters and garbage items will be deleted from the map, and any other miscellaneous processing, such as night and day or torches burning out, is completely ignored.

Ultima VII was not processor-clocked when it was designed, and it runs very fast on my computer -- I use a do-nothing loop TSR program to slow it down (not the company -- terminate-and-stay-resident). It goes to show that back then, they had to obey some fundamental programming techniques to get it to work.

And since every location is subdivided into 256 subsections, that means that location is not done by x,y coordinates, but rather, tile numbers. (There is a Z coordinate, though. Ultima lets you stack objects on one another.) This means that an object's location in the whole wide gigantic world can be specified with merely FOUR bytes!


Here's an interesting tidbit: I derive more pleasure from that game when messing around with boxes and crates, dinking around with the various physical aspects, blowing up harmless civilians, murdering guards who patrol back and forth over caltrops, exploring, and moving things around, than I do with actually playing the game to win.

The game is so large, there's plenty of room to mess around in.

I believe Ultima Online adds another level of chunk -- UO, from what I've heard, seems to be approximately 16 times larger in width than U7's map... and that's per server, uh, shard.
In response to Spuzzum
Spuzzum wrote:

What it does is it keeps a FIFO (for non-programmer types, that means file-in-file-out) constantly running. You drop an item, it is immediately written to the file. You pick it up, it is removed from that file and added to your character, and so on.

Overall very informative. Just thought I would correct you on a technicality.

FIFO (at least in the original use of this acronym) stands for First In, First Out. This is opposed to the idea of Last In, First Out (LIFO). The latter is sometimes referred to as FILO, which works out to the same thing.

These are two basic schemata for list processing. The first is a cue or buffer system, the latter works like the stack space in memory.

And since I fired my own curiosity now, I just looked this up on dictionary.com, and found the following useful explanation of FILO:

stack n. The set of things a person has to do in the future. One speaks of the next project to be attacked as having risen to the top of the stack. "I'm afraid I've got real work to do, so this'll have to be pushed way down on my stack." "I haven't done it yet because every time I pop my stack something new gets pushed." If you are interrupted several times in the middle of a conversation, "My stack overflowed" means "I forget what we were talking about." The implication is that more items were pushed onto the stack than could be remembered, so the least recent items were lost. The usual physical example of a stack is to be found in a cafeteria: a pile of plates or trays sitting on a spring in a well, so that when you put one on the top they all sink down, and when you take one off the top the rest spring up a bit. See also push and pop.

At MIT, PDL used to be a more common synonym for stack in all these contexts, and this may still be true. Everywhere else stack seems to be the preferred term. Knuth ("The Art of Computer Programming", second edition, vol. 1, p. 236) says:

Many people who realized the importance of stacks and queues independently have given other names to these structures: stacks have been called push-down lists, reversion storages, cellars, nesting stores, piles, last-in-first-out ("LIFO") lists, and even yo-yo lists!

See? This is where we get "Stack Overflow" from! Probably way more than you needed to know, but I like this sort of stuff. :-)

/mob/skysaw
In response to Spuzzum
Your idea raises an interesting question: Do you think it's possible as of right now to implement a system like this via save files in BYOND games?

I mean, obviously there would have to be some sort of map manager installed that would handle the loading, saving, updating, and so on. Then, it would need to set up teleport systems to load and unload maps as needed. (Some maps without active player mobs could perhaps be "cached", running in memory until another map was needed, at which point they could then be unloaded.) On top of that, you'd then want to install a means by which NPCs and other less essential items could be handled behind the scenes in the manner you suggested--perhaps some rudimentary "shortcut" API, or a procedure call to all items in the map upon loading, plus some means of teleporting a non-player object from a loaded map section to an unloaded one via file storage.

Seems to me this could be done, but I don't know nearly enough about BYOND internals at this point to speculate on the exact code to do it.

Lummox JR
i wonder if some how byond could possibly use 2D BSP maps, allowing for ADVANCED trees, lighting!!!, and all kinds of effects. And hell, if it was BSP format, we could even have some cool effects, using textures libraries from games such as QUAKE 3, like the fire effect for a spell.

BSP runs pretty fast if im not mistaken, BUT could be a GRAVE mistake if byond tried to do this(bugs, and tons of man hours to change the entire system)

but its just an idea. =D

FIREking
Page: 1 2