RE: [Algorithms] Collision Detection on a MMORPG server

 RE: [Algorithms] Collision Detection on a MMORPG server From: Richard Fabian - 2002-08-29 13:41:06 ```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. ```

Thread view

 [Algorithms] Collision Detection on a MMORPG server From: Wong Kong Yew - 2002-08-29 08:05:57 ```Hi, I was just wondering, how MMORPG games do collision detection for their AI? Especially since there could be 1000 AI on a single server. Wouldn't it be too slow? I mean I see games like DAOC that does no collision for trees, their AI just go right through them. This is one of the potential way to simplify collision detection. Especially on terrain, you can easily find out the highest point the AI is on the terrain by heighmap or simple calculation. But on an indoor scenes with lots of collision triangles, this will slow it down a lot. Also because most collision detection & resolution routine need to cap the magnitude so that it will not cause too many problems, basically the slower it get, the worse it become beacuse the magnitude will be bigger and bigger. What others ways is there to do collision detection for 1000 AIs for maybe at least 2-3 times per seconds? I and just thinking of optimisation and simplication possible. regard, Kong Yew, Wong Phoenix Games Studio ```
 RE: [Algorithms] Collision Detection on a MMORPG server From: Richard Fabian - 2002-08-29 08:33:01 ```> Behalf Of Wong Kong Yew > > I was just wondering, how MMORPG games do collision detection > for their AI? > Especially since there could be 1000 AI on a single server. > Wouldn't it be > too slow? Not if you are REALLY running a MMORPG, as you should be able to dump off the collision system as a parrallel process on another machine(s)... If not, then you can just do full collision detection on Ais in sight of a player... > I mean I see games like DAOC that does no collision for > trees, their AI just > go right through them. This is one of the potential way to simplify > collision detection. Especially on terrain, you can easily > find out the > highest point the AI is on the terrain by heighmap or simple > calculation. > But on an indoor scenes with lots of collision triangles, > this will slow it > down a lot. Also because most collision detection & > resolution routine need > to cap the magnitude so that it will not cause too many > problems, basically > the slower it get, the worse it become beacuse the magnitude > will be bigger > and bigger. Larger magnitudes are actually better normally... Take two cases.. Timestep of 0.01 seconds... Timestep of 1 seconds With 0.01 seconds, you almost always get a no collision, but when you do it is very important, so you just have to keep doing it until you hit something. With 1 seconds, you almost always hit something, and you know when you hit it, so you can sleep the system until the dynamics change, or you would have collided. > What others ways is there to do collision detection for 1000 > AIs for maybe > at least 2-3 times per seconds? I and just thinking of > optimisation and > simplication possible. Try not to think about doing things x times per second, try approaching the problem from a "Tell me when I will do this" direction. E.g. have the collision system cap its magnitude at the point in time that the dynamics system expects to be modified... Then run the collision system ONCE. > regard, > > Kong Yew, Wong > Phoenix Games Studio ```
 Re: [Algorithms] Collision Detection on a MMORPG server From: Sin Chian - 2002-08-29 09:08:13 ```Just a small suggestion: why don't you divide your game world into many small areas and only check for collision between game objects that are found within the same area? One method that come to my mind immediately is the BSP (binary space partitioning) tree approach. You can organize your world and static objects in the world into a hierarchical BSP tree, this way you can quickly filter through the static objects that might be colliding with your moving AI-controlled entities. Another similar method is the Portal-based method. May be you would like to check out the article by Nick Bobic. http://www.gamasutra.com/features/20000330/bobic_pfv.htm Hope this is useful to you. ----- Original Message ----- From: "Wong Kong Yew" To: Sent: Thursday, August 29, 2002 4:20 PM Subject: [Algorithms] Collision Detection on a MMORPG server > Hi, > > I was just wondering, how MMORPG games do collision detection for their AI? > Especially since there could be 1000 AI on a single server. Wouldn't it be > too slow? > > I mean I see games like DAOC that does no collision for trees, their AI just > go right through them. This is one of the potential way to simplify > collision detection. Especially on terrain, you can easily find out the > highest point the AI is on the terrain by heighmap or simple calculation. > But on an indoor scenes with lots of collision triangles, this will slow it > down a lot. Also because most collision detection & resolution routine need > to cap the magnitude so that it will not cause too many problems, basically > the slower it get, the worse it become beacuse the magnitude will be bigger > and bigger. > > What others ways is there to do collision detection for 1000 AIs for maybe > at least 2-3 times per seconds? I and just thinking of optimisation and > simplication possible. > > regard, > > Kong Yew, Wong > Phoenix Games Studio > > > > ------------------------------------------------------- > This sf.net email is sponsored by:ThinkGeek > Welcome to geek heaven. > http://thinkgeek.com/sf > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ```
 Re: [Algorithms] Collision Detection on a MMORPG server From: Wong Kong Yew - 2002-08-29 09:34:31 ```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. ----- Original Message ----- From: "Sin Chian" To: "Wong Kong Yew" ; Sent: Thursday, August 29, 2002 5:01 PM Subject: Re: [Algorithms] Collision Detection on a MMORPG server > Just a small suggestion: why don't you divide your game world into many > small areas and only check for collision between game objects that are found > within the same area? > One method that come to my mind immediately is the BSP (binary space > partitioning) tree approach. You can organize your world and static objects > in the world into a hierarchical BSP tree, this way you can quickly filter > through the static objects that might be colliding with your moving > AI-controlled entities. Another similar method is the Portal-based method. > > May be you would like to check out the article by Nick Bobic. > > http://www.gamasutra.com/features/20000330/bobic_pfv.htm > > Hope this is useful to you. > > ----- Original Message ----- > From: "Wong Kong Yew" > To: > Sent: Thursday, August 29, 2002 4:20 PM > Subject: [Algorithms] Collision Detection on a MMORPG server > > > > Hi, > > > > I was just wondering, how MMORPG games do collision detection for their > AI? > > Especially since there could be 1000 AI on a single server. Wouldn't it be > > too slow? > > > > I mean I see games like DAOC that does no collision for trees, their AI > just > > go right through them. This is one of the potential way to simplify > > collision detection. Especially on terrain, you can easily find out the > > highest point the AI is on the terrain by heighmap or simple calculation. > > But on an indoor scenes with lots of collision triangles, this will slow > it > > down a lot. Also because most collision detection & resolution routine > need > > to cap the magnitude so that it will not cause too many problems, > basically > > the slower it get, the worse it become beacuse the magnitude will be > bigger > > and bigger. > > > > What others ways is there to do collision detection for 1000 AIs for maybe > > at least 2-3 times per seconds? I and just thinking of optimisation and > > simplication possible. > > > > regard, > > > > Kong Yew, Wong > > Phoenix Games Studio > > > > > > > > ------------------------------------------------------- > > This sf.net email is sponsored by:ThinkGeek > > Welcome to geek heaven. > > http://thinkgeek.com/sf > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > ```
 RE: [Algorithms] Collision Detection on a MMORPG server From: Richard Fabian - 2002-08-29 13:41:06 ```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. ```
 RE: [Algorithms] Collision Detection on a MMORPG server From: Scott Shumaker - 2002-08-29 15:30:04 ```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: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...]On Behalf Of Richard Fabian Sent: Thursday, August 29, 2002 9:41 AM To: 'Wong Kong Yew'; GDAlgorithms-list@... 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 GDAlgorithms-list@... 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 sshumaker@... -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...]On Behalf Of Richard Fabian Sent: Thursday, August 29, 2002 9:41 AM To: 'Wong Kong Yew'; GDAlgorithms-list@... 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 GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ```
 Re: [Algorithms] Collision Detection on a MMORPG server From: Wong Kong Yew - 2002-08-30 02:15:47 ```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. ----- Original Message ----- From: "Richard Fabian" To: "'Wong Kong Yew'" ; Sent: Thursday, August 29, 2002 9:41 PM 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. > > ```
 Re: [Algorithms] Collision Detection on a MMORPG server From: Toong See Wan - 2002-09-03 14:09:13 ```I believe that u could try using an Sphere Tree . It should be very cheap to cull alway objects before u do a detail collision test. Also why do u need to test it with triangles? Would u have alot of triangles to test the collision with? Toong See Wan Surreal Online Pte Ltd ----- Original Message ----- From: "Wong Kong Yew" To: "Richard Fabian" ; Sent: Friday, August 30, 2002 10:30 AM 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. > > > ----- Original Message ----- > From: "Richard Fabian" > To: "'Wong Kong Yew'" ; > > Sent: Thursday, August 29, 2002 9:41 PM > 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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```