• Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • By ThunderTwonk
      Hello everyone, I am working on a game idea and since I am still in the process of learning C# and the features available in unity I was hoping some of you might be able to offer me a little insight on things in general for getting started.
      I guess the basic components of what I'm wanting to create would be a Multi-levels management/city builder/rpg.
      The goal is to provide a framework for players to interact with, build in and affect the world both from a 3rd person action RPG as well as a zoomed out 4x style view (This would be something unlocked through gameplay)
       
      As for my questions go I was wondering if anyone had resources that could help me learn.  I've been on youtube as well as enrolled in an online course for basic unity and C# and will continue those but if anyone has any words of advice, a place that has good information and tutorials etc.
       
      Thanks for your time.
    • By Cahit Karahan

       
      Hi, I'm new in this forum. It is honorable to see such communities exist. I would like to share my new game. I did for android with unity. I know the game is a little awkward , but you have to know that this game is from the time when Unity's name is Unity3D  I have made my first game when I was 12. Now I am 22.  I have taken a lot of experience in this process and I can make better games nowadays. I have published this game nowadays but actually this game is very old but also it is very special for me :))
      I have just wanted to retouch and share this game, because it has a very important place for me.
       
      DESCRIPTION FROM GOOGLE PLAY STORE

      It's a special free 3D horror adventure action game for the halloween. Fun with scary sound effects and musics, 3D realistic graphics, you will feel the horror in the deep of your heart. Use your reflex. Totally free adventure. Totally scary horror game. 

      Tamarra, she is a beast from our world. She needs to consume souls from innocent people to stay alive. Story begins, the old Elaris tribe had lost their everything because of this beast who lived in the well. Araknas was the most powerful warrior of the tribe. One day, Araknas's mother was killed by the servant beasts of Tamarra. That's how Araknas's journey to the well begins. Tamara's well is guarded by horrible beasts. Araknas has to pass all servant beasts until he reaches Tamarra.

      Even death at the end is worth the revenge. 
      Are you brave enough to jump into Tamarra's well?

      Survive from witch attacks, clown attacks and many scary creature.

      - Realistic 3D graphics.
      - Scary sounds.
      - Scary musics.
      - Best experience with headphones.
      - A demon cage where you can imprison all the demons one by one
      - The witches do not like help, but they love blood stone. Witch store where you can develop your abilities and get new abilities.
      - Countless beasts.
      - At the end of the well there is a hidden surprise for you.

      *We do not recommend this game to people with clown phobia, spider phobia, or panic attacks.*

      **!!!**Note : This game is an early-access game, we are upgrading new features every day, new beasts, new improvements, as an example online 1vs1 fall on the list, so stay on connect and follow Halloween : Horror Well on Google Play.**!!!**

    • By INFRA
      SCAN. DRILL. SURVIVE.   ISOLATED Release in May 1st 2018   https://store.steampowered.com/app/805950/Isolated/   A game by Jérémie Bertrand Music & Sound Design by Pierrick Querolle *** Our solar system has been invaded by strangers. For the purpose of a possible negotiation, a team of astronauts is sent to the moon. Alas, they are shot before even arriving on the scene. Only one astronaut survives the crash and his only goal will be to go home...   GAMEPLAY   Shoot enemy ships to avoid being invaded. Be precise in your movements, because it's better to lose a bit of life at the top than to lose it all at the bottom. Take out your drill to destroy the stones in your path. Validate your identity to cross the different laboratories. Reach the flag before losing your three lives.   And all that... at the same time! Will you be able to go home? If the answer is yes, how long will it take?
    • By BigJiggly
      Hello! So, I've been the leader of BJP for a while now. I'm a bit bored of taking the role I always take, leader. I was hoping someone out there is looking to forge a team maybe and needs a programmer. 
      I have experience mainly in the Unity engine(C# intermediate) and I have a very small amount of knowledge on Shaders, as well as experience on developing games(usually end up stuck in dev hell) and leading experience from my last team which at one point reached 11 people. I personally love the Unity engine and prefer to use it as it's the development environment I'm comfortable with. 
      I have used Unity for over a year and a few months, I'd consider myself an intermediate at the Engine, but to this day Unity still surprises me. 
      I live in the United Kingdom, I find it a bit strange to work with other programmers as the ones I've worked with tend to leave their code heavily unoptimised and I'm a on the go optimise kind of guy, I also like to get things done quickly.
       
      If you're a new team and need a programmer that has high levels of ambition and strives to maintain the motivation throughout the team, then I'm your guy. I don't care if you're just beginning because I'm all for helping people learn!
       
      To finish this off: I like to get things done and I like to get them done right the first time, if I fail I will do it again and again, etc, until I loose all motivation. So if you're a modeller or an artist, please don't leave me to do all the modelling/art as well as the programming and sound. I do have experience in all those areas but my main power is in programming and I'd prefer to keep it that way.
       
      [If this was posted in the wrong forum, sorry, I don't really know the layout of this website yet]
    • By Alexia
      Hi all,
      A small team are currently undertaking a fairly large game project involving multi-playing, taming and other complex game mechanisms.
      We are looking for someone who is experienced in programming a wide range of mechanisms, more information is on our discord server. It is also a learning experience and we wouldn't expect you to know how to do everything we wanted, but just ask that you would be willing to learn how to.
      If you are interested in joining the (rather long term project) just message me and i'll add you on discord.
      Thanks for your time,
      Alexia 
  • Advertisement
  • Advertisement
Sign in to follow this  

Unity QuadTree: design and implementation question, (n+1)th topic

This topic is 699 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey,

 

I've implemented a QuadTree but I'm not sure if I'm doing it in the best way. Here is my concept:

 

First, the basic design of my scene system:

 

I'm using an object+component system, where the object can be placed in the world but actually does nothing. The objects contain components, eg. RenderableMesh, PointLight, Camera, etc. which are stored by the corresponding system (DisplaySystem, PhysicsSystem and so on).

 

Some components should be structured by a QuadTree (or any other spatial partitioning tree). These are inherited from a class, let's call it TreeElement. The TreeElement is nothing more just stores a pointer to the container node (which can be modified by the spatial implementation only - friend class) and the world-space bounding volume (AABB) which tells us where to put the object in the tree.

 

I'm also using a layer-system. The user can define a custom layer and place objects into it. An object belongs to a single layer. Some components have to be stored per layer (it's only the RenderableMesh for now). This way, the user can say that a camera should render only the specific layers. This is similar to the Unity's solution.

 

And finally, I'm using a simple reflection-system, so I can query the type of a component, like this:

const TypeInfo& t = TypeOf<RenderableMesh>();
// or if I have a pointer to a component
const TypeInfo& t2 = component->GetTypeInfo();

The QuadTree design

 

Because I wanted to re-use the same implementation over and over again I had to make it generic - at least from the component side of view. When I'm rendering the scene, I have to query the visible RenderableMesh components, so it's more efficient to store the different type of components in different containers in the quad tree.

 

And here comes the reflection system. When I'm creating the quad tree, a set of type infos can be passed to the constructor, which stores a <typeInfo, id> map. The size of this map determines how many containers will be created for each quad tree node (referred as node in the future). When querying a specific component (like RenderableMesh), the proper container is selected by this map. Like this (sample code)

template <class T>
void CollectElements(std::vector<T*>& result)
{
    auto it = typeIdMap.find(TypeOf<T>());
    // error handling for invald iterator
    const uint32 typeId = it->second;
    
    // ...
    
    for (Node* node : visibleNodes)
    {
        const Node::Elements& elements = node->elements[typeId]; // <--- here
        
        // ...
    }
}
 
Placing an element into the tree is similar, I have to find the typeId of the component. This whole process made it generic for every component but it's another map search (which is pretty small btw, contains only 1-2 elements).
 
Another problem is the layer system I'm using. Because some components have to be stored per layer, I ended up using a different quad tree for each layer. So if I have n layer, I have at least n+1 quad tree (+1 for the "global", non-layer-related components).
 
The QuadTree structure
 
The whole QuadTree is (re)built when the scene loading is completed or when a transformed object's bound component would be outside of the current quad tree bounds. The rebuilding means to drop all the previos data, create a completely new tree and reinsert all elements.
 
I'm actually using a hiearchial-grid design like in this article (I've found it after I've done with the implementation :)). It costs more memory, but no run-time merging and splitting is required. And with some maths, the tree's node can be indexed easily without recursion when searching for an element's location. However this is not implemented yet, and I'm using a simple recursive search (which works O(log n) I guess).
 
Questions
 
This seems to work but I'm not sure this is the best design.
 
* Should I use a template quad tree class and store only one type of component in each tree?
* Or should I hardcode every type of component in the quad tree?
* Or just use a single container and store the type of the element (component) as well. And when querying, I get ALL visible elements, iterate over the result and filter the components by its type. - this is pretty bad IMHO
 
If I'll use the current design, the same QuadTree class can be re-used many times with a cost of another small map search.
Edited by csisy

Share this post


Link to post
Share on other sites
Advertisement

As I understand QuadTree, it contains object ids or references to game objects, and not components. For me putting a component into a QuadTree is like a grin without a cat. You can access any component through a game object and the appropriate container. This is an extra indirection comparing to your solution, but I don't think it's much slower, especially because it doesn't need to store so much extra data.

 

Of course you can put some convenience methods in the QuadTree which return components, but it should use the game object and the component containers to do that.

 

A small optimization is to store the AABB box besides the game object reference in the QuadTree, it might simplify code and makes it a bit faster.

 

For the layers it's a solution to create a QuadTree for every layer and a common QuadTree containing all the layers. But that sounds like an overkill. Here the best thing you can do is to check which is faster in your case using a single QuadTree or using separated QuadTrees.

Share this post


Link to post
Share on other sites

Thanks for your reply!

 

In the past I implemented the QuadTree to store the objects and not components but things changed. :)

 

