Sign in to follow this  
luzarius

How many tiles was ultima online? How big was it?

Recommended Posts

Anyone know how many tiles a single shard had in ultima online? One more question, how should my game world be represented at the server level? I am making a tile based game and I was using a 2 dimensional array to store data for each x,y tile. If I make the 2 dimensional array too big I run into problems. Luzarius

Share this post


Link to post
Share on other sites
Quote:
Original post by luzarius
If I make the 2 dimensional array too big I run into problems.


Don't try to hold your whole map in an array.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Quote:
Original post by luzarius
If I make the 2 dimensional array too big I run into problems.


Don't try to hold your whole map in an array.


Can you recommend me another technique or point to an article that discusses this?

Share this post


Link to post
Share on other sites
Do not create large arrays on the stack: use dynamic allocation or a std::vector. Chop your map down in smaller chunks which can be loaded and unloaded as appropriate: it'll keep memory usage down. Take a course on data structures. Do not bother with two dimensional arrays: learn to fake it: arr[row][col] → arr[row*row_size+col]

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Do not create large arrays on the stack: use dynamic allocation or a std::vector. Chop your map down in smaller chunks which can be loaded and unloaded as appropriate: it'll keep memory usage down. Take a course on data structures. Do not bother with two dimensional arrays: learn to fake it: arr[row][col] → arr[row*row_size+col]


Thanks man that sounds good.

Share this post


Link to post
Share on other sites
Also - use several small maps that can be loaded / unloaded as required, rather than trying to keep the whole world in RAM at any one time. Keeping everything loaded only really has an advantage if the whole world has players constantly passing through it (where loading in and out can actually cause problems, unless you use a caching system) In practice, it's more likely that your players will congregate in hotspots (around monster spawns etc). Use this to your advantage and read up on texture management - this is actually pretty close to what you need to do with area maps.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Do not bother with two dimensional arrays: learn to fake it: arr[row][col] → arr[row*row_size+col]

*cough* arr[row*col_size+col] *cough* [wink]

Share this post


Link to post
Share on other sites
no way on earth did ultima online use static tile allocation, and I'd bet money that the server side of things didn't even keep a listing of tiles at all, but instead a sort of optimized version of the data, meant to reduce space. Let the player figure out that they are standing on grass, the server doesn't give any concern to it. The server only needs to know when the player has attempted to cross a boundry they were'd supposed to, and where actual moving/movable objects are in relation to eachother. The player can have all the bloat they need to, but you should still only load the map in chunks as was already mentioned.

Personally, last way i did it was to have my map files with an offset list in the start of the file, which specified the starting point and the size of the given map blocks [blocks that were coordinate chunks X by Y in size, or in my case, 32 tiles by 32 tiles in size, which i suppose wold be X by X]. When the player moved sufficiently far away from a block, it was deleted [no reason to keep coordinate 0,0 when the player is over at 198,392], and the new block was loaded up [in my case, using the exact same memory].

Share this post


Link to post
Share on other sites
Quote:
Original post by Evil Steve
Quote:
Original post by Fruny
Do not bother with two dimensional arrays: learn to fake it: arr[row][col] → arr[row*row_size+col]

*cough* arr[row*col_size+col] *cough* [wink]


*cough* *cough* *splurge* When I read row_size I interpret it as row length not number of rows and when I read col_size I think column height (length) not number or columns. Therefore *choke* *choke* I'd stick with Fruny's arr[row*row_size+col]

Share this post


Link to post
Share on other sites
Quote:
Original post by xstreme2000
*cough* *cough* *splurge* When I read row_size I interpret it as row length not number of rows and when I read col_size I think column height (length) not number or columns. Therefore *choke* *choke* I'd stick with Fruny's arr[row*row_size+col]
Ah, that's true. That's one reason I always refer to the number of rows or columns.

Sorry for derailing the thread...

Share this post


Link to post
Share on other sites
A better approach could be memory mapping the whole map. The kernel will handle loading/unloading/caching automatically. The only important factor is to use a chunked format so you get a better page locality. This means cut the W*H map into N*N pieces, like it's done for large images in image editor programs.
Example: map[A][B][C][D] where A=W/N, B=W/N, C=W%N, D=H%N

Viktor

Share this post


