A little background. The project I’m working on uses a tile based grid, as is typical, that is a 2d grid overlapped onto 3d terrain. Line of sight is meant to be a circle cut out of the 2d grid, as is typical in many strategy games. With that said, I’m attempting to optimize the LOS portion so to as accurately as possible [within the bounds of fast computation] allow for portions of the 3d map to be explored/unexplored as one would expect them to actually be. For example, if the 3d map has a trench, a person standing in the trench should not be able to see the ground above them, but a person standing outside of the trench should not be able to see the person in the trench [unless close enough to look down into it]. Also, if an unmovable object [like a brick wall] is in the way, it should obstruct vision somewhat accurately. Static objects like moving characters will not block view, so they can be disregarded. I’m doing this for many units each time the terrain changes/ each time a unit moves, so the calculation should be as quick as possible. The terrain hardly ever changes, only doing so when [to use the previous example] brick walls or whatever, are destroyed. Units move often though. So far I use a mask to determine possible viewable zones, then a few dot products between a vector drawn from the point of view to a tile group and a stored normal vector for that tile group to determine what portion of the tiles are visible [not considering any obstructions]. At this point it is well optimized, and I’m happy with the results, but removing terrain that passes that first test, but is actually obstructed by other terrain or unmovable objects, is proving complicated. What I’m trying to avoid is doing a line-polygon intersection test on the map mesh for each and every tile I’m going to have to check [up to several hundred tiles per unit tile transition]. Is this avoidable? Any suggestions on optimizing this more? Any suggestions on when a LOS check can just be thrown out completely? [in the case of everything that would be tested already being visible by someone else for example] I know this has been done before, because I've seen it's effects in other games, but am unsure if they are updated for every move or not, or if they are done efficiently at all. Really don't want to just give up 3d LOS and just got with the circle shaped 2d, since it is a neat little feature, but if thats what i end up being forced to do, any advice on how to still optimize the consideration of obstructions? Obstructing objects are stored as a tile location, and a height min and max that they obstruct [so things can hide under things]. Dynamic objects that should be determined to be visible are stored as the same, but do not obstruct vision. It is sufficient to consider each entire tile as having the height it has at it’s center.

Currently tinkering with the idea of having a graph propogate outward from the center [where something stands] to get the object obstructions and the initial mask out of the way outright. A node delivers to all the nodes would be blocked by an obstruction on the tile that the node represents, a dHeight, and a height, that describes the surface slope difference that is acceptable to consider something visible, and the current height in question. Anything under the height + dheight would be invisible, anything equal to or over it would be visible, and the values are updated as the graph propogates outward to create a mask. The mask is stored and is used to remove visibility when the unit leaves the square. The graphs can be precomputed easily enough, but the memory footprint of having every unit have it's own full vision description sounds like a pretty big hit, and it sounds like it'll kick me pretty hard in the performance in terms of memory eating. Another problem, this method almost requires that every tile be obstructable by only one path through the graph, which seems a bit risky. It's pretty fast for a couple hundred units though if the it's only computed on tile transition [maybe 6 times a second for a pretty quick unit, not like every single unit is going to be moving around anyway, most things sit still at least occationally]. For things with restricted vision anyway [like a camera that only points one direction], killing off some of the directions that are tested outright would reduce the view field. Also, since the depth isn't described, you could use the same huge graph for things that can see 80 tiles as can see 3 tiles [so long as the original graph is large enough to compensate the largest range], but some of the results are less than convincing. On the plus side, each tile is checked only once, and irrecoverable obsticles [walls, that for the sake of example extend infinitely upward] can cull out large sections of the graph, reducing the searched areas in the case of enclosed rooms or whatnot. Adding a maximum height with a maximum dHeight wouldn't be so bad to allow the roof to obstruct looking down a long cooridore that suddenly slopes downward, but this requires obstructions to extend from the ground up, or from the roof down, as to elminate mid-level [think a saloon door in a wild west flick] like objects obstructing vision properly.

Have the feeling there is a better way though. Total annihilation had something similar to what i'm looking for. Dark reign had it too [though its graphics were really inhibiting to it's ability to represent just how detailed it's LOS really was]. Both of those were old games, running on slow processors, and doing this task very quickly. There has got to be more info on this somewhere :P

[Edited by - Overseer on April 15, 2006 8:58:34 PM]