Sign in to follow this  
popel

Algorithem/model for player-positions in periphery of position x/y?

Recommended Posts

Hello iam new here and also new to gamedeveloping, but programming in different languages since somehow 8-9 years... iam programming a browser game (flashclient) using a Java based media Server, so there is no engine, framework or api made specialy for gaming... the game is a MMO-RPG, so player Charakter striving the gameMap will move into a "view" of your player somewhen.. imagine a radar that shows enemys... if a enemy is close to your player the radar will show you a "point" where your enemy is on map... now my question: what will give me the best performance to notify each user about the players are on +/- n positions from its own position... lets say thee are 1000 concurrent Players , lets say the time between ticks is 100ms... 10.000 DB querys only to update positions annother 10.000 to get a result from database... 20.000 DB querys each second? Current iam using to load all importent datas from SQL via hibernate and putting them into hashMaps and use to change those instances and only save in DB when needed... there are ways to compare collections, do filter criterias... i also could add a extra datastructure with different access methods and performance... but anything i found did not satisfy what iam searching for, so i found my way to here. this "List all Items and Players in a area 20 positions in each diretion from position 100/100 (x/y coordinates its a 2d game)" issue has a common solution i suppose... well if so i dident found it yet! can someone point me to literature/tutorial about exspecially this issue? any help is welcome.. greetz

Share this post


Link to post
Share on other sites
You keep the state in a spatial index in RAM. Querying a quad tree or similar for that information is very fast. Of course, if you can't implement things at that level, and can't keep a persistent session, then you're pretty much toast. Use the right tool for the job!

Share this post


Link to post
Share on other sites
well the funny thing with ppl that are such genius that them cant answhere a simple question with a simple anshwere is, them are just too genius, i will wait for someone thats not that genius and maybe is able to answhere the question with a simple anshwere... because yours wasent a helpfull for anyone.

well maybe it helps someone that does not know that quering can be fast:) and whanted to know about that... and not about the common way is used with some performance tipps.

thank you anyway

:)

or is that here a forum for ppl only using tools and frameworks without own ideas of better perfomance?

Share this post


Link to post
Share on other sites
Quote:
Original post by popel
well maybe it helps someone that does not know that quering can be fast:)


Well, it's your choice to use 20K queries per second or not. If they're fast enough for you, then why are you asking about performance optimizations?

Non-query solutions exist *because* a database is not the best solution for all problems.

I don't see how a quadtree is too difficult to understand.

If you want to treat it like a collision detection system you could optionally use a cached sweep-and-prune system.

'Quadtree' and 'sweep and prune' are things that you can Google if you need details. Like you said, they are common solutions and it's just tedious to explain them in detail.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nypyren
I don't see how a quadtree is too difficult to understand.


my comment was more regarding the last sentence, i just fiendly asked about the common way, becauase i come from webapplication develeopment where latency isent that important and interpolated results are unwished, whats totaly different to game development...

quering a quadtree and collision detecung are techniques to find the position next to mine

but i dont have a problem to understand that and dident asked that aswell

to explain in "brainpictures", may my english is too bad:

[CODE]
target.x < me.x + view.width >> 1 || target.x > me.x - view.width >> 1 || target.y < me.y + view.height >> 1 || target.y > me.y - view.height >> 1 ? pushStack : NULL;
[/CODE]

is not my problem to understand...

may question was regarding to the performance, using CollectionFilters where i can use certain cruterias compared to a model where a abstract class uses copied datas with a different access Method

for example a class expressed like

(Array) MapArray = (int) Key = MapID, (Array) Value = - >
(int) Key = 0 for x and 1 for y, (Array) Value = - >
(int) Key = position X, Value = ((int) Array) (UserID1, UserID2, userID3...)
(int) Key = position Y, Value = ((int) Array) (UserID1, UserID2, userID3...)


would be the structure of it (hope u can follow)...

the first query would result in raw itterating a collection, hashMap.. whatever, or even using the filter criteria for a better performance

using the Abstract object would allow me to concat indexed Array´s and compare only those... which i aspect would have a better perormance... because it rapidly redices the number of needed loop-counts...

compared to collision detection where the target adds itselfs to a list for each client where the querry is true, also with a copy of datas to avoid a search.

what is the best way to combine these pragramticly techniques.

:)

Share this post


Link to post
Share on other sites
hmm
it looks like no one understands me, well ok, may this here helps you to understood what i was talking about

ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/thesis.pdf

i just talk about a handcrafted! implementation theory but i gues u dont know how to do optimize performance there:)

well thx anyways, do you know a forum for developers that uses something weird like native code in native editor, not for framework users?

bye

Share this post


Link to post
Share on other sites
I still don't understand your quesiton.

Is your question "how do I get the position of the 20 closest people out of a database table that contains the people locations?"
If that is the quesiton, the answer is simple[1], but it's the wrong question. Nobody in their right mind does that.

Is your quesiton "what do MMORPGs and other such games generally do to get the 20 closest people to each player?"
If so, the answer is simple: They do not use standard database queries or application servers, because they are not tools suited to the task. Instead, they use in-memory spatial structures, such as quad trees, and a custom network protocol to query that structure.

Is your question "how can I implement a specific algorithm (such as quadtree) using the specific tools I have at my disposal (such as a Java media server)?"
If so, your question is not only poorly worded, but it is also asked in the wrong forum. The right forum would be the support forum for the Java media server you're using.

If your questions is something else, then I fear that you need to make your requirements a bit clearer before someone on the web can actually answer the question. For example:

1) What kind of data do you have? Where does it come from?
2) What answer do you want, based on that data?
3) What execution environment is used to calculate that answer?
4) What communication method are you using to communicate data updates, and answers?
5) Do you already have a solution? If so, what's wrong with it that makes you want another answer?
6) What are the other constraints on the solution?


[1]:Assuming this table for players by id and position:
create table player(x int, y int, id int);

And assuming you have "player_x," "player_y" and "player_id" for the player/point-of-view you want to select neighbors for, and your database has the "sqrt" function:
select p.id as id, p.x as x, p.y as y, sqrt((p.x-player_x)*(p.x-player_x) + (p.y-player_y)*(p.y-player_y)) as distance from player p
where p.id != player_id
order by distance asc
limit 20;

You will note that no current database technology will be able to optimize this kind of query. Which is why these kinds of queries are built using custom, in-memory data structures, generally with custom communication protocols.
You can order/display without the sqrt() too; you'll get distanceSquared instead.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this