Hi, I recently learned about quadtrees but I have plenty of questions google wasn´t able to answer so if you could help me I would be grateful.
First though, I should explain what I intend to use them for. I would use them for my infinite/very large (millions x millions)-procedurally generated-rolling world (the world loads and unloads around player to give the impression of massive world) game.
I intend to use quadtree to:
A) Search for the correct parts of world to load/unload (square “chunks” of certain size that load/unload everything in them) based on the location of players
B) Contain data of the chunks - Probably structs representing objects in the world
C) Save them in files (binary) with that data and load them back
Is that possible? Are quadtrees capable of those? If not why, if yes, how and by how I mean I have NO idea how to construct quadtree so please help me with code or something. Thanks a lot.
Quadtree is quite suitable for such a solution to your question, but in my opinion this is an unnecessary complication. I think that the default UE streaming system is enough. Each level can contain its own necessary sets of data and at the same time be controlled by one manager. Here I just may not quite understand what exactly you want to do, but it’s just that for a large open world UE already has everything.
In any case, the concept of infinity will rest on the size of the memory, so you need to work not with infinity, but with utilization and data recycling.
Oh so there was perfect solution right in front of me the entire time… Nice…
Well thanks! Thats actually very helpful. As to your question, I mean infitiny like in minecraft. It may not be infitine, but it will 100% be massive BUT I definitelly dont expect players to generate and save the entire possible map, just the area they traveled trough. The map will generate in chunks around the player and those would be saved, so it will be that the map is POTENTIONALLY massive. Do you think level streaming can support that?
Hmm, no. for dynamic level generation by the algorithm streaming will not be the best solution. But what you really need is a world rebasing when the player’s coordinates begin to exceed 1-2 tens of kilometers from the center. Working with generation you will need to base everything on seeds so that you do not have to save the entire structure of the world for the player +for correct synchronization if you are planning multiplayer. In this case, you will need to save the chunks ids and data around the player and the generation seeds for different elements of the world. I have never worked with such worlds before, but this is where I would work. Maybe you will find a more convenient solution for yourself.
Yeah I thought there would be problems after looking more deeply into it, that it is only for pre-made levels. The problem is I want the world to be “editable” (you destroy this tree, its gone forever, you build something, its there forever) and for that I need at least some data structure/saving. I want to save the least possible and get the most out of seeds such as floor like in Dont Starve that serve as basis for the world could be one such thing that really does not save, but objects like buildings etc. I would need to save and load. Any ideas? I am newbie to unreal so everything helps.
Also, just to make it clear, I know things about generating the world, I can make complex mathematical functions that will determine data based on seed and position, creating things like biomes, where trees are etc. and I even have idea how I would determine which chunks should be loaded/unloaded (everything from simple double “for” loop to I-dont-even-know-what). What I need is HOW to load/unload and how to save/load (into file) in a way that separates the data into chunks.
You should look at the documentation about save/load. You need to save asset IDs and their location as cell numbers, also some their data like build state, damage etc - depending on your game mechanics. In UE there is such a thing as a Data Table that you can fill with any objects in the form of structures and get their basic information from there by their ids - you should take a look at this.
Its a list of rows. Each row can contain any type data and references to assets (textures, models etc). You can import/export it as csv (wich support microsoft excel if I’m not mistaken).
Oh I see. Lets say I make a chunk (part of world) one grid, how do I make it store everything in that chunk (the trees, building etc.) if one chunk might be pretty much empty and the other may be choke full of objects to save?
This is a rather abstract question. I do not know the structure of your game, use what suits you - arrays, sets, maps. And I cannot compare the performance of the DT. Performant compare to what? This is simply the most convenient way to store objects data. Of course, you can connect a third-party database, but it will be a terrible complication and will definitely not give a performance increase.