Implement ray cast selection through non-uniform 3D grid

[afritz1]

The current ray casting system for clicking on doors and things is flattened to a 2D plane for simplicity and bootstrapping support for interacting with some of the game's features, but it doesn't allow for things like selecting loot piles or keys on raised platforms.

The height of voxels in Arena is not constant; some dungeons have fairly square walls, others have very high walls, which makes this problem a little more difficult in my mind.

The ideal system would step through the 3D grid of voxels and do ray intersection tests with the various voxel types (wall, raised platform, etc.) and sprites. Not sure yet how I want to store entity references per voxel, maybe a mapping of entity ID to a set of voxels.

Probably just need to sit down and do the math for this, but if anyone else wants to help out, that'd be nice.

To do:

• [x] Obtain voxel intersection data from ray casting through 3D grid
  • [x] Wall
  • [x] Floor
  • [x] Ceiling
  • [x] Raised
  • [x] Diagonal
  • [x] Transparent Wall
  • [x] Edge
  • [x] Chasm
  • [x] Door
• [x] Obtain sprite intersection data from ray casting through 3D grid

Places of note:

• Physics::rayCast()
• VoxelData class
• Entity::getAnimation() for obtaining entity animation frame and dimensions in world space

[Digital-Monk]

Just thinking out loud, and tossing out something from the land of OpenGL: If you render the scene without lighting/fog, and instead of texturing you use solid colors where the color isn't actually a color but is an object ID, then the final "image" is really a map of the object ID for every pixel on the screen.

Not sure if that actually helps you, though. I mean, your entire renderer is in software, so you already have the 3D raycasting needed for any given pixel query. The ID-as-color trick is all about letting OpenGL handle perspective and depth and occlusion and so forth, but I'm not sure it's helpful to you...

(Really excited by this project, btw!)

[afritz1]

I considered doing it that way but doing the ray casting separately is what was decided on. It has an option for pixel-perfect selection too, which is implemented by giving the intersection information to the renderer and having it do a texture look-up at the UV coordinates determined by the entity hit point. See pull request #169.

There are certain complications with doing it the way you suggested. For example, transparent walls without collision such as archways block ray casts, so there might also need to be some kind of stencil buffer for what object IDs to conditionally write to the screen, and that's just getting a little too complicated/expensive to shade.

Memory bandwidth is at a premium with a software renderer and I wouldn't want to have to read/write from three (or even four) frame buffers (color, depth, object IDs, object ID stencil buffer).

Thanks for the idea though.

[afritz1]

Closing this for now and putting remaining tasks in a separate polish issue #172.