Interesting to hear that the ray checks are still rather expensive. Ray-tracing software tends to say otherwise, but they have several methods of overcoming of these limitations.
Uhh, no, raytracing is still incredibly expensive. There's a reason why raytracing isn't used in interactive graphics.
The most commonly used trick in real lens design softwares is to use sequential ray-tracing, meaning that the program always knows what surface follows which and is unaware of the surfaces outside the now intersected and the following to be intersected surface.
But that's something you can't do in raycasting. Not that you'd have to; a raycast delivers a boolean result, true if there is a line to target, false if not.
But this can't be used in a dynamic environment. The other trick is to use bounding volumes, no doubt they are already used in the FPSs, or are they?
Bounding boxes are used extensively, especially when it comes to determining hit locations on actors (an actor being defined as being anything under AI or player control, as opposed to level geometry).
Generally, I'd think that the LOS determination can be done parallel to some extent.
Oh, certainly. And I believe modern engines do this quite often, but this only distributes the cost, it doesn't really reduce it.
What I have heard of path finding, the most common thing seems to be several predetermined way points along the level, more than this I don't know.
As i said above, and as mentioned in the article battuta linked, this is indeed so.
Nevertheless, finding good paths across a waypoint grid is a very hard problem and setting up waypoint grids is a nontrivial task as well.
There are some other things that are usually not considered in AI, like the contrast of the player against the surrounding environment, and the type of motion player is currently doing. Motionless person is very hard to see from 150 m away, while a moving person is considerably easier to see. This is usually somehow wrong in most of the games I have seen.
Metal Gear Solid, Splinter Cell, any stealth game in recent years has done this. Doing it correctly however is once more a hard problem that involves a lot more raycasting. The pseudocode for it looks like this:
for every actor
for every target in sight
evaluate level geometry surrounding target
evaluate target camouflage
It's a lot of processing to do this "realistically", so most games fudge around a bit in order to speed the process up. For example, Metal Gear Solid 3 only computes a global visibility for the player based on his current camo and surroundings as well as movement, then used that as a modifier for the probability to get spotted.
