Anyone has any idea on how did they perform a tile based engine that isn''t divided in areas (or, at least, it seems that it''s not). I mean... You can run from the bottom to the top of the map and it will never stop to load another "area". It''s continuosly and I don''t want to imagine they used a 1278932335x2317823831 vector

They probably send just enough so you don''t notice.

Ben
http://therabbithole.redback.inficad.com

I''m guessing since this is an online game, the server sends lines of tiles at the far reach of the ''local'' map radius... ever try running one direction during a lag-fest? Note that the screen is black in a perfect line perpendicular to the direction you''re headed.

I guess this simplifies transferring between servers too, since ALL data must not be transferred to the client at once.

And anyways small, frequent uploads to clients is much faster than bogging modems down with huge chunks of data at once.



MatrixCubed
http://MatrixCubed.org

Ah, an excellent question!

I''ve thought about this problem myself and I''ve come up with a number of possible solutions. In fact, I''ve been thinking about writing an article about it (big maps in general, not UO). I just haven''t written the code yet to prove it works.

First off, I seriously doubt any map information is sent over the wire for UO. I don''t think that would really be feasible. Map data is almost certainly stored on the local harddrive, just like when you play Quake or Unreal.

Some possibilities...

Compression: The UO map is somewhat amenable to this... even simple RLE compression would probably give you a big savings. The map could then be dynamically uncompressed for whatever section you happen to be sitting in. But for the record, I don''t think this is how it''s done in UO.

Meta-tiles: Why do games use tiles in the first place instead of just storing the maps as big huge bitmaps? Size limitations of course. You can define a whole screen with just 20x15 (or whatever) pieces of data instead of 640x480. So then how do you handle a map that is so big even tiles are too granular and you can''t fit them all in memory? With meta-tiles... tiles made up of tiles. A single 8x8 meta-tile can take the place of 64 regular tiles where the same tiles would be repeated over and over again, such as in a big swatch of grassland. I am pretty certain that Ultima 6 used this technique, so it would stand to reason that Origin would think of this again when it came time to implement UO. But maybe not. Read on.

Dynamically loaded map: This one is pretty obvious... if you have a map that is 10,0000 x 10,0000 tiles in size, chances are you can''t fit it all in memory. But you don''t need to. The user only needs to have the *illusion* that he is running through a seamless world. All you have to do is keep loading new map areas when the user moves. The average PC harddrive is plenty fast enough to seek through a file and load up a few thousand bytes of new data several times a second. I think this is probably the technique that UO actually uses, or possibly a combination of these.

If anyone else has some other ideas... please share! I''d be interested in hearing something I haven''t thought of.

-Bryan


Dynamic load from file:

Here''s an even tougher question: How did they implement the seamless server boundaries? Each UO "shard" is made up of several servers... but crossing over from one to another is done quite transparently, unlike Everquest, where it''s painfully obvious.

quote:

---

Original post by Pyabo

Here''s an even tougher question: How did they implement the seamless server boundaries? Each UO "shard" is made up of several servers... but crossing over from one to another is done quite transparently, unlike Everquest, where it''s painfully obvious.

---

I don''t know for sure... but... I think that the server bounderies in UO are seemless because MOBs or NPCs do not exist in these areas. My point is that these are dead zones and if you happen to be being chased by a monster and you run across the sever boundery you will always get away.



<Dak>

This is a problem I''ve been thinking about for some time (seamless area boundaries). The problem is, in our situation, the map data changes occasionally, so storing all the map data on the client''s harddrive isn''t really feasable. They can cache map data, however, but even that becomes invalid..I was thinking something along the lines of including a timestamp of the last time a given areas terrain changed, and the client caches that along with the data, so it can update only if neccessary. However, for seamless boundaries, we do have a problem..

