Hi all, we are a group of newbies interesting in game development. we are going to design a large scale real time 3D internet game (actually it is a robot shooting game, so you can imagine it as a 3d diablo/quake like game). as the scale is so large, we think that partitioning of players according to their geometric positions at the game is a better design. that is, split the game world into partitions dynamically. every players belong to one certain partition at a time, where communication within a partition is present. this is to reduce the network traffic, (now, some data could be sent to those needed only, such as controls ..) i am responsible for the design of this part of the game. however, i got no idea on how to implement this design. the major difficulties i face are: 1. since the players are allowed to join at anytime, the number of partition should be able to increase and reduce dynamically. in other words, split a partition and combine several partitions are needed. 2. when players moves to the edge of a partition, it is expected that he/she can see those outside his/her partition. (as there is no physical boundary between the partition at the game) 3. when players moves to one place to another, it is possible that his/her partitions has been changed. so let me summarise the problem as (1)dynamical partitioning, (2)partition communication and (3)partition transition. my friend told me that a quad tree may help to implement this design. as a quad tree can recursively split a game world into its node. so the player position can be easily found. however, i found it quite difficult to solve the problem 2 and problem 3. so is their any advice from you on the implement of this design? is tree structure a good data type in implementing this?? is there any internet resources talk about this??? (i could only find the introduction of BSD tree. but it seems to me that it's only related to graphic object partition, and not related in this type of partition, am i right? if no, pls correct me!) is there any other advices???? thank you very much for your help. it's quite URGENT as i have spent so much time on it already.. >< [edited by - rtigame on January 13, 2003 6:28:38 AM]

newbie, and largescale... 2 words that dont mix

quote: Original post by rtigame

(i could only find the introduction of BSD tree. but it seems to me that it''s only related to graphic object partition, and not related in this type of partition, am i right? if no, pls correct me!)
is there any other advices????

BSP tree, not BSD... I suggest you guys take on some simplier projects and do a little more reading and coding before you try to make this game.

actually we have developed many simple 2d network games. for example, a car racing game, chess game, etc.

what i meant by newbies is that we are newbies to 3d network games.

so any suggestion on that design?

Somewhat of a canned reply but
Real Time Rendering by Moller nad Haines

The Game Programming Gems books are also good.
Tricks of the Windows Game Programming Gurus is also good.

As for actual algorithms for Binary Tree based and Oct tree based designs on the web you aren''t likely to find very much.

Seem though you are wanting a portal engine. This still leaves questions about how you are to store your world but the portal system does what you are talking about, divides a physical area into distinct smaller areas (using doors that are or aren''t there). Unless I''m mistaken (general disclaimer).

Webby

quote: Original post by rtigame
split the game world into partitions dynamically. Every player belongs to one certain partition at a time, where communication within a partition is present. this is to reduce the network traffic, (now, some data could be sent to those needed only, such as controls ..)[sic]

1. since the players are allowed to join at anytime, the number of partition should be able to increase and reduce dynamically. In other words, split a partition and combine several partitions are needed.[sic]

The word your searching for here is scalability. You want your design to run on one machine, or scale across multiple machines if need be. I think you have two options here, you can use COM/DCOM or you can use sockets.

I'd use sockets. Basically each partition would communicate with other partitions via sockets. Should it be required that you farm the partitions out to other machines then you automatically switch from local sockets to networked sockets. The majority of your code doesn't even need to know that you are no longer using local sockets.

I'd recommend that you change your usage of "partition" to something more akin to what it is used for like "AreaComponent". I would assume that each partition handles a certain area of terrain and that given a small user load only a single AreaComponent exists on one machine. Should the AreaComponentManager determine that the user load has increased to the point where another AreaComponent is necessary then I'd create another AreaComponent and have them communicate via sockets.

quote: 2. when players moves to the edge of a partition, it is expected that he/she can see those outside his/her partition. (as there is no physical boundary between the partition at the game)[sic]

3. when players moves to one place to another, it is possible that his/her partitions has been changed.[sic]

I believe that problems 2 and 3 are closely related and can be solved through "windowing". IF you want seamless transitions from AreaComponent to AreaComponent at the expense of possible added latency of commands then make your AreaComponent's area covering responsibilities overlap each other such that a player can be seemlessly moved from one partition to the next whenever the server has ample resources for the transaction.

Here is a case study. When the player is in partition one and reaches the 3/4 mark, getting close to the next area, the AreaComponent will notify the next component (which is overlapping this one) that it should take over the handling of this player because the boundary is close by. Basically the second AreaComponent has between the time it takes the player to get to the end of the first AreaComponent to transition the player to the second AreaComponent.

This method requires that all movement and actions of players in one AreaComponent be broadcast to the AreaComponent that directly overlaps it (I can elaborate further later if you'd like). Theoretically two players could be a few feet from each other but they could be handled on separate machines in separate AreaComponents. I'm sure that eventually one of the players would be transitioned to the other partition but

This means that you'll increase your inter AreaComponent communication via sockets since the AreaComponent spaces will overlap but this shouldn't be a problem if you use a gigabit ethernet. Using sockets to communicate between AreaComponents will require that you develop a message passing protocol so that one AreaComponent can understand commands sent by another, then you have to have a message handler/parser in each AreaComponent.

quote: so is their any advice from you on the implement of this design?

I think I'd use a quad tree to store the player positions.

I hope this helps.

RandomTask

[edited by - RandomTask on January 14, 2003 2:57:41 PM]

quote: Original post by RandomTask


I think I''d use a quad tree to store the player positions.

I hope this helps.

RandomTask

[edited by - RandomTask on January 14, 2003 2:57:41 PM]

thx all.
and dear RandomTask,

would you pls further explain a bit the use of the quad tree in the storage of the player positions?
...as i have got no idea till now ><

what would be the root node and the leaf nodes represent??
and how its use will benefit my design??

RandomTask


[edited by - RandomTask on January 15, 2003 11:02:05 AM]

oh i understand it now, thx for your clear figure.

however, how is it different from my prelimilary thinking, which i got an vector of the adjacent AreaComponents in every AreaComponent Object?

the ''adjacent AreaComponents'' refer to those visually connected to that particular AreaComponent.

would you mind pointing out which one is better? or both of them are acceptable??

sorry that i forgot to mention another thing.

in every AreaComponent object, besides vector of adjacent AreaComponents, there is another attribute: an array of players in that area.

then, it seems to me that a quad tree and a implentation using array is similar, rite?
or i got a wrong idea??

thx a lot!!