Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (773)
Games in Android Showcase (230)
games submitted by our members
Games in WIP (856)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Efficient Fog of War  (Read 12119 times)
0 Members and 1 Guest are viewing this topic.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Posted 2014-07-02 12:31:42 »

Hi!

I'm implementing fog of war into my tile based game. It's chunky, meaning that a tile either has the fog, or does not have the fog.
Every frame I set all tiles to "not visible". Then, I loop through all the entities, lighting up circles of tiles around them. For the circle, I use this algorithm:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
public class CircleAlgorithm {
   
   private ArrayList<GridPoint2> pointList = new ArrayList<GridPoint2>();
   
   public List<GridPoint2> getCirclePoints(int x, int y, int radius) {
      pointList.clear();
      for(int j = -radius; j <= radius; j++) {
         for(int i = -radius; i <= radius; i++) {
            if(i*i+j*j <= radius*radius + radius* 0.8f) {
               pointList.add(new GridPoint2(x+i, y+j));
            }
         }
      }
      return pointList;
   }
}


I know it look shady, but it produces really good looking circles for its low complexity. I fear this method of having, and maintaining fog of war is not the best. Here's an overview of the task, each frame:
  • Loop through entire map, setting "not visible" on each tile.
  • Loop through all Actors, light up circle (r=3) around the Actor
  • The "lighting up" procedure loops through 6*6 tiles, for a radius 3 circle.

I would very much like some input as to how this can be improved! I ruled out only updating the changing parts (as opposed to recalculating every point every frame), because a lot of the vision from actors close to eachother overlap. Because of this, I can not simply "turn off" the circle of vision around an actor.

Maybe I am missing something.

Offline Hermasetas

Senior Devvie


Medals: 6
Projects: 2
Exp: 7 years


I do gamez, yes!


« Reply #1 - Posted 2014-07-02 13:19:43 »

I am actually having the same problem with my game:P

But consider this:

1: Is your light changing every frame? If not you could save some time by only calculating it when it changes.

2: Do you have a performance problem with the way you're doing it? Seriously I would like to know Tongue
Offline Phased
« Reply #2 - Posted 2014-07-02 13:26:42 »

I am assuming it is 2D.

First of all, you shouldn't need to search through every tile, you should just check the tiles being rendered on the screen.

you can just recheck the fog of war when an actor moves.

you could only update the fog of war in locations where an actor moves, instead of checking every actor within view every time it updates, you could have only the tiles around the actor to update.

if your using shaders, you could just send an array of vectors, and create lights around the points, with the rest of the tiles being black / darkened.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #3 - Posted 2014-07-02 20:28:23 »

Don't use LinkedList.

Myomyomyo.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #4 - Posted 2014-07-03 08:11:07 »

I am actually having the same problem with my game:P

But consider this:

1: Is your light changing every frame? If not you could save some time by only calculating it when it changes.
2: Do you have a performance problem with the way you're doing it? Seriously I would like to know Tongue

Alright, only frames that has updates to the fog of war will recalculate it. If this calculation proves costly, this will result in lag-spikes every time the fog of war updates.
Currently, I have no problems. However, I have not tried a real scenario with many units moving on a large map. This means I actually don't know how well this scales. It does not seem like it would, though.

I am assuming it is 2D.

You are correct!

First of all, you shouldn't need to search through every tile, you should just check the tiles being rendered on the screen.

I actually do need to update more than is shown on the screen. The fog is not merely aesthetic - I plan to use the info in AI.

you can just recheck the fog of war when an actor moves.

That's true. Thank you.

you could only update the fog of war in locations where an actor moves, instead of checking every actor within view every time it updates, you could have only the tiles around the actor to update.

I don't see how this would work, seeing as the circle of vision might overlap with other nearby actors. I cannot simply fill the circle around a dead Actor with fog, because some other entity might have shared some of that vision. I hope this makes sense.

if your using shaders, you could just send an array of vectors, and create lights around the points, with the rest of the tiles being black / darkened.

I think this still poses the same problem. I don't use shaders, but I still need to know which tiles are visible in the model.


I fixed it.

Offline theagentd
« Reply #5 - Posted 2014-07-03 13:16:38 »

How large area are we talking about here? How many tiles per actor? How many actors?

Myomyomyo.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #6 - Posted 2014-07-03 13:25:50 »

How large area are we talking about here? How many tiles per actor? How many actors?

