ID:1297541
 
Normally when we see map generation talked about on BYOND it is normally processes that observe the entire map at once and generate it as a whole. Not to long ago there was a project I was told about which was a RPG game built similar to minecraft. The game generated the map as the player played, so as the player walked around the map the new areas they entered were actually being created. I find these seperate concepts to be interesting, I haven't played around outside of simple things very often and I feel like I need to begin being more adventurous with my programming. I am thinking about making a dungeon crawler using some form of map generation and I am hoping we can spark a conversation on why one might be better then the other. Performance wise I'm not sure but it seems like BYOND might actually benefit from generation being done at a small level as the player walks around the map. I have seen some games that use full scale generation and there is usually a pretty big hiccup when the generation occurs and this might elevate that. Anybody have anything they might want to weigh in?
I'd say either do small generation (Which could be noticable on a low-end machine) or generate everything at the start, resulting in a bigger hiccup at first but smooth throughout.
In a persistent-world rpg it would make sense to generate the whole world so that the server doesn't lag out during play. It would be really cool however to have dungeons that constantly regenerate new levels, which I first encountered in Wyvern and then later in Zangband. Both games feature a persistent overworld with multiple dungeons, each one generating new floors as players enter them (unless someone is already there).
If I make this it would be single player for sure. The idea of a world that generates itself as you play in the persistant world really makes more sense outside of BYOND. Outside of BYOND you're only generating the items that need to be on screen at one time for view, so It is plausible to include the world generation code as part of that, Since we don't really have the ability to edit those sort of functions with BYOND maybe it doesn't make sense. I just want to make a dungeon crawler to work with generation and possibly learn a little more.

http://opengameart.org/content/32x32-fantasy-tileset

this amazing pixel art set is what has given me the inspiration to play with it tbh.
Ah, my main problem with most tilesets is the lack of movement frames or even other directions for any people/monsters/etc.
In response to Albro1
I think in this case because he just wants to play around with the idea it makes sense to use a tileset like that. Animation, directional movement states, they're not really all that important if you just want to make something. I'd really love to see what he could do with those.
Piecemeal generation is much easier for overworld-ish areas than it is for dungeons - there's much less overall context that needs to be preserved, whereas dungeons need to have corridors going to places and connectivity and suchforth.

Big open world games never have the entire world in memory at once, for obvious reasons. Generating overworld areas piece by piece isn't just a good idea, it's a necessity if you want a big world. You do it by chunking the world into large blocks of tiles and then dynamically generating each block as the player approaches it. Use a technique like this:

var/seed = rand(0, 65535)
rand_seed(seed)


to set the seed used to generate that block, then save the seed for each block - if your generation algorithm doesn't change, now you only need to save one number to generate the same overworld area each time.

Do the generation in the background - it needs to be fast enough that you can generate three chunks in the time it takes for the player to walk from the middle of one chunk to a corner, if you're suitably clever about deciding what to generate and what to discard. There's some art here, rather than just science, in terms of selecting chunk size, how and when to discard chunks, and suchforth.

You'd need to take especial care to make sure terrain features match between terrain boundaries. I'm not sure how Minecraft does it. You can't necessarily communicate terrain information between boundaries because blocks are being generated without every one of its neighbours necessarily being generated. Your options there include generating some kind of coarse world map that guides the chunked generation, or first-chunk-to-a-border-wins (and then you need to save the border information so that both chunks respect it in future).

EDIT: Oh, and if you want to have a look at how other people have done /dungeon/ generation, as distinct from overworld generation, I've written some code that does that: http://www.byond.com/developer/Jp/jp_DungeonGenerator
Evol works based on the concept that only the parts of the world will be generated and used, which need to be used, otherwise they are unloaded and stored in files until the time comes that they are needed.

The concept is very similar to schrödinger's cat. It does not exist before it is observed. This reduces the resource usage in the long run, apparently.
In response to Jp
This is ideal, but unfortunately the way BYOND handles worlds means it's not practical on a large scale.

