3D 'physics' for huge world (Solved)
Yo, Its been a while since I've actually asked a question but I've got little experience in this region and so far I've come up short.
Sorry I got a bit Lengthy, the main portions are my #'ed Requirements for the system, and the Data-Set section if ya only want to see the major points.
Basically I have a huge environment, completely 3d meaning objects and surfaces going every which way. Ok anyway, I don't need or really want full featured physics hence the quotes. I need 3 things,
1. Navigate Surfaces that are not slopes ( Dot(Normal,Up) < 0.707 )
2. Not walk into walls (meaning characters have a radius)
3. Not fall through floors, meaning they just need to stand on the surfaces.
I don't need characters to be able to walk off edges, or fall, if I can its a plus but I don't need it.
Data-Set:
Objects exist in element form, have a matrix to transform data to final data, objects can be anything from boxes, to buildings or even height maps.
I already have a way to process all this data into a polygon soup, and a quad tree like method that can find local triangles fast.
Objects can intersect, however there doesn't need to be support for 'stair' like objects where you can hop up small distances.
Previous-Attempts:
So far I have tried a few things including cutting all the triangles on their edges and intersections and creating a 'linked list' of triangles that a character can transverse, and simple line vs triangle collision tests with 'gravity' just to keep them on the ground.
Neither turned out well,
the first ended up having duplicate edge issues, and I never could find a way to prevent the character from going straight up to a wall and stand half-in-half-out of it.
The attempt at adding simple physics was far to slow for the requirements, each physics step took around 0.1 seconds for 10,000 objects. which is too slow for my system, especially considering that it was only part of the planned method.
Final-Statement:
I hope that some one with some experience in this area can perhaps outline a method for doing this or perhaps point me in the right direction.
Thanks for takeing your time to read and consider my problem.
[Edited by - AlgorithmX2 on March 7, 2007 2:24:24 PM]
Objects at rest can be ignored until something in motion gets near them.
To prevent a player from walking 'half into' a wall, he needs a radius greater than 0. And a collision check that accounts for this.
To prevent a player from walking 'half into' a wall, he needs a radius greater than 0. And a collision check that accounts for this.
So you want a cityscape with agents walking around, and you want 10,000 of them!
First off, I know a guy who did research for something similar, for A.I. and simulating cities.
The basic way of doing it is first to isolate the walkable surfaces into a mesh. Mesh can be 3D of course. That mesh represents the part of the world the agents can walk in. Then that mesh is partitioned into convex pieces, each piece linked to each other for agent navigation and localisation.
For the collision, it can be rather crude. Since you have the triangles underneath, you can use barycentric coordinates to fix the agents on the floor. That should be fairly quick. You can also look up the paper on Autonomous Agent Steering.
Secondly, How much accuracy do you need for your agents. I mean, if a guy is programmed to walk from A to B a mile away, and you don't actually see him moving, do you really need to compute his movement every frame? What you can do instead is use his programmed path, and when he comes into view, quickly evaluate where he should be, place him there, and switch on his simulation to a finer degree (switch on his walk animation, his collision...). a behavioral LOD if you will. These agent AI is usually very simple, and worked on programmed events, like a giant state machine. Wake up at 8:00, go to the kitchen, turn on the kettle, go for a shower... So at any moment in time, you can predict with a fair amout of accuracy where that guy should be and what he should be doing. It's the oldest trick in the book for games such as the old Ultima series, and Populous kind of stuff, where you play god and you have a multitude of little guys doing your bidding, but you're not quite sure what they are actually doing until you spy on them!
You can also totally fake it like in GTA. Turn around, and that sports car with a beautiful girl at the wheel that went just past you has been replaced by a 20 ton truck with a fat dude.
First off, I know a guy who did research for something similar, for A.I. and simulating cities.
The basic way of doing it is first to isolate the walkable surfaces into a mesh. Mesh can be 3D of course. That mesh represents the part of the world the agents can walk in. Then that mesh is partitioned into convex pieces, each piece linked to each other for agent navigation and localisation.
For the collision, it can be rather crude. Since you have the triangles underneath, you can use barycentric coordinates to fix the agents on the floor. That should be fairly quick. You can also look up the paper on Autonomous Agent Steering.
Secondly, How much accuracy do you need for your agents. I mean, if a guy is programmed to walk from A to B a mile away, and you don't actually see him moving, do you really need to compute his movement every frame? What you can do instead is use his programmed path, and when he comes into view, quickly evaluate where he should be, place him there, and switch on his simulation to a finer degree (switch on his walk animation, his collision...). a behavioral LOD if you will. These agent AI is usually very simple, and worked on programmed events, like a giant state machine. Wake up at 8:00, go to the kitchen, turn on the kettle, go for a shower... So at any moment in time, you can predict with a fair amout of accuracy where that guy should be and what he should be doing. It's the oldest trick in the book for games such as the old Ultima series, and Populous kind of stuff, where you play god and you have a multitude of little guys doing your bidding, but you're not quite sure what they are actually doing until you spy on them!
You can also totally fake it like in GTA. Turn around, and that sports car with a beautiful girl at the wheel that went just past you has been replaced by a 20 ton truck with a fat dude.
AP:
Hmmm I guess its true that those not in motion don't need calculations, however that truly doesn't solve the problem as they can all potentially move at the same time. since I'm only simulating Agents and Characters. barycentric coordinates to attach them to the floor, but how can I move them from one triangle to another in the soup seamlessly.
olii:
Not exactly a city scape, but a very large world that has number Agents and players in it, most need to be tracked, and they don't necessarily need to have destinations farther away then a few meters or so. So it doesn't necessarily have to be extremely robust, Thanks for that link however, I took a look and its extremely interesting I think I will need to add a few of these behaviors to my AI when I get there. I could easily sort the triangles into a list of walls and a list of floors however I don't have the understanding of how to work with them and the Agents or for that matter the players.
I've though about it and I figured for a simple way to prevent people from entering walls I would need a kinda of swept cylinder test, which I don't know to implement nor have I been successful in locating it, and I need a way to keep the Agents/Players on the surface. like you said I could use
At the moment my hardest part is just how to use the 3d data as a means to an end. I can't simply just drop the height values and make it 2d or anything. and some of the worst cases are very common, such as ramps being placed into a height map, and requiring you to walk over them to a location over a bridge, possibly with parts over head or a large pole with a 'wrapping ramp' around it taking you up many stories up a cliff.
Like I said I'm not really experienced in the area, most of my work so far in similar systems has been 2d, and thus much simpler.
Hmmm I guess its true that those not in motion don't need calculations, however that truly doesn't solve the problem as they can all potentially move at the same time. since I'm only simulating Agents and Characters. barycentric coordinates to attach them to the floor, but how can I move them from one triangle to another in the soup seamlessly.
olii:
Not exactly a city scape, but a very large world that has number Agents and players in it, most need to be tracked, and they don't necessarily need to have destinations farther away then a few meters or so. So it doesn't necessarily have to be extremely robust, Thanks for that link however, I took a look and its extremely interesting I think I will need to add a few of these behaviors to my AI when I get there. I could easily sort the triangles into a list of walls and a list of floors however I don't have the understanding of how to work with them and the Agents or for that matter the players.
I've though about it and I figured for a simple way to prevent people from entering walls I would need a kinda of swept cylinder test, which I don't know to implement nor have I been successful in locating it, and I need a way to keep the Agents/Players on the surface. like you said I could use
At the moment my hardest part is just how to use the 3d data as a means to an end. I can't simply just drop the height values and make it 2d or anything. and some of the worst cases are very common, such as ramps being placed into a height map, and requiring you to walk over them to a location over a bridge, possibly with parts over head or a large pole with a 'wrapping ramp' around it taking you up many stories up a cliff.
Like I said I'm not really experienced in the area, most of my work so far in similar systems has been 2d, and thus much simpler.
ok, I've got a couple of demos you might find useful for collision detection in 3D environments. They go up in complexity.
http://members.gamedev.net/oliii/very_basic_collision.rar
http://members.gamedev.net/oliii/satpost/DXInputs.h
http://members.gamedev.net/oliii/satpost/DXInputs.cpp
http://members.gamedev.net/oliii/satpost/3DSpherePolygonCollision.cpp
http://members.gamedev.net/oliii/satpost/3DBoxPolygonCollision.cpp
http://uk.geocities.com/olivier_rebellion/simple_collision.zip
For a large scale environment, a BVH (Bounding volume hierarchy) will certainly be on the menu. The last example uses a crude Axis Aligned bounding box hierarchy (I think this one is non-compressed). There are others.
Still, it's probably not enough for 10,000 agents. You will need to compromise and use shorcuts, unless you plan on running your sim on Deep Blue.
http://members.gamedev.net/oliii/very_basic_collision.rar
http://members.gamedev.net/oliii/satpost/DXInputs.h
http://members.gamedev.net/oliii/satpost/DXInputs.cpp
http://members.gamedev.net/oliii/satpost/3DSpherePolygonCollision.cpp
http://members.gamedev.net/oliii/satpost/3DBoxPolygonCollision.cpp
http://uk.geocities.com/olivier_rebellion/simple_collision.zip
For a large scale environment, a BVH (Bounding volume hierarchy) will certainly be on the menu. The last example uses a crude Axis Aligned bounding box hierarchy (I think this one is non-compressed). There are others.
Still, it's probably not enough for 10,000 agents. You will need to compromise and use shorcuts, unless you plan on running your sim on Deep Blue.
Well I really dont need complex collision or the like, Only simple characters are required, im doing mostly rpg style combat and such so I dont need actual accurate collision bodys that you might require for more interesting systems.
Its true 10,000 might be pushing it, perhapes I would think up a way to reduce the Agent Computational weight by ignoreing those far from a player, like mentioned eariler.
I don't have time to look over your demos at the moment but I'll take a look once I have a free moment.
Its true 10,000 might be pushing it, perhapes I would think up a way to reduce the Agent Computational weight by ignoreing those far from a player, like mentioned eariler.
I don't have time to look over your demos at the moment but I'll take a look once I have a free moment.
All I can say is wow, heh Based on David Eberly's math(saw in code), and your code I've created a simulation for 10,000 'agents' to at least stand or fall in a test environment with a fps of 10-13 and a time of ~.08 for one simulation I'm fairly amazed at how well this worked, I'm fairly confident that this will be able to handle the final requirements of my project.
Thank you very much for all your help.
Thank you very much for all your help.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement