OpenClonk Bugtracker - OpenClonk
View Issue Details
0001105OpenClonkScenariospublic2014-08-09 15:222016-08-19 09:38
Reporterala 
Assigned ToMaikel 
PrioritynormalSeverityminorReproducibilityalways
StatusclosedResolutionfixed 
Platform64 bitOSWindowsOS Version7
Product Version 
Target VersionFixed in Version 
Summary0001105: Iron Peak Goal - Lags
DescriptionThe goal, trying to locate the flag area lags hard core.
Additional InformationWe had lag in Iron Peak (LAN) and Zapper tracked the lag down to the goal object.
TagsNo tags attached.
Attached Files

Notes
(0003076)
Zapper   
2014-08-09 15:28   
Confirmed. The FPS drop by around 10 or so (bad laptop hardware, but can run other scenarios at full speed).

Some script-profiler results of different duration during that round:
---------------------------------------------------------------
[17:00:03] 02492ms Goal_Expansion.FxIntAreaMonteCarloTimer
[17:00:03] 02343ms Goal_Expansion.CoveredByFlag
[17:00:03] 01278ms Ropeladder.FxIntHangTimer
[17:00:03] 01277ms Ropeladder.TimeStep
[17:00:03] 00881ms Ropeladder.SatisfyConstraints
[17:00:03] 00550ms Ropeladder.ConstraintLength
[17:00:03] 00346ms Ropeladder.UpdateLines
[17:00:03] 00317ms Ropeladder.ConstraintLandscape
[17:00:03] 00236ms Cloud.FxProcessCloudTimer
[17:00:03] 00160ms Cloud.Evaporation
---------------------------------------------------------------
[17:07:54] 02356ms Goal_Expansion.FxIntAreaMonteCarloTimer
[17:07:54] 02229ms Goal_Expansion.CoveredByFlag
[17:07:54] 00093ms Cloud.FxProcessCloudTimer
[17:07:54] 00059ms Cloud.MoveCloud
[17:07:54] 00035ms Global.FxIntScheduleCallTimer
[17:07:54] 00029ms Global.GetDefHeight
---------------------------------------------------------------
[17:20:23] 25135ms Goal_Expansion.FxIntAreaMonteCarloTimer
[17:20:23] 23780ms Goal_Expansion.CoveredByFlag
[17:20:23] 01718ms Cloud.FxProcessCloudTimer
[17:20:23] 01083ms Cloud.Evaporation
[17:20:23] 00571ms Cloud.MoveCloud
[17:20:23] 00362ms Global.GetDefWidth

The goal is only contested by the ropeladder...
(0003086)
Maikel   
2014-08-14 08:43   
I'll have a look on how to improve this.
(0003087)
Maikel   
2014-08-14 10:10   
What kind of hardware were you using?

I think I can reduce the lag by a factor of 4, but it also implies it take 4x as long to calculate the increased coverage if a new flag is build
(0003092)
Maikel   
2014-08-17 14:37   
I have improved the speed by a theoretical factor of 4, can you tell me if it still lags?
(0003274)
Zapper   
2014-12-25 14:35   
(Last edited: 2014-12-25 14:36)
It's still pretty slow for the gain (see log), but at least on my high-end computer, it does not seem to produce noticable lag (in a short test).

Someone with a lower-end hardware should try it and see if they can get 38FPS in the scenario.

==============================
00371ms Goal_Expansion.FxIntAreaMonteCarloTimer
00367ms Goal_Expansion.CoveredByFlag
00023ms Global.FxIntScheduleCallTimer
00016ms Clonk.FxIntWalkTimer
00014ms Clonk.FxIntTurnTimer
00012ms Lorry.TurnWheels
00010ms Clonk.FxIntScaleRotTimer
...

PS: In this test I had removed all clouds, because they got in the way and I constantly dragged them around..

(0003444)
Zapper   
2015-01-22 09:51   
PS: I'd still suggest an approximation using the area of intersecting squares instead of the current Monte Carlo approach. The approximation would be extremely fast and would have to be calculated only when new flags are built.

Even if the Monte Carlo approach is obviously cooler.
(0003446)
Sven2   
2015-01-22 13:28   
(Last edited: 2015-01-22 13:32)
Doesn't the power library already keep a list of all connected flags and in the process needs to find overlapping neighbours? It could easily calculate the area, subtract overlaps and keep that result to be queried by the goal object.

If flags are prioritized, subtracting overlaps is also simple: You subtract the full overlap if your flag has lower priority than the overlapping one. That way you don't need to worry about triple overlaps, etc.

Edit: Formula for overlapping region is here: http://mathworld.wolfram.com/Circle-CircleIntersection.html
 (A(d, R, r) = overlapping area). I'm sure it can be approximated well enough by a 2nd order polynomial.