Link to post
Share on other sites
In my opinion, memory mapping sucks for real-time applications.

The problem is that the thread that makes the reference has to stall, waiting for disk, before it can make progress. Typically, in games, you want to know that reading a tile out of your map is not going to take 10 milliseconds.

Instead, I would recommend using asynchronous I/O of some form to pre-load map areas that are close to the currently active area, so that the map is always loaded when you need it.

In some OS-es, you can get around the memory mapping problem by "wiring" certain pages into RAM, although it's sometimes hard to tell when the wiring has taken effect -- your management of that becomes as hard as the management of just reading a file into memory, so you might as well stick with the asynchronous or threaded file approach (which is more portable in concept).

Share this post


Link to post
Share on other sites
According to Raph Koster, UO's map was built primarily of 8x8 "chunks" of tiles seeded by a central "egg" which provided natural-looking distributions of resources, splats and other tile properties.

One would therefore assume that the chunks were paged in and out of memory as necessary, and designed to be very lightweight network-wise.

Storing your entire game map in one single giant array is almost definitely a bad idea.

Share this post


Link to post
Share on other sites
Quote:
Storing your entire game map in one single giant array is almost definitely a bad idea.


Depends on how big it is, and how you do zoning or clustering.

Suppose a single zone will never be bigger than, oh, 4000x4000 tiles, and there aren't more than 4,000 tile kinds in a single zone (which gives us room for tile plus status bits in a 2-byte value), then that'll only be 16 MB. Certainly quite feasible for modern computers. In fact, I dare you to create a playable, interesting zone that comes anywhere near 4000x4000 tiles in size :-)

Share this post


Link to post
Share on other sites
is it true the server application only cares about tiles that are boundaries of some sort.. a rock, wall, end of the map, a player, npc..

i'm coming to think i should never create a tile in memory server side if nothing occupies it...

is this thinking correct?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by luzarius
is it true the server application only cares about tiles that are boundaries of some sort.. a rock, wall, end of the map, a player, npc..

i'm coming to think i should never create a tile in memory server side if nothing occupies it...

is this thinking correct?




There will always be scenery in it. And you want the same scenery when you go back to it later.


Look into 'infinite universe' methods if you want to understand more about generating worlds 'on the fly'. Unfortunately a completely random world (like based on randoms seeds from coordinates) wind up being random. To build a cohesive world (like with realistic patterns of continents/rivers/cities/communities) it takes fairly complicated generating functions and manually placed seeds or tuned coefficients (like for fractals -- most patterns are rubbish and the good looking ones are hand picked).

You can have it be generate from standard overlapping templates with variations
for much of the world (ie- most of the ocean surface looks the same...) and a coarse level seed map to control the terrain placement. Specific high detail or specially (hand) detailed areas can be premade and stored in full detail.

Similar to the terrain locations of Mobs (mobiles) spawn points can be based on
terrain features and added as needed (and then evaporate after the player moves far enough away). With complex generator functions, entire towns could be built up when needed -- but if you allow changes caused by players actions, you will either have to save the result data fully or figure out a patching mechanism to recreate the changes made.

Of course with a MMORPG, players are crawling all over the fairly small world so it doesnt pay to do this 'on the fly' building. In future the world may become large enough to require a generating system (at least to fill in fine details that would be prohibitive to store if a large world).



Share this post


Link to post
Share on other sites
[all the information presented here about ultima online is from quite a long time ago, several years, which was when i last played it]

Since this thread is rotating around a specific game, ultima online, it just happens to be the case that 'constant' things, like rivers, oceans, general map forms, dungeons, ect, where all saved in their complete form on the client side. This even goes as far as to say that things like trees, houses, tables, candles sitting on the tables, anything that was considered by the game to be constant and server [or shards in ultima's case] independant, was fixed within the client's version of a given map [these constant things could not be move by the player, many of them could not even be used by the player, only identified by a single click, which showed the objects name, like 'a chair']. Things that were dependant, even if unmovable, were not saved on the client side, but a truely huge amount of the data was saved.

Ultima online had no random dungeons, and as far as i know, entire maps were never transmitted.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by hplus0603
Quote:
Storing your entire game map in one single giant array is almost definitely a bad idea.


Depends on how big it is, and how you do zoning or clustering.

Suppose a single zone will never be bigger than, oh, 4000x4000 tiles, and there aren't more than 4,000 tile kinds in a single zone (which gives us room for tile plus status bits in a 2-byte value), then that'll only be 16 MB. Certainly quite feasible for modern computers. In fact, I dare you to create a playable, interesting zone that comes anywhere near 4000x4000 tiles in size :-)



