Jump to content
  • Advertisement
Sign in to follow this  

space partitioning on the server for a 2D tile based MORPG

This topic is 4884 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi, im working on a 2D MORPG (persistant, online RPG). the game is futuristic and "actiony" - there are guns, and when you shoot a gun, you see the bullet come out of the gun and head towards where you shot. you can either freely aim with the mouse in 360 degrees or lock on to your target and auto fire. combat is encouraged so there could be a decent amount of enemies and bullets flying around in the world at any given time. like i said, the game is tile based, 32x32 square tiles. my goal is to support 30 players at once, however, im writing the game to be as scalable and efficent as possible. characters, projectiles, etc, can be of any dimension. all the geometry is AABB's and i just do simple bounding box collision for the coldet. the wall collision is fine, for that i use the tiles, but it is the character/object collision that i am worried about. anyway, i was thinking about doing space partioning on the server. currently if i want to do collision detection with a character/projectile, i loop through all characters and if they are on the same map i do collilsion detection and if they collide i do the reaction. now, i have looked into Quadtree's, but i think they might be overkill. since the game is tile based, i was thinking i could take advantage of that somehow. im just not sure how to do it. the collision detection is very cheap, its a single if statement really, at worst 4 comparisons, at best 1 comparison. so i dont want to cause more overhead then i will save. thanks for any help. [Edited by - graveyard filla on January 3, 2005 1:40:19 AM]

Share this post


Link to post
Share on other sites
Advertisement
What I would do is partition overlapping collision areas (just barely overlapping) and do this manualy for each area that would normaly be more dense.

Share this post


Link to post
Share on other sites
characters can overlap one or a group of adjacent tiles. for each tiles, you can have a list of overlapping characters, these objects need to be tested against each other.

you need a double-bookkeeping list. The tiles need a list of overlapping objects, the objects need the list of covered tiles.

the downside is, you'll need to keep a pointer to a list for each tile of the world, even when no objects are covering the tile (then it's NULL). You can reduce that to 16 bits if you need to (then you are limited to a maximum of 65,000 buffered nodes for your lists).



Share this post


Link to post
Share on other sites
hi,

so you think that Quadtree's would just make things slower then?

@Paul

i dont really understand what you mean. care to explain a little more?

@oliii

im trying to understand what you are saying. so give my Tile class a pointer to a container, possibly a std::list? why not give it an actual instance of a std::list?

anyway, each time a player moves, he fills his pointer with the tiles he occupies, and removes himself from the other tiles. when doing collision detection, i only check against characters who are in the list's that i occupy?

so, why does the player need a list of tiles then? also, this seems like it will be difficult to implement. my main fear is that i wont remove myself from a tile properly, and my pointer will sit there forever. (i have actually attempted to implement this scheme before for sorting purposes, and that was one of my biggest problems).

thanks for anymore help.

Share this post


Link to post
Share on other sites
I *think* what Oliii is trying to say is that your "map" needs to have pointers to the occupants it contains at given coords so you can call something like this

Actor* tilemap->GetOccupant( int x, int y )

also, you "actors" need to keep their locations stored internally so you could alternatively call

Point Actor->GetLocation() { return current_location; }

That's "double bookkeeping"

That's what i did for my last project. I just put the whole thing in one function


Actor::MoveTo( int x, int y ) {
tilemap->RemoveOccupant( current_x, current_y, this );
tilemap->AddOccupant( x, y, this );
current_x = x;
current_y = y;
}


You can expand that as needed if actors occupy more than one square. Just use lists instead.

Share this post


Link to post
Share on other sites
Why do all the tiles have to have a pointer? Surely you can generate a unique id based on it's x and y position in the world then have the GetOcupant function do a lookup in a map. If the tile isn't listed in the map then it's empty, return 0, else return whatever the tile is linked to.

Put all the tiles in a manager and you can put all the functionality you need for tile interaction here.

edit: yeah basically what you said leiavoia with your tilemap.

Share this post


Link to post
Share on other sites
In terms of space partition just divide the whole map up in to sub maps each slightly bigger than whatever can be displayed on screen at once. At most your player will be able to see 4 sub-maps at once. Then you can do octree like tests but it's so much simpler.

Share this post


Link to post
Share on other sites
hi everyone,

im still trying to figure what to do. maybe i should just do something simple, such as dividing a map into possibly 8 sections? or maybe i should just use quad trees (which i guess would do the same thing?) ? im thinking that the pointer thing might actually be slower, since i would have to be constantly deleteing and inserting from a container each time a single projectile or character moves.

Share this post


Link to post
Share on other sites
Quote:
Original post by graveyard filla
im still trying to figure what to do. maybe i should just do something simple, such as dividing a map into possibly 8 sections? or maybe i should just use quad trees (which i guess would do the same thing?

Quad trees recusively devide them selves so it first devids the map into 4 spaces then those 4 into 4 more and so on... But remember to not overdue it and devide to much because then it might not help at all.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!