opinions on collision / draw sorting in a top down 2d RPG
Author
hi,
ive been working on a 2d RPG in C++ for 4 months or so now. anyway, ive been working on some of the hardest part - Collision between characters and draw sorting. by draw sorting, i mean things are drawn correctly depending on the Y axis. IE, a character can stand below another character, and the one above will be drawn "behind" the one below. Collision is just the 2 characters colliding properly and responding to the collision.
the first method ive been trying for the past week to get working, is this:
- make a class : Render_Object. has a method virtual void Render(). have my npc, player, and enemy class inherit from this.
- have my Tile class have a member - Render_Object *ocupant.
now, i already have pathfinding implemented. so each frame, if a character has a path to walk, he moves towards the next step in his path. so basically, i will do this each frame:
-if a character has a path to walk, mark the tile he is moving towards with his pointer, and un-mark the tile hes standing on
-if a character has no path to walk, and is just standing still, just mark the tile hes standing on with his pointer.
then, each frame, i draw my screen tile by tile, row by row, starting from the top and working down. my loop would look like this on the inside:
draw_tile(map[y][x]);
if(map[y][x]->ocupant != NULL)
map[y][x]->ocupant.Render();
so, this would sort everything! now, for collision, i just do this:
-when calculating my path, dont consider nodes which are occupied.
-each time i step, check if the tile im stepping towards is occupied. if so, re-calculate my path.
all of this should work in theory, no? ive been trying to implement it for the past week, but am going through hell trying to get it to work. mainly the characters pointer seems to ocupy more then one tile at a time at points, screwing everything up. basically this method depends heavily on Pathfinding to work. theres no collision detection / response at all. the pathfinder just doesnt allow you to walk into walls / other characters. in fact, all movement would be required to use the pathfinder, even arrow-key movement would just calculate the path for the adjacent tile =).
theres one alternative solution:
-stick all my Render_Objects into a std::list.
-.sort() the list on the Y axis
-render each object in the list
this will sort everything, and should work great. the problem comes with collision. i would use bounding box, im guessing. but how do i allow one character to stand "behind" the other, if that happends, they will collide since there sprites will be colliding. so i was thinking that, instead of the characters bounding box be their sprite, it would be only a lower portion of their sprite. then a character could stand below / above another, plus a character could stand "in front" of a building, etc. but would this work smoothly?
my main concern for the second method is collision D. how do i do collision detection / response? i mean, sure, its easy to detect if 2 characters are colliding, but then what? how do i respond to it in a nice, subtle way, putting the character where they are suposed to be? it seems very difficult.
so, what do you think? should i give up on my first method, and try to get the second method to work? basically, the first method is collision avoidance and automatic sorting, which basically depends on using pathfinding for all movement. and the second method is collision detection / response and sorting by the Y axis, and wouldnt need pathfinding to work. im guess the second method would be slightly less efficent, but at this point it seems like it would be easier to implement. oh, and any alternatives are welcome. ive been checking out old Genesis RPG's, and cant for the life of me figure out how the hell they had perfect sorting / collision / pathfinding.
Hmm.. just to toss out some ideas (not sure I understood everything you were concerned about)...
As far as draw sorting goes, you could always layer your approach. By layers I mean having multiple drawing layers. Things with less priority would be lower on the list (think of it in terms of a ladder, maybe), so lower things would be drawn first, and therefore appear under or behind things with higher priority. Lists/vectors would handle this fine.
As for collision, you could do it in the exact same way. Use collision layers, maybe. Where some things collide with others, but are immune to eachother. As far as response goes, you could use a slot/signal approach, state machine/messaging system, or something of that nature.
When something collides, tell it has collided, and call it's on_hit() routine, and make it do whatever is necessary. In the case of a guy walking around town, if he collides with a building/tile/whatever, tell him to not move into it, and move him just outside the rect of whatever he just tried to move into.
There's quite a bit of documentation on using step ahead vectors for determining intersection with objects (usually only a concern with very fast moving objects). Otherwise, an old rect intersection and puttin it back at it's old location should be pretty good?
Not sure if any of this helps!
edit: typos, etc.
As far as draw sorting goes, you could always layer your approach. By layers I mean having multiple drawing layers. Things with less priority would be lower on the list (think of it in terms of a ladder, maybe), so lower things would be drawn first, and therefore appear under or behind things with higher priority. Lists/vectors would handle this fine.
As for collision, you could do it in the exact same way. Use collision layers, maybe. Where some things collide with others, but are immune to eachother. As far as response goes, you could use a slot/signal approach, state machine/messaging system, or something of that nature.
When something collides, tell it has collided, and call it's on_hit() routine, and make it do whatever is necessary. In the case of a guy walking around town, if he collides with a building/tile/whatever, tell him to not move into it, and move him just outside the rect of whatever he just tried to move into.
There's quite a bit of documentation on using step ahead vectors for determining intersection with objects (usually only a concern with very fast moving objects). Otherwise, an old rect intersection and puttin it back at it's old location should be pretty good?
Not sure if any of this helps!
edit: typos, etc.
I had a hard time understanfing all that but what i think you are asking is: "how do i get a 3D feel with a 2D game?" (allowing players to stand behind each other and such)
I think the best example would be good ol' Double Dragon. The hit detection works (i assume) if you within a reasonable distance of the other player on the Y axis. If you were not lined up with the other guy, your punches and kicks would not hit. The same is true of other similar games like Secret of Mana and Final Fight.
I think your Y-sorting trick would work fine if it's trully tile based. What i did for my last strategy game project was loop through all the tiles and draw each componant of the tile including the playing pieces.
instead of
I would do this:
If the occupant is always centered on the tile that works or is off on the Y axis. If he overlaps horizontally, it does not work.
I think the best example would be good ol' Double Dragon. The hit detection works (i assume) if you within a reasonable distance of the other player on the Y axis. If you were not lined up with the other guy, your punches and kicks would not hit. The same is true of other similar games like Secret of Mana and Final Fight.
I think your Y-sorting trick would work fine if it's trully tile based. What i did for my last strategy game project was loop through all the tiles and draw each componant of the tile including the playing pieces.
instead of
foreach tile (list of tiles) { DrawBackground(); }foreach tile (list of tiles) { DrawOccupant(); }I would do this:
foreach tile (list of tiles) { DrawBackground(); DrawOccupant(); }If the occupant is always centered on the tile that works or is off on the Y axis. If he overlaps horizontally, it does not work.
Author
@catch
thanks for youre reply. its the on_hit() function im worried about. also, structuring it all. basically, i dont understand how to do collision detection / reaction to all my characters... im guessing i will have to do something like this:
make a Collision_Object class. have it store : x , y, w, h. or better yet, i could just have my Collision_Object class have a single function - Get_Rect(). it will return the rectangle that represents the objects collision information.
now, i have player, npc, and enemy inherit from this. then i have a "master list" of collision objects. each frame, after (or before?) i Update() all of my objects, i should loop through all my collision objects, and do collision detection / reaction. im just not sure how exactly to do this....
@leavoia
thats the approach im trying now, but its not working too well. im starting to seriously consider swithcing, as ive been working for a week battling bugs and getting nowhere. this leaves me back to my original problem, how to do collision reaction to all my objects. also, i dont want to check each object against each object, IE, check A against B, but dont check B against A again since its already happend... to be honest, the draw sorting should be extremely easy to do, just stick all my characters in a master list and call .sort() each frame... its this collision that scares me...
thanks again guys for any further help
thanks for youre reply. its the on_hit() function im worried about. also, structuring it all. basically, i dont understand how to do collision detection / reaction to all my characters... im guessing i will have to do something like this:
make a Collision_Object class. have it store : x , y, w, h. or better yet, i could just have my Collision_Object class have a single function - Get_Rect(). it will return the rectangle that represents the objects collision information.
now, i have player, npc, and enemy inherit from this. then i have a "master list" of collision objects. each frame, after (or before?) i Update() all of my objects, i should loop through all my collision objects, and do collision detection / reaction. im just not sure how exactly to do this....
@leavoia
thats the approach im trying now, but its not working too well. im starting to seriously consider swithcing, as ive been working for a week battling bugs and getting nowhere. this leaves me back to my original problem, how to do collision reaction to all my objects. also, i dont want to check each object against each object, IE, check A against B, but dont check B against A again since its already happend... to be honest, the draw sorting should be extremely easy to do, just stick all my characters in a master list and call .sort() each frame... its this collision that scares me...
thanks again guys for any further help
I've torn my collision scheme apart and put it back together again several times now and i'm getting pretty good at it. If you need specific collision help you can email me. I'll let you know that i'm reorganizing my PollingEngine to accomidate the collision detection, so that may be important to you. Basically, it will go like this now:
1) Update() all objects
2) Check For collisions
3) Regress any object positions if they hit a wall or whatever
4) Draw() all objects
Update() and Draw() will now be handles by my PollingEngine, but collision is handled through a seperate collision list much like my polling objects are.
There are lot of slick tricks i've put together to limit collision checking, but it depends somewhat on your game layout. Since your game is tile-based, that makes it much simpler than what i'm currently doing. The only thing you really need to keep track of is active moving objects (like players).
Other timesavers include:
- Don't check A::B and B::A too. you can do that by:
This relies on the use of pointers. it prevents you from checking each other and also from checking yourself.
- Don't check passive non-moving objects against other passive objects. If object A is not moving and object B isn't either, of course they don't collide!
- Don't check stupid things like bullets versus other bullets. Give each object a collision_type and sort them somehow.
- Use spatial partitioning. Since you are using a tile map, that's already done for you!
1) Update() all objects
2) Check For collisions
3) Regress any object positions if they hit a wall or whatever
4) Draw() all objects
Update() and Draw() will now be handles by my PollingEngine, but collision is handled through a seperate collision list much like my polling objects are.
There are lot of slick tricks i've put together to limit collision checking, but it depends somewhat on your game layout. Since your game is tile-based, that makes it much simpler than what i'm currently doing. The only thing you really need to keep track of is active moving objects (like players).
Other timesavers include:
- Don't check A::B and B::A too. you can do that by:
Collide( Thing* A, Thing* B ) { if ( A < B ) { /* do collision check */ } }This relies on the use of pointers. it prevents you from checking each other and also from checking yourself.
- Don't check passive non-moving objects against other passive objects. If object A is not moving and object B isn't either, of course they don't collide!
- Don't check stupid things like bullets versus other bullets. Give each object a collision_type and sort them somehow.
- Use spatial partitioning. Since you are using a tile map, that's already done for you!
For my last shooter game I used a simple collision system (was just a shooter game!), but I'll be doing collision for an RPG type game soon-ish (in a month maybe), so I haven't thought too deeply on it, but here's my at the moment rambles.
In the shooter game I used a layered approach for both my drawing and collision systems. They were nothing but very simple (custom) linked lists. I'd probably abandon that and use STL containers. Anyway, the point is, breaking things up into layers gives you a way to categorize your objects.
My shooter game, for example had a couple collision lists.
1) Friendly list (the player, his bullets, etc)
2) Enemy list (asteroids, baddies, etc).
3) Powerups (can't remember if I got this far :)
All I did was add objects to the lists via their class (on creation), and processed them in my "world" object as a linked list (maybe coulda done it faster, but it was such a small game...) So I wouldn't compare the ship's bullets to its own ship, but I would compare the bullets and the ship to the asteroids, baddies etc. Likewise, I might compare the powerups to the player, but not to the enemies. It really doesn't matter, but that's the main principle.
Now for an RPG, you might have similar layers and compare them against eachother, but it would more complicated, no doubt.
Take for example diablo 2. The allied players can't move through one another, so they are collided against each other, but their spells, projectiles, and other things can pass through everything other than mosters/obstructions. In this system, they may have made a list of friendly projectiles, and not compared it to the lists containing players, but compare the player lists to one another, among everything else.
Does this sort of make sense? All I'm proposing is an organization system, like lists, to function as something like "alliance layers," so bad things bump good things, and good things don't bump other good things.
I guess it's up to you to decide how to make the lists and iterate them.. Of course, there are other ways to do this I'm sure.
One way I could think off the top of my head is just collide EVERYTHING, and have some kind of flags to pick through. Is this an enemy? a blocked passage tile? etc, and handle each accordingly. If you're worried about a lot of duplicated checks, you could always keep a list in every object that makes sure it won't double check a previous collision, but linear searching like that might yield as much speed penalty as just doing the check again (albeit the a double check might produce undesirable results).
In any case, you have to rather predict how much collision will be happening on screen in a "busy" area/time frame, and decide what system would work best for you.
Sorry for the long babble :P
In the shooter game I used a layered approach for both my drawing and collision systems. They were nothing but very simple (custom) linked lists. I'd probably abandon that and use STL containers. Anyway, the point is, breaking things up into layers gives you a way to categorize your objects.
My shooter game, for example had a couple collision lists.
1) Friendly list (the player, his bullets, etc)
2) Enemy list (asteroids, baddies, etc).
3) Powerups (can't remember if I got this far :)
All I did was add objects to the lists via their class (on creation), and processed them in my "world" object as a linked list (maybe coulda done it faster, but it was such a small game...) So I wouldn't compare the ship's bullets to its own ship, but I would compare the bullets and the ship to the asteroids, baddies etc. Likewise, I might compare the powerups to the player, but not to the enemies. It really doesn't matter, but that's the main principle.
Now for an RPG, you might have similar layers and compare them against eachother, but it would more complicated, no doubt.
Take for example diablo 2. The allied players can't move through one another, so they are collided against each other, but their spells, projectiles, and other things can pass through everything other than mosters/obstructions. In this system, they may have made a list of friendly projectiles, and not compared it to the lists containing players, but compare the player lists to one another, among everything else.
Does this sort of make sense? All I'm proposing is an organization system, like lists, to function as something like "alliance layers," so bad things bump good things, and good things don't bump other good things.
I guess it's up to you to decide how to make the lists and iterate them.. Of course, there are other ways to do this I'm sure.
One way I could think off the top of my head is just collide EVERYTHING, and have some kind of flags to pick through. Is this an enemy? a blocked passage tile? etc, and handle each accordingly. If you're worried about a lot of duplicated checks, you could always keep a list in every object that makes sure it won't double check a previous collision, but linear searching like that might yield as much speed penalty as just doing the check again (albeit the a double check might produce undesirable results).
In any case, you have to rather predict how much collision will be happening on screen in a "busy" area/time frame, and decide what system would work best for you.
Sorry for the long babble :P
Author
thanks a lot for your guys help. i was about to email leavoia, but figured id just post this here instead. anyway, i was gunna start coding this but would like opinions from you guys before i start. i figure my last attempt at this took a week to do before i gave up, this time ill plan a little more.
first, id like to tell you, that object - > wall collision is implemented. ie even have projectile (bullet) - > character collision implemented. since no collision response is needed for this (when a bullet hits you, thats it, the bullets life ends), it was easy to implement bullets colliding with things. but i think id like to throw bullets into this system too, to keep everything grouped togeather, plus right now im doing some sloppy hacks to not check bullets against everything (a bunch of if statements basically, which is ugly).
make a pure virtual class called Collision_Object. have it look like this:
basically, ill keep a "master list" of all collision objects ( the static collision_obj_list). this list will manage itself, IE, all collision objects will register themselves with the list in their contructor, and will remove themselves from the list in their destructur. then ill have another static function which will perform all collision D / reaction, called Cycle.
where Rect is:
now have Player, Enemy, and Npc classes inherit from this. for example, i could do this:
now, that i have a "master list" of all collision objects, and can get their Rect info. its time to perform collision. this is where the Collision_Object::Cycle() comes in.
ok, this is as far as i can figure out. right now ill check each object against each other object (except themselves, hence the continue statement). but obviously i dont want to keep it like that, but for now just getting it working is all im concerned about. been thinking about it for a little while and just cant figure out how to do the proper collision detection / reaction. well, detection is easy, just use bounding box to see if the rectangles over-lap. its the reaction i dont understand. how do i re-position the objects so it appears they never collided in the first place? i just dont get that part. also thinking about it more, Collision_Object will probably need to know more then just the Rect, since it will have to at the least re-set the objects position, you know? maybe give the RO a virtual Set_Position() function also.
thanks for any help!!!
first, id like to tell you, that object - > wall collision is implemented. ie even have projectile (bullet) - > character collision implemented. since no collision response is needed for this (when a bullet hits you, thats it, the bullets life ends), it was easy to implement bullets colliding with things. but i think id like to throw bullets into this system too, to keep everything grouped togeather, plus right now im doing some sloppy hacks to not check bullets against everything (a bunch of if statements basically, which is ugly).
make a pure virtual class called Collision_Object. have it look like this:
class Collision_Object{ public: Collision_Object(){collision_obj_list.push_back(this);} Collision_Object(const Collision_Object &cpy){collision_obj_list.push_back(this);} ~Collision_Object(){collision_obj_list.remove(this);} virtual Rect Get_Rect() = 0; static list<Collision_Object*> collision_obj_list; static void Cycle();};basically, ill keep a "master list" of all collision objects ( the static collision_obj_list). this list will manage itself, IE, all collision objects will register themselves with the list in their contructor, and will remove themselves from the list in their destructur. then ill have another static function which will perform all collision D / reaction, called Cycle.
where Rect is:
struct Rect{ float x,y,w,h;};now have Player, Enemy, and Npc classes inherit from this. for example, i could do this:
Player::Get_Rect(){ return Rect r(x,y,w,h);}now, that i have a "master list" of all collision objects, and can get their Rect info. its time to perform collision. this is where the Collision_Object::Cycle() comes in.
void Collision_Object::Cycle(){ for(list<Collision_Object*>::iterator i = collision_obj_list.begin(); i != collision_obj_list.end(); i++) { for(list<Collision_Object*>::iterator i2 = collision_obj_list.begin(); i2 != collision_obj_list.end(); i2++) { if(i == i2) continue; do_schtuff_here(); } }}ok, this is as far as i can figure out. right now ill check each object against each other object (except themselves, hence the continue statement). but obviously i dont want to keep it like that, but for now just getting it working is all im concerned about. been thinking about it for a little while and just cant figure out how to do the proper collision detection / reaction. well, detection is easy, just use bounding box to see if the rectangles over-lap. its the reaction i dont understand. how do i re-position the objects so it appears they never collided in the first place? i just dont get that part. also thinking about it more, Collision_Object will probably need to know more then just the Rect, since it will have to at the least re-set the objects position, you know? maybe give the RO a virtual Set_Position() function also.
thanks for any help!!!
void Collision_Object::Cycle() { for(list<Collision_Object*>::iterator i = collision_obj_list.begin(); i != collision_obj_list.end(); i++) { for(list<Collision_Object*>::iterator i2 = collision_obj_list.begin(); i2 != collision_obj_list.end(); i2++) { if(i == i2) continue; do_schtuff_here(); } }}should be
void Collision_Object::Cycle() { for(list<Collision_Object*>::iterator i = collision_obj_list.begin(); i != collision_obj_list.end(); i++) { for(list<Collision_Object*>::iterator i2 = collision_obj_list.begin(); i2 != collision_obj_list.end(); i2++) { if( (*i) < (*i2)) { do_schtuff_here(); } } }}That will save you a lot of trouble. Refer to my earlier post. Also find a zip in your email.
Author
hey everyone,
leavoia's source code he sent me was a little over-whealming. well, really over-whealming =). basically, i just need to figure out how to respond to a collision. if 2 bounding boxes collide, how do i responde (ie move them) to it so that it looks like they never collided? keep in mind this can be 2 moving characters... surely there must be someone here who can describe to me how to do this ? thanks for any help!!
[Edited by - graveyard filla on August 22, 2004 3:33:50 PM]
leavoia's source code he sent me was a little over-whealming. well, really over-whealming =). basically, i just need to figure out how to respond to a collision. if 2 bounding boxes collide, how do i responde (ie move them) to it so that it looks like they never collided? keep in mind this can be 2 moving characters... surely there must be someone here who can describe to me how to do this ? thanks for any help!!
[Edited by - graveyard filla on August 22, 2004 3:33:50 PM]
Your email account is throwing errors, so here is my partial reply. also note that this subject can be found elsewhere on the forum if you search. It's a pop topic.
------------------
2 boxes overlap. To test their "overlapness", you already know. But for
response, there are a million ways to handle that. Ideally, you want the
response code to be a virtual function.
virtual RespondToCollision( collision_data -or- CollisionObject* );
That is harder than it looks, but if you are only working with boxes, it's a
piece of cake.
First of all, the reason it is a virtual is because not all objects will react
the same way of course. A land mine will explode on contact. Exploding is
it's reaction. A player will repell, an enemy will do damage, a wall of
spikes will inflict damage as well.
If you simply want to repell two objects away from each other, assuming you
already know they collide, find out which edges of the two objects are
closest. Either
- Object A's left edge with Object B's right edge, or
- Object A's right edge with Object B's left edge
same goes for the top and bottom. Find the difference between the two edges
and move each object in the other direction by exactly half that difference
(half for each). Something like that.
You need to decide if the penetration is more vertical or horizontal . If it's
more vertical, move away vertically. same for horizontal. If you do both,
you'll end up with the corners of the two boxes always touching and that's
not quite what you want.
The other cheaper way is the "reset" trick. You'll see this on some games
where you walk into a wall and the whole figure "stutters" back and forth
really quick. What happens is that you move the player and if the player
collides with another object, you reset to the previous pre-moving position.
The reason it's inelegant is that it doesn't work well for fast moving
objects and doesn't allow for "sliding".
For a lot for information, especially if you want to get into 2d polygon
collision, here is some good stuph from Oliii:
Important linky
------------------
2 boxes overlap. To test their "overlapness", you already know. But for
response, there are a million ways to handle that. Ideally, you want the
response code to be a virtual function.
virtual RespondToCollision( collision_data -or- CollisionObject* );
That is harder than it looks, but if you are only working with boxes, it's a
piece of cake.
First of all, the reason it is a virtual is because not all objects will react
the same way of course. A land mine will explode on contact. Exploding is
it's reaction. A player will repell, an enemy will do damage, a wall of
spikes will inflict damage as well.
If you simply want to repell two objects away from each other, assuming you
already know they collide, find out which edges of the two objects are
closest. Either
- Object A's left edge with Object B's right edge, or
- Object A's right edge with Object B's left edge
same goes for the top and bottom. Find the difference between the two edges
and move each object in the other direction by exactly half that difference
(half for each). Something like that.
You need to decide if the penetration is more vertical or horizontal . If it's
more vertical, move away vertically. same for horizontal. If you do both,
you'll end up with the corners of the two boxes always touching and that's
not quite what you want.
The other cheaper way is the "reset" trick. You'll see this on some games
where you walk into a wall and the whole figure "stutters" back and forth
really quick. What happens is that you move the player and if the player
collides with another object, you reset to the previous pre-moving position.
The reason it's inelegant is that it doesn't work well for fast moving
objects and doesn't allow for "sliding".
For a lot for information, especially if you want to get into 2d polygon
collision, here is some good stuph from Oliii:
Important linky
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