If you have a 100x100 map, and need to expand it to 150x150, this is fine, it takes a split second. But if you need to keep expanding it, it will take longer and longer to do. Though totally unrealistic, if your world is 5000x5000 and you need to increase it to 5050x5050 it could take a minute or two, if not longer to do this.

Unfortunately, as you make the world bigger, it's size increases and there is no way to decrease it. You might only need a 50x50 area of the map at any point in time, but on a 5000x5000 map you'll always have 4950 other parts loaded into memory. (Fun fact: An entirely empty world in BYOND with a size of 5000x5000 uses over 1.2GB of RAM)

Unless you do something crazy like keep the player at the center of a 50x50 map and move the entire world and create/delete the world as it moves, this is a limitation you're going to run into eventually.


Also, if I'm not mistaken, Minecraft uses Diamond Square, which makes it very easy to generate small sections of a world and seamlessly put them together.
In response to The Magic Man
Well, my system uses 16x16 maps and then expands it by adding more Z levels, which in return are registered in a list basically.

The maps are seamless in their form. Based on the amount of new maps and objects needing to generate it can take a max of 4/10th of a second, but normally 1-2/10th of a second is taken, largely dependent on the generation method, saving and loading is pretty much instant, without day.

Unused maps are saved and then unloaded, although you can anchor certain parts of the world, which need to be loaded at all times. The unloaded map's space gets emptied in the registry and then a new map can be loaded in the very same space.

For example: Map gets loaded onto Z level 4, it hasn't been in use for a minute (random time span), it gets unloaded, items/objects on that level get deleted. Player enters an unloaded area, the map gets loaded onto Z level 4, the turf gets generated/loaded and objects/items get placed over the map.

Based on this system you pretty much walk off the edge of the map and jump between Z levels instead of being on a huge map. You keep recycling the maps and it keeps memory costs very low. You can also make the system relocate maps from one Z level to the next so it can transfer higher level Z maps into lower and empty up space.

For example: Z levels 1,2,5,8,9 are in use, which means 9 levels of the map are currently in use even though only 5 of them are used by players etc. You run the relocation function, it will transfer level 9 to level 3 and level 8 to level 4. After that it will set the world.maxz to 5.

While yes it is kind of annoying to have the player constantly walk off the map to a new area etc, it can also be used to make a unique styled map and give the world a different feel. By understanding the limitations of the system, you can take advantage of it's possibilities.
In response to Taitz
That's a very interesting system. I didn't consider the possibility of loading map chunks using Z levels. Switching the Z level should be a much faster method than constantly relocating everything and resizing the map. I'm sure that there would be some lag from parsing the locations of everything, but if you want a truly gigantic, or even limitless world map, then it may be worth it.

However, I can imagine the code base for a system like that would be quite massive and complex. You would also probably want to abandon Dream Maker's map editor in that case, and just make your own runtime mapper, which would also likely be just as complex, or more so than the Z level parsing system. Either way, someone is going to make these kind of systems eventually. I think DM development is moving into a new age of runtime development. This is similar to what Spirit Age does already. I suspect that Dream Maker's time in BYOND is limited. Once we combine all the necessary systems to do everything Dream Maker does and more, all at runtime, it will simply fade into the background, as we blur the boundary between net dream and net reality.
In response to Multiverse7
Actually yes, I no longer use the Dream Maker's mapping function and do everything on run-time, it is one of the methods to speed up the creation process and yes the infinite world thing works completely. I have done experiments where over 700 actual maps were saved and.. they could be called and loaded at any time and place.

I wouldn't say that the system is overly complex. You can also generate multiple realms parallel to each other and each of them having a unique world generation format. This method also enabled something like housing creation, in terms of bigger on the inside. One tile on the map, but larger on the inside etc.
In response to Taitz
Taitz wrote:
Well, my system uses 16x16 maps and then expands it by adding more Z levels, which in return are registered in a list basically.

