Search in a 3 values map

Performance Tuning
#1

Hello there.

Lets supose i have a Map<String, Object> and this object has X Y Z.

Given a X Y Z, i want to find the closest objects to me within a range for example.
For now im looping thro all objects to find the ones i want.

What would be the best search algorith to implement this ?

Thanks alot for your attention !

#2

Well that depends if and how this hashmap would be sorted…

#3

If you’re only working with three objects, just calculate the distance to each one. For each obj in {X, Y, Z} …

if(min * min <= rsquared && max * max >= rsquared && rsquared < bestrsquared) { best = obj; bestrsquared = rsquared; }
#4

Ill try to explain better my explanation as very bad, sorry.

I have an Region object, witch has 2 locations (a location is a X Y Z )

I having 1 location, i want to find the closest region there is for example distance < 200 , or lets say for example, the region i am in !

The algo to know if im inside the region is done, i just dont want to loop thro all regions.

And i can sort this map the way i want, but i cant find a good way.

Thanks for the help.

#5

By region to you mean a cell in a three dimensional grid? In other words, a block of space in 1, 2, or 3 dimensions with a fixed boundary. A node on a graph? A region with the same properties but not organized in homogeneous grid space. In either case you can do the same thing if you can get a set of neighboring regions for a given region.

Or do you mean something besides a region? Maybe a sparse collection of independent objects that have (x, y, z) coordinates and occupy space defined by a point?

Do you mean something that defines a range of possible locations in space (a “region”) or something that occupies a location in space (like a physical object)?

#6

The region is a field composed by blocks, imagine as a Minecraft region. So its 2 locations, the ‘minimum’ and the ‘maximum’ one, made by X Y Z

Its a collection of region objects who defines the space, and i can have 2 regions in the same space for example.

thanks for the attention

#7 
//          /\
//          Up     __ N
//        ______    /\
//       /____ /|  /
//      |     | |
// <- W |  S  | | E ->
//      |_____|/
//
//       Down 
//        \/

Since you’re on a grid, you only need to check 8 locations. X +/- 1 (N/S) Y +/- 1 (E/W) Z +/- 1 (Up/Down). Just check which of the 6 sides of the cube is closest and the closest neighbor will be in that direction.

#8

But then again, i would have to run the whole list to find the region i want to :frowning:

#9 
level.getRegion(x + 1, y, z);

You can’t implement a fast version of that?

#10

hows that ? ???

im still not sure how to do it.

thanks for the attention !

#11

You might want to consult Stack Overflow, a search engine, or a pen and paper software engineering design system.

#12

its kinda vague, ive looked forward to it but i couldnt make it :frowning:

the most effort ive tryed is storing used a PRTree :-
http://www.khelekore.org/prtree/

#13

I think you need to be a little more specific in what you are using this for. But, if you want to get objects close to you in a specific region, a HashMap will allow you to search without having to traverse the entire list. However, it really depends a lot on…

How your game is set-up (tile-based or some other system).
If the entities you are checking are moving entities.
How many entities need to perform this check.

All those factors are going to determine the speed and each one is going to have a dramatic difference on how searching is approached. Simple answer: use a Hashmap of values if you want to prevent traversing an entire list.

#14

Its for a minecraft plugin, so yeah there are moving entityes, this will be called everytime a player hits a block. I need to know if is there a region on that block, but i didnt wanted to run all regions for it.

Thanks for the attention !

#15

as ive read as much as i can, an R-Tree is the most you can get for finding points inside rectangles… but i cant understand how to use it… does anyone have a snippet or a cool library ?

Thanks for the attention.

#16

R-Tree libraries for Java (Thanks Google).
R-Tree Powerpoint

I suppose you are just trying to create a map that leads people to a certain tile.

If the range is a (fixed) binding box around the player, then you can run an A* type search looking for the nearest items around you.
If the range is around a certain area, then just have the player search for that area. Once they enter the area, then search out the specific nodes.

R-Type is a lot of work to implement and it is pretty slow. I thought you were looking for speed. The fastest way to find anything is to limit the space you are searching for it in, and using A* to find it. 8)