Quadtree or List?

1

Lets say you have a big gameworld with 100000 enemies or objects spread all over the world.

To have a better performance you will only draw/update enemies which are in the viewport.
You will have much more perfomance when doing this, but you still have to go trough 100000 List Elements and check each of them if their position is inside your current visible area.

This method works fine but would it be better to use a Quadtree for such a scenario?

As far as I know Quadtrees are like BinaryTrees just with Rectangles(Quads) and the whole world is divided to some Quads and you check only those Quads where your visible area is instead of going trough the whole list?

2

Having 100,000 enemy’s Updating each frame within the view is going to be THE performance problem. A quad tree or any spacial algorithm will still need to store all those objects be it in a list a array ect… It will need to access and make insertions and deletions per movement of each object.

This said quadtrees spacial hashes grids and such minimize collision checks by a enormous amount. That is the purpose of them and collisions with that many objects without some sort of collision grid quadtree or the like will be very poor performance wise. The one you choose and in some cases such as a grid, it is typically tweeked to the type of game or simulation you are designing and its constraints or specifications.

1 Like
3

I completely agree with Will Motil’s assessment with an additional caveat.

No matter how you design a confrontational game as you describe yours to be, all such “enemies” as well as player entities will be supported by a single or possibly multiple object structures for each. All simulations are designed this way as is any type of confrontational type of game. The object structures store all the necessary data in a compartmentalized form.

Object structures will take up quite a bit of memory, even if virtualized, and as such will yield a declining level of performance no matter how you store such data as the numbers of such entities increase dramatically. This is just as true for in-memory representation as it is for disk-based storage.

In this case you may be better off considering a high speed object database that also has in-memory capabilities, which will be separate from the applications space.

I have just gone through a design phase for the storing and accessing of 4000 hexagonal objects representing my map-board and it took me over a week of tinkering and refining an idea into a somewhat efficient concept just for this aspect of my own simulation. The addition of AI for the computer-based opponents will most likely have an underlying RDBMS supporting therm out of necessity.

The most efficient technique, at least in the .NET world, for storing such data other than a list appears to be the dictionary, which in the .NET environment, is a generic disallowing the need for boxing and unboxing objects as a result of typing determinations.

