Jump to content
  • Advertisement
Sign in to follow this  

Generating line of sight in Tile based RTS

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

Hello, I've come across a problem recently. I'm working on a game much like Age of Empires. Every unit in it has its own line of sight. The game is updated several times per second, and after each update follows a Draw. Im having problems determining which tiles are visible to the player. The algorithm i'm using now simply clears the entire map of visiblity every update, in other words at the beginning of every update everything is dark. After that, when each unit/structure is updates, it sets the tiles within its radius to visible. Suppose you have 200 units(which is quite common), and suppose its radius is 10, that would lead to 200*10*10*3.14 = 62,800 tiles that will be set to visible every update.Perhaps you can see where this is leading. This takes way to much time, I need an other algoritm. I've tried some thing like exploring on movement of te unit only, but a unsolvable problem occurs when a unit walks by a standing unit. The standing unit will be left in the dark. Conclusion: false algorithm. I've also tried exploring only the edge of the line of sight, but that attempt failed pretty soon. I hope you guys know a way to effectively determine which tiles are visible to any player and being able to update a few times per second.

Share this post


Link to post
Share on other sites
Advertisement
Are you doing actual distance calculations when setting the tiles?
What you should do is precalculate a set of "visibility layers" for each radius that your units can have. Then you can just get the visibility layer for radius=5 (for example), and put it down so that the middle of the layer is in the middle of the unit.

Also, make sure that the actual process of determining visibiliy is as fast as possible, code wise. Call as few functions as possible, and sacrifice readability for pure speed.

I hope this helps.

Share this post


Link to post
Share on other sites
No, i'm not doing distancecalculations.
I have a loop that goes from x = -radius to x >= radius and foreach x the column is filled like a circle. This is my code:
for (int x = -Radius; x <= Radius; x++)
{
int h = (int)(Radius * Math.Sin(Math.Acos((double)x / (double)Radius)));
for (int y = -h; y < h; y++)
Game.Map[x + Centre.X, y+Centre.Y].Visible = true;
}



This code sets each tile within the circle exactly once. It still is to slow.
I suspect the Math.Sin and Acos make it so slow. But still, even if I precalculate all layers, if I have over 100 k tiles to set, it will still take too long.
I was looking for an alternative to filling each units circle.

Share this post


Link to post
Share on other sites
When an unit moves, add one reference to each tile it discovers, and remove one from each tile it stops looking at.

When reading the contents of tiles for any purpose (rendering, AI, building placement, and so on), return 'empty' whenever the reference count for a tile is zero.

This means you will explore a number of tiles linear in the radius of the sight area every time the unit moves from one tile to another, and the entire radius every time an unit dies or appears, which will be fast enough.

Share this post


Link to post
Share on other sites
Since I programmed the LOS system for Age of Empires, I suppose I can step up and answer. :)

I documented the techniques used for AOE in the book Game Programming Gems 2, Section 3.5 'A High-Performance Tile-based Line-of-Sight and Search System'.


ToohrVyk has the correct idea. For each player there is a 2d array of tile reference counts, which hold the number of units belonging to that player that can see that tile.

Each unit has a LOS 'shape' corresponding to it's size and LOS radius that is used as a mask to update the 2d reference count array. It's more efficient to have a table of LOS shapes (which are lists of horizontal 'strips' to update, using relative coordinates)

When a unit is placed into the world, the reference count array in the LOS shape around the unit is incremented.

When a unit is removed from the world (or dies), the reference count array in the LOS shape around the unit is decremented.

When a unit moves onto a different tile, or its LOS shape changes, the reference count array is decremented, the move or change is then applied, and then the reference count array is then incremented.

This way has the following advantages.

The reference count array is only touched when a unit is created, moves a tile, or dies, and then only the elements corresponding to the tiles around that unit are touched. So most of the time, nothing is done, resulting in a very high efficiency.

To ask the question, "can player X see me?" You just look at one number in player X's reference count array (the tile location of the unit in question).

In AoE, there was an additional array maintained that unified the LOS status for all the players, and it was used to the concepts of explored but currently in fog and shared line of sight between players.

For the number of units in AoE, using a byte array (0 - 255) for the reference count was sufficient. The arrays were initialized to 255 to indicate the tile was not yet explored (black), and the explore/increment code checked for wraparound to 0 to catch the initial exploration and incremented it again if it was 0. This allowed for 0 to indicate 'explored but in fog', 255 to indicate black, and 1 to 254 to indicated visible to 'n' units.

I hope this helps.

Share this post


