RE: [Algorithms] Collision Detection on a MMORPG server
Brought to you by:
vexxed72
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 |