Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Random832]

Have a simple tag on the tile "has changed" - set by anything happening (creature moving on, creature moving off, something melting, etc), cleared by running a _successful_ LoS check.

And I don't think you're getting the concept if you think the trailing edge would need to be checked. What needs to be checked are tiles within your basic LoS radius which either have not ever been revealed or which have changed since the last time you saw them.

Lighting _wouldn't_ make everything need checking all the time, because your torch burning lower isn't an actual change in what's on the ground.

[Sowelu]

Okay...You're saying that things can be classified as "things which need to be seen/not seen for purposes of display or AI" and "things which actually break up the LOS a bit"?

I can see that if you're standing there and someone tosses a bucket into your LOS, you don't need to do many calculations--just say "Bucket is on this tile.  That tile is inside five critters' LOS on a square already marked as visible.  So, now it's on a list of things they can see."

And I can see that the only time you need to update the actual LOS is when something happens that can actually block vision.  For example, someone opens a door.  But when someone opens a door within your vision radius you pretty much need to run the whole LOS check again, because you don't know offhand which squares that door was blocking your vision to.

I DO think that lighting complicates it though.  The hard part of LOS isn't just "which items are near me", it's "what squares are visible regardless of contents".  If your torch burns down a little, some squares may become hidden because they're dark.  Heck, if someone opens a door outside of your max vision range, it might let light spill onto previously dark squares.  Still...I guess I can accept that lighting will be its own, separate thing, and only one copy exists of the light map (as opposed to the LOS projection map that every critter has a copy of).  So nevermind the lighting I guess?  Maybe it's not that important.

Anyway.  Yeah, only updating that LOS projection when you have a reason to, that makes sense.  If you're standing still, you only need to update it when a door opens or something.  That'll save you lots of time.

Unfortunately, you do always need to update that projection whenever you move, because now maybe you can see behind that tree...  and, well, even if the PLAYER is standing still, chances are there's always twenty NPCs moving around, and they all need to update their own LOS every move.

Or am I missing something?  Because I think every critter needs to project a lot of rays from their new position each time they move, to tell what tiles are visible or occluded.  And I think THAT is the time consuming stuff.

[TrombonistAndrew]

Wellll, if I were to try to optimize a LOS algorithm, I'd start with some concept like:

assume that at the beginning of each turn, terrain is unrevealed.

make a recursive algorithm which checks LOS in a spiral moving outward from the PC or NPC. For each tile outward from the current point of interest, reveal the tile and check for a blockage of vision, if the tile has already been checked, and for maximum sight range. If tile is NOT one of these, run the algorithm again on that tile.

This won't help much on a flat plain, but in a cluttered environment like a forest, this could drastically cut down on the tiles to be checked for LOS.

DF may already do something like this; I'm not quite sure. But I'm not sure if it's valid to only furthermore check for unrevealed terrain, because in addition to this, LOS needs to be checked for the "fog of war." It's probably more efficient to lump the "fog of war" LOS calculation and the "reveal new terrain" into one operation.

[Random832]

Or am I missing something?  Because I think every critter needs to project a lot of rays from their new position each time they move, to tell what tiles are visible or occluded.  And I think THAT is the time consuming stuff.

I don't think stuff other than the player operates with incomplete knowledge of terrain, so pretty much the only thing that needs to be checked is whether they can see the player, and only then if in fact they either are chasing you or would run away from you. Projecting that many rays (one for each tile within your vision radius) to just _you_ on every single turn seems like it would be time-consuming enough to account for the delays.

Wellll, if I were to try to optimize a LOS algorithm, I'd start with some concept like:

assume that at the beginning of each turn, terrain is unrevealed.

make a recursive algorithm which checks LOS in a spiral moving outward from the PC or NPC. For each tile outward from the current point of interest, reveal the tile and check for a blockage of vision, if the tile has already been checked, and for maximum sight range. If tile is NOT one of these, run the algorithm again on that tile.

This won't help much on a flat plain, but in a cluttered environment like a forest, this could drastically cut down on the tiles to be checked for LOS.

DF may already do something like this; I'm not quite sure. But I'm not sure if it's valid to only furthermore check for unrevealed terrain, because in addition to this, LOS needs to be checked for the "fog of war." It's probably more efficient to lump the "fog of war" LOS calculation and the "reveal new terrain" into one operation.

Um, yeah. I was saying they _should_ be lumped in, but that LOS calculation shouldn't be run on tiles for which neither fog of war nor reveal new terrain applies - that is, tiles that have not in fact changed state since the last time they were seen.

(I'm assuming by "fog of war" you mean "hide creatures you can't see" - if you're talking about actually showing what area you can see as a visual highlight - yeah, sure, keep it as an option, even on by default, but since that's going to multiply the number of calculations you have to do by some huge number, it may make sense to just let the player do it in their head.)

[TrombonistAndrew]

By "fog of war" I mean both terrain and creatures that are known but are not in LOS.

Adventure mode defines it similarly.

[Random832]

By "fog of war" I mean both terrain and creatures that are known but are not in LOS.

Adventure mode defines it similarly.

Right, but if showing what terrain is in LOS is not necessarily strictly useful information (it can be done, at least to a reasonable approximation, in the player's head), and eliminating it would reduce CPU usage and allow the game to run more smoothly, it should at least be an option

[Calessa Lynn Orphiel]

Assuming that other people's assumptions are correct:  I think the most significant optimization would be removing LOS calculations from NPCs and monsters.  What benefit do they really serve for the player?  Certainly, it would give your enemies a slightly higher level of omniscience than they already have, but as it is they'll pathfind through anything anyway.  If anything, at least reduce LOS calculations only to creatures that are within minimum visual range of the player.  Things happening outside of the player's perception can't be verified by the player, so fudging LOS altered combat between two creatures too far away for the player to see isn't a big deal anyway.