Hi all, Would like feedback on how well/badly the below method would work. During initilisation the map areas around the player are pre-loaded. Once the player starts moving I would like it to load up the next part of the map from file seemlessly into the game. So when a player comes into range of the next sector (or a portal to another sector) the engine invokes a "sector" thread to fetch that sector from file. And.... Q: How can I load in a level/map during gameplay with minimum decreases in performance to game play (FPS). A: Generate a linked list of objects to add to the current game world in the “sector” thread. At a point in the game cycle add and remove objects where appropriate. For each linked list the following applies, Loading sectors shall be loaded in a "sector" thread. The linked list shall have 2 mutexs. The first mutex marks that the main program wishes to access the linked listed, the second mutex marks that the "sector" thread is currently writing to the linked list. Before writing a new object to the linked list, the thread checks the first mutex flag. If it is on it will wait to be polled before checking the flag again. If the flag is off then it will mark the second mutex flag as on and write to the linked list. When it finishes, it releases the flag and polls the main program. When the main program wishes to read/write to the linked list, it flags the first mutex flag. Then checks the second flag. If the second flag is marked then it waits until it is polled. If the flag is not marked then it continues with the read operation. When it finishes it unmarks the first flag and polls the thread. In the case of the program, when it makes accesses to the linked list, it does not release it until it finishes with the entire list (i.e. to the point where the state no longer matters) In the case of the write operations it does it on a per object basis since the main program has priority over the write program. Q: What if a player comes into range of a sector so it starts loading, then they go out of range of a sector so it unloads. A: Halt the loading of the sector and unload objects of that sector (unless still in the range of player). Each object is marked with which sector it originally came from so this can be done by transversing the world object list. Implement a border overlap so that a player cannot keep crossing over the point of loading/unloading the sector and hence bogging down the engine with starting to load a sector and halt loading a sector.

What you could do is completly load the level then use oct-trees or BSP trees to determine when a certain part of the level should be rendered. If you wanted a lil bit of fog can be used to hide the farther parts of the level until you are ready to render them. Let me know what you think of that idea. If I have any other suggestions I''ll let you know.

I'm not a Win32 threading expert by any means (I've studied it briefly, and in very little detail) but this might be an idea to consider. If you want to background-load a map (without the pauses that Half-Life has when you move into a new area) then try this: create a separate thread to your game thread. This way, your program has two threads, one which is devoted to your game, one which is devoted to loading a new map.

This way, you can background-load a map without significantly impacting the framerate of your program. After all, a new thread will take a portion of processor time from each thread running, and so your game thread will only lose a fraction of it's time, rather than a lot if you tried to use the game thread to load the map and run the game at the same time.

I just figured out, looking at your post, this isn't what you're asking. I thought you meant background-loading whole maps, but that's not what you meant. My bad. Oh well, I've written it now. It might come in useful, so I'm not going to delete it, I'll just write an answer to your question below...

A BSP with PVS will solve the problem I think you are describing. You are trying to figure out what objects to show when the user walks around, right? Well, forget doing that real-time, even with clever linked lists. All that stuff needs to be done at design time, and executed very, very quickly at runtime to get any kind of decent framerate. Thats where the PVS (Potential Visibility Set) comes in. You need to research spatial partioning techniques. Try gameinstitute's Advanced BSP, CSG and PVS course. It might be what you're looking for...


