Determing player/objects within a certain radius of "self"

Game Mechanics Artificial Intelligence
#1

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

#2

Perhaps you can need something like this?

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

#3

Seems very interesting, gonna give it a read. Thanks for the reply

#4

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:

#5

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 ;D

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.

#6

[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.
[/quote]
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.
[/quote]
Yes. Good solution, have a look at http://mindprod.com/jgloss/hangingmoss.html