The forums have permanently moved to forum.kirupa.com. This forum will be kept around in read-only mode for archival purposes. To learn how to continue using your existing account on the new forums, check out this thread.


Results 1 to 5 of 5

Thread: Sorting nodes by x & y location.. in a good way

  1. #1
    395
    posts
    Registered User

    Sorting nodes by x & y location.. in a good way

    Hey.

    Im making a game in which users via a flash frontend controll a character in a huge world.

    The client connects to a server written in Java, running at my home via sockets. This is not what i have a problem with

    As users join a new class (userInfo) is created for them this class contains methods for getting the values; xloc(), yloc(), rotation(), movementSpeed(), rotationSpeed(). These values are being updated just fine by the server and this isent where i have a problem either..

    The users are all in a big world, there are no zones. Users are server side kept in a huge hashtable with their socket values as keys and induvidual classes as values (above). Now as i want to keep the users updated on whats happening (otherwise this game wouldent be much fun) i send them the data for the entire world every 100ms and interpolate actions inbetween. This is touching on the problem =P

    As more users join, say we have 100 users connected, i need to send 100 complete sets of data for the entire world. This is bad. Uses excessive server power and uneccesarry bandwidth. This is the problem

    So what im trying to get help with is a way of figuring out which clients need data about what other clients, i drew a pretty little picture to help explain.

    (the picture text is not completly correct anymore, whats in the post is true)

    From the picture you can see that we have 6 users connected. but only the nodes (node = user) 4, 5, 6 need to know about eachother. nodes 4, 5, 6 do not need to see what nodes 1, 2, 3 are doing and the nodes 1, 2, 3 dont need to know anything about anyone but themselves.

    the reason i drew in r ( radius ) in the picture is that each user has a given screen size and only need to get data about what they can see on their screen ( 2D game ), r is the same for all users and a little bigger than the clients visible area to provide a buffer.

    So.. in what ways could one figure out which users need data about what other users without iterating through all the users and comparing their distance to all other users. This would be bad b/c it would provide a algorithm running time of O(n^n) and basically become a big *** bottleneck

    Hope i made the problem clear and that you all understood.

    Any help would be grand!
    //VoS
    Last edited by VoS; April 10th, 2008 at 05:51 AM.

  2. So basically you need the fastest algorithm to find every other user that's close enough for the user to see them. I think you are looking for are space partitioning, for example quadtrees:
    http://en.wikipedia.org/wiki/Quadtree

  3. #3
    395
    posts
    Registered User
    That seems like a pretty good way of doing it..
    but i can think of a few problems im not sure how to deal with, the biggest one being..

    Say 'player' has two zones on his screen, hes in zone2 and getting data about player 2 & 3, but he should also be seeing player 1 whom is in another zone but still in the users viewing area.

    Simple solution to this could be to give the player data from the current zone and all adjacent zones, but with that algorithm you never know how small a zone is, you could if enough players were near eachother probably fit a couple of zones on the same screen. This making it so that more than the one zone you are in and its adjacent zones are visible on the users screen.

    And the same problem arises even with just a few players, if you are in one zone and another player in a currently visible different zone is on, you dont see each other untill you are in same zone.
    Simply showing adjacent zones dosent seem like a nice fix.

    If this could be worked around this way would be really nice.

    Thanks!
    //VoS

  4. #4
    395
    posts
    Registered User
    Any more ideas or suggestions please?

  5. #5
    This is pretty basic stuff. Just think of a grid where the entities are inserted into the cells (sometimes into multiple cells). If you know the player's viewing rectangle you'd send data from the view.X/cellSize to (view.X+view.Width)/cellSize and same for the y. You'll end up with a nested for loop. Every player has a view range and you can cull their viewing area using this method. It works well. (I use it in my engine to handle large maps. It's also scalable if you're doing server clusters for zones)

    //edit. Oh yeah and for anyone building large multiplayer games I normally link them to this:
    http://gpwiki.org/index.php/Binary_Packet
    here's my development binary packet:
    C# Development Version
    AS3 Development Version
    I only spent a few hours on them and haven't work much on them (busy with school) but they might help you to optimize bandwidth. (100 players is small once you understand how to optimize serialization methods).
    Last edited by Sirisian; April 11th, 2008 at 12:07 AM.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Home About kirupa.com Meet the Moderators Advertise

 Link to Us

 Credits

Copyright 1999 - 2012