The maps are seamless in their form. Based on the amount of new maps and objects needing to generate it can take a max of 4/10th of a second, but normally 1-2/10th of a second is taken, largely dependent on the generation method, saving and loading is pretty much instant, without day.

Unused maps are saved and then unloaded, although you can anchor certain parts of the world, which need to be loaded at all times. The unloaded map's space gets emptied in the registry and then a new map can be loaded in the very same space.

For example: Map gets loaded onto Z level 4, it hasn't been in use for a minute (random time span), it gets unloaded, items/objects on that level get deleted. Player enters an unloaded area, the map gets loaded onto Z level 4, the turf gets generated/loaded and objects/items get placed over the map.

Based on this system you pretty much walk off the edge of the map and jump between Z levels instead of being on a huge map. You keep recycling the maps and it keeps memory costs very low. You can also make the system relocate maps from one Z level to the next so it can transfer higher level Z maps into lower and empty up space.

For example: Z levels 1,2,5,8,9 are in use, which means 9 levels of the map are currently in use even though only 5 of them are used by players etc. You run the relocation function, it will transfer level 9 to level 3 and level 8 to level 4. After that it will set the world.maxz to 5.

While yes it is kind of annoying to have the player constantly walk off the map to a new area etc, it can also be used to make a unique styled map and give the world a different feel. By understanding the limitations of the system, you can take advantage of it's possibilities.

This method requires your view to be fixed, yeah?
In response to Taitz
This isn't really open world though is it? It's just a lot of small maps you move between.

This is the difference between a town in Morrowind, and a town in Skyrim. Morrowind towns are part of the world and seamless. Skyrim towns are their own little map which you have to enter with a loading screen that is not physically connected to the rest of the map. It's not a seamless world if it has seams.

Also, 700 maps at 16x16 isn't actually very big. It's about 423x423. I've been playing a game recently that has a map about 25000x25000 in size. That's 2,441,406 maps at 16x16.
In response to The Magic Man
What game?
In response to FIREking
Haven and Hearth. The map is probably a lot bigger than that now since every now and then the world is made bigger (and past worlds have been a lot bigger).

If you want an example of how big it is. The game has over 1000 people playing at a time, and it's been over a month and the large majority of the world is still unexplored.
In response to The Magic Man
It is open world, you can continue to walk in one direction for hours without finding an end. What I was saying that it handled 700 16x16 maps with very little memory usage allocated to it, it could easily go up to a few thousand and way past it, potentially any number of maps, it is only limited by the maximum list length. On of it's other strengths is that the maps don't need to be generated in a particular order, you can teleport to cordinates like -1000000x,9997524y in a particular realm and it would generate it like it would normally at very fast speeds.

The elements, which record data about the map chunks can also hold icons of the terrain, one pixel being one tile in terms of color code, which would mean a dynamic real-time changing map.

@FIREking The view can be fixed or bound to the edge or what not, the size of the map can also be changed to a larger size, I used 16x16 because I liked it like that, that in it self doesn't affect how the world is generated though, all locations remain the same. The locations of objects are defined by a globalized x and y, which can be a positive or a negative number and of course by the realm_id.

Realms in themselves can allow parent-child relationships. For example you can open a new realm at the location -1578,785,Overworld and everything in that world can be considered to be at that very same location in terms of coordinates, when searched by a radar or a sensor or whatever other method.

There are various applications.
If you could make it free scrolling, I think you'd have something, but the view lock is a bit disheartening.
BYOND doesn't exactly support that kind of thing and you can make it semi-free scrolling. The perspective can be set to EDGE_PERSPECTIVE or it can be normal and then use bigger map chunks like 24x24 or 32x32, the generation time goes up, but you'd have some scrolling as well, although completely free scrolling, no.

The only way to do completely free scrolling would cause more resource uses than necessary and it wouldn't be any good at all.
In response to Taitz
But it's not a seamless open world. What you've described is similar to the older Zelda (2D) games. Would you consider them to be open world games?
Page: 1 2 3