Thread: RE: [Algorithms] Collision Detection on a MMORPG server
Brought to you by:
vexxed72
From: Guillaume P. <Gui...@ps...> - 2002-08-29 15:23:51
|
This is a good approach, but calculating collisions on a polygon soup can be quite expensive. I would either decompose the object into convex hulls: (cf - convex polyhedral surface decomposition) http://portal.acm.org/citation.cfm?id=220311&coll=portal&dl=ACM&CFID=4101614 &CFTOKEN=40529892#FullText Or treat the terrain as a height field, and wrap objects laying atop it in either hulls or some other, simpler primitive. Guillaume. -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Richard Fabian Sent: Thursday, August 29, 2002 9:41 AM To: 'Wong Kong Yew'; GDA...@li... Subject: RE: [Algorithms] Collision Detection on a MMORPG server Why do you need to slice the collision system by the max mag? Use a continuous collision system, and alleviate yourself of this problem... Continuous collision systems for RPGs can be quite simple if you declare people to be ellipsoids, and the world to be just a bunch of polygons... If you can, design out the activities that would dissallow the use of a continuous system (such as curved paths and rotational collisions...) > Behalf Of Wong Kong Yew > > The problem with the magnitude is simple, when the magnitude > is too large, I > will need to slice the magnitude to my max mag, and do the collision > multiple times depending on the no of slices, this actually make the > collision detection slower and actually increases the > magnitude in the next > frame, and this will actually go on forever. The reason for > capping the > magnitude is because when the magnitude is too big the > collision detection > routine will start giving me invalid result. > > Actually the 1000 AI is just a worse case scenario. It will > be probably > less. ------------------------------------------------------- This sf.net email is sponsored by:ThinkGeek Welcome to geek heaven. http://thinkgeek.com/sf _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |
From: Chris B. (BUNGIE) <cbu...@mi...> - 2002-08-29 17:03:24
|
You need to have a lot of trust in your pathfinding system to use the no-collision system that you describe. And since you can never trust any pathfinding solution in a dynamic environment to be 100% reliable, I've found that there often needs to be more effort spent on the transition back into a collidable state - i.e. "Find out whether my pathfinding made me walk into a solid object, and then find a safe place for me to be standing nearby". This can lead to a huge amount of grief. I used this technique aggressively on Oni and we were never able to fix all the bugs that resulted from it. Even in the shipping build, if you know what you're doing, you can find Oni characters standing on the roof, embedded in stairs, on the wrong side of locked doors, inside solid columns or (my favourite) standing around idly in the wrong place while a cutscene takes place around them. Having said that, there are some scenarios where it makes sense to place that level of trust in your pathfinding. I imagine that the people working at Elixir do something similar for their AI characters in Republic, as there really aren't dynamic obstacles of the kinds I describe when you're walking around outdoors in their city. -- Chris Butcher Rendering & Simulation Lead Halo 2 | Bungie Studios bu...@bu... =20 -----Original Message----- From: Scott Shumaker [mailto:ssh...@ou...]=20 Sent: Thursday, August 29, 2002 08:31 To: GDA...@li... Subject: RE: [Algorithms] Collision Detection on a MMORPG server I'd imagine some sort of LOD scheme would work pretty well. Example: If an AI isn't moving, you don't need to do any collision detection against the world geometry. If the AI is moving and there are no players around, you could just have the AI follow pathfinding and fly through space, ignoring all geometry. If players are far enough away, the AI can even just warp to its destination. If there are players around, you can set up the pathfinding so you basically do very little collision detection - the AI should pathfind around obstacles and properly navigate through interior environments. The geometry can all be analyzed offline to generate a path graph that doesn't do anything illegal like pass through walls. If your pathfinding system doesn't support this, you could always have the level designers place routes or path nodes that avoid colliding with the walls. If AIs stay on the path, they're guaranteed to not collide with any geometry, so you don't need general purpose collision-detection. If AIs get knocked off the pathfinding grid somehow (when they try to pursue a player, perhaps), you could always run through real collision detection until they get back on. You'll still need to do collision detection against other moving objects, but simple sphere-to-sphere (or ray-to-sphere) with spatial subdivision should make that more feasible. And once again, you really don't need to do anything when there are no players nearby. Scott -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Richard Fabian Sent: Thursday, August 29, 2002 9:41 AM To: 'Wong Kong Yew'; GDA...@li... Subject: RE: [Algorithms] Collision Detection on a MMORPG server Why do you need to slice the collision system by the max mag? Use a continuous collision system, and alleviate yourself of this problem... Continuous collision systems for RPGs can be quite simple if you declare people to be ellipsoids, and the world to be just a bunch of polygons... If you can, design out the activities that would dissallow the use of a continuous system (such as curved paths and rotational collisions...) > Behalf Of Wong Kong Yew > > The problem with the magnitude is simple, when the magnitude > is too large, I > will need to slice the magnitude to my max mag, and do the collision > multiple times depending on the no of slices, this actually make the > collision detection slower and actually increases the > magnitude in the next > frame, and this will actually go on forever. The reason for > capping the > magnitude is because when the magnitude is too big the > collision detection > routine will start giving me invalid result. > > Actually the 1000 AI is just a worse case scenario. It will > be probably > less. ------------------------------------------------------- This sf.net email is sponsored by:ThinkGeek Welcome to geek heaven. http://thinkgeek.com/sf _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 -- Scott Shumaker Assistant Lead Programmer, "Mystery Project" Outrage Games - THQ ssh...@ou... -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Richard Fabian Sent: Thursday, August 29, 2002 9:41 AM To: 'Wong Kong Yew'; GDA...@li... Subject: RE: [Algorithms] Collision Detection on a MMORPG server Why do you need to slice the collision system by the max mag? Use a continuous collision system, and alleviate yourself of this problem... Continuous collision systems for RPGs can be quite simple if you declare people to be ellipsoids, and the world to be just a bunch of polygons... If you can, design out the activities that would dissallow the use of a continuous system (such as curved paths and rotational collisions...) > Behalf Of Wong Kong Yew > > The problem with the magnitude is simple, when the magnitude > is too large, I > will need to slice the magnitude to my max mag, and do the collision > multiple times depending on the no of slices, this actually make the > collision detection slower and actually increases the > magnitude in the next > frame, and this will actually go on forever. The reason for > capping the > magnitude is because when the magnitude is too big the > collision detection > routine will start giving me invalid result. > > Actually the 1000 AI is just a worse case scenario. It will > be probably > less. ------------------------------------------------------- This sf.net email is sponsored by:ThinkGeek Welcome to geek heaven. http://thinkgeek.com/sf _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 ------------------------------------------------------- This sf.net email is sponsored by:ThinkGeek Welcome to geek heaven. http://thinkgeek.com/sf _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 |
From: Scott S. <ssh...@ou...> - 2002-08-29 19:01:24
|
You have a good point. However, most MMORPGS I've seen have pretty static environments. In fact, I'm pretty sure the only thing remotely dynamic in EQ is the occasional door and teleporter, which can be handled as special nodes in your pathfinding system. In a static world, if an AI is moving between two points that can be located on your pathfinding 'grid', you should be able to guarantee that the AI does not cross any intervening geometry, or at least not noticeably (If the AI is very large you might see parts of it clip through narrow passageways). The overall behavior would be correct, though; you wouldn't end up with an AI stopping inside a solid object; at most it would brush by it on its way to a valid destination. In a dynamic environment, you can run mostly through the static code but check for collisions against only the dynamic portions, which can simplify your problem. If the AI needs to veer off to avoid a dynamic obstacle, you'll need to run full collision detection on both static and dynamic geometry, of course, since you may be going off the known pathfinding regions. If players are not nearby, only the end result of the pathfinding matters, so you can greatly simplify the problem (even teleportation is an option). But this brings us to your point - it's really dangerous to turn off collisions if the pathfinding system is going to place the destination inside a solid object. Trying to find a safe place nearby is a nightmare, especially in narrow hallways and non-smooth geometry (like stairs). In this case, the best option might just be to to rewind time a few seconds, and then simulate forward with collision detection on to reach an eventual resting point. How did you approach this problem in Oni? Scott -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Chris Butcher (BUNGIE) Sent: Thursday, August 29, 2002 1:03 PM To: GDA...@li... Subject: RE: [Algorithms] Collision Detection on a MMORPG server You need to have a lot of trust in your pathfinding system to use the no-collision system that you describe. And since you can never trust any pathfinding solution in a dynamic environment to be 100% reliable, I've found that there often needs to be more effort spent on the transition back into a collidable state - i.e. "Find out whether my pathfinding made me walk into a solid object, and then find a safe place for me to be standing nearby". This can lead to a huge amount of grief. I used this technique aggressively on Oni and we were never able to fix all the bugs that resulted from it. Even in the shipping build, if you know what you're doing, you can find Oni characters standing on the roof, embedded in stairs, on the wrong side of locked doors, inside solid columns or (my favourite) standing around idly in the wrong place while a cutscene takes place around them. Having said that, there are some scenarios where it makes sense to place that level of trust in your pathfinding. I imagine that the people working at Elixir do something similar for their AI characters in Republic, as there really aren't dynamic obstacles of the kinds I describe when you're walking around outdoors in their city. -- Chris Butcher Rendering & Simulation Lead Halo 2 | Bungie Studios bu...@bu... -----Original Message----- From: Scott Shumaker [mailto:ssh...@ou...] Sent: Thursday, August 29, 2002 08:31 To: GDA...@li... Subject: RE: [Algorithms] Collision Detection on a MMORPG server I'd imagine some sort of LOD scheme would work pretty well. Example: If an AI isn't moving, you don't need to do any collision detection against the world geometry. If the AI is moving and there are no players around, you could just have the AI follow pathfinding and fly through space, ignoring all geometry. If players are far enough away, the AI can even just warp to its destination. If there are players around, you can set up the pathfinding so you basically do very little collision detection - the AI should pathfind around obstacles and properly navigate through interior environments. The geometry can all be analyzed offline to generate a path graph that doesn't do anything illegal like pass through walls. If your pathfinding system doesn't support this, you could always have the level designers place routes or path nodes that avoid colliding with the walls. If AIs stay on the path, they're guaranteed to not collide with any geometry, so you don't need general purpose collision-detection. If AIs get knocked off the pathfinding grid somehow (when they try to pursue a player, perhaps), you could always run through real collision detection until they get back on. You'll still need to do collision detection against other moving objects, but simple sphere-to-sphere (or ray-to-sphere) with spatial subdivision should make that more feasible. And once again, you really don't need to do anything when there are no players nearby. Scott -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Richard Fabian Sent: Thursday, August 29, 2002 9:41 AM To: 'Wong Kong Yew'; GDA...@li... Subject: RE: [Algorithms] Collision Detection on a MMORPG server Why do you need to slice the collision system by the max mag? Use a continuous collision system, and alleviate yourself of this problem... Continuous collision systems for RPGs can be quite simple if you declare people to be ellipsoids, and the world to be just a bunch of polygons... If you can, design out the activities that would dissallow the use of a continuous system (such as curved paths and rotational collisions...) > Behalf Of Wong Kong Yew > > The problem with the magnitude is simple, when the magnitude > is too large, I > will need to slice the magnitude to my max mag, and do the collision > multiple times depending on the no of slices, this actually make the > collision detection slower and actually increases the > magnitude in the next > frame, and this will actually go on forever. The reason for > capping the > magnitude is because when the magnitude is too big the > collision detection > routine will start giving me invalid result. > > Actually the 1000 AI is just a worse case scenario. It will > be probably > less. ------------------------------------------------------- This sf.net email is sponsored by:ThinkGeek Welcome to geek heaven. http://thinkgeek.com/sf _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 -- Scott Shumaker Assistant Lead Programmer, "Mystery Project" Outrage Games - THQ ssh...@ou... -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Richard Fabian Sent: Thursday, August 29, 2002 9:41 AM To: 'Wong Kong Yew'; GDA...@li... Subject: RE: [Algorithms] Collision Detection on a MMORPG server Why do you need to slice the collision system by the max mag? Use a continuous collision system, and alleviate yourself of this problem... Continuous collision systems for RPGs can be quite simple if you declare people to be ellipsoids, and the world to be just a bunch of polygons... If you can, design out the activities that would dissallow the use of a continuous system (such as curved paths and rotational collisions...) > Behalf Of Wong Kong Yew > > The problem with the magnitude is simple, when the magnitude > is too large, I > will need to slice the magnitude to my max mag, and do the collision > multiple times depending on the no of slices, this actually make the > collision detection slower and actually increases the > magnitude in the next > frame, and this will actually go on forever. The reason for > capping the > magnitude is because when the magnitude is too big the > collision detection > routine will start giving me invalid result. > > Actually the 1000 AI is just a worse case scenario. It will > be probably > less. ------------------------------------------------------- This sf.net email is sponsored by:ThinkGeek Welcome to geek heaven. http://thinkgeek.com/sf _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ------------------------------------------------------- This sf.net email is sponsored by:ThinkGeek Welcome to geek heaven. http://thinkgeek.com/sf _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ------------------------------------------------------- This sf.net email is sponsored by:ThinkGeek Welcome to geek heaven. http://thinkgeek.com/sf _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: Nick P. <NPe...@cl...> - 2002-08-30 12:53:12
|
Are you testing your ellipsoid against each candidate triangle's edges (and corners) as well as the plane? Glancing tests against planes can yield precision errors, leading to incorrect results (make sure your epsilon is robust enough) - make sure you're also testing against the edges and corners. Cheers, .....Nick Pelling..... -----Original Message----- From: Wong Kong Yew [mailto:kon...@ph...] Sent: 30 August 2002 03:30 To: Richard Fabian; GDA...@li... Subject: Re: [Algorithms] Collision Detection on a MMORPG server Actually I am using continuous collision system and ellipsoid as the characters for collision. The problem with this technique is that when the magnitude get too large sometimes it will failed to determine collision with a triangle. This usually happened when the triangle is slightly slanted/ almost parallel to the direction. So in the next loop, the character will fall right through the triangle. |