Jump to content
  • Advertisement
Sign in to follow this  
caymanbruce

Optimization When I do a spatial partition, how often should I insert/delete entities?

Recommended Posts

For example I have 6000 entities on a 2D map and I want to get about 180 which are on my player's screen. When my player is moving new entities may appear on the map, at the same time some entities or enemies die so they disappear. I used to clear the entire spatial hash and insert everything again a few times a second. But I am thinking maybe it is better to only update those entities that change on the map, the number of changes may be huge though, but still, compared to the number of entities on the map it is still small. I am just not sure if this is worthy or not.

Edited by caymanbruce

Share this post


Link to post
Share on other sites
Advertisement

It sounds like you're mixing up the concept of a spatial partitioning method - which is just an efficient data structure for storing and finding things with positions - with the concept of interest management - which is a system for knowing which entities are of interest to which players/clients/whatever.

The server should have precisely 1 spatial hash / quadtree / whatever, containing all the relevant entity positions. You can use that to quickly determine which entities are of interest. But that data structure should not be attempting to represent any individual player's area of interest, nor changing based on what a player can see.

Most spatial partitioning methods will let you remove an entity and re-add it very efficiently. A simple hash or a grid falls into this category. Some spatial partitioning methods are not quite as effective with that, e.g. kd-trees, and some are in the middle, e.g. octrees. This is the simplest approach, to simply adjust the position in the structure where needed, so start with that, and see if it's performant enough.

If it's not, you might find that you get better results by recreating the whole structure, but that seems unlikely except in some extreme cases.

 

Share this post


Link to post
Share on other sites
13 minutes ago, Kylotan said:

It sounds like you're mixing up the concept of a spatial partitioning method - which is just an efficient data structure for storing and finding things with positions - with the concept of interest management - which is a system for knowing which entities are of interest to which players/clients/whatever.

The server should have precisely 1 spatial hash / quadtree / whatever, containing all the relevant entity positions. You can use that to quickly determine which entities are of interest. But that data structure should not be attempting to represent any individual player's area of interest, nor changing based on what a player can see.

Most spatial partitioning methods will let you remove an entity and re-add it very efficiently. A simple hash or a grid falls into this category. Some spatial partitioning methods are not quite as effective with that, e.g. kd-trees, and some are in the middle, e.g. octrees. This is the simplest approach, to simply adjust the position in the structure where needed, so start with that, and see if it's performant enough.

If it's not, you might find that you get better results by recreating the whole structure, but that seems unlikely except in some extreme cases.

 

Yes I have 1 spatial hash. But what I am doing is for every player I clear the hash and insert everything again and use the player's position to determine the interested entities. I am just being lazy not to look into the performance details when I first implemented it. I find the spatial partitioning method is easy to find interested entities of a player. I used to use a radius-based system to get interested entities but that's more like brutal-force so I removed that. But I guess what you mean is to only insert/delete those players/entities that change their status. How should I use spatial partition correctly? How often should I check the environmental updates in interested region for each player? a few times a second or less, or more?

Edited by caymanbruce

Share this post


Link to post
Share on other sites

You don't need to perform any changes to the data structure "for every player". You should be able to query the hash based on any arbitrary position you give it. These structures are literally just a way to efficiently implement the following query:

List<Entity> FindEntitiesNear(Position x, float max_distance)

The data structure needs updating as objects move; whether you do that via deleting and re-adding, or via some internal method that can make the adjustment, is an implementation detail.

How often you check for updating a client/player's area of interest is a completely separate issue and has nothing to do with the spatial partitioning. That's a choice you make based on your game's needs. Start with once per second perhaps, and adjust if you need to.

 

Share this post


Link to post
Share on other sites

