Finding the sprite nearest a sprite

[ForgeableSum]

I know posting to this forum is pretty much a hopeless cause as all I get are cricket chirps these days, but I wonder if anyone could shed light on this topic. 

Currently, the easiest way, that I can conceive of, to find the nearest sprite from a particular sprite, is to simply iterate through all sprite and due a distance check. While this methodology works fine if you only have a small number of sprites, it starts to be taxing resource-wise if you have a lot of sprites e.g. 500.

My question is: does anyone know of a better method .. perhaps involving quad trees? Is there anything Phaser has built-in that would assist with finding the nearest sprite to a sprite?

   

 

 

 

[squilibob]

Using Phaser.Quadtree would definitely be more efficient.

[ForgeableSum]

I have experimented with a quad tree before but don't quite understand its implementation in phaser. 

For instance, suppose I have a group of sprite that are more than 5000 pixels away from each other. All sprite are inside the quad tree and have physics bodies. I call retrieve and it just gives me all the sprites. I change the max level property on the quad tree to 16 instead of 4 - the same result, retrieve gives me all the sprites. 

Suppose I wanted the quad tree to only retrieve sprites within a certain radius of the sprite .. why is that not a paramater on the retrieve method? It's for reasons like these that I abandoned quad trees.

[mattstyles]

16 hours ago, feudalwars said:

Suppose I wanted the quad tree to only retrieve sprites within a certain radius of the sprite .. why is that not a paramater on the retrieve method? It's for reasons like these that I abandoned quad trees.

I've no idea about the phaser quad tree implementation, but quad trees do not work like this (indeed, can not). They are simply a space partitioning utility, a method of grouping elements together based on some metric (which could be position) with the goal of limiting your search space to run your expensive operations over.

I've only theoretical knowledge of how you use them, but, in order to sort your big list of elements into smaller lists they get boxed via the tree algorithm, so to find nearby units you'd query which box unit X is in and you'd be returned all units within that box to run your distance checks against, a smart implementation would give you all units in adjacent boxes to cover the use-case where unit X is right by a box boundary, but that is a special case rather than the general case for any tree, although a fairly straight forward one to implement.

Another smart optimisation of quad trees is often to try node balancing to ensure all boxes have comparable (or even, optimal) items within, but, again, this isn't necessarily the general case for a tree. If you do not load balance nodes (and many trees are implemented—or, indeed, maybe should be implemented—so that only leaf nodes contain items) then you'll usually have to define some metric for defining the granularity of your leaf nodes that defines your boxes (this is often best visualised as sub-dividing a 2d area into rectangles, how many rectangles/squares defines your granularity), this is often arbitrary and almost always based on best-guess for performance rather than convenience. 

You mentioned something about 5000 pixels apart? Generally this is not important information to a quad tree, its only job is partitioning a big list into smaller ones, but if you don't take a load balancing approach then you'd probably want to consider it when considering the granularity to apply, but, even so, the tree doesn't care about the dimensions of any search space, its just dividing it all up into boxes based on some metric.

[Fatalist]

Phaser's quad tree is not very efficient. For example, you can't update a single object, you need to clear and repopulate it every time something changes. And sometimes it returns too many objects, see this thread - Understanding Phaser Quadtree

So you may have to find some better implementation.

 

 

[samme]

Maybe some kind of binary search on an axis-sorted group.

[ForgeableSum]

Thanks for all the feedback everyone. It's nice to know this forum isn't dead. I'll have to research each of the solutions suggested, but it looks like there isn't going to be anything built-in to Phaser that would help with this. 

Perhaps I'm looking at the problem the wrong way and instead of looking for a more efficient method to find the nearest sprite, look for a way to improve the implementation I already have. i.e. only look when you absolutely need to. After all, looping through all objects and doing distance checks isn't that inefficient - it's simple math calculations. But when you do that a couple hundred times a second - that's when it becomes a resource problem.