That simplifies things alot.

> 1. What is an efficient method of implementing a "map" such that the locations
> of all objects and players on the map are kept track of.

For tile based games, it's usually just an array of structures, maybe with a linked list of objects on the square. For 3D games, you'll need some sort of BSP tree. The format of the data is pretty much up to you.

> 2. When an event or a change on a part of the map changes, how will we determine
> which players need to be sent data notifying them of the change?
>
> 3. Similarly, how should we send map data to a player when he or she moves to a
> new area?

There are 2 ways to do this: players know what goes on everywhere on the map (lots of unnecessary messages for remote chagnes) -or- players know only what goes on nearby (and need to access the server as they move through the world).

In both cases, tho, you'll need to send an update to every nearby player so they can draw the change.

You should check out http://www.codewhore.com for lots of documents on network game design.

In 3D the coordinate system has lots of coordinates. 3D usually uses floating point coordinates to determine the position of an object. When redrawing at some number of frames per second it is possible for an objects position to change during every frame. Communication of the position of every object to every other object every frame consumes a tun of bandwidth. This is why Doom could only handle 4 players in its network modes during the first version.

The problem is resolved by increasing the time between broadcasts of position data to other objects. Bandwidth goes down and the clients effectively sample the position data over time of other objects. Since this is a sample of data it is bound by all of the rules of statistics and is prone to error of some percent.

We have achieved the bandwidth reduction we are looking for but the outcome was that you could never be sure where objects were on the client side because of statistical probabilities. This is where prediction algorithms come into play. The client takes not only position data but speed data and vector data. An object moving on vector PQ at a given speed will arrive at Q in such an amount of time. Comparing that time to the refresh time allows us to extrapolate where the object should be at all points between PQ for any time t. This works wonderfully as now the position data can be generated by the client and interactivity with the object increases as statistical probabilities decrease.

The drawback here happens when the object on vector PQ decides to change to vector RS which is some angle off of PQ. If this event occurs before the broadcast time to other clients then the clients prediction algorith thinks the object is at Q after time t when in fact it is following vector RS and no where near position Q. Solving this is finding the balance between your bandwith restrictions, the broadcast interval, and a myriad of other pieces of information. I hope this helps you see the problem. There are ways to speed this up, some are effective while others are not.

In the 3D world flagging objects as immobile allows prediction algorithms to always correctly position the object with respect to its position on the server.

Having the broadcast interval shorten as a user gets closer to the object is another way to decrease the percent error of the prediction algorithm as compared to the server.

Less acceleration and more constant speed helps the prediction algorithm tremendously. The faster the object moves the larger the real position error can be over a given time. Acceleration is speed over time over time and since time is the problem in the prediction the percentage of error rises when time is factored into the equation twice. Acceleration and deceleration only exascerbate the problem inherent to the prediction algorithm.

When you see this problem to its fullest you will have a new appreciation for what games like Quake, EverQuest, Asheron's Call, Ultima Online and others are doing. Again I hope this helps you out.

Kressilac
ps If you have questions please feel free to email me. I will try to help as much as possible. Geometry books and Physics books can help the Vector math and acceleration/speed math as well.

------------------
Derek Licciardi