@Kylotan Thanks but I am already doing what you said. Maybe I didn't explain it properly. I did only query based on a player's position. I do not perform the insert/clear operation on every player. I am just worrying about inserting all the entities too many times during game play. For example when my player is moving I find player A is also moving around me, 250ms later when I do a second spatial partitioning by inserting all the entities again into the hash, A is still moving around me. So I am inserting it two times. after 1 second maybe A is still moving in the same region and I am inserting it and removing it 4 times already. The same applies to the foods for example, which are static unless they are removed from the map. When my player is moving sometimes half of the foods on the screen never change, but during this time I have to insert them many times for spatial partitioning.

Edited by caymanbruce

Share this post


Link to post
Share on other sites

"250ms later when I do a second spatial partitioning by inserting all the entities again into the hash" - don't do that. There is no reason to keep recreating the whole structure.

"I am inserting it and removing it 4 times already" - why are you worried about moving a single object a few times in a second, when your computer is capable of calculating and showing showing you something like 100 million new pixels every second?

Share this post


Link to post
Share on other sites

@Kylotan I 

35 minutes ago, Kylotan said:

"250ms later when I do a second spatial partitioning by inserting all the entities again into the hash" - don't do that. There is no reason to keep recreating the whole structure.

"I am inserting it and removing it 4 times already" - why are you worried about moving a single object a few times in a second, when your computer is capable of calculating and showing showing you something like 100 million new pixels every second?

I worry that because I am not inserting only one object. I am inserting and clearing 8000 objects 4 times per second. Maybe that's not a lot for a game but I have no idea because I am building a game for the first time. Now I guess your suggestion is like what I said in my first post, just update/add/remove the entities that actually change, instead of recreating everything again, is that correct?

Edited by caymanbruce

Share this post


Link to post
Share on other sites

Yes. There's no reason to clear the whole data structure. If I was writing bank software I wouldn't build a whole new database every time someone made a transaction.

Share this post


Link to post
Share on other sites

I see the things that worry you.    

I believe you profiled it .... if not, you should do it before trying to optimize.

If it is really a bottleneck of your game  :-

1. Hash is too slow ?

2.  Inserting / deleting causes too much ?

  • try to optimize the data structure instead of trying to reduce inserting/deleting

3. Query every frame is too expensive ?

For me, cache miss always causes more CPU times than "often" hash-query.