An object itself does not have bounds. And if I attach a DirLight component to an object, what would be the AABB of the object? Or if I attach multiple components to the same object, eg. a RenderableMesh and a Collider. The Collider can be "bigger" than the actual mesh which means the two component's bounds are different. This was the reason why I decided to store the components and not the objects.

 

What's about the 1:1 relation of components and quadtrees? I mean to create a separate quad tree for each sortable component? This solution has the highest memory cost but probably the fastest search. But the extra memory consuption is not a big deal IMHO, it's just a couple extra MB at most.

Share this post


Link to post
Share on other sites

An object itself does not have bounds. And if I attach a DirLight component to an object, what would be the AABB of the object? Or if I attach multiple components to the same object, eg. a RenderableMesh and a Collider. The Collider can be "bigger" than the actual mesh which means the two component's bounds are different. This was the reason why I decided to store the components and not the objects.

Since QuadTrees are used for collision detection (object-object, object-line, object-frustum, etc), the collision bounds should be used for placing the object in the tree. That means Collider component will give the position and size of the object that is used to place the object in the QuadTree.

 

Or do you want to use the tree for a different purpose?

Share this post


Link to post
Share on other sites

What's about the 1:1 relation of components and quadtrees? I mean to create a separate quad tree for each sortable component? This solution has the highest memory cost but probably the fastest search. But the extra memory consuption is not a big deal IMHO, it's just a couple extra MB at most.

 

