Sign in to follow this  
GlennNZ

Unity How to best organise a world of moving objects.

Recommended Posts

I have a 3D scene with a lot of Mobiles (basically world objects that move all the time) and I'm trying to figure out the best way to organise them so as to speed up collision detection.

I'm leaning towards using a kd tree to divide my game world up into a binary tree of nodes, and then adding each mobile to a node.
- If there is an overlap between the mobile's bounding sphere and multiple nodes, then they go in a parent node.
- Every time a mobile moves, a check is required to see if it is still in its current node, and moved to a new node if required.
- A collision detection test with a mobile (mobA), would require a check between mobA and all the mobiles that are in the same node as mobA and all the mobiles that are in parent nodes.


This is as about as good as I can think of, but am really keen to get some advice before I pour some hours into this.

Alternatively I was thinking about using
- Quad trees
- Perhaps not using the kd-tree nodes as 'buckets' of mobiles but instead making each mobile a kd-tree node, so that mobiles have child mobiles. I figured this would get crazy complex when mobiles moved and the kd-tree would have to get entire branches re-added to the tree.

I see there are lots of good articles on collisions between two objects, but I can't find much in the way of better organising a world of moving objects.
I did find:
http://www.gamedev.net/community/forums/topic.asp?topic_id=434610

Cheers for any tips.

Share this post


Link to post
Share on other sites
I'd recommend a Spatial Hash.

It's efficient enough for dynamic and deformable bodies, thus it works well with normal rigid bodies as well.

For mobile objects, you'd have to first clear the spatial hash. Then update each objects bounding volume (like an AABB). Then rehash each object into the Spatial Hash. That may sound kind of bad but it handles the problem of updating the structure positions for fast moving objects and has an algorithm cost of O(N), which is doable. Once everything is in place, asking the game engine "What is by this point," "What is in this volume of space," or "What other objects may collide with this game object?" becomes an easy and efficient thing to answer.

I did an implementation for convex shapes with AABB for bounding volumes and it's been working well for my broad phase collision detection.

