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?

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.

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 :)

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.

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?

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.

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.