You mean 4000 x 4000 x 2 bytes == 32 meg......

(just a bit bigger and still within most low end computers these days...)

I actually am doing something like this on a 'create zones on the fly' type system that has a large array of seed values in_mem for the 'infinite universe' style generating functions (precanned static seed data so the land forms have some cohesion....)

32meg these days is only a tiny part of memory (even after Billy Gates Bloatitus has done its worst...)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Peachy keen
[all the information presented here about ultima online is from quite a long time ago, several years, which was when i last played it]

Since this thread is rotating around a specific game, ultima online, it just happens to be the case that 'constant' things, like rivers, oceans, general map forms, dungeons, ect, where all saved in their complete form on the client side. This even goes as far as to say that things like trees, houses, tables, candles sitting on the tables, anything that was considered by the game to be constant and server [or shards in ultima's case] independant, was fixed within the client's version of a given map [these constant things could not be move by the player, many of them could not even be used by the player, only identified by a single click, which showed the objects name, like 'a chair']. Things that were dependant, even if unmovable, were not saved on the client side, but a truely huge amount of the data was saved.

Ultima online had no random dungeons, and as far as i know, entire maps were never transmitted.



They later had a patching mechanism (or maybe even early on as a 'house' changed the clients view and navigation map). Items could be added to the map and the objects were downloaded 'on the fly' as you walked within view (actually it was probably an extension of the code that made dropped items viewable).

I remember watching the delay when large numbers of patch objects -- like on building roofs or inside (they even changed the server code that made items in a house only be transmitted to the player when the player stepped inside a house -- it was slowed people just walking by down so much ).

Later they really overworked that patching mechanism when the added the building block houses (was that 5 years ago??)


The UO mechanism was so stiff that when you entered a dungeon you actually were teleported to a different section of the large 2D array (you can see this on some of the world maps people made).


I am still amazed at what they were able to do with the 2D isometric interface and how little most of the glitzy 3D games actually added. Even though UO botched many things (poor management decisions and wasted efforts like UO2 and UOX) its still was an amazing game.


Share this post


Link to post
Share on other sites
Not entirely on topic, but it was a great resource to me...
The RunUO project has recreated the server side of Ultima Online. You can download the server and run your own Ultima Online game...kinda fun for nostalgic reasons. The biggest thing is that the code is available for you to use, look at and modify. Going thru their code and how they recreated the server is very educational. It was done in C# and requires .NET, however it still reads well and is clearly commented...and if you dont have C#, MS has a free version C# Express to DL and use.
All in all its a great resource and it should help with mapping issues as well as many others that may arise.
So just ask yourself wwUOd...

oh ya http://www.runuo.com is the link

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The largest map in Ultima Online is 6144 by 4096 tiles. It is indeed divided into 8 by 8 'blocks' for performance reasons. The individual file formats for the map is seperated into 3 files:

One file represents the terrain. This is structured in a straight-forward manner, like:
block[map-size-in-blocks] {
int checksum; // deprecated; originally used for dynamic map updates

cell[block-size-in-tiles] {
short graphic;
sbyte z; // altitude / height-map value
}
}

Then, two additional files are used to represent tiles on the terrain, like walls, trees, etc. The first is used as a lookup table into a second, where the actual block data resides. If memory serves, the file formats are akin to:

index[map-size-in-blocks] {
int lookup; // file position, or -1 if there are no tiles in this block
int length; // length of data
int checksum; // see above
}

block[...] {
tile[length / 7] {
short graphic;
byte x; // x and y are offset relative to this block
byte y;
sbyte z;
short color;
}
}



This format is pretty good. There is certainly some room for improvement, for example, x and y in static data could be combined into only a single byte. For the most part, however, this is an efficient implementation. Data locality, caching, and file performance all benefit from a block/chunk system such as this.

I hope that answers some of your questions.

- Krrios

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this