Jump to content
  • Advertisement
Sign in to follow this  
faylar

Line of Sight for 2D grid based RTS

This topic is 4219 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

Hey everyone, I'm currently still new to games programming in general (1 year experience) and even newer to Strategy-based games so I'm pretty concerned on the way I work stuff (whether this or that is the best/most optimized or not...etc...). So on to the topic, I'm trying to do the line of sight detection for each unit. Actually I have already done it but I'm very curious to know if there is a better way. Like the topic says, this is a grid based game, and it was decided that we use the grid for any processing. The method I'm using now (and the only one I could think of atm) was to simply create an object from the player every tick and sorta 'throw ' it towards the target, at the same time collecting data from the grid it is on whilst it travels until it reaches the target's grid. If the grid the object is on is an impassable terrain/wall, I stop the processing immediately and declare that the units cannot see each other. No matter how much I think of the method, I believe that there are better ways to do it, because I keep thinking that this way is rather...unoptimized. I'm still new to games programming and I have yet to see a clear line between what is optimized and what is not (of course, there are the most obvious cases :P). Thanks for reading :) Oh yeah, I was wondering what is the usual method for RTS for detecting line of sight. Ray casting?

Share this post


Link to post
Share on other sites
Advertisement
Well, for grids [RTS, RPG, whatever], the general way of doing line of sight is to just draw a line along the grid from the source to the target and check each tile it crosses over for obstruction. Sounds like the way you're already doing it. There are plenty of ways to optimize it, including level of detail checks [eliminating large chunks of the tile space when you're in large open rooms, or a field], or even just looking for a really fast line-draw alg [they're all slow, but some are faster than others]. It's pretty much the 2d version of ray-casting.

Unfortunately though, visibility is a nasty subject in general, and it's going to be an expensive process.

Since you brought up RTS games specifically, many games use a mask for visibility that they overlay ontop of the unit in question, that is just the pattern of everything they can see. This method doesn't handle obstacles too well, but works nice if you just want a ring of vision around something, and it is computationally much faster than doing the full visibility tests. There are also augmented versions of that to exclude areas behind objects and such, but they mostly rely on incorporating line-tests like above.

In the end, it depends on the kind of game. Something like 'x-com', where visibility is long range and all important, and unit counts are low, a higher precision method would be much better. For something like warcraft you could get away with cutting a whole lot of corners, and giving best-guess answers, even if they aren't totally correct.

Share this post


Link to post
Share on other sites
I really doubt that starcraft test a ray on the grid between each unit for all other units.
When you see about 50 lings and 32 marines in one screen shooting to each other, and fast switching between target. They should use a very fast technic, and I can't visualize which one. But I'm pretty sure it's not ray tracing :)

Share this post


Link to post
Share on other sites
You can have a PVS set for each tile. Saying which tile, or group of tiles are visible from one tile. But that's a lot of memory.

BTW, there are optimisations for raytrace queries in a tile map. See the cube-marching algorithm. And these can be really fast.

I know for FPS and that types of games, but I'm not 100% sure about RTSs, but I would guess, ray-tracing has a big part in that.

Oh yeah, a Ray-marching example.

http://members.gamedev.net/oliii/satpost/3DDDA.cpp
http://members.gamedev.net/oliii/satpost/DxInputs.h
http://members.gamedev.net/oliii/satpost/DxInputs.cpp

Share this post


Link to post
Share on other sites
I don't think starcraft has unit-based LOS.

A unit is either visibe nor not visible to a player.

If a unit is visiable to a player, and it is in range, the unit can attack it.

Visibility to a player is easier than visibility to each unit, because you end up with only having to make one visibility map.

Share this post


Link to post
Share on other sites
Thanks guys, I'll look into it :)

I'm actually more concerned on things like obstacles obstructing the LoS of a unit, like say:

o x o
1 x 2
o x o

assuming 'x' is a wall, 1 cannot see 2 and such.

Any suggestions?

Share this post


Link to post
Share on other sites
if you have nicely formed obstacles, then PVS 'Potentially Visible Set' can be a solution.

PVS is basically a pre-calculation of what cells are visible to every other cells. If you can group your cells in areas (convex areas), then you can save a lot of memory too. The process can be complex though, and very time consuming.

Share this post


Link to post
Share on other sites
Note that starcraft and warcraft don't do what you describe, hence your observation that they seem to do it fast, and wondering how they do it, really doesn't show anything. Units can fire through any and all terrain.

...

*nod* -- instead of having obsticles, have areas where you can see things clearly, and portals.

Each unit would then belong to a family of such areas.

This should reduce the size of the search problem, and make most searches "free".

As noted, it would be tricky.

Share this post


Link to post
Share on other sites
You certainly have multiple options here. One would be to break the map into sections, each of which would be invisible to the other. If you keep a list of pointers to units for each section, you can say that anyone in that area is visible to the others. You may have to do this as a graph to allow crossover for some areas.

The only other option I really know of is ray casting. For a large part, that's what modern games use--depending on how much area-based occlusion there is.

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!