space partitioning on the server for a 2D tile based MORPG
Author
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]
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.
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).
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).
Author
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.
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.
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
You can expand that as needed if actors occupy more than one square. Just use lists instead.
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.
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.
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.
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.
Author
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