Edited by hyyou

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Tags

  • Similar Content

    • By davejones
      I have been doing research into optimising 3d models in 3ds max. There seems to be so many different ways to optimise 3d models. I am unsure which method is the best and have been trying different tools such as the pro optimizer tool in 3ds max. Does anyone know the best way to optimise 3d models in 3ds max? I am trying to reduce the file size whilst maintain a high quality model. So produce a low polygon model which looks like a high polygon model. 
    • By Phanoo
      It's for a 2D game, but the question is broader...
      Let's say I want to have some object (eg. a projectile) interact with some other object (eg. a button) so the projectile thrown by the player can trigger the button. I know there could be several ways of doing this, like the brute force o(n^2) method, the 'optimized' method using a QuadTree or spatial hash... But i thought about another method, and was wondering if it's a good idea or not :
      It consist of iterating two times over the active game object list:
      - the first looks for projectile objects, storing their pointers into some array
      - the second looks for button objects, checking if collision occurs with one of the projectiles in the array
       
      Other specific collisions checks could be done with this method, but that would need multiple pointer lists.
       
      Do you know how old games (like thoses on Genesis, we're talking about 8Mhz cpus...) achieved that ?
      Should I just implement some spatial hashing and checking all the collisions inside the restrained area, avoiding storing pointer lists ?
       
      My levels would have about 1000 objects, i'm not that much concerned about performance since I know how to optimize, but more on finding an elegant/simple way of doing this. I'd like keeping the code small and maintainable.
    • By JoshuaFraser
      Hi and thanks for reading, I have an issue with this reactive crosshair script, everything works fine until I start changing the offset. Give the script a go and you will see what I mean, when I do SetOffset(0f); it doesnt always set back to the origional state, if anyone can spot a fix I'd be super appreciative!
      using System.Collections; using System.Collections.Generic; using UnityEngine; public class ReactiveCrosshair : MonoBehaviour { [SerializeField] GameObject c_limb_prefab; private float center_offset = 0f; private float current_offset = 0f; private float max_offset = .5f; private int number_of_limbs = 4; private float limb_length = .05f; private float limb_width = .005f; private List<GameObject> c_limbs = new List<GameObject>(); public void SetupCrosshair(){ for (int i = 0; i < number_of_limbs; i++) { GameObject line_go = (GameObject)Instantiate (c_limb_prefab); line_go.transform.SetParent (this.transform); Vector3 limb_pos = new Vector3 (0f,0f,0f); //line_go.transform.position = limb_pos; line_go.transform.localPosition = limb_pos; LineRenderer line = line_go.GetComponent<LineRenderer>(); line.startWidth = limb_width; line.positionCount = 2; line.SetPosition (0, line_go.transform.localPosition + new Vector3(center_offset, 0f, 0f)); line.SetPosition (1, line_go.transform.localPosition + new Vector3(center_offset + limb_length, 0f, 0f)); line.useWorldSpace = false; c_limbs.Add(line_go.gameObject); } if (c_limbs != null) { OrientLimbs (); SetOffset (0f); } } public void OrientLimbs(){ for (int i = 0; i < c_limbs.Count; i++) { float rotation_step = 360f / (float)c_limbs.Count; c_limbs [i].transform.RotateAround (c_limbs[i].transform.position, c_limbs[i].transform.forward, 90f + (rotation_step * (float)i)); } } public void SetOffset(float _current_spread){ float offset = Mathf.Lerp (0f, max_offset, _current_spread); for (int i = 0; i < number_of_limbs; i++) { if (offset > current_offset) { Vector3 pos = c_limbs [i].transform.position + (c_limbs [i].transform.TransformDirection (Vector3.right) * offset); c_limbs [i].transform.position = pos; } if (offset < current_offset) { Vector3 pos = c_limbs [i].transform.position - (c_limbs [i].transform.TransformDirection (Vector3.right) * offset); c_limbs [i].transform.position = pos; } } Debug.Log ("SetOffset() offset: " + offset.ToString () + " _current_spread: " + _current_spread.ToString() + " localPos: " + c_limbs[1].transform.localPosition); current_offset = offset; } }  
    • By Woody Stevens
      Hi,
       
      I am looking for a TCP or HTTP networking library similar to Lidgren (UDP).
       
      This is primarily for sending game map data and potentially other large messages from Server to Client.
       
      I do want to keep Lidgren for my chat messages, player position, small fast updates etc. I especially love the flow of data and the library usage in general, so any libraries of a similar style would be excellent. Preferably something open source, free and reliable.
      I also must be able to swap between localhost and an ip address with ease, like Lidgren, as I run a server for singleplayer/mp/lan.
       
      My game maps are similar to minecraft, but it is 2d and only one Z-level, so i'm sending a jagged array of Tile object data (currently only enum TileID.Grass) down the pipe to the Client. Problem is if i'm sending a large map 1024 x 1024 tiles down the to client that's quite a lot of data, and Lidgren is relatively slow to build the writes (before the message is even sent!). It is fine when i'm using smaller maps < 512 x 512 ( xTiles * yTiles ).

      I know about chunking and will look into implementing this later, whilst taking into account the user's position in the world to only send nearby chunks.
       
      An example of my code that can be slow:
      private void WriteWorld(NetOutgoingMessage outgoing) { try { var world = WorldManager.Instance.CurrentWorld; outgoing.Write(world.XTiles); outgoing.Write(world.YTiles); for (int x = 0; x < world.XTiles; x++) { for (int y = 0; y < world.YTiles; y++) { // Write Tile obj data outgoing.Write((int)world.Tiles[x][y]); // <-------- Slow here when xTiles and yTiles are each > 512 ! } } } catch (Exception ex) { // log send error } }  
      I'd love to hear from you guys, especially if any of you have come across a similar challenge.
    • By tromtrom
      I've been doing some research on delta compression (used and described in the Quake3 doc http://trac.bookofhook.com/bookofhook/trac.cgi/wiki/Quake3Networking,), and I'm looking for some clarifications on that topic please if possible.
      I understand that the delta compressed state is the difference between any given world states, meaning that if we store the state of every entity in a world state at every tick, the difference would be only the states of entities that changed between these two world states.
      Now when sending back the delta state to the client, do we go as far as only mentioning the properties that changed? Let's say a character moved only on X axis but didn't move on the Y axis between two states, are we sending to the client the whole state (x, and y) or only the new x position?
      If that's the case and let's assume there are a few more properties that describes a character, how can the client identify which properties have actually changed when rebuilding the information from binary data.
       
    • By Dave Haylett
      Hi.
      I have pulled in five NuGet packages for my Visual Studio 2017 project, however when I build the project, VS spits out 10 .DLL and .XML files in the root of the binary folder, to do with the packages. Can't I shove them into a \packages folder so the user doesn't see these ugly resources next to the .exe file?
      I've Googled moving the packages but the only responses seem to be around moving the installation folder of the NuGet packages on the local machine, as opposed to where VS builds them to.
    • By Scouting Ninja
      So I have hundreds of moving objects that need to check there speed. One of the reasons they need to check there speed is so they don't accelerate into oblivion, as more and more force is added to each object.
      At first I was just using the Unity vector3.magnitude. However this is actually very slow; when used hundreds of times.
      Next I tried the dot-product check:  vector3.dot(this.transform.foward, ShipBody.velocity) The performance boost was fantastic. However this only measures speed in the forward direction. Resulting in bouncing objects accelerating way past the allowed limit.
       
      I am hoping someone else knows a good way for me to check the speed with accuracy, that is fast on the CPU. Or just any magnitude calculations that I can test when I get home later.
       
      What if I used  vector3.dot(ShipBody.velocity.normalized, ShipBody.velocity)?
      How slow is it to normalize a vector, compared to asking it's magnitude?
    • By macmanmatty
      I have   spirtes that will be turned into animation images  for  the game actors.  What would be the best way to change the weapon / armor for each actor?  IE walking with sword swinging sword  then when he equips axe walking with axe  swinging axe  ECT.  Same for armor? Have sheets with  the weapons and armor and then overlay them on to the base spirte when the user changes the weapon  or have premade sheets  with all of the various combos of  armor / weapons  that the solider can have and then just grab the ones needed for the current selection. I'm thinking the first option is better, but are there any other better ways?
    • By Colm
      Hey all, I've been trying to work out how LittleBigPlanet handles its objects for a while now.
      For those unaware, LittleBigPlanet has a building component where you can build 2D-ish (there are 2 - 16 2D layers that you can build on) objects. There are a number of shaped brushes to do this with, from basic squares and circles to teardrops and eye shapes. There's a decent video showing this off, actually.
      Anyways, I've been trying to work out how this works for a while now. My current thought is that it might be along the lines of storing a list of object corners and then drawing an object within those bounds - this makes the most sense to me because the engine has a corner editor for making more advanced shapes, and because some of the restrictions in the engine are based around corners. Of course, that could also be completely wrong and it's something else entirely.
      What are your thoughts?
    • By Liquifire
      I'm making an small 2D engine using Kha and I have a timer class, which basically simply either waits a certain amount of time to call a function, or repeatedly calls a certain function after every x seconds. I simply want to know if I should have timers run on different threads. I'm aware that makes sense, but I might use many timers in a game for example, would that still be okay? Also I'm currently writing an animation components, which waits every x seconds to draw another image using the timer class. And in a normal 2D games, I would have many objects with animations on them, other than the other timers. So I just wanted to ask people who have more experience and knowledge than I have what I should do for timers: Either leave them on the same main thread, or make them run on different threads. Thanks in advance.
  • Advertisement
  • Popular Now

  • Forum Statistics

    • Total Topics
      631394
    • Total Posts
      2999754
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!