Large, very VERY large worlds.
Author
We have run into yet another problem, how to make very large worlds, such as 5km squared.
I''m sorry I can''t be more detailed, but here goes.
We are currently using a special map format we made, somewhat like a heightmap.... It can be up to 60km squared large, but the engine can only load 1024x1024 at a time... Anyone have a solution to this? I can''t really explain the technical side, seeing as its 6am and this isn''t my specialty.
Heres an example of what we have
Everquest''s Zone system, you load one zone, can walk around in it, then you go thru an invisible wall, 10-15second loading time, and you''re in a new zone.
What we want
Asheron''s Call''s world, its very VERY big, and has NO loading times in it whatsoever, you can walk from Point A at one ocean, to point B at the other ocean without seeing one loading screen. How do they do this?
(So far the engine is coming along very smoothly, www.lejendz.com/screes.php for an idea of what we have.)
I'm one of the programmers from Lejendz. The main problem isn't the loading time on the client but rather the amount of data transmitted to receive the data of all the new objects,etc. if we tile the terrain in 320m² pieces.
The player would have to receive up to 1.8 kb per second if he is running through the world.
I think that's pretty much, especially if you have a 56 k modem. How did the makers of Asherons Call manage this bottleneck?
[edited by - Daywalker313 on October 2, 2002 9:27:33 AM]
The player would have to receive up to 1.8 kb per second if he is running through the world.
I think that's pretty much, especially if you have a 56 k modem. How did the makers of Asherons Call manage this bottleneck?
[edited by - Daywalker313 on October 2, 2002 9:27:33 AM]
I played AC at one time and wondered the same thing. I think the reason they are able to stream out the map is that the resolution of their heightmap is rather small, therefore the data sent is small enough they can do it over a modem connection. If you ever notice in that game, the first time you enter a dungeon, it takes significant time to download the level. That seems to be just the poly data as the textures are stored on the client. As for the outdoor scenes, data just past the clipping horizon is streamed as the player moves about then cached on the client. Or at least that is how I think they are doing it.
I''ve been wondering about the same problem as I am working something similar. From what I have come up with so far is to store all static data on the client and server. Bascially the stuff that does not need to move, like trees and buildings. Use a spatial algo, like octrees to partition that data for easy frustrum culling. Then use another octree structure for dynamic objects like players, mobs, etc. Then you just send updates to the client about any dynamic entities near them that change.
A cool way (I think as I have not done it yet) to only update clients with objects close to the player is to use a bit of reverse thinking. What you do is a collision test between the player and any other closeby dynamic object using a large bounding sphere that is equal to the distance you want the player to be able to see that other object. Then you add the player to a linked list attached to that object. You also add a decay time to the pointer attached to the other object.
Now as you run your object update loop, if anything changes in an object, you send a message to the players that are linked to that object and decrement the delay counter. If the player moves out of range of that object, then they will no longer be updating the list and the decay timer will count down. When it hits 0, you send the client a delete object message to clean things up. You can also use this list to do AI updates since you will have a list of other nearby dynamic objects.
Using this method, you only need to send info to the client if a dynamic object near them changes. If they don''t change then no message needs to be sent.
Just a thought...
I''ve been wondering about the same problem as I am working something similar. From what I have come up with so far is to store all static data on the client and server. Bascially the stuff that does not need to move, like trees and buildings. Use a spatial algo, like octrees to partition that data for easy frustrum culling. Then use another octree structure for dynamic objects like players, mobs, etc. Then you just send updates to the client about any dynamic entities near them that change.
A cool way (I think as I have not done it yet) to only update clients with objects close to the player is to use a bit of reverse thinking. What you do is a collision test between the player and any other closeby dynamic object using a large bounding sphere that is equal to the distance you want the player to be able to see that other object. Then you add the player to a linked list attached to that object. You also add a decay time to the pointer attached to the other object.
Now as you run your object update loop, if anything changes in an object, you send a message to the players that are linked to that object and decrement the delay counter. If the player moves out of range of that object, then they will no longer be updating the list and the decay timer will count down. When it hits 0, you send the client a delete object message to clean things up. You can also use this list to do AI updates since you will have a list of other nearby dynamic objects.
Using this method, you only need to send info to the client if a dynamic object near them changes. If they don''t change then no message needs to be sent.
Just a thought...
Though its more work could you not code it so that, as an object/piece of the map comes into the clients viewable area (or predicted viewable area) it is sent to the client, the client can then piece by piece build up the map as the player walks around the map. This should decrease the amount of bandwidth your server needs since you dont'' have to send the entire map every time, but only the bits the player sees. When the player returns to the same place on the map, you simply send updates if the surrounding area has changed, if not don''t send any changes.
To save of client memory you can either get it to forget parts of the map the player can no longer see, are out of range or put a timer on each piece of the map so that it will clear it from memory if it isn''t visited after N seconds.
To save of client memory you can either get it to forget parts of the map the player can no longer see, are out of range or put a timer on each piece of the map so that it will clear it from memory if it isn''t visited after N seconds.
I don''t understand why so many people consider this to be a big deal these days. Maybe people are so used to loading screens that anything else must be a wonderful technical achievement. Ultima VII had a very large seamless map for its time (386/4MB days) and the secret comes down to 2 things. Firstly, an efficient data structure. U7 used tiles, and then tiles of tiles. This meant that you had very detailed tiles that could make things look unique when necessary, but you could also group common configurations of such tiles into metatiles. That way, given that many wilderness areas are quite simple, you could send a few screens of terrain data in a matter of bytes. Secondly, you have to stream things in at a reasonable rate. If your ''chunks'' are too big then you''re sending too much at once, and not often enough. It''s better to have a steady trickle of information than nothing for a long time and then a large download.
As for object positions and so on... the 2nd point obviously applies to them too. But there are other ways to optimise things... many object properties don''t need to be sent until the object is close enough to interact with. A little thought and careful coding (eg. Proxy objects) could allow you to defer sending of most of the information for each object until it''s really needed. Static objects such as items can be cached on the client with a ''last modified'' date and only need to be sent if they''ve changed since then.
Finally, all your data can be compressed with something like gzip before it''s sent. Given the obvious repetition in a lot of data, you might get a 50% bandwidth reduction using something like this. Even run-length encoding can help a little in some cases, although it should be tested first.
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
As for object positions and so on... the 2nd point obviously applies to them too. But there are other ways to optimise things... many object properties don''t need to be sent until the object is close enough to interact with. A little thought and careful coding (eg. Proxy objects) could allow you to defer sending of most of the information for each object until it''s really needed. Static objects such as items can be cached on the client with a ''last modified'' date and only need to be sent if they''ve changed since then.
Finally, all your data can be compressed with something like gzip before it''s sent. Given the obvious repetition in a lot of data, you might get a 50% bandwidth reduction using something like this. Even run-length encoding can help a little in some cases, although it should be tested first.
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
I know that UO, AC and EQ already have the map data on the client side. This in UO lingo is called statics. Statics include the land and any buildings that are located within the world. The dynamic objects (again referring to UO) are the only data that is sent to the player. As Kylotan said, an efficient data structure and an optimized algorithm for sending this dynamic data will/should solve all of the issues that you are facing.
Dave "Dak Lozar" Loeser
Dave "Dak Lozar" Loeser
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