Though I am hardly knowledgeable of QaudTree structures, finding what appears to be a decent explanation of them with C coding examples on Wikipedia (https://en.wikipedia.org/wiki/Quadtree), you may also want to consider the use of the B+Tree, which is probably the most efficient tree structure ever designed. All RDBMS database systems use B+Tree or its variants. Like the QuadTree, standard BTree lists are limited to only two leaf nodes (if I remember my structures correctly), while B+Tree lists can have up to 12 or 24 leaf nodes (I cannot remember which).

In any event, years ago back in the 1990s, a good friend of mine (he was a genius level developer and an internals specialist) took Borland International’s Turbo Database Toolbox, which was based upon a B+Tree design (surprisingly all of the source code for this ISAM database system was made available with its purchase at $65.00 USD) and did internal comparisons and bench-marking with some of the most powerful database algorithms available commercially, including the then very powerful FOCUS database system (his brother was technical representative of the company and so was able to get the source code to study). My friend found even to his amazement that the Borland algorithms created by college graduate students was the most efficient and fastest of them all.

1 Like
4

Thanks for the replies and the great story.
I don’t really have that much enemies, but just wondered how I would handle so many objects.

Big games like World of Warcraft are using Databases too. I’ll check the B+ Tree and play around a bit…

5

A spatial data structure is definitely a good idea in your case. I’d recommend trying to use a grid first, because it’s very easy to implement and in many cases better than a quad tree (because of management and lookup overhead). I don’t think it makes sense to use a B+tree. I don’t see how you can split up space with it (it’s not a spatial datastructure).

6

I’ll just use zoning technique on this case : - D Say your world game have 1 million zone : - D and I’m on Zone02 and on that zone has only 5 enemies… just load and draw what ever content on that zone and the 5 enemies entity ^ _ ^ y If u play Ragranok or other MMO if you leave each zone there’s always a loading splash screen.

7

I don’t really have that much enemies, but just wondered how I would handle so many objects.

…

A spatial data structure is definitely a good idea in your case. I’d recommend trying to use a grid first

I agree if you have few objects that are enemy’s and tons of static collidable objects like walls and such. A spacial grid is great not just because its straight foward to implement and understand. Also because as a enemy moves into or is inserted near a occupied spacial grid you can add that object to be checked for collision to a list of objects that must be checked that list may have a last alive item marker allowing it to minimize its own checks. Basically allowing its checks to be linear to the number of objects that actually only have the possibility of colliding.It is nearly a collision check on insertion for only moving objects. All static (non moving) objects can be excluded in the general sense.

8

The original concern was the efficiency of the draw routine, which in this case would require an internal search. Thus the query regarding the QuadTree algorithm is an understandable one.

Not being knowledgeable on such a search processes I suggested a B+Tree algorithm, which may be better suited for the efficiency of such searches. I only recommended this as an alternative from my own experiences with using it and the experiences of a good friend years ago.

The recommendation for using some level of a spatial database may be a good one if StealthKitty was concerned about searching through some type of geographic data. However, his concern appears to be only the need to check if an element is within the boundaries of the currently visible display, which is how I interpreted the statement of a current visible area.

If an entity or object is within the space of the user’s display would it not be simpler to add an attribute to that entity’s structure such as a Boolean indicator as to whether or not that entity has fallen within the bounds of the displayed area? This can be just as easily done with B+Tree algorithms without getting into the complexities of spatial database processes, could it not? By holding a mini-object within the leaf of a tree it could also have an attribute that references the entity’s unique key so that if further data was required the entity’s full data structure could be looked up.

9

Performance is tied to knowing a lot about what kind of game or scene you will have typically and the extent of the possible edge cases plus the level of culling required. So more information is required, then given.

If this is indeed a 3d visibility question then i would recommend you browse this page to get a general sense of some of the terminology involved in 3d visibility culling. In 3d octrees are used instead of quadtrees typically but there are many options.

https://www.researchgate.net/publication/220061856_Occlusion_Culling_Algorithms_A_Comprehensive_Survey

10

@willmotil

I took a look at the PDF your notes referred readers to.

I can see why you would suggest such a recommendation considering that there are enough algorithms presented in the paper to solve the majority of topographical issues. :relaxed:

However, admittedly I find much of the information somewhat over my head as it appears to require quite a bit of advanced mathematics to understand a number of the algorithms. And though I wanted to major in a mathematics-based discipline when in university I needed either great texts or great teachers. Back in the 70s it was very likely that the classes would have neither so I never got beyond university advanced Algebra and trigonometry.

Aren’t your notes more concerned with the displayed objects touching upon static entities in the viewable area whereas StealthKitty is asking how to determine in an efficient manner what player and enemy entities are actually visible to the user?

11

more information is required, then given.

it’s not my post not much effort is needed to respond this is academic until we have a more solid scenario one step is not that far from the other the burden is upon the poster to reply.

12

Hi guys,

I have a huge 2D Tilemap with lots of objects/enemies all around the world. Like Trees, Ores and other collectibles.

I wanted to divide the map in Regions and just check the Objects in the region where the player is. I think I would save lots of checks like this.
Just Divide the map by 2, then the next layer of the tree again by 2 and so on.
Then I would check if the player is on the left half of the map i would go to the left part in the tree and search further.
Every region has a own List with objects.

sketch.png800×490 11.3 KB

I also found the R-Tree https://en.wikipedia.org/wiki/R-tree which works similar i guess.

13

I have used both quadtree and octtree (depending if the objects were mainly in a 2D plane or we needed the full 3D partitioning) in commercial console games for just such a thing. They are very efficient and simple, and well suited to this situation.

1 Like
14

Is it fine in regards to moving objects? It can be a pain to handle them or slow

15

Each leaf node contains a list of objects within that node. If an object moves outside the bounds of a node, it can be removed from that node and added to the neighbouring node. Depending on your use case, large objects may even temporarily be members of two nodes as they straddle the boundary between nodes.

1 Like
16

I use this type of structure all the time. Don’t know the terminology as I gave up maths at ‘O’ level!

Basically an intersecting grid, each grid square gets divided into another ‘x’ grid squares (configurable) until you reach a defined smallest size (again configurable). The smallest grid square contains a list of enemies (or whatever) within it. Sometimes I’ve found it can be beneficial to make the edges of the grid squares overlap. Used simple linked list structures and avoid enumerating with foreach as this can be really inefficient.

Often enemies will have some kind of ‘roaming range’ that takes them outside of any particular square, this means a single enemy can ‘belong’ to more than one grid square (so you have to make sure it only gets updated once per frame).

And there may be certain enemies that can roam the entire map. There’s no way round it but to update these every frame, or possibly only update them when they’re within a certain distance of the player.

I was able to run large game worlds with this type of approach even on really shitty systems (ie old java mobile phones). You’d run out of memory for the objects before you’d hit performance problems with the updating.

1 Like
17

"I wanted to divide the map in Regions and just check the Objects in the region where the player is"

Why use Player position? I would rather use your 2D CAMERA rectangle coordinates where it is in the map region, as I’ve done on my Isometric Tile Manager, when 2D CAMERA Moves it knows what to draw whatever the size of the map and it knows how many tile to be drawn base on screen-size and tile-size and what object are drawables on that region.

18

From what I read in the past / xna days, retrieving the object in the octree was one of the cons (needed a sort of ID), so reassigning it to the neighbouring node and finding the right leaf was (depending on the depth too).

Maybe with a quadtree it is ok, but concerning an octree, with a lot of moving objects (~10000 spaceships) and a few ms (~2ms in my tests 2 years ago on an “average” computer) to resolve the movement of one object in the octree can become a bottleneck, even with multithreading.

19

That is basically a quadtree you have described there, with the extension of overlapping leaf nodes to allow an entity to only occupy one node while moving, even when crossing a boundary.

It all depends on your data structures. The quad/octtree is not intended for looking up an object by ID. It is intended for finding a collection of objects within a specified area. You can have a separate dictionary to look up an object by ID or by name if needed. An object can have a reference to its owning leaf node if desired.

2 Likes
20

Adding things can be expensive, sometimes I do something like add everything I need at the beginning of the ‘level’ and then activate them (or make them visible or whatever) as needed. Sometimes I’ve kept references to the smallest ‘nodes’ (ie the ones that actually contain the enemies) in a 2D array which can make accessing a certain node for ‘add’ operations much quicker.

Personally I’ve never found the need for adding/removing when things cross boundaries but I can see scenarios where this could be useful. In this instance I’d probably add the enemy to a list of stuff that needs updating every frame when it becomes ‘active’ (remove it from the tree) and only return it to the tree when it becomes inactive.

There’s tons of different ways to tweak it, you can even use different structures for different enemy types within a level - not necessarily a need for a ‘one size fits all’.