Is there an algorithm or method people recommend for accomplishing collision detection on a terrain that has concavity and things like caves? I have been using the GJK and EPA algorithms for collision detection and then breaking down concave shapes into multiple convex shapes but this method becomes problematic when dealing with a potentially massive triangle mesh like terrain.

I think a common practice is to break up the terrain triangle mesh into a grid of squares. This allows you to construct a spatial grid or quadtree of triangle meshes and you can use this to easily figure out which sections of the triangle mesh to actually perform collision detection on. Breaking it up into squares can also be good for streaming in and out different terrain chunks if the world is so big you don't want to keep it all in memory at the same time.

For something like a cave, you might need to have a special case that checks if you are in or near the cave first and then performs the collision detection if that special case is met.

I forgot to mention that I am asking for a 3D space situation. So I assume the squares would be cubes in this case? What about randomly generated terrain with the possibility of real time editing? Like a person can dig to create their own cave. It seems like needing a special case for caves would make this situation difficult. Thank you for the reply.