Coding Stuff ->  [ iNsAn1tY Games | DarkVertex | How To Do CSG | Direct3D Vs. OpenGL | Google ]
Fun Stuff    ->  [ Evil T-Shirts | Stick-Based Comedy | You're Already Here | The Best Film Reviews ]

[edited by - iNsAn1tY on November 4, 2002 4:57:48 PM]

Thanks for the feedback all! Got me to rethinking some stuff and gonna do a bit more research into some areas. Sorry for these posts being quite long ^^ can''t really find a way to squish it all up.

[iNsAn1tY] Isn''t you first point exactly the same as what I said in the first Q&A? Or were you implying something else?

I am already using PVS, etc though I want to do some more reading up on them.

Also, you mentioned the design time and real time issues. I''ve attempted to over come this by instead of loading a sector object by object, loading it as a whole, straight from a compiled map file, and then appending it to the end of the object list. Is this what you mean''t?
[iNsAn1tY/]

hmm. I think I should provide some more information on what I''m trying to do. My aim in this project is to create a FP/3rdP game that gives the illusion of maps of very large size. In order to do this I plan to try and make sections of the map load seemlessly. This also requires breaking maps up into smaller sections otherwise too much memory gets used up between sectors.

-- All objects are in a linked list
-- All sectors (maps) are stored as objects. However, the model information and polygon information are stored differently, and this type of object is processed differently.
-- Every game cycle (or every N game cycles) a list of all objects that are potentially visible, (and portals and the objects that can be seen from them) are placed in another linked list. During rendering this list is used.
-- When considering if a map is potentially visible it is done on a per polygon basis since most of the map will be off the screen.
-- When the user comes into range of a portal, the counter for the sector associated with that portal is incremented (or if it doesn''t exist it is created and set to 1), the sector is then loaded into memory.
-- When the user goes out of range of a portal, the counter for the sector associated with that portal is decremented. If the counter becomes < 0 then the sector is unloaded and the counter freed from memory.
-- Loading sectors (maps) is done by loading the compiled map into memory and appending it to the object list.
-- Unloading sectors (maps) is done by iterating through the object list and removing any objects that belong to that sector.
-- When an object moves between two sectors it changes ownership.


The reason for doing this project is for serveral reasons,

-- When playing a game there is no pause or break so the game flows well. Also, (for me) players don''t get impatient waiting for levels to load.

-- Come up with a method of using large game worlds with minimum use of memory and processor time. Since only need to store information about areas surrounding the player (or in the case of a server, the players. But I''m not worried about servers for now.)

-- Sectors are modular, hence (by using scripting) maps can be dynamic and be different every time you play.

-- Game could be expanded for a MMOG.

Hello.
Loading stuff durring play of the game will not work as expected, unless you load few things.
Loading textures, objects and keeping the play smooth requires that the loading thread to have a very low priority, resulting in loading times of 10-20-30 secconds. I tried this and abandoned the ideea.
If you give a normal priority to the loading thread, you will notice many times that the play is blocked.
I tried on a Duron 900, so... problablly on a very fast computer might work.
But I prefer to load stuff at the begining... takes few secconds... instead of locking repeatlly the game.

Petru, what size areas were you loading? I''m planning on slicing levels into quite small pieces (i.e. a large building at the most)

Also, common textures/models and sounds are pre-loaded at the start of the game.

Here are just some thoughts just off the top of my head. I hope it helps.

It definately can be done without too much performance hit (Dungeon Seige runs well on slower machines)
If you keep things in your map files as precomputed as possible and make each area a resonable size. I think your on the right track. I spent a bit of time working on this im my own engine but never got finished. I had various worlds loading in at initialization of the app and portals between the worlds. In essence this is not far from semlessly loading worlds. If you can travel abitraily travel between worlds loading in the new worlds shouldn''t be much more work (threading issues and ensuring that adjacent worlds are loaded in memory).

If you create some sort of region based data structure to keep track of all your different worlds you can use it to make sure that all adjacent worlds to the one your camera is in are loaded in memory and all other ones are flattened. Portals can be used to move between the worlds that are loaded. In the case if the use travels so fast that he enters a region that is not yet loaded (perhaps you can just bring up the clasic ''loading...'' screen). This should be far and few between because you ensure that all adjacent worlds are loaded. When you move to a new world, then your other thread will unload non adjacent worlds to the one your in and load in the adjacent ones to the current world that havent been loaded. If you precompute as much data as possible like collision data lighting....etc at level build time as opposed to level load time, the second thread should simple be reading the file and instantiating the new worlds with as little computation as posssible.

Keeping adjacent worlds in memory should reduce pop up as well. Textures do take a bit of time to load and propbly hog bandwith as you load new ones on to the game card, so maybe you can restrain your adjacent worlds to only differ from the last by a few textures.

Another possible issue that you should consider:
You would also have to worry about dynamic objects in your world. suppose that there are some things going on in adjacent worlds. When these worlds are no longer adjacent to your current world then they are unloaded. Do you flatten the state of the dyanimic objects an un flatten them as the return the world is loaded back in and do you try to update them for the time that they were flattened?

I''m not too worried about objects resetting when a area is unloaded then reloaded again. Though I have been considering keeping a small list of details about unloaded objects last location and state. But, I don''t think I will implement this until a later stage.

As you say, I want to try and make constant reuse of textures and pre-load the lighting (I''d forgotten to consider lighting ^^), textures and models use a similar counting system to the areas. In that every time an object needs a texture a counter is incremented, and when an object no londer needs the texture it decrements it. if it reaches 0 then it is unloaded. Same with models and standard objects.

As for a region based thing, the information about areas is simply stored in a linked list,

sector, in-range, out-range, loaded(3 states, unloaded, loading, loaded)

Should there be alot of sectors in the game world then I probably need to split the linked list into further linked lists in order to save time while tranversing the list, or even perform a similar action to the sector list (in that when I come into range of a region I load the sector list for that region into memory.)

The other point you made was about hte loading screen. As I mentioned in my last post, one of the aims to to remove the loading screen. In order to avoid having things suddenly appear and dissapear, I plan on giving portals a 2d pre-render of what is on the other side of the portal or some other similiar trick. Though while close to a portal a player can tell it is a 2d image, by the time the player reaches a portal I would hope that the next area is pretty much loaded.

Do you think this would not work? I realise on the odd occasion for areas that require alot of loading the player may acturally run across the 2d image on a portal.