URL:
  <http://gna.org/patch/?5357>

                 Summary: common/tech.c: player_invention_reachable call cost
is exponential with deep technology trees: fixed with memoization
                 Project: Freeciv
            Submitted by: None
            Submitted on: Sun 12 Oct 2014 09:05:06 AM UTC
                Category: None
                Priority: 5 - Normal
                  Status: None
                 Privacy: Public
             Assigned to: None
        Originator Email: aloril+free...@iki.fi
             Open/Closed: Open
         Discussion Lock: Any
         Planned Release: 

    _______________________________________________________

Details:

Originally player_invention_reachable has exponential cost.
When technology tree is too deep, for example 10 additional layers, it takes
too long time. With enough levels over that it practically never returns.

This uses memoization to cache recursive result. Memoization table is
calculated from scratch at every call and discarded when function returns.
Converts call cost from exponential to linear.




    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Sun 12 Oct 2014 09:05:06 AM UTC  Name: tech.patch  Size: 5kB   By: None

<http://gna.org/patch/download.php?file_id=22607>

    _______________________________________________________

Reply to this item at:

  <http://gna.org/patch/?5357>

_______________________________________________
  Message sent via/by Gna!
  http://gna.org/


_______________________________________________
Freeciv-dev mailing list
Freeciv-dev@gna.org
https://mail.gna.org/listinfo/freeciv-dev

Reply via email to