Link to post
Share on other sites
You're perfectly clear, thnx :P
Just one question, you used a 2d array of bytes, under the assumption that no tile can be seen by over 254 units of the same player simultaneously. Was that simply not possible in Age of Empires, or did you have some other magic trick to handle that problem?
I could always used (u)shorts ofcourse.

Besides, there still remains a problem. I remember from Age of Empires that when the tile was gray(byte = 0), and an opponent built a building there, it was not visible.
Wouldn't that mean that every gray tile would also have remember a state per player it was last seen in? With state I mean whether it contained a building/tree/etc.

[Edited by - JBSnorro on April 3, 2008 5:46:15 PM]

Share this post


Link to post
Share on other sites
JBS,

It would have been ungodly rare for more than 254 units belonging to the same player to be close together enough to have the same tile in all of their LOS's in Age of Empires. There was a 50-unit per player unit (non-building) population cap, which was raised to 200 in Age of Kings. Even still, I never recall seeing it happen or hearing reports of it.

You should choose the data type in your game based on what you expect to be realistic for your game design.

I think I did have some code to compensate for that case anyway. most likely if you decremented 0, it went to 254 instead of 255. It's possible you would see artifacts with 255 units overlapping, but they would go away as soon as the count changed.

Remember that game was released in 1997 could run on a 16MB Win95 machine, which typically was a Pentium at 75 to 200mhz. We were very memory and performance sensitive. Just use shorts instead of bytes in your game and don't worry anymore about it.

As for not seeing your opponents buildings in the fog, I made another system which provided that behavior by making use of the LOS system. Basically, each building kept track of who it was visible to and compared it to the previous turn (by looking at the unified LOS status for the tile it sat on).

Other player's unit were not visible to you in the fogged area, but when a building detected that it had transitioned out of your LOS, as special "ghost" object, visible only to you and visible in the fog, was spawned with a snapshot of how that building looked at that moment (when it went out of your sight). The ghost object then looked at the same tile LOS info each turn to detect if it had come back into your LOS, and if so it destroyed itself. *poof*

The point was to have the objects do the work, not the tiles. There would be thousands of tiles, but only dozens or hundreds of objects to update each turn.

Share this post


Link to post
Share on other sites
Okay, I've managed to get it to work, just one more question :P

There is one thing that stands out, the amount of "ghost"-objects is huge!
If a tile is set to gray, it will create such a ghost-object containing whatever the tile contains at that moment(trees/buildings/roads/stones/fish/etc/no units).
Suppose a player sees most of the map in gray, wouldn't that mean that there is a ghost object for practically every tree on the map?
And if a second player also sees most of the map in gray, doesn't it have a seperate huge list of ghost-objects?
Or am I missing some technique?

Share this post


Link to post
Share on other sites
JBS,
I was thinking of teasing you to put on your thinking cap. :)

Yes, there is more to it/more you can do to keep the number of ghost objects in check.

For each object (or object template) there needs to a flag or two that you set to control FOG/LOS behavior.

For player units like soldier, priest, etc you set the flags to: not visible in fog, no Ghost object behavior

For player units like buildings you set the flags to: not visible in fog, and create Ghost units on transition to fog.

For static world objects like trees, you set the flags to: Visible through fog, Create Ghost object on death.

So for a tree, it show through in the fog, but if another player chops it down, you create a ghost unit for the other player *IF* the other player has already explored it/seen it, and it currently is in fog for that other player. That way the other player doesn't know you are harvesting that tree until it explores the area again. You do trees this way to minimize the ghost object numbers.

You'll find the LOS/Ghost object behavior gets a little bit complicated and you'll need to think it through and document the behavior for your different classes of objects to make it optimal.

A couple other things you should probably have is a unified LOS map. Make a 2d array of DWORDs, and have the lower 16 bits represent the current visibility status of the tile for each player# (0 to 15), and the upper 16 bits represent if that tile has been explored by each player or is in black to each player. Make the code that increments and decrements the individual player's LOS reference counts update the unified LOS map on the key events (initial exploration: 255->0->1, transition out of fog: 0->1, and transition to fog: 1->0).

With this unified LOS data you can quickly do the following: Determine if all players on a team can see a tile (using binary OR/AND masks), and have an object see when it's tile's visibility changes (keeps the DWORD copy of the Unified LOS data from the previous turn and compares it the current).

And you get something that is really important: multi-tile areas. IF you have a building that is 2x2 tiles in size, i.e. it covers 4 tiles, you just binary OR the unified LOS data for each of the 4 tiles together, and it works the same as for a single tile object.

As I said it can get a bit complicated, mostly in tracking initial explorations and shared LOS, but it won't get crazy.

Good luck.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!