5 deleted 96 characters in body; edited title

RTS: Determining which units are visible for playerUnit sight in fog of war

I am making an RTS game, and I need a way to determinelike most RTSs, which units are visibleyou can see what's going on in a part of a map only if you have a unit over there.

Here's what I have:

• Server runs game at 30 fps and sends keyframes to clients about 10 times a second.
• Clients do not run any game logic, and only interpolate whatever is sent by the server.

I want clients to receive only the data which they need few ideas how to know. E.g. they won't receive any information about units hidden in the fog of waraccomplish this, but there are problems with them.

• How to efficiently calculate which units are visible by a player?Algorithm must be efficient.
• How do I know when unit appears in another unit's visibility range? It can happen eitherneed to notify players (over network), when given unitan enemy comes into sight of another unit, or another unit moves and “sees” given unit.
• How do I account for obstacles obstructing sight (such as cliffs).

And then run this calculation each frame, compare results with previous frame and send updates to playersout events, like “enemy unit detected”.

I bet there is much more efficientdid some benchmarking, and using approach thanlike this may take up to 2/3 of a frame, which is unacceptable. Is there?

EDIT:

I figured out a better way to calculate which units are visible. This approach is to use a visibility map.

• Subdivide the map into N×M cells.
• Each cell is marked by IDs of players that can see the cell.
• To determine which players can see an unit, I need only to check cells that contain given unit.

However, but I don't know how to generate updates with such systemfill the map in the first place. It is as follows:I could iterate through all units and use a circle-drawing algorithm.

SubdivideBut I'll have to redraw the visibility map into N×M cells. Each cell is marked by IDs of players that can seeevery frame, so this doesn't look much more efficient than the cellfirst approach. To determine which players can see an unit,Unless I need only to check cells that contain given unitupdate it at a lower rate, but then there's a problem with fast-moving units.

However, as I said,And how do I don't know a way to send updatesdetect when visibility of an unit changescomes in player's sight, except enumeratingthan iterating through every unit. and comparing with previous frame?

Another problem withHow is this approachdone in modern RTS, such data structure can a lot of space.

And yet another problem with this: how do I update the visibility map? Do I iterate through all cells within unit's sight rangeas StarCraft 2? This does not seem like a good way.

RTS: Determining which units are visible for player

I am making an RTS game, and I need a way to determine, which units are visible.

Here's what I have:

• Server runs game at 30 fps and sends keyframes to clients about 10 times a second.
• Clients do not run any game logic, and only interpolate whatever is sent by the server.

I want clients to receive only the data which they need to know. E.g. they won't receive any information about units hidden in the fog of war.

• How to efficiently calculate which units are visible by a player?
• How do I know when unit appears in another unit's visibility range? It can happen either when given unit comes into sight of another unit, or another unit moves and “sees” given unit.

And then run this calculation each frame, compare results with previous frame and send updates to players.

I bet there is much more efficient approach than this. Is there?

EDIT:

I figured out a better way to calculate which units are visible, but I don't know how to generate updates with such system. It is as follows:

Subdivide the map into N×M cells. Each cell is marked by IDs of players that can see the cell. To determine which players can see an unit, I need only to check cells that contain given unit.

However, as I said, I don't know a way to send updates when visibility of an unit changes, except enumerating every unit.

Another problem with this approach, such data structure can a lot of space.

And yet another problem with this: how do I update the visibility map? Do I iterate through all cells within unit's sight range? This does not seem like a good way.

RTS: Unit sight in fog of war

I am making an RTS game, and like most RTSs, you can see what's going on in a part of a map only if you have a unit over there.

I have few ideas how to accomplish this, but there are problems with them.

• Algorithm must be efficient.
• I need to notify players (over network), when an enemy comes into sight.
• How do I account for obstacles obstructing sight (such as cliffs).

And then run this calculation each frame, compare results with previous frame and send out events, like “enemy unit detected”.

I did some benchmarking, and using approach like this may take up to 2/3 of a frame, which is unacceptable.

I figured out a better way to calculate which units are visible. This approach is to use a visibility map.

• Subdivide the map into N×M cells.
• Each cell is marked by IDs of players that can see the cell.
• To determine which players can see an unit, I need only to check cells that contain given unit.

However, I don't know how to fill the map in the first place. I could iterate through all units and use a circle-drawing algorithm.