For the map, 256 * 256. Each actor will light up a circle of radius 3 around it, meaning 6 * 6 tiles will be checked. There are many Actors, since each tile with a building also will light up tiles.

Offline theagentd
« Reply #7 - Posted 2014-07-03 13:33:59 »

That's nothing. You're prematurely optimizing. Test it, time it and if it's slow fix it. The only thing you should optimize right now is possibly pooling your GridPoint2 instances so you don't generate as much garbage.

Myomyomyo.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #8 - Posted 2014-07-03 20:55:29 »

That's nothing. You're prematurely optimizing. Test it, time it and if it's slow fix it. The only thing you should optimize right now is possibly pooling your GridPoint2 instances so you don't generate as much garbage.

The pooling is easily fixable. Thanks for the suggestion, by the way. Smiley

I know I should not prematurely optimize, although I would like a solution that scales a little bit better than this does. I know my game is not going to be able to run the levels I would like it to, if I do not fix this.

I imagine the final product to have levels the size of 512^2, or even 1024^2. I seriously doubt a 256^2-size world would be any fun to explore. This is a building game, akin to Warcraft I. That's a lot of tiles. In this world there would be actors running around. Not one or two, but 50 or 80. Each with a lighting distance of 3, that is (80 * (3*2)^2) 2880 tiles to light up. The player would then have made around 10 buildings, each taking up 4 * 6 tiles. Each of the tiles also light up the world around them, in a circle with a radius of 3. That is another 240 checks through the getCirclePoints code, checking another 8640 tiles. I don't have time for 11520 checks, even if I limit it to once every movement cycle. This means the game is just not feasible.

Even if this is not possible, I want to get as close as I can. How can this be faster? 


Offline theagentd
« Reply #9 - Posted 2014-07-03 21:12:52 »

Have you even tried this and timed it? 10 000 tiles is almost nothing.

Myomyomyo.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Hermasetas

Senior Devvie


Medals: 6
Projects: 2
Exp: 7 years


I do gamez, yes!


« Reply #10 - Posted 2014-07-03 21:16:04 »

One easy optimization I can spot:

Do you need to calculate the circles every time?
If it is tile based and all the circles are the same size, couldn't you store the light in an array?
A 6x6 array as you keep saying Wink
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #11 - Posted 2014-07-03 21:58:09 »

Have you even tried this and timed it? 10 000 tiles is almost nothing.

I have not. I will come back though. Expect necro-threading in a year or two. Tongue

One easy optimization I can spot:

Do you need to calculate the circles every time?
If it is tile based and all the circles are the same size, couldn't you store the light in an array?
A 6x6 array as you keep saying Wink

I don't need to, no. This would remove quite a few calculations. Thanks!

Offline klaus
« Reply #12 - Posted 2014-09-07 08:20:17 »

A little late for my input, but maybe it still matters. As @Hermasetas said: you usually don't need to calculate the FOW every frame. What I did was I set up a Timer that runs every 500 ms to recalculate the fog.

You could just recalculate the fog every 100 frames or so, but the big advantage of doing it in a timer thread is a second thread taking care of these calculations. So you can use multi threading, that means with today's hardware (almost everybody has more than one core) you can transfer cpu load away from your main thread.

Be warned though, that it will get more complicated. You have to take care of concurrent updates to maps and lists (and maybe also other data structures) you need in your fog calculations. That means you have to implement a locking mechanism.

The whole multi threading topic is quite complex, but concerning performance optimisations it is worth learning.
Pages: [1]
  ignore  |  Print  
 
 

 
EgonOlsen (1850 views)
2018-06-10 19:43:48

EgonOlsen (1879 views)
2018-06-10 19:43:44

EgonOlsen (1245 views)
2018-06-10 19:43:20

DesertCoockie (1680 views)
2018-05-13 18:23:11

nelsongames (1345 views)
2018-04-24 18:15:36

nelsongames (1963 views)
2018-04-24 18:14:32

ivj94 (2736 views)
2018-03-24 14:47:39

ivj94 (1938 views)
2018-03-24 14:46:31

ivj94 (3029 views)
2018-03-24 14:43:53

Solater (1078 views)
2018-03-17 05:04:08
Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45

Deployment and Packaging
by philfrei
2018-08-20 02:33:38

Deployment and Packaging
by philfrei
2018-08-20 02:29:55

Deployment and Packaging
by philfrei
2018-08-19 23:56:20

Deployment and Packaging
by philfrei
2018-08-19 23:54:46
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!