Sign in to follow this  

Collision detection / response for enclosed 3d levels

This topic is 1957 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm looking for methods of handling collision detection and response for enclosed 3d levels where walls are not necessarily axis-aligned, and parts of the level could be over or under other parts (so there are ramps, but the player cannot jump off of a higher section and land on a lower one). The player is able to shoot projectiles.

I'd like to avoid using a full 3d physics engine since it seems like overkill, and I'd like to avoid having a physically based character controller. Also, learning has priority over actually making a game.

The projectiles seem like they should be pretty easy to handle to me. I can treat them as points and do line segment vs plane intersection testing for the walls. I'd probably put the walls into a grid/octree/etc.

What I'm not sure about is handling collision detection/response between the player and the level. One idea I had was to use a sort of "navmesh" for determining where the player could walk. I would constrain the player's movement to the "navmesh" by tracking the triangle that they are currently on, and using BFS to find a path to their target location. I'd probably put the navmesh triangles into a grid/octree as well, to aid in finding the starting triangle when the player is spawned, for example. Having the navmesh might also be useful for when I get to NPCs.

I'm thinking the trickiest part of this approach would be the creation of the navmesh. I would like to be able to just cover the entire walkable area with a mesh in Blender/etc and then programmatically offset it based on the player's radius, which would allow me to treat the player as a point instead of a sphere. It seems like this would be tricky when the angle between two wall segments is greater than 180 degrees on the inside of the level (or less than 180 on the outside) since it would require additional vertices, and then I'd need to generate additional triangles.

Any suggestions? Thanks.

Share this post


Link to post
Share on other sites
[quote name='jrh2365' timestamp='1343824333' post='4965184']
I'd like to avoid using a full 3d physics engine since it seems like overkill,
[/quote]
Sorry, but this is the way to go, everything else will be a very painful experience.

[quote name='jrh2365' timestamp='1343824333' post='4965184']
and I'd like to avoid having a physically based character controller.
[/quote]
Even when using a phyiscs engine, you can control a character without using forces. In this case you only utilise the collision detection features of a physics engine.

[quote name='jrh2365' timestamp='1343824333' post='4965184']
The projectiles seem like they should be pretty easy to handle to me.
[/quote]
Projectiles are a very good example of objects which can be simulated with a physics engine.

[quote name='jrh2365' timestamp='1343824333' post='4965184']
What I'm not sure about is handling collision detection/response between the player and the level. One idea I had was to use a sort of "navmesh" for determining where the player could walk. I would constrain the player's movement to the "navmesh" by tracking the triangle that they are currently on, and using BFS to find a path to their target location. I'd probably put the navmesh triangles into a grid/octree as well, to aid in finding the starting triangle when the player is spawned, for example. Having the navmesh might also be useful for when I get to NPCs.
[/quote]
Though this is a valid option, it is still a physics engine (you project the 3d environment on a pseudo 2d environment, still you need collision detection and your projectiles will need special handling).

My suguestion: evaluate some physic engines (like [url="http://bulletphysics.org/wordpress/"]bullet[/url], btw. using in the blender game engine), you will see, that using a phyiscs engine isn't that terrible Edited by Ashaman73

Share this post


Link to post
Share on other sites
Navigation meshes are extremely cool and fast, and well worth it for AI creatures (doing real physics on a whole bunch of AI characters uses up a lot of CPU and opens up a can of worms with giving 'solid' behaviour). They *can* also be used for your main character physics, providing you are willing to put up with a lot of limitations. This kind of approach is very valid for e.g. a mobile phone, where you can save yourself a lot of CPU using this approach.

But you have to have a playstyle that will work with it, otherwise you end up needing to implement a full collision detection / physics system in addition to the navmesh. I think the projectiles could be the problem, you are going to end up needing either a full collision mesh for the level, or at least building a simplified version of it for the projectile collisions. At which point you have to ask whether it would be better to have full physics main character and be done with it.

An alternative is to tweak your game design so you don't need the full collision mesh. Perhaps instead of using projectiles, only allow your characters melee combat.

Share this post


Link to post
Share on other sites
[quote name='Ashaman73' timestamp='1343824842' post='4965187']
Even when using a phyiscs engine, you can control a character without using forces. In this case you only utilise the collision detection features of a physics engine
[/quote]
Which part of Bullet would I use for doing that? It looks like maybe ContactTest mentioned here? [url="https://code.google.com/p/bulletsharp/wiki/CollisionCallbacksAndTriggers"]https://code.google....acksAndTriggers[/url] The issue with only using the collision detection features is that then I have to implement sliding collision myself, and I'm not entirely sure how that would work. A specific issue that comes to mind is how to handle corners where the angle between the walls is acute. Simply pushing the character out of one wall would push them into the other wall. I don't think I would run into that issue with the navmesh which is one of the reasons I was considering it, but the problem there is how to offset the navmesh from the walls.

[quote name='lawnjelly' timestamp='1343829429' post='4965205']
They *can* also be used for your main character physics, providing you are willing to put up with a lot of limitations. This kind of approach is very valid for e.g. a mobile phone, where you can save yourself a lot of CPU using this approach.
[/quote]
Good to know, thanks.

I'd need a full collision mesh for the level either way. I don't think it would be too bad to do the projectile collision myself, though. The main issue is how to get nice sliding collision for the character (preferably without having to use forces). If I can do that more easily with a physics engine, then I'll do so and use it for the projectiles as well.

Share this post


Link to post
Share on other sites
Wall sliding is done by moving the colliding object along the collision normal until he stops colliding.
I assume any physics engine gives a collision listener which also feeds the collision "force", which is just the penetration vector's length.
You can use that to apply your own response, but remember to check the normal's direction, or you'll slide down on ramps too.

Share this post


Link to post
Share on other sites
[quote name='wolfscaptain' timestamp='1343908973' post='4965492']
Wall sliding is done by moving the colliding object along the collision normal until he stops colliding.
I assume any physics engine gives a collision listener which also feeds the collision "force", which is just the penetration vector's length.
[/quote]
I understand that, but how would you handle the cases where moving the object out along the normal causes it to collide with something else. For example, if the character tries to move into a corner with an angle of less than 90 degrees. Moving the character out of one wall could push them into the other wall.

Share this post


Link to post
Share on other sites

This topic is 1957 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this