But I'll have to redraw the visibility map every frame, so this doesn't look much more efficient than the first approach. Unless I update it at a lower rate, but then there's a problem with fast-moving units.

And how do I detect when unit comes in player's sight, except than iterating through every unit and comparing with previous frame?

How is this done in modern RTS, such as StarCraft 2?

4 added 168 characters in body

I am making an RTS game, and I need a way to determine, which units are visible.

Here's what I have:

• Server runs game at 30 fps and sends keyframes to clients about 10 times a second.
• Clients do not run any game logic, and only interpolate whatever is sent by the server.

I want clients to receive only the data which they need to know. E.g. they won't receive any information about units hidden in the fog of war.

Problems are:

• How to efficiently calculate which units are visible by a player?
• How do I know when unit appears in another unit's visibility range? It can happen either when given unit comes into sight of another unit, or another unit moves and “sees” given unit.

Naïve approach would be like this:

// pseudocode
func calculate_visibility:
vector<Bitfield> visible;

for all units on map:
let unit = enumerated unit

for all human players:
let player = enumerated player

for all units of player:
let player_unit = enumerated unit

if player_unit sees unit
visible[unit.id][player.id] = true
process next player


And then run this calculation each frame, compare results with previous frame and send updates to players.

I bet there is much more efficient approach than this. Is there?

EDIT:

I figured out a better way to calculate which units are visible, but I don't know how to generate updates with such system. It is as follows:

Subdivide the map into N×M cells. Each cell is marked by IDs of players that can see the cell. To determine which players can see an unit, I need only to check cells that contain given unit.

However, as I said, I don't know a way to send updates when visibility of an unit changes, except enumerating every unit.

Another problem with this approach, such data structure can a lot of space.

And yet another problem with this: how do I update the visibility map? Do I iterate through all cells within unit's sight range? This does not seem like a good way.

I am making an RTS game, and I need a way to determine, which units are visible.

Here's what I have:

• Server runs game at 30 fps and sends keyframes to clients about 10 times a second.
• Clients do not run any game logic, and only interpolate whatever is sent by the server.

I want clients to receive only the data which they need to know. E.g. they won't receive any information about units hidden in the fog of war.

Problems are:

• How to efficiently calculate which units are visible by a player?
• How do I know when unit appears in another unit's visibility range? It can happen either when given unit comes into sight of another unit, or another unit moves and “sees” given unit.

Naïve approach would be like this:

// pseudocode
func calculate_visibility:
vector<Bitfield> visible;

for all units on map:
let unit = enumerated unit

for all human players:
let player = enumerated player

for all units of player:
let player_unit = enumerated unit

if player_unit sees unit
visible[unit.id][player.id] = true
process next player


And then run this calculation each frame, compare results with previous frame and send updates to players.

I bet there is much more efficient approach than this. Is there?

EDIT:

I figured out a better way to calculate which units are visible, but I don't know how to generate updates with such system. It is as follows:

Subdivide the map into N×M cells. Each cell is marked by IDs of players that can see the cell. To determine which players can see an unit, I need only to check cells that contain given unit.

However, as I said, I don't know a way to send updates when visibility of an unit changes, except enumerating every unit.

Another problem with this approach, such data structure can a lot of space.

I am making an RTS game, and I need a way to determine, which units are visible.

Here's what I have:

• Server runs game at 30 fps and sends keyframes to clients about 10 times a second.
• Clients do not run any game logic, and only interpolate whatever is sent by the server.

I want clients to receive only the data which they need to know. E.g. they won't receive any information about units hidden in the fog of war.

Problems are:

• How to efficiently calculate which units are visible by a player?
• How do I know when unit appears in another unit's visibility range? It can happen either when given unit comes into sight of another unit, or another unit moves and “sees” given unit.

Naïve approach would be like this:

// pseudocode
func calculate_visibility:
vector<Bitfield> visible;

for all units on map:
let unit = enumerated unit

for all human players:
let player = enumerated player

for all units of player:
let player_unit = enumerated unit

if player_unit sees unit
visible[unit.id][player.id] = true
process next player


And then run this calculation each frame, compare results with previous frame and send updates to players.

I bet there is much more efficient approach than this. Is there?

EDIT:

I figured out a better way to calculate which units are visible, but I don't know how to generate updates with such system. It is as follows:

Subdivide the map into N×M cells. Each cell is marked by IDs of players that can see the cell. To determine which players can see an unit, I need only to check cells that contain given unit.

