Make sea_depth much faster with dynamic programming

[MM1nd]

Hi Folks,

in 2016 I played around with worldengine and found it to be slow to the point of not being fun to use. Maybe my machine is to blame, I don't know. I found that a lot of speed could be gained, not by dreaded "premature optimisation" but by simply thinking more clearly about what we are trying to accomplish and using numpy better. Unfortunately I never got around to pushing any of that work upstream.

One of the things I found while profiling was that worldengine will spend ~15% of total runtme in is_land on my machine for a 128*128 map with otherwise default parameters. I don't think that is acceptable and I think we can do much better.

Unfortunately I was struggling with git while I did this so the pull request contains my additions to .gitignore and a series of unneccessary commits just to get back to status quo of readme.md. Other than that, the changes are straightforward.

All tests are green after the change. It's functionally equivalent to the old slow implementation.

If you find this helpful I have made many more performance improvements locally which I'll gladly share over time.

Let me know what you think.

Cheers

Alex

[MM1nd]

P. S. I'll make better use of branches next time. I was confused about how branches work when I did this.

[coveralls]

Coverage decreased (-0.1%) to 85.071% when pulling a0f56c306a353d8cb2205faf8e631c5888f1a54b on MM1nd:master into f749e993cadde5a13c732fddbaddb5c8bc75000f on Mindwerks:master.

[codecov-io]

Codecov Report

Merging #242 into master will increase coverage by 0.73%. The diff coverage is 100%.

@@            Coverage Diff             @@
##           master     #242      +/-   ##
==========================================
+ Coverage   80.21%   80.94%   +0.73%     
==========================================
  Files          28       28              
  Lines        3872     3884      +12     
  Branches      763      768       +5     
==========================================
+ Hits         3106     3144      +38     
+ Misses        574      543      -31     
- Partials      192      197       +5

Impacted Files	Coverage Δ
worldengine/generation.py	91.3% <100%> (+0.7%)	:arrow_up:
worldengine/model/world.py	75.87% <0%> (-0.15%)	:arrow_down:
worldengine/simulations/erosion.py	70.75% <0%> (+10.67%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update f749e99...a7436c4. Read the comment docs.

[coveralls]

Coverage increased (+0.07%) to 85.248% when pulling d9b7443edbc24357f4e77d875350b7ed0bb129f0 on MM1nd:master into f749e993cadde5a13c732fddbaddb5c8bc75000f on Mindwerks:master.

[coveralls]

Coverage increased (+0.07%) to 85.248% when pulling d9b7443edbc24357f4e77d875350b7ed0bb129f0 on MM1nd:master into f749e993cadde5a13c732fddbaddb5c8bc75000f on Mindwerks:master.

[coveralls]

Coverage increased (+0.07%) to 85.248% when pulling d9b7443edbc24357f4e77d875350b7ed0bb129f0 on MM1nd:master into f749e993cadde5a13c732fddbaddb5c8bc75000f on Mindwerks:master.

[psi29a]

Reviewing... but looks promising. :)

[psi29a]

Well damn, not only is there code... there's test code and I don't see any regressions. Going to do a little testing on my side but looks good to me.

@ftomassetti what do you think?

[MM1nd]

I pushed the suggested changes. Thanks for the feedback.

[ftomassetti]

For me is ok to merge it, leaving it to @psi29a

[MM1nd]

Yeah, travis failed with a type problem not present on my machine. Investigating.

[coveralls]

Coverage increased (+0.05%) to 85.221% when pulling 60a2c56a6bc2692f9bb6ee561aed83ae192b8a5a on MM1nd:master into f749e993cadde5a13c732fddbaddb5c8bc75000f on Mindwerks:master.

[coveralls]

Coverage increased (+0.05%) to 85.221% when pulling 60a2c56a6bc2692f9bb6ee561aed83ae192b8a5a on MM1nd:master into f749e993cadde5a13c732fddbaddb5c8bc75000f on Mindwerks:master.

[MM1nd]

Fixed the type problem. Should be ready for merge now.

[psi29a]

One last thing, can you add an entry to:

https://github.com/Mindwerks/worldengine/blob/master/CHANGELOG.md

that we know what you did instead of having to hunt it back down later before releasing? :)

After that, it's merge merge merge.

[MM1nd]

Done.

[coveralls]

Coverage increased (+0.9%) to 86.045% when pulling a7436c4b6a1c67f635653c09e7d6862fc8b22574 on MM1nd:master into f749e993cadde5a13c732fddbaddb5c8bc75000f on Mindwerks:master.

[psi29a]

Merged, thank you! :)