the grid

A place to discuss and present upcoming features for the SWG:ANH Server

the grid

Postby Schmunzel » July 7th, 2010, 7:32 am

Grid Implementation

Currenly as a spatial Index we use a quadtree which is linked in as an external library. With current implementation we can query the quadtree for a list of Objects close to us. The implementation will then filter out the requested Objects based on the Object type.

When we are dealing with create and destroy messages we need to keep track of all objects the player knows. Double creation or double deletion of objects need to be prevented at all costs, as this will crash the client.

To this end we query the spatial index for players in *VIEWING RANGE*, create them for us, create us for them (if they are players) and add them to our known objects (or knownplayers)list and us to theirs.

When we move through the world, every set amount of time the spatialindex around us is updated. To this end we query all objects around us and check whether they are on our known objectslist. If they are, they get ignored, if we dont know them we will be introduced (ie created, added to the list etc). last, we will check our known objectslist for objects that are NOT in the current query. They are not known to us anymore (they left viewingrange). And need to be destroyed.

Please note that the knownobjectslist /knownplayerslist of the player is what we use to determine the players world. whether we decide whom to send our chat to, or what players a mob can attack is all determined over the knownObjects knownPlayers list of Object.h

This works nicely with a few problems.

1) To generate and maintain the knownObjects / knownPlayers List we need to do a lot of work. To this end we iterate through lists a lot. This is expensive

2) Currently we do not differ between chatrange and viewing range. This is expensive in terms of packets created.

3) To properly handle containercontent (cell content should only be created when we enter a cell to safe banwidth, as we only will enter a fraction of the houses we will encounter, it can be deleted however as soon as the cell goes out of range) we need a second list ( Ipropose knownContainers) which will keep track of the containers whose content has been created. If such a container is destroyed, the players on the containers knowncontentlist need to be updated. - this will be implemented by me regardless of whether we use grid or qtree.

4) QTree queries are expensive in terms of cpu - the qtree has a high resolution, which will ultimately not be necessary for our goals.


Alternatively we can use a grid implementation. A grid is more or less a a collection of containers which will hold all objects of a square of the gameworld.
To this end we will divide the gameworld into evensized squares with a number of buffersquares at each margin that is slightly bigger than our viewríngrange to prevent us from seeing stuff from the other side of the map.
Every square will have a unique Number and a list of objects AND a list of players (we need performance when looking for players for movementupdates and dont want to iterate through a thousand big objectlist for 10 players).

the size of a single field will have to be a compromise between objectlistsize and amount of managing necessary for the single field.
I propose squares of something around 32m to 40m ; not smaller than 16 however.
As max viewing range is 128 and chatrange 32m (afaik) 32m seems like an excellent choice for me.

This way we have 3 rows of fields around us, which can easily be used to reduce viewing range in highload situations. More on that later.

When we add now a player to a field, we will determine all the fields around this field we have to update based on our viewing / chatrange. The grid will now assemble a list of the objects in these fields and create them for us, or us for them should they be players.

Should we move inside the grid, no updates of players around us are necessary, as we still are in the same field.

Only as soon as we leave the field will we have to determine where we moved to. Basically in this case we will check what fields are now surrounding us, and what fields left our surounding based on viewing range.

The Content of the fields we left will be detroyed for us (or again we for them) and the content of the fields that there added to our surrounding will be added.

Another benefit of the grid implementation is, that it will allow us to power NPCs; creatures Lairs over the grids cpu share rather than the AI managers. This has the simple benefit as to make sure that we do use cpu only on creatures NPCs which are in grids which have player near. Grids without a player in their vicinity would be removed from the grids cpusharelist .
Should a player decide to come near, the grid will be added and creatures in the grid will receive a share of the cpu to determine their actions.
The majority of lair spawns should be handled this way.

1) we need creatures that are handled by the AIManager nevertheless to account for special cases (Old Man, certain roaming Monsters)

2)we should discuss the possibility of having AI methods in a separate thread. - Is this worth the hassle ???? -
Code: Select all
grid for examples sake of 10 by 10 with one square as our viewingrange (if were in the middle it would be reduced to 64 so please note that this is an obviously simple example to explain the principle)

   1   2   3   4   5   6   7   8   9   0
