Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (480)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (547)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Search in a 3 values map  (Read 3305 times)
0 Members and 1 Guest are viewing this topic.
Offline 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 !
Offline Cero
« Reply #1 - Posted 2012-08-18 18:42:22 »

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

Offline Best Username Ever

Junior Member





« 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; }
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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.
Offline Best Username Ever

Junior Member





« 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)?
Offline 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
Offline Best Username Ever

Junior Member





« 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.
Offline 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 Sad
Offline Best Username Ever

Junior Member





« 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?
Offline Ziden

Senior Newbie





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

hows that ?  Huh

im still not sure how to do it.

thanks for the attention !
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Best Username Ever

Junior Member





« 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.
Offline 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 Sad

the most effort ive tryed is storing used a PRTree  Undecided
http://www.khelekore.org/prtree/
Offline 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.

Offline 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 !
Offline 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.
Offline 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.  Cool

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.

atombrot (23 views)
2014-08-19 09:29:53

Tekkerue (22 views)
2014-08-16 06:45:27

Tekkerue (21 views)
2014-08-16 06:22:17

Tekkerue (12 views)
2014-08-16 06:20:21

Tekkerue (19 views)
2014-08-16 06:12:11

Rayexar (57 views)
2014-08-11 02:49:23

BurntPizza (37 views)
2014-08-09 21:09:32

BurntPizza (29 views)
2014-08-08 02:01:56

Norakomi (36 views)
2014-08-06 19:49:38

BurntPizza (66 views)
2014-08-03 02:57:17
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!