Print

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

[Random832]

I've heard that LoS is the big CPU-eater in adventure mode just like pathfinding is in dwarf mode - so... how about this: only calculate line-of-sight when new terrain might be revealed or there are creatures within the radius whose visibility needs to be checked - don't bother with coloring the tiles according to visibility (or maybe just color the radius); assume otherwise that the player is smart enough to know that you might not be able to see behind that tree. Maybe as an option

[Sowelu]

LOS checking *is*, classically, a huge CPU eater in roguelikes.  Don't know if it's the biggest thing here but it probably is a big part...  Keep in mind, though, that one of the biggest problems is that ALL critters have to check LOS as well.  The display almost certainly has nothing to do with the slowdown.

[Random832]

LOS checking *is*, classically, a huge CPU eater in roguelikes.  Don't know if it's the biggest thing here but it probably is a big part...  Keep in mind, though, that one of the biggest problems is that ALL critters have to check LOS as well.  The display almost certainly has nothing to do with the slowdown.

But the display _does_ have to do with the slowdown - LoS is being checked for tiles that there is no reason to check it EXCEPT to display, because the terrain is already revealed and there are are no creatures.

LOS checking right now does something like - for every tile in the radius, do a LOS check, and display it as lit or not depending on whether it's visible. This could be replaced by an algorithm that only runs the LOS check on unrevealed terrain or creatures.

[Footkerchief]

Good idea.  The performance payoff might be significant.

[Sowelu]

I feel like I want to post something snarky, except that DF is early enough in development that you're probably right.  There's probably a ton of optimizations to be made.  Nethack had TONS of LOS optimizations over its lifespan.

Still, it's pretty much impossible to know what optimizations can still be made in DF and which have already been done.  Again, the biggest improvements won't be player-specific, because I'm guessing most LOS is done by critters (since there's so many critters).  The fact that LOS can be 3d, really not helping. 

Of course, optimizations are one of the most annoying things to code, and we might even be wrong about there being much left to fix...  though I bet there is still a lot left at this point and a substantial payoff waiting.

[Random832]

I feel like I want to post something snarky, except that DF is early enough in development that you're probably right.  There's probably a ton of optimizations to be made.  Nethack had TONS of LOS optimizations over its lifespan.

Still, it's pretty much impossible to know what optimizations can still be made in DF and which have already been done.

Well, I know _this_ hasn't been done because it requires not caring about LOS for tiles that are currently hilighted/dimmed based on LOS. There'd be a pretty clear visual effect to this change. If I know what terrain is somewhere, I don't need LOS to be run on that tile every time I move to tell me if I can still see it. I only need LOS to be run to check whether I can see a _creature_ that has just moved into that tile.

[Capntastic]

Wouldn't you need to run an LOS algorithm to determine if the stuff in your LOS is worth using an LOS algorithm on?

[Random832]

Wouldn't you need to run an LOS algorithm to determine if the stuff in your LOS is worth using an LOS algorithm on?

Huh? no. going through every tile within a certain radius to do a basic check "does this contain a creature or unrevealed terrain" and then running LOS only if the answer to that question is yes, would be much cheaper than doing the raytracing LOS algorithm for every single tile.

[PTTG??]

indeed, you could do the whole thing backwards: check each tile for any item that could be detected, then raytrace to all nearby seers, and thus only those items that can "see" a seer are visible to that seer. Is that clear? I can't tell.

[Draco18s]

indeed, you could do the whole thing backwards: check each tile for any item that could be detected, then raytrace to all nearby seers, and thus only those items that can "see" a seer are visible to that seer. Is that clear? I can't tell.

Pretty much, yes.  And it only needs to check once, really, if you store the data of all tiles that it can "see" and checking against that when the adventurer moves.

[Capntastic]

I can imagine that LOS will play an important role in Adventure mode as more things are added, though, and keeping it intact would be desirable.

[Random832]

I can imagine that LOS will play an important role in Adventure mode as more things are added, though, and keeping it intact would be desirable.

I'm not saying get rid of it as a concept. But it doesn't have to be run on tiles that _don't_ have anything worth checking.

Can you name an example that this wouldn't work for?

[Footkerchief]

^^^ Showing the player where s/he can see is a legitimate reason for using the current LOS.  That's why this should be an option, as you said.

[Idiom]

Perhaps Toady should contact the NetHack developers and get some tips?

[Sowelu]

I can imagine that LOS will play an important role in Adventure mode as more things are added, though, and keeping it intact would be desirable.

I'm not saying get rid of it as a concept. But it doesn't have to be run on tiles that _don't_ have anything worth checking.

Can you name an example that this wouldn't work for?

The advantage of checking from scratch, no assumptions, every turn is that it takes a HUGE burden off of the rest of the code.  It seems quite acceptable to only check tiles that get affected by stuff...like, when you move, check leading edge, check trailing edge, when a door opens then check the door and do some kind of cascading thing...

Problem is, there's already all kinds of edge cases.  If you're only checking for, say, buildings and creatures... what happens when a block of natural stone melts?  What happens when a tree grows?  Some amount of code needs to be moved there and it's easy to miss something.

I think the biggest thing though, is the lighting arc.  Any square that either WAS affected by light, or is NOW affected by light, is going to need -some- kind of update.  So pretty soon "only run it on tiles with things worth checking" is going to be pointless, because lighting means almost everything will need checking all the time...even if you're holding still, your torch might burn a little lower.  Etc.