c                    c5  c6  c7
d                    d5  d6 d7
e                    e5  e6  e7

Lets assume our grid has fields of 128 times 128 m. Thats just for (an easy) examples sake.
Player moves from d6 to e6. For us that would mean to destroy the content of d6 - player is out of the field and doesnt see stuff anymore thats in there. We will create content of e6 - thats what the player sees.

In our implementation we will have a viewing range of n grids. With n = 128/gridsize.
so instead of deleting grid d6, we will delete grid (d-n)6 ((d-n)6+(n/2) ... (d-n)6-(n/2))
and subsequently create the contents of grid (d+n)6. Together with adjacent grids. (d+n) 6-(n/2) to (d+n) 6+(n/2).

  • 1) we do not keep known objectslist - to know what is in range we query the gridrange. Everything in the grid will be created.
  • 2) soemthing in the grid gets removed it will be removed for all players in the gridrange
  • 3) something gets added to the grid we add it for all players in gridrange.
  • 4) container contents like cells / items in a house or backpackcontents are NOTpart of the grid
    • all children of objects get created when the parent fulfills certain base requirements, when it is in a certain range.
    • when a container goes out of range and is destroyed all children get destroyed.
      - that raises certain issues - we do not need to create house content for a house 120m away - just cells *need* to be send with the create (otherwise the create fails.)
      so we need a knownContainerList were we keep track of what container had its content created - when said container gets destroyed we query the knowncontainerlist and destroy the content.
      the knowncontainerlist (or knownobjectslist for containerchildren) keeps thrack of who is watching a container and subsequent updates to the container will affect all players on that list.

      issues to still be resolved
      - do we care that we keep stuff created until the container goes out of range ? - we dont care - clientmemory use ist most likely trivial, the mainissue is bandwidth use on create. keep stuff created - the player might come back
      so in short - create when in create range (say 32 or 16m) and destroy when parentcontainer is out of viewing range.

further benefits is have spawns and creatures be powered by the grid theire in - so a grid can be shut down if there are no players in its neighboring grids
Last edited by Schmunzel on July 9th, 2010, 3:32 am, edited 7 times in total.
SWG:ANH Resident Wookiee :evil:
Posts: 39
Joined: December 24th, 2008, 8:18 pm

Re: the grid

Postby Schmunzel » July 7th, 2010, 8:05 am

1) implement grid code - done

2) hook creates destroy up to grid - in progress

3) hook containercontent creates and destroys in and keep track of containers whos content is known - todo

4) prepare grid for spawnmanagement - todo

5) review listuse in grid listhandling
for xyz
list temp = *getcelllist()
returnlist->splice(it, temp)

getcelllist creates its return with new. temp just gets assigned a new returnlist without deleting the old first. does temp needs to be cleared before continuing ? what exactly does splice do ? the old list might very well be empty after a splice and a cxlear() not necessary?
SWG:ANH Resident Wookiee :evil:
Posts: 39
Joined: December 24th, 2008, 8:18 pm

Re: the grid

Postby Schmunzel » July 9th, 2010, 9:30 am


Implementation of the grid will be nontrivial.
Potentially all major subsystems will need to access lists of Objects in the spatial index.
Examples are:

A moving player will generate every 2 seconds a datatransform message. The movement update must be send to all players in viewing range.

A chatting player or NPC must send his chat to all players in chatrange

A player using a ticket will start a search for a ticket droid nearby. The same goes for most game commands which require a terminal to be nearby (craftin/repairing swoops etc)

A Creature checking whether it needs to attack anyone will check for players in its aggro range.

These gamesystems need direct access to the grid in order to query for objects or players nearby.
The grid will return an Object List where - depending on need (and thus query) - known Objects or known players or both are on.

it will be the subsystems responsibility to filter out the objects of interest.
A preliminary filtering of objects due to type by the grid is possible. In scenarios where speed is important (movement, chat) this should be avoided however, as we would just iterate several times through the same list. Prime example are movement updates.
SWG:ANH Resident Wookiee :evil:
Posts: 39
Joined: December 24th, 2008, 8:18 pm

Return to Feature Proposals

Who is online

Users browsing this forum: No registered users and 1 guest