Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (522) Games in Android Showcase (127) games submitted by our members Games in WIP (590) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Search in a 3 values map  (Read 3477 times) 0 Members and 1 Guest are viewing this topic.
Ziden

Senior Newbie

 « Posted 2012-08-18 18:31:57 »

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 !
Cero
 « Reply #1 - Posted 2012-08-18 18:42:22 »

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

Junior Devvie

 « Reply #2 - Posted 2012-08-18 18:55:01 »

If you're only working with three objects, just calculate the distance to each one. For each obj in {X, Y, Z} ...
 1 `if(min * min <= rsquared && max * max >= rsquared && rsquared < bestrsquared) { best = obj; bestrsquared = rsquared; }`
Ziden

Senior Newbie

 « Reply #3 - Posted 2012-08-18 18:57:52 »

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.

Junior Devvie

 « Reply #4 - Posted 2012-08-18 19:14:25 »

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)?
Ziden

Senior Newbie

 « Reply #5 - Posted 2012-08-18 19:57:51 »

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

Junior Devvie

 « Reply #6 - Posted 2012-08-18 20:16:43 »

 1  2  3  4  5  6  7  8  9  10 `//          /\//          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.
Ziden

Senior Newbie

 « Reply #7 - Posted 2012-08-18 20:40:59 »

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

Junior Devvie

 « Reply #8 - Posted 2012-08-18 20:53:28 »

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

You can't implement a fast version of that?
Ziden

Senior Newbie

 « Reply #9 - Posted 2012-08-18 20:54:53 »

hows that ?

im still not sure how to do it.

thanks for the attention !

Junior Devvie

 « Reply #10 - Posted 2012-08-18 21:15:01 »

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

Senior Newbie

 « Reply #11 - Posted 2012-08-18 21:32:14 »

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

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

JGO Wizard

Medals: 99
Projects: 1
Exp: 7 years

Not a glitch. Just have a lil' pixelexia...

 « Reply #12 - Posted 2012-08-18 23:01: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.

Ziden

Senior Newbie

 « Reply #13 - Posted 2012-08-19 00:24:15 »

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 !
Ziden

Senior Newbie

 « Reply #14 - Posted 2012-09-02 13:55:42 »

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

JGO Wizard

Medals: 99
Projects: 1
Exp: 7 years

Not a glitch. Just have a lil' pixelexia...

 « Reply #15 - Posted 2012-09-02 14:48:19 »

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.

Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 trollwarrior1 (29 views) 2014-11-22 12:13:56 xFryIx (71 views) 2014-11-13 12:34:49 digdugdiggy (50 views) 2014-11-12 21:11:50 digdugdiggy (44 views) 2014-11-12 21:10:15 digdugdiggy (38 views) 2014-11-12 21:09:33 kovacsa (62 views) 2014-11-07 19:57:14 TehJavaDev (67 views) 2014-11-03 22:04:50 BurntPizza (64 views) 2014-11-03 18:54:52 moogie (80 views) 2014-11-03 06:22:04 CopyableCougar4 (80 views) 2014-11-01 23:36:41
 theagentd 28x basil_ 27x HeroesGraveDev 23x BurntPizza 21x Riven 19x Spasi 18x princec 17x KevinWorkman 13x kpars 11x SHC 11x gouessej 10x Grunnt 10x Nate 9x Longarmx 9x LiquidNitrogen 8x CopyableCougar4 8x
 Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50List of Learning Resources2014-07-31 16:26:06
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org