Jump to content
  • Advertisement
Sign in to follow this  
Galdred

Line of sight algorithm for precomputation and fast recomputation on door opening

This topic is 491 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am looking for a symmetrical LoS algorithm that would allow me to precompute all pair los when creating a level (dungeon or outdoor), and quickly update the table whenever a terrain change is made (mostly when someone opens a door, breach a wall, or when a character creates some kind of barrier).

So I would need to first determine all of the tiles that can see the one being updated, and raycast through the updated cells to update the visibility changes. 

I wanted to go with this algorithm to compute LoS from each point, but I would need to change it to make it symmetrical: I was thinking about tracing LoS from center to center, but then, it becomes impractical to determine which cells are affected by a terrain change (because LoS can still be blocked even if you don't have LoS from center to center): I would have to first test each cell to determine whether it sees any part of the one being updated (unless I also store this value for this specific purpose, so I would store whether A can see any part of B, whether B can see any part of A, and whether the center of A can see the center of B).

 

I suppose if LoS was from center to any part of the target hex, or from any part of the target hex to center, it would remain symmetric, and would make it much easier to get all the cells affected by the change at once (instead of storing whether a center can see another one, I would have to store whether A can see any part of B, and whether B can see any part of A, then OR the results, so that would double the size of the table). That doesn't make for a very elegant rule, and I fear it could be pretty difficult to guess which cells can see each other at a glance.

 

What other options should I consider?

Thanks!

Share this post


Link to post
Share on other sites
Advertisement

precompute all pair los when creating a level

Well the first question is why?  In a dynamic world, things like LOS are usually most easily handled on the fly - when possible.

Then you can get down to the nitty gritty of what type of LOS algo to use: raycast, swept volume, etc. You'll need it either in real time, or for your pre-computing.  depending on your definition of "has LOS"  odds are there is already an algo out there for tiled maps.

Share this post


Link to post
Share on other sites

Indeed, a single LoS query would be fast, but I need the AI to know the visibility from all the tiles reachable in a turn to all tiles reachable by each of the player characters, so that would make quite a lot of LoS queries, while opening or closing a door, or breaching a wall would be a much less common occurrence.

Share this post


Link to post
Share on other sites
so that would make quite a lot of LoS queries

But is it too many for realtime? that's the REAL question. If you're only talking LOS for movement, not sighting, then distances will be shorter, and thus the checks will be faster than raycasting (or whatever) out to the limits of visible range. So that's one thing to consider.  

 

Then you  want to nail down your exact definition of "has LOS / LOF".  this will determine your algo.  Also, your definition of "has LOS" will determine the complexity of your checking code, and thus how fast your checks run.   if you haven't tested real time and proven it to be too slow, that would be the next step. if that doesn't pan out, then you go to pre-computing.  

 

The line of sight requirement to move  is a bit unusual. Why do they need LOS to a tile in movement range?  They can just move towards it, and are guaranteed to have LOS by the time they reach it.   You may not need to calc LOS at all. There may be another (easier) way to do what you want.   But you haven't really said what effect you're trying to achieve, only that you think you need to pre-compute possibly visible tiles - which is a an optimization i haven't heard of anyone resorting to since Quake 1 circa 1995.  and unless you've already tested realtime, or make a game like this before where realtime didn't work, or have run the numbers and the number of iterations is insane (beyond trillions per frame),odds are pre-computing is premature optimization.  I would be somewhat surprised if you actually need LOS and also somewhat surprised if it couldn't be done in realtime if you actually did need it.

 

So just what is it you're trying to achive that seems to need LOS for movemnet and pre-computed visiibilty lookup tables?

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

Sorry, I was not very clear:

I am making a turn based tactical game.

I don't need LoS to move units, but I need to get the field of vision for each position an AI unit can reach during its turn to evaluate how good this position is.

Even for a single turn look ahead, I would need to check around 100 tiles for a single unit.

Of course, I can save the processing time for all the non passable tiles, and reuse the results of one unit for another one if they are close enough, but that still makes a lot of Field of views to compute, especially outdoor. 

Edited by Galdred

Share this post


Link to post
Share on other sites
Your requirement for precomputing for performance reasons and having it dynamic to respond to changes are at odds with each other. Being that the precomputing seems like a premature optimization I would do what Norman Barrows suggested and just do it real time. 100s of tiles should be no problem for computers these days.

Share this post


Link to post
Share on other sites

Rather than calculating visibility for every single tile (which could very well just be thrown away on turn 1, the moment the terrain changes), consider calculating the LoS at run-time and caching the result into some kind of lookup table. The next time the game needs to check visibility for that tile, it can use the cached result.

Invalidate the cache when the world geometry changes. A naive solution would be to clear the entire level's cache when the level is modified, but if you have an upper bound on visibility distance, you could get away with dropping cache entries for locations within a box of a certain size.

All in all, this means that the areas of your map where no action is happening aren't doing visibility checks that will just be thrown away before any actors can get there.

With all this said, be sure to profile your game to determine the impact of visibility checks on performance before going down this road.

Good luck. :)

Share this post


Link to post
Share on other sites

Thank you for your answers.Indeed, both requirements are at odds. 

 

Rather than calculating visibility for every single tile (which could very well just be thrown away on turn 1, the moment the terrain changes), consider calculating the LoS at run-time and caching the result into some kind of lookup table. The next time the game needs to check visibility for that tile, it can use the cached result.

That sounds like a good compromise to me:

Cache the results, and start updating the cache during the player turn, as the AI pieces won't move at this time.

Share this post


Link to post
Share on other sites

but I need to get the field of vision for each position an AI unit can reach during its turn to evaluate how good this position is.

What does the view at the the AI's final position have to do with how "good" that potion is?   Do you win by seeing more of the battlefield or something?

What's your criteria for how "good" a final position is?  unless its "where ever they can see the most map tiles", odds are you're going about it wrong.  and i can't think of any real use for "where ever they can see the most map tiles", unless its some sort of hide and seek type game of some sort perhaps.

You still haven't told us what you're trying to achieve by determining the final position with LOS to the most map tiles. tell you the truth i've never heard of a need for such a thing in any game. that's why this doesn't make sense. and it appears you want to optimize an algo you probably shouldn't even be using in the first place. can't say for sure until you tell us what overall behavior you're trying to achieve. 

so - move to the tile with LOS to the most tiles - why? what does that get you?  nothing that i can think of off hand.... 

please explain.

Share this post


Link to post
Share on other sites

The Los situation is only one of the parameters that will be used. The viability of a tile will be the result of a weighted sum of several factors.

 

I never said I wanted to move to the tile with the highest number of tiles seen, I merely said that visibility to all "relevant" tiles was important.

 

The game system would be in the same family as X(-)COM:

The reason for this is that if you want an AI agent to defend an objective by overwatch (opening fire during the player's turn), it better had LoS to the path that leads to it and the player can take if the player is either not visible by the agent, or too protected to shoot now.

On the other hand, if the AI is willing to protect a VIP, it better put it in a position where it can hardly be seen by the player on its next turn.

 

So if the AI agent is meant to go on overwatch, the idea would be to run an expected value minimax  search for the possible moves of the player, and try to find positions where as many as these tiles can be covered.

 

If he is to attack a given target, on the other hand, the best location would be one where he can see the target, while minimizing the number of player agents that can move and shoot him during their turn.

 

If it is scouting, maximizing the field number of tiles which are currently unknown to the AI is also desirable.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!