(0003447)
Zapper   
2015-01-23 09:27   
Flags do have a priority: their construction time is saved.
(0003448)
Maikel   
2015-01-23 09:37   
I can have a look at this when looking into the power library again. Currently not that motivated, so maybe for a 6.1 release. I think we have an arccos anyways (or we can derive it from Angle()), so no need for approximations I think.
(0003566)
Caesar   
2015-03-31 05:01   
Sven: If you subtract overlaps, you have to readd triple overlaps, then subtract quadtruple overlaps, … No fun.
(0003567)
Sven2   
2015-03-31 09:14   
Caesar:

> If flags are prioritized, subtracting overlaps is also simple: You subtract the full overlap if your flag has lower priority than the overlapping one. That way you don't need to worry about triple overlaps, etc.
(0003569)
Caesar   
2015-04-02 08:38   
Sven: I don't think you have thought this through, at least I don't see why priority should help in any way. Maybe you should implement it and show me…

Let me ask: What do you do with that flag, that has middle priority, in a triple overlap?
(0003570)
Sven2   
2015-04-02 12:02   
Hm you are right, always subtracting the full overlap subtracts too much.

I don't implement anything until my disseration is done :P
(0003912)
Clonkonaut   
2015-10-13 14:05   
What's the progress on this?
(0003920)
Caesar   
2015-10-14 09:42   
(Last edited: 2015-10-14 09:43)
None, afaik. I've tried implementing a function that calculates the circle area by partitioning it in sectors and the polygon spanned by the midpoints and the intersections. https://bpaste.net/show/9814fdbc8c17 However, the order of intersections on the circle is crucially important but I couldn't keep it (screw numerics).

Host background thread engine monte carlo implementation anyone? Or maybe Netwon's polygon library?

(0004226)
Maikel   
2015-12-02 10:01   
The situation can be improved by making GetFlagpoleForPosition faster for a large number of flags. I will try this.
(0004449)
Maikel   
2016-01-02 21:09   
This only barely worked, but locally I don't have any noticeable lag. Let's test this in a network round.
(0004454)
Maikel   
2016-01-03 21:53   
We played a test round with a steady 38 FPS, on large map. So I close this report for now.
(0005305)
Newton   
2016-08-19 09:38   
arhiving old resolved bugs

Issue History
2014-08-09 15:22alaNew Issue
2014-08-09 15:28ZapperNote Added: 0003076
2014-08-09 15:28ZapperAssigned To => Zapper
2014-08-09 15:28ZapperStatusnew => acknowledged
2014-08-11 10:10ZapperAssigned ToZapper =>
2014-08-14 08:43MaikelNote Added: 0003086
2014-08-14 08:43MaikelAssigned To => Maikel
2014-08-14 08:43MaikelStatusacknowledged => assigned
2014-08-14 10:10MaikelNote Added: 0003087
2014-08-17 14:37MaikelNote Added: 0003092
2014-08-17 14:37MaikelAssigned ToMaikel => Zapper
2014-08-17 14:37MaikelStatusassigned => feedback
2014-12-25 14:35ZapperNote Added: 0003274
2014-12-25 14:36ZapperNote Edited: 0003274bug_revision_view_page.php?bugnote_id=3274#r711
2015-01-22 09:48ZapperAssigned ToZapper =>
2015-01-22 09:51ZapperNote Added: 0003444
2015-01-22 13:28Sven2Note Added: 0003446
2015-01-22 13:32Sven2Note Edited: 0003446bug_revision_view_page.php?bugnote_id=3446#r771
2015-01-23 09:27ZapperNote Added: 0003447
2015-01-23 09:37MaikelNote Added: 0003448
2015-03-31 05:01CaesarNote Added: 0003566
2015-03-31 09:14Sven2Note Added: 0003567
2015-04-02 08:38CaesarNote Added: 0003569
2015-04-02 12:02Sven2Note Added: 0003570
2015-10-13 14:05ClonkonautNote Added: 0003912
2015-10-14 09:42CaesarNote Added: 0003920
2015-10-14 09:43CaesarNote Edited: 0003920bug_revision_view_page.php?bugnote_id=3920#r956
2015-10-16 00:32Sven2Target Version => 7.0
2015-12-02 10:01MaikelNote Added: 0004226
2015-12-02 10:01MaikelAssigned To => Maikel
2015-12-02 10:01MaikelStatusfeedback => assigned
2016-01-02 21:09MaikelNote Added: 0004449
2016-01-03 21:53MaikelNote Added: 0004454
2016-01-03 21:53MaikelStatusassigned => resolved
2016-01-03 21:53MaikelFixed in Version => 7.0
2016-01-03 21:53MaikelResolutionopen => fixed
2016-08-19 09:38NewtonNote Added: 0005305
2016-08-19 09:38NewtonStatusresolved => closed