Quadtree or List?

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’.

21

Again a grid might be simpler as it makes resolving the visibility simple. It handles the collisions under the same basic ideas and its easy to implement. It has one more benifit in that the collision grid can be used seamlessly for A* path finding and variants of it that automatically contain weighting information.

A collision grid is very good for maps with a lot of non moving collide-able (static) objects like tons of walls ect.

if however you will have 10,000 ships moving at once that will be a lot of insertions and deletions and then it will suffer unless the grids are much larger then the ships themselves and these ships are spread out. In that case a quad tree will probably be better.

Eliminating broad phase collisions is not even (n) time with a simple grid in fact it can be considered 0 as in no time, as moving the object itself is the only thing that really costs, To say moving into a already occupied grid simply flips a bool and some id and grid number is added to a collision check result list. Insertion consists of adding a object to a number of collision grids or one same for removal and these are usually integer id placeholders to some object.

The grid size chosen makes a big difference for how much can be eliminated in a broad phase check and how fast or slow the algorithm handles moving objects these two factors are usually opposites. Such that tweeking the grid size alone can make a considerable performance difference with a grid.

The jist is simple with grids for both visibility and collisions.

you need to basically define a couple transformation methods.
WorldToMapTileIndex and the reverse
WorldToCollisionGrid and the reverse

you define the total size of your game world.
you define all your objects and tiles in 2d world space by the actual size of your game world.
you define all your tiles by there tile size in the world say 50x50 ect…
you define the size of a collision grid say it’s world size say 125x125 whatever you want.

then

the total number of collision grids is world size / collision grid size.
(you get a bucket xy size to use for a bucket array)
the total number of map tiles is world size / tile size.
(same you get a total x y tile map size for a map array)

to find were a point is in your world, be it a character position or a map tile rectangle.

related to the collision grid space you do the following.
position / collision grids size
related to the tile grid space.
position / map tiles size.

To know what map tiles to draw you need to know the screen width and height.
the scroll position these positions can be found by a camera projection as well.
in a simple version well just increment or decrement x or y scroll values with arrow keys.
so you end up with a bounding rectangle that is your screen to world window.
you find the visible tiles by simply dividing that bounding rectangles values by the map tiles world width and height respectively. To get integer array coordinates in a new looping rectangle to the map array…

You loop that visible map rectangle with a for x and for y loop and draw the map tiles at those stored locations to the screen by (x - loopingIndexRectangle.X) * tileWidth ect… to smooth the scrolling is fairly simple but i digress.

The entire process is very straight forward if you think of all aspects including were your screen is in relation to or within your virtual game world. Which as far as all your objects and even your screen is concerned are the only real coordinates that they all must relate to.

Maybe ill throw together a simple example class and post it.
If you like ?
and
if i have time, though it wouldn’t take long, i don’t know when ill have much free time for a few days.

1 Like
22

Here’s a grid and, in the last paragraph of the readme, a nice explanation of when to chose a Quadtree instead.