However, as I said, I don't know a way to send updates when visibility of an unit changes, except enumerating every unit.

Another problem with this approach, such data structure can a lot of space.

And yet another problem with this: how do I update the visibility map? Do I iterate through all cells within unit's sight range? This does not seem like a good way.

3 added 660 characters in body

I am making an RTS game, and I need a way to determine, which units are visible.

Here's what I have:

• Server runs game at 30 fps and sends keyframes to clients about 10 times a second.
• Clients do not run any game logic, and only interpolate whatever is sent by the server.

I want clients to receive only the data which they need to know. E.g. they won't receive any information about units hidden in the fog of war.

Problems are:

• How to efficiently calculate which units are visible by a player?
• How do I know when unit appears in another unit's visibility range? It can happen either when given unit comes into sight of another unit, or another unit moves and “sees” given unit.

Naïve approach would be like this:

// pseudocode
func calculate_visibility:
vector<Bitfield> visible;

for all units on map:
let unit = enumerated unit

for all human players:
let player = enumerated player

for all units of player:
let player_unit = enumerated unit

if player_unit sees unit
visible[unit.id][player.id] = true
process next player


And then run this calculation each frame, compare results with previous frame and send updates to players.

I bet there is much more efficient approach than this. Is there?

EDIT:

I figured out a better way to calculate which units are visible, but I don't know how to generate updates with such system. It is as follows:

Subdivide the map into N×M cells. Each cell is marked by IDs of players that can see the cell. To determine which players can see an unit, I need only to check cells that contain given unit. However

However, as I said, I don't know a way to send updates when visibility of an unit changes, except enumerating every unit.

Another problem with this approach, such data structure can a lot of space.

I am making an RTS game, and I need a way to determine, which units are visible.

Here's what I have:

• Server runs game at 30 fps and sends keyframes to clients about 10 times a second.
• Clients do not run any game logic, and only interpolate whatever is sent by the server.

I want clients to receive only the data which they need to know. E.g. they won't receive any information about units hidden in the fog of war.

Problems are:

• How to efficiently calculate which units are visible by a player?
• How do I know when unit appears in another unit's visibility range? It can happen either when given unit comes into sight of another unit, or another unit moves and “sees” given unit.

Naïve approach would be like this:

// pseudocode
func calculate_visibility:
vector<Bitfield> visible;

for all units on map:
let unit = enumerated unit

for all human players:
let player = enumerated player

for all units of player:
let player_unit = enumerated unit

if player_unit sees unit
visible[unit.id][player.id] = true
process next player


And then run this calculation each frame, compare results with previous frame and send updates to players.

I bet there is much more efficient approach than this. Is there?

EDIT:

I figured out a better way to calculate which units are visible, but I don't know how to generate updates with such system. It is as follows:

Subdivide the map into N×M cells. Each cell is marked by IDs of players that can see the cell. To determine which players can see an unit, I need only to check cells that contain given unit. However, as I said, I don't know a way to send updates when visibility of an unit changes, except enumerating every unit.

I am making an RTS game, and I need a way to determine, which units are visible.

Here's what I have:

• Server runs game at 30 fps and sends keyframes to clients about 10 times a second.
• Clients do not run any game logic, and only interpolate whatever is sent by the server.

I want clients to receive only the data which they need to know. E.g. they won't receive any information about units hidden in the fog of war.

Problems are:

• How to efficiently calculate which units are visible by a player?
• How do I know when unit appears in another unit's visibility range? It can happen either when given unit comes into sight of another unit, or another unit moves and “sees” given unit.

Naïve approach would be like this:

// pseudocode
func calculate_visibility:
vector<Bitfield> visible;

for all units on map:
let unit = enumerated unit

for all human players:
let player = enumerated player

for all units of player:
let player_unit = enumerated unit

if player_unit sees unit
visible[unit.id][player.id] = true
process next player


And then run this calculation each frame, compare results with previous frame and send updates to players.

I bet there is much more efficient approach than this. Is there?

EDIT:

I figured out a better way to calculate which units are visible, but I don't know how to generate updates with such system. It is as follows:

Subdivide the map into N×M cells. Each cell is marked by IDs of players that can see the cell. To determine which players can see an unit, I need only to check cells that contain given unit.

However, as I said, I don't know a way to send updates when visibility of an unit changes, except enumerating every unit.

Another problem with this approach, such data structure can a lot of space.

2 added 660 characters in body
1