The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

good approach to dividing a world into areas of interest

Suppose you have a client-server game, where the game world has lots of actors - players, enemies, and the like. Each player is a remote client, and the server must inform each client of what the other actors in the world are doing. Naturally, to save bandwidth, you give each player a limited "area of interest" (AOI), and only inform them of what is happening within that area.

My question is, what would be the best way to approach this problem on the server side, to keep track of each AOI and which actors are in it? I'm wondering if there is some method for this that is generally thought best, before I reinvent too many wheels.

For example, my first-blush guess is that one ought to divide the world into a grid, where each grid knows all actors inside it. If the size of a grid square is equal to the radius of the AOI, then only the actors in the nine grid squares around the player need to be considered. Then I suppose one could save CPU by just sending all such actors, or one could save bandwidth by checking the square distance of each actor from the player, but such things would need to be rechecked fairly often and it seems like the multiplies would add up.

I know the answer will likely depend on my hardware/bandwidth requirements, but how would people here approach this? Have people dealt with this before? It seems like there should be smarter ways to go about it than what I outlined above.

Thanks!
game_programmer
Sunday, July 01, 2007
 
 
If most events of interest will be the result of other nearby agents, there are a number of clustering algorithms (see, for an introduction, http://en.wikipedia.org/wiki/Data_clustering) that could be used to dynamically cluster the agents based on their location. Many such algorithms will also cluster heirarchically, giving you the opportunity to provide lower-resolution data or lower-frequency updates to members of progressively larger clusters.
Doug McClean Send private email
Monday, July 02, 2007
 
 
I felt sure there was a whole body of thought on this if I knew what to google. This sorts me out, thanks!
game_programmer
Monday, July 02, 2007
 
 
Assuming that your game-world is navigated in a 'realistic' manner, where the player can move freely about and not move from grid to grid in a 'zoning' way (like Everquest, WOW, etc...)

Since your character has coordinates, x,y and possibly z, it occurs to me that his area of interest (AOI) would be either a radius surrounding the character. To simplify, I'll assume the world is 2D in terms of what actors are in the  player's collection of actors. As the character moves through the world, the coordinates of the player's AOI will also change. That also means that the collection of actors that are visible to the player will also change as the player moves through the world. That is fairly obvious, and I think there aren't too many other ways to deal with it.

The server will have a collection of actors loaded, each with it's own coordinates, what I would do would be to figure out a good algorithm for moving actors in and out of the player's collection. Assuming the game is multi-player, other players will be able to interact with, and probably aggress, damage, etc... So, logically they have their own collections associated with their session, and following that, they will share references to the same actors as other players if they are in the same area.

The work of the server managing those collections is to decide which actors will pop into which session's collection - and pop out again. You also have to consider that every session is constantly hitting the same data as players move throughout the world... and depending on the size of the world and the number of potential actors in it, you wll need to consider how your objects will handle all the load - and that will significantly affect your design decisions.

Other people have found solutions to these problems, who were paid a bunch of money to come up with a good solution. I would look at games that have been around a long time, like Ultima Online, though their source is not public, I believe you can still find the source of a player run server system - NOT licensed by EA, but for educational purposes, I think it is a good example. There are two versions I think, UOX and FUSE, though it's been many years since I have run a server. You should also research shooter type games for source, since they are usually optimized for high-speed, close range interaction with server actors, but it sounds more like you are looking at a MMORPG type game.

Fun stuff! I wish I had plenty of free time to work on such things!
I still code in Delphi
Tuesday, July 03, 2007
 
 
I'd also like to add a couple of examples.

Asheron's Call uses a zoneless system in the sense that you literally can run from one "edge" of the game world to the opposite edge without needing to transition between zones. Teleportation between any two points is instantaneous. Turbine says they accomplished the task by using a avatar-centric cluster based system. The only time two characters are required to be on the same physical server is when they're interacting with each other. If I can't see you because you're on the other side of the mountains, another server is likely keeping track of the objects in your vincity. Their clustering approach will put us both on the same server if there are only a few people in our corner of the world to the extent that one machine can easily accomodate us.

First Person Shooters for the most part work rather differently in that all the boundaries are precalculated...  err... the algorithms I've seen aren't so much "what can you see" but "where are you within this box?"  Anything outside that box is just wallpaper so to speak and the game engine doesn't bother calculating whether you should be able to see (and walk up to) that mountain in the distance or not.

I think the decision on how to define the world is largely a game design issue and a hardware support issue rather than a software algorithm decision. One of the first questions you'll ask yourself when designing the game, is whether you can snipe at someone that you can barely see, or bombard via artillary, someone on the other side of a ridge. If that "technology" isn't available within the game itself, that drastically reduces your sphere of interaction.
TheDavid
Tuesday, July 03, 2007
 
 
@TheDavid

Yes, I see that part all right - my education was in physics, so I see the area of interest much like the border of what's called a "light cone" - the AoI is effectively the limit of event-causality, and so the assumption must be that anything outside the AoI of an event cannot and will not ever know about that event unless I leave behind remains (like a scorch mark).

My worry was more along the lines of: okay, I have 50,000 actors in the world, and player 37 just moved four units west. I now need to know which actors, if any, must be added to the list of actors I'm informing player 37 about.

Like I said my first guess is to divide the world's actors into a grid, but I don't know if there's a better way. Depending on the grid size, I'd be looking at a set of actors where maybe half or fewer would actually be in the AoI I want, and it would be a bunch of multiplies to figure out which.

For those who seem to be familiar with what has been done in other games, do you have any articles handy, or are you going from memory?
game_programmer
Wednesday, July 04, 2007
 
 
A grid approach sounds reasonable to me. You can simply divide the x and y coordinates by the size of a grid cell, and store a 2D array of linked lists containing the entities that are in each cell. It's then trivial to get a list of all cells (and therefore entities) which are close to another one, for example you could iterate through a rectangle of cells.

Obviously if the cells are too small then you will have to iterate through lots of empty cells, and if they are too big the search area will be significantly bigger than intended, so you'll have to find a reasonable balance between the two. You may also find it quicker (and easier) to rebuild the linked lists on each update instead of making incremental changes when things move.

If you want something more advanced a quadtree might be worth a try, but it'll be slower to build and update.

To start with I'd go with the simple option, but encapsulate it so you can replace it if you find performance isn't good enough.
Adam
Wednesday, July 04, 2007
 
 
There are algorithms based on Peano's curves to minimize the cost of calculating relative distances between two points. Maybe they may help you to quickly find out what agents are inside range 'X' from a given agent position.

I quickly googled for this (I originally read about this approach in an old DDJ magazine, in case you want to hunt it down) and found the following:

http://www.edbt2000.uni-konstanz.de/phd-workshop/papers/Bajerski.pdf
Paolo Marino Send private email
Wednesday, July 04, 2007
 
 
Here is the specific issue:

Dr. Dobb's Journal of Software Tools Volume 24, Number 7, July, 1999

Ron Gutman  Algorithm Alley: Space-Filling Curves in Geospatial Applications

----------------------

The example case was an application used to store data for a real estate company.
Among the other criteria, the end product would benefit from queries like "I'm looking for something no more than 50 miles from point X,Y".
The obvious way (calculate the relative distance from X,Y for each house that satisfied other query parameters - like price range) was considered too expensive, and the product was based on a standard SQL engine.

Using Peano's curve, you could obtain a specific "index" (actually a point on the curve) which was trivially calculated at insertion time.

When running the query, you could calculate i1 as the index  of a point as most -50 miles from your desired reference point, and i2 as a point at most +50 miles from it.

(Again this was trivial to calculate given X,Y for your interest point).
 
The resulting query would be something like
SELECT HOUSE from HOUSE TABLE
WHERE ... house_peano_index between i1 and i2;
Paolo Marino Send private email
Wednesday, July 04, 2007
 
 
Well, don't distance check everybody against everybody which is an n^2 problem. Online games at least when I was in the industry used spatial partitioning in various forms, sort of what Adam suggested although keep in mind some adjacent "grids" may be permanently occluded from others even within your maximum culling range and don't need to be linked. We used to build the grids dynamically in the level editor since that kind of linking typically only needs to be done once.
Former_Game_Programmer
Friday, July 06, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz