# How to implement a symmetric 3d field of view algorithm for a roguelike

I've been thinking about adding 3d support in my roguelike. It would still be top-down like other roguelikes, yet it would have layers, such that things like platforms, tunnels, and bridges, etc, could be added to levels. Whether I do this hinges on whether I can get the fov routine I'm using working with the layers.

Note that I don't care that it doesn't make sense to some of you that I'm trying to have a 3d field of view routine for a 2d roguelike. The roguelike does have a 3d space, and I want to determine what the player can see, even if what the player can see can't logically be displayed. Let me worry about how to handle that problem.

I would be grateful for some advice in how to approach this problem. Perhaps this is utterly crazy, and I should just make a 2d roguelike...

Update:

I erroneously stated before that the problem with Bresenham's line algorithm was with artefacts. I should have mentioned that I needed the fov routine to be symmetric. Such a requirement can't be met by Bressenham's line algorithm.

• It's hard to grasp what you are trying to ask. You experienced some artefacts, what artefacts? And why? Dec 25, 2011 at 9:30
• Yes, we know the definition of the word "artefact". The problem is that the specific "artefact"s in question would go a long way into helping us find out what's wrong with what you're doing. Saying that there are "artefacts" is really no better than saying, "It doesn't work." What does it look like, and what do you expect it to look like? Dec 27, 2011 at 21:32

Real time strategy games routinely deal with this problem (take, for example, Starcraft 1 which was pseudo-3D) - maybe you could find some literature on how they managed it.

What I would do is probably pre-calculate some form of a 'visibility mesh' (akin to a navigation mesh). Each region of the mesh would link to regions that are visible to it. You should be able to lift a lot of logic from light-map generators (or possibly find a light-map library). Ideally you would place a large amount of lights in 'walkable' areas and calculate the light map for each, following this you would resolve similar areas into a single mesh.

This would probably result in a large amount of regions near corners - but corridors should be nice and clean.

To determine if two entities can see each other merely check if the meshes that contain them are connected; and that they are within field of view range.

• Note - don't do a A* search (like my original answer indicated). Unlike an a nav mesh you shouldn't be doing a 'visibility via' check; the regions need to be explicitly connected. Dec 28, 2011 at 11:56

Modifing a FOV algorithm to work in a 3D isn't terribly difficult, you need to have the algorithm take into account all possible directions in a sphere instead of just a circle.

Are you using a symmetric FOV algorithm now? If not, you should switch to one first, then make the modifications. If you put up the code/more information about the algorithm you are using now, we would be able to help you more.

• Considering how complicated the 2d version of the precise, permissive field of view algorithm already is, making a 3d version seems an act of lunacy. I may just have to give up on this. Dec 31, 2011 at 6:54

Make the algorithm symmetric, just implement a way of making sure that two points are always fed to the algorithm in the same order, no matter which is the viewer and which is the viewee. This is for instance easily done by giving all points an id and sorting by that.