A QuadTree is a storage structure with attention to a partial neighborhood relation. By itself it is totally independent on what kind of objects are stored. Any higher level of abstraction can use (its own instance of) QuadTree to manage its belonging objects. For example, a sub-system that manages the Listener (meaning a simulated hearing) component can check for spatial vicinity by utilizing a QuadTree; the Collision sub-system can manage a set of colliders by utilizing a QuadTree (where a collider itself refers to Collision component); the lighting sub-system manages lights in a QuadTree; and so on. However, in an implementation where separation of concerns are respected, a QuadTree is just an utility used behind the scenes, and there is an instance of QuadTree for each concern. A sub-system provides services on its interface, and whether it used a QuadTree or whatsoever is irrelevant from a clients point of view. Doing this allows to change internal implementations when necessary without impact on the clients.

Share this post


Link to post
Share on other sites

Or do you want to use the tree for a different purpose?

 

 

This tree can be used for selecting the visible objects by the camera or by a point light as well. But of course I'll use the same implementation for collision-detection (when I'll implement one :P)

 

QuadTree to manage its belonging objects. For example, a sub-system that manages the Listener (meaning a simulated hearing) component can check for spatial vicinity by utilizing a QuadTree; the Collision sub-system can manage a set of colliders by utilizing a QuadTree (where a collider itself refers to Collision component); [...]

 

So yea, in short, it would be better to make a separate quad tree for each component. And should it be a template class or a class with a generic "QuadTreeElement" container and statically cast when I query the components?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement