views:

620

answers:

4

Disclaimer: I'm not actually trying to make one I'm just curious as to how it could be done.

When I say "Most Accurate" I include the basics

  • wall
  • distance
  • light levels

and the more complicated

  • Dust in Atmosphere
  • rain, sleet, snow
  • clouds
  • vegetation
  • smoke
  • fire

If I were to want to program this, what resources should I look into and what things should I watch out for? Also, are there any relevant books on the theory behind line of sight including all these variables?

+2  A: 

Typically, one represents the world as a set of volumes of space held in some kind of space partitioning data structure, then intersects the ray representing your "line of sight" with that structure to find the set of objects it hits; these are then walked in order from ray origin to determine the overall result. Reflective objects cause further rays to be fired, opaque objects stop the walk and semitransparent objects partially contribute to the result.

You might like to read up on ray tracing; there is a great body of literature on the subject and well-understood ways of solving what are basically the same problems you list exist.

moonshadow
most ray tracing resources that I've seen have focused soley on what I listed as the basics, and I couldn't find anything related to any of the advanced
Soldier.moth
Just think of all those things as semitransparent objects. So, smoke is a volume of space that contributes an amount of opacity proportional to the length of the section of ray that crosses it, etc. For actual raytracing you'd also need to read up on subjects like procedural noise generation, but for LOS you're just interested in opacity/reflectiveness, right?
moonshadow
A: 

There is no "one algorithm" for these since the inputs are not well defined. If you treat Dust-In-Atmosphere as a constant value then there is an algorithm that can take it into account, but the fact is that dust levels will vary from point to point, and thus the algorithm you want needs to be aware of how your dust-data is structured.

The most used algorithm in todays ray-tracers is just incremental ray-marching, which is by definition not correct, but it does approximate the Ultimate Answer to a fair degree.

Even if you managed to incorporate all these properties into a single master-algorithm, you'd still have to somehow deal with how different people perceive the same setting. Some people are near-sighted, some far-sighted. Then there's the colour-blind. Not to mention that Dust-In-Atmosphere levels also affect tear-glands, which in turn affects visibility. And then there's the whole dichotomy between what people are actually seeying and what they think they are seeying...

There are far too many variables here to aim for a unified solution. Treat your environment as a voxelated space and shoot your rays through it. I suspect that's the only solution you'll be able to complete within a single lifetime...

David Rutten
+3  A: 

I personally don't know too much about this topic but a quick couple of Google searches turns up some formal papers that contain some very relevant information:

http://www.tecgraf.puc-rio.br/publications/artigo_1999_efficient_lineofsight_algorithms.pdf - Provides a detailed description of two different methods of efficiently performing an LOS calculation, along with issues involved

http://www.agc.army.mil/operations/programs/LOS/LOS%20Compendium.doc - This one aims to maintain "a current list of unique LOS algorithms"; it has a section listing quite a few and describing them in detail with a focus on military applications.

Hope this helps!

Donut
+2  A: 

The obvious question is do you really want the most accurate, and why?

I've worked on games that depended on line of sight and you really need to think clearly about what kind of line of sight you want.

First, can the AI see any part of your body? Or are you talking about "eye to eye" LOS?

Second, if the player's camera view is not his avatar's eye view, the player will not perceive your highly accurate LOS as highly accurate. At which point inaccuracies are fine.

I'm not trying to dissuade you, but remember that player experience is #1, and that might mean not having the best LOS.

A good friend of mine has done the AI for a long=-running series of popular console games. He often tells a story about how the AIs are most interesting (and fun) in the first game, because they stumble into you rather than see you from afar. Now, he has great LOS and spends his time trying to dumb them down to make them as fun as they were in the first game.

So why are you doing this? Does the game need it? Or do you just want the challenge?

Nosredna
The challenge was a big part of it, the thought came to me when I was looking into Weather forecasting models and wondered how hard it would be to create a line of sight algorithm to work with them.
Soldier.moth