Read the paper and if you're interested in discussing implementation details, let me know.

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  

  • Forum Statistics

    • Total Topics
      628282
    • Total Posts
      2981812
  • Similar Content

    • By ForgedInteractive


      Who We Are
      We are Forged Interactive, a small team of like-minded game developers with the sole purpose of making games we love! We're a team of artists, animators, programmers, level designers, writers, composers, producers, and other creative minds. We want to make games that you, the modern gamer want to play! We hope to build a community that enjoys our games as much as we love creating them. With your feedback and support we will be able to achieve that.

      About the Game
      GAME NAME is a fun, action-packed army builder with unique characters, challenges and engaging levels. Set forth on an adventure to protect friends, family and countrymen from new adversaries. Once defeated your enemies turn coat and join you in your adventures. Players can enjoy a range of troops and abilities based on their gameplay style which become more important as maps introduce more challenging terrain, enemies and bosses. Strong orc knights, dangerous shamans, and even a dragon are out on the prowl. Knowing when to fight and when to run, and how to manage your army is essential. Your actions alone decide the fate of this world.

      Previous Work by Team
      Although we are working towards our first game as a team, our team members themselves have past experience in the industry.
      This includes members who have worked on titles including:
      Final Fantasy Kingsglaive, FIFA, Xcom 2 and Civilization.

      Who are we looking for? 3D Modellers Concept Artists Marketing Specialists Level Designer

      What do we expect? Reference work or portfolio. Examples what have you already done and what projects you have worked on academic or otherwise. The ability to commit to the project on a regular basis. If you are going on a two-week trip, we don't mind, but it would be good if you could commit 10+ hours to the project each week. Willingness to work with a royalty based compensation model, you will be paid when the game launches. Openness to learning new tools and techniques
      What can we offer? Continuous support and availability from our side. You have the ability to give design input, and creative say in the development of the game. Shown in credits on websites, in-game and more. Insight and contacts from within the Industry.
      Contact
      If you are interested in knowing more or joining. Please email or PM us on Skype. Myself or Colin will reply to you within 48 hours.

      E-mail: Recruitment@ForgedInteractive.com
      Skype: ForgedInteractive

      Regards,
      David and Colin

      Follow us on:

      Facebook: https://www.facebook.com/ForgedInteractive/
      Twitter: @ForgedInteract
      Youtube: https://www.youtube.com/channel/UCpK..._as=subscriber
      Reddit: https://www.reddit.com/user/Forged_Interactive/
    • By Eck
      I just saw their courses were knocked down to $10 each and figured I'd share the info here. They have stuff for Unity, Unreal, drawing, business, etc. I haven't used their stuff before, but the previews I looked at seemed pretty good and there is a user review system as well.
      https://www.udemy.com/courses/search/?q=Unity&src=ukw
      - Eck
       
    • By zizulot
      first and only logo , for now
    • By sidbhati32
      I am working on a game in which we control a rectangular box at the bottom of the screen. Three sphere which has alphabets in it fall down. When the game starts, a word is generated from the predefined list of words(which I'll give) and we are supposed to touch the correct sphere having the alphabet based on that word. The question is how to detect if I have touched the correct sphere. 
      secondly, if I have touched a correct sphere before and there is no recurrence of that alphabet in that word then during the second wave the game should not proceed if I touch the same alphabet again.
      Looking forward to your answers, i have to submit this project in a couple of days. please help! (Working on Unity 3D)
      Thanks
    • By NDraskovic
      Hey guys,   As the title says, I'm trying to control a desktop game by using my mobile phone as a controller.  I created two scenes, one that acts as a server, other as a client.    Server has this code: void Start () {         Test = "Nothing yet happened";         NetworkServer.Listen(25000);         NetworkServer.RegisterHandler(888, ServerReceiveMessage);     }         private void ServerReceiveMessage(NetworkMessage message)     {                 StringMessage msg = new StringMessage();         msg.value = message.ReadMessage<StringMessage>().value;         if (!String.IsNullOrEmpty(msg.value))         {             Test = "Message received";             string[] deltas = msg.value.Split('|');             Horizontal = Convert.ToSingle(deltas[0]);             Vertical = Convert.ToSingle(deltas[1]);             TestScript.MoveForward(Vertical);             TestScript.RotateAroundY(Horizontal);         }         else         {             Test = "Nothing received";         }     }  
        And client this:  private void Connect()     {              client.Connect(IPAddress, 25000);           }     void Start () {         client = new NetworkClient();         Connect();            }         void Update () {    #if UNITY_ANDROID         MobileTouches = Input.touches;         if (MobileTouches.Length > 0)         {             for (int i = 0; i < MobileTouches.Length; i++)             {                 if (MobileTouches[i].phase == TouchPhase.Moved)                 {                     Horizontal = MobileTouches[i].deltaPosition.x;                     Vertical = MobileTouches[i].deltaPosition.y;                 }else if(MobileTouches[i].phase == TouchPhase.Stationary)                 {                     Connect();                                  }             }         } #elif UNITY_EDITOR               Horizontal = Input.GetAxis("Horizontal");         Vertical = Input.GetAxis("Vertical"); #endif         thumb.Translate(Vector3.up * Vertical * Time.deltaTime);         thumb.Translate(Vector3.right * Horizontal * Time.deltaTime);         SendControllerInfo();     }     static public void SendControllerInfo()     {         if (client.isConnected)         {             StringMessage msg = new StringMessage();             msg.value = Horizontal + "|" + Vertical;             client.Send(888, msg);         }     }  
        Ip address is hard coded, I just replaced it with the "IpAddress" variable. The code itself builds fine, and when I try to run in on a desktop computer, it works as expected (just a simple movement of an object on the server screen). However when I try to publish the client scene to a mobile device (Android), it doesn't connect to the server. They are both connected to the same network. Can anyone tell me what the problem might be?   Thanks
  • Popular Now