It seems to me that the easiest case would involve the "dead areas" like someone above posted. When a player is near a boundary of an area, it contacts the server owning the bordered area, and downloads the immediate data required (if its not already cached), as well as information on who/what is nearby. Thus, the players "know" whats across the boundary, but the servers themselves are ignorant..all they know is their own area..everything else is empty, as far as they''re concerned. This poses a problem because crossing an area boundary means the player disappeared, as far as the server (and any creatures in it) are concerned..they just fell off the edge of the world. So a player getting chased by a computer controlled "something" can just run to the edge of the area and the creature doesn''t know where the player went (and can possibly be shot up full of arrows or bullets or whatever, standing around dumbly at the border).

The scheme I''m contimplating now is the following:

* The world is carved up into rectangluar "areas", which are
of arbitrary size. A server can hold many of these areas, but adjacent areas are not guaranteed to be on the same server.

* Each area maintains a list of everything "inside" the area, and also maintains a connection to each adjacent area, via a socket. Again, this socket might just be a loopback, but it might go halfway around the world. Periodically, each area polls it''s neighbours and builds a list of whats on the edges.
This may not simply be other creatures, but its anything of importance to the server..players, CPU controlled creatures, possibly resources, etc.

With this scheme, there are no "dead zones" between areas, but it does require some thought on how to efficiently do this. It also has inherent redundancy, because area A stores border info from area B, and area B stores border info from area A, but I think thats OK. Creatures move around quite a bit, so it might want to refresh the entire list every time it polls, while stuff like resources only change when something interacts with it, so it might just send a series of deltas to the querying server.

Anyone have any better ideas, problems with this scheme, etc? I haven''t actually put this into practice yet, so I might have missed something important.

I think that is a good idea, but that the bandwidth required for a well-populated server would be extremely high. UO or similar system could probably get away from this because all of the servers reside on the same 100Mb backbone -- hell, they might even have a dedicated interface just for communication from one server to another.

But to have adjacent areas be "halfway around the world" as you say... well, that would take quite a bit of chatter over slow connections.

If I remember correctly, Ultima 7 (as an example) had 3 levels of tile, namely superchunks, chunks, and tiles. I think there were something like 20 superchunks in the game, each of which was a square collection of chunks. And each chunk was a square collection of tiles. I can see 2 immediate benefits to this:

1) Instead of needing to index every tile individually, and therefore having to use large indices (eg. a short int), there might only be 16 different tiles used within any given chunk, so each tile space only occupies 4 bits (the amount needed to store a number from 0-15). Each chunk could contain a ''palette'' of tiles used within it. This would take advantage of the fact that you''re rarely gonna have more than a certain number of tile types in one given area (eg. snow and sand will probably not be seen together). This means your map data is now fairly small.

2) You only need to store, at most, 4 superchunks in memory at any one time. Usually it will only need to be 1... but when you approach the corners, it could increase. By staggering them somewhat (like brickwork), you can reduce this to 3, but that complicates the calculations. But since you have an easy way of reducing the amount of map data that the player will need to see, you can therefore easily predict what data needs to be sent.

quote:

---

Original post by Pyabo

First off, I seriously doubt any map information is sent over the wire for UO. I don''t think that would really be feasible. Map data is almost certainly stored on the local harddrive, just like when you play Quake or Unreal.

---

Well, you''re wrong here, yet right . Most of the map data is stored on each client machine (walls, trees, grass etc - it''s in statics0.mul or something) while other things such as signs, anvils, player owned houses etc. are stored on the server and thus sent over the network to the client. This is also true for any special scenery the shard might have added (I only suppose this applies to UO shard emulators) but not requiring you to download a new map file.

Anyways, if anyone is interested in how UO works the entire "UO protocol" has been documented. And there are several open-source shard emulators (UOX crosses my mind, that''s also where you can find the protocol documentation).

---

"This album was written, recorded and edited at Gröndal, Stockholm in the year of 2000. At this point in time money still ruled the world. Capitalistic thoughts were wide spread. From the sky filled with the fumes of a billionarie''s cigar to the deepest abyss drenched in nuclear waste. A rich kid was a happy kid, oh..dirty, filthy times. Let this be a reminder."
- Fireside, taken from back of the Elite album