[DONE] Help test new FOV calculation executable (playable long view distances)

[Stian]

I've had some problems with stuttering gameplay with long view distances and noticed that it is apparently a quite common problem. Hence I decided to take a look at the way the game handles Field of View (FOV) calculations and made a significant improvement in calculation speed. You may download this new version and help test the changes below.

What does faster FOV calculations mean for you as a player:
Greatly reduced delay after each movement step for all units. This leads to smoother gameplay, faster AI turns and playable long view distances. The handling of post hit and post explosion vision calculations also benefit which leads to less delay after each shot. This in turn means faster auto fire and reduced delay whenever the terrain changes.

Download and source
Windows executable (My own additions built on Meridian's v2016-04-28) The runtime libraries normally compiled into the executable, are not, hence you need to download some additional .dll files and put the ones from "deps\lib\Win32" within your game folder with the executable. Now included in Meridian's executable.
Source code
Should you find something amiss, let me know.

PS: To get increased view distance you have to change the "maxViewDistance: 20" line in Piratez.rul.

[Dioxine]

Hell yes. I do experience drops in FPS myself, and this should save A LOT of CPU time, when done in a non-retarded way like this. Why the hell check at every step since tiles can only change due to attacks? I recommended this to be added to Meridian's fork once tested. Kudos for that.

The exec version stayed unchanged, so this one is compatible with the newest mod version. Or at least should... unless Windows incompatibility issues rear their ugly heads.

[Bloax]

Haha shit, really?
Vision was calculated for every unit every single action? (Despite the only time it should be recalculated is after shooting/moving and only for the shooting/moving unit)

That's hilarious.

[Stian]

Not quite. It had two modes. One updating per unit and one updating around a set position on the map. The per unit is decently fast, but uses a method of fetching visible units which doesn't scale well with view distance. The around position function uses the unit one internally and triggers it for every unit within a given range of the point.

The stuttering was mostly to do with the latter function as every moved tile every unit in range had to check if it saw new units (which is fine, as otherwise you wouldn't get reaction fire or aborted movement), but since the function is also responsible for revealing tiles this lead to a lot of busywork.

[Yankes]

I think that you mess up line ending in your commit. GitHub should display only lines you change not big diff containing whole function.
This hide most important changes you made in it.

I planed at some point look at this functions too, but as you do hard work I will gladly pull it to my branch (Meridian will probably do the same).

[Stian]

Oops, you're quite right. Mixed windows and linux line endings. I reverted the latest commit and uploaded it again with slightly better consistency. BTW: Would it be better if I recreated the branch with all changes in one commit?

[Yankes]

At least for me will be a bit easier to cherry-pick it. Overall if all commits have one goal and touch only one thing then probably better if it is only one commit.
If you did some heavy refactoring  that touch lot of other files then would be better to move it to separate commit, other that one implementing main functionality.

[Stian]

I'm planning some additional changes to how and when the FOV calculation is used. Here's a rundown for movement-related FOV calculations:

For every step of movement:
what it was:

• Every unit in range of the moving unit clears and updates their visible units.
• All player units in range clears and updates their visible tiles.

what the new version does:

• Every unit in range of the moving unit clears and updates their visible units (in a faster manner).
• Only the moving character clears and updates its tiles (if a player unit).

What I'm planning to change next:

• Only units which saw the moving unit before its move needs to check for new visible units. (In case the moving unit blocked sight to someone behind it.)
• Every unit in range needs to check if it can see the moving unit after the step.
• Only the moving character clears and updates its tiles (if a player unit).

So thats my todo-list for movement-related FOV calculations. I may also update the projectile hit code for explosive projectiles to use the optimizations I added for the non-explosive ones (basically don't recalculate the entire maps' worth of sun and other lighting, as well as the FOV of all units in range, unless something has actually changed as a result of the hit)

I see there's a bit of back and forth in my commits, so I'll make a new branch when I've updated the source with the new features.

[Yankes]

So thats my todo-list for movement-related FOV calculations. I may also update the projectile hit code for explosive projectiles to use the optimizations I added for the non-explosive ones (basically don't recalculate the entire maps' worth of sun and other lighting, as well as the FOV of all units in range, unless something has actually changed as a result of the hit)

I see there's a bit of back and forth in my commits, so I'll make a new branch when I've updated the source with the new features.

how performance look after your changes? How much far you can now push visibility to see problems?

I recently change some lighting handling in my branch: https://github.com/Yankes/OpenXcom/commit/10fd826aed10cdf3b89d3b25599ce357bc1a26b2
It had some low hanging fruit improvements.

[Hazard]

I haven't noticed any fps drops or lagging animations with this .exe in the few missions I've played, and no clear bugs either. So good job so far.

[Hazard]

Would it be possible to update the .exe with Meridian's latest additions? I'd appreciate it a lot, playing without the movement stutter on maxviewdistance: 30 is very enjoyable, but some of Meridian's bug fixes and new features are also pretty tempting. In any case, thank you a lot for making this.

[Stian]

Glad you're still finding it useful!

I should have a new version with greatly improved performance for you fairly soon. I just need to update a few more places where the new FOV calculation is initiated, then run a couple more battles to look for the most obvious bugs.

how performance look after your changes? How much far you can now push visibility to see problems?

Attached is a graph of my latest test on movement-related calculations. The "original" bars is the current OXCE build. The newFOV2 bars is my current build. (not the executable from the original post). The graph tracks a single unit running to a craft door, then a second unit running into the craft and opening a second door. Each step along the X-axis is one step for the unit with a FOV calculation for every unit in range (34 units in range total). The Y-axis plots the time used per step for both algorithms. The view distance was set to 30. The median time used per calculation was 58.41ms and 5.782ms. The two slow newFOV2 bars are the doors opening, as that part of the code hasn't been updated to use the new features yet, which causes the algorithm to default to a semi-original behaviour.

I've tried playing with view distances up to 60, but the reactionfire gets really crazy when everyone can see across the map....

[new_civilian]

Now that IS a huge performance improvement 

[Yankes]

Reaction shoots will be "fixed" in next Extended version (this is already implemented). You will have full control when units will react.

One way to fix doors performance could be options to add some kind of "dirty rect", in each update only LOS that cross it will be calculated for each unit.
This could be used with explosions too. If you pass rect that contains whole map you will get current behavior, if empty nothing will be updated.

[Stian]

That's actually pretty close to how I'm updating FOV at the moment. I imagine a circle around the event (with some clearance) then place lines tangent to the circle as viewed from the unit and update units and/or tiles within that area. For tiles it's a little more complicated due to the nature of the bresenham lines used to reveal terrain, but it appears to work well now.

As for the doors I just haven't updated the function call from the code handling the doors yet, as I've been busy testing the basic functionality. With it using the old function call convention certain parameters are set to default values causing the algorithm to ignore the arc handling part of the update. Should be an easy fix as long as I remember that doors can have different sizes and scale the event accordingly.