Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
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  
  Determing player/objects within a certain radius of "self"  (Read 2685 times)
0 Members and 1 Guest are viewing this topic.
Offline Jannick

Senior Newbie




Java games rock!


« Posted 2006-02-17 13:25:20 »

Hi

Im looking at some advice for a method for determing which players/monsters are within LOS (ie within a certain radius) of another player/monster emitting an event of sort. Im working on the server for a game where we have some pretty large playfields (mmo style) and where transmitting every event to the entire playfield population is not an option. So the problem really boils down to: given an object with an x,y coordinate, find a fast way to determine other objects that are within a certain distance.

Let me start by telling about my current idea for an algorithm/datastructure. I'm thinking about splitting the entire playfield up in non-overlapping squares of side width equal to the wanted LOS in the game, lets say 50x50. Meaning the entire playfield is sort of covered in tiles. When a player moves around he is constantly associated with a single square. Once the player generates an event I can then create a list of "observers" present in the current square, and the 6 squares around it. That ensures that I find all observers within 50 units of the event without getting the entire population. This structure also gives me a simple way of keeping track of which players have been "introduced" to each other, and thereby when to send a "CharEnteredAreaEvent" and such things.

Anyway, im pretty new to all this so I was hoping I could pick up a few suggestions on other ways to do something like this =)

Thanks in advance
Offline SubZero

Junior Newbie





« Reply #1 - Posted 2006-02-17 15:51:55 »

Perhaps you can need something like this?

http://www.cs.ncl.ac.uk/research/pubs/trs/papers/888.pdf
Offline Jannick

Senior Newbie




Java games rock!


« Reply #2 - Posted 2006-02-18 00:06:47 »

Seems very interesting, gonna give it a read. Thanks for the reply
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline SubZero

Junior Newbie





« Reply #3 - Posted 2006-02-18 00:17:54 »

You're welcome. I was looking for the same problem a few weeks ago, and there i found this little paper. Unfortunately i hadn't enough time for implementing this method. If you get some results about this issue, i would be glad if you could give a short note Wink

Offline Jannick

Senior Newbie




Java games rock!


« Reply #4 - Posted 2006-02-18 00:25:29 »

Just read it, and although it have some interesting ideas its not really a complete solution. I have my doupts about the architecture they suggest, but even if that works out the paper doesnt describe the most important properties of the technique, the datastructure and algoritme to support this approch. If I read it correctly it also seems to delegate some responsibility for the interest management to the client. Thats like building in exploits =)

On a side note, I study computer science myself, and this paper have many phases where it feels like the "I dont understand this, lets toss out some fancy word and skip over it" solution  Grin

Edit: As an example, using aura calculations is technically the most precise answer to telling which objects are within LOS, but you need to do an initial reduction of the set of object you will have to perform this operation on. Also, this method alone doesnt work very well in term of determing when an object should be "removed" from the knowledge of another client. The same moment that updates no longer come in, the observer have to know that it can remove the object, so that it doesnt seem to freeze.
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #5 - Posted 2006-02-18 18:33:37 »

Quote
So the problem really boils down to: given an object with an x,y coordinate, find a fast way to determine other objects that are within a certain distance.
This is basically what a fast collision systems need to do. You don't want to test every object with every other other world object every cycle.

Quote
I'm thinking about splitting the entire playfield up in non-overlapping squares of side width equal to the wanted LOS in the game, lets say 50x50. Meaning the entire playfield is sort of covered in tiles. When a player moves around he is constantly associated with a single square. Once the player generates an event I can then create a list of "observers" present in the current square, and the 6 squares around it. That ensures that I find all observers within 50 units of the event without getting the entire population.

Yes. Good solution, have a look at http://mindprod.com/jgloss/hangingmoss.html



Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
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.

Dwinin (21 views)
2014-09-12 09:08:26

Norakomi (55 views)
2014-09-10 13:57:51

TehJavaDev (66 views)
2014-09-10 06:39:09

Tekkerue (33 views)
2014-09-09 02:24:56

mitcheeb (54 views)
2014-09-08 06:06:29

BurntPizza (38 views)
2014-09-07 01:13:42

Longarmx (24 views)
2014-09-07 01:12:14

Longarmx (30 views)
2014-09-07 01:11:22

Longarmx (28 views)
2014-09-07 01:10:19

mitcheeb (37 views)
2014-09-04 23:08:59
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!