Procedural Generation Experiments
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
cereal
gsl
imgui
includes
media
saves
src
test
.gitignore
LICENSE
Makefile
README.org

README.org

Procedural Generation Experiments

Philosophy

Implemented

  • (Simple) L-systems
  • (Simple) Turtle interpretation
  • Static GUI to display parameters
  • Dynamic GUIs to interact with the parameters
  • Basic and necessary user interactions (mouse dragging, adding, removing, copy-pasting)
  • Saving and loading LSystems to and from files

Main Roadmap

  1. Make the generated vertices pretty (colors and growth) (example in dev.color and dev.time)
  2. Add genetic algorithm or constraint-based algorithm for new LSystem generation

Other ideas

Next Bugs

Optimization, non-urgent bugs and cleanup

  • Optimization With the current algorithm, execution time and memory consumption are exponential. Memory consumption is the biggest factor, as several GB can be allocated easily (from 16 iterations).
    • Cache multi-iteration production rules (very good for execution time (from O(x^n) to O(n)) but bad for memory consumption). Useful when calculating L-System productions but not for vertices computation, which is the biggest time hog.
    • Compute the vertices from the position (0,0) and use sf::RenderStates to define real position and angle: huge gain for the most common operation: moving around the vertices.
    • Use raw OpenGL vertices instead of SFML’s sf::Vertex to reduce their size (no texcoord for example)
      • Use `sqrt` instead of `cos` and `sin` for angles to calculate vertex’s position
  • Bugs
    • Correct zoom level and drag behaviour when resizing window (in Gnome)
    • Maybe using arbitrary floating point precision (even with doubles some geometric LSystems are not so geometric anymore)
  • Cleanup
    • Make ‘DrawingParameters’ an Observable

Development framework

  • Environment: debian sid chroot with these development packages: g++ make git libsfml-dev googletest gdb valgrind
  • Dependencies:
    • SFML / 2.4.1 / Website / installed from packages /
    • googletest / 1.7.0 / Github Repository / installed from packages
    • dear imgui, / 1.5 / Github Repository / installed via release 1.5 / included in the repo
    • imgui-sfml / 2017-07-04 / Github Repository / installed via the instructions from the README.org of the repository / included in the repo
    • GSL (Guidelines Support Library) / 2017-06-27 / Github Repository / cloned from the repository / included in the repo
    • cereal / 1.2.2 / Website / downloaded from the website / included in the repo
  • Coding rule: ISO C++ Core Guidelines with GSL
  • Compilation: make and C++17 needed
  • Testing suite: googletest

Warnings:

  • The save format is not yet stable, the save files may not be compatible between two commits. It is however possible to manually edit them to support the new features. the ‘saves’ directory will always be populated with valid examples.
  • The API is not stable (and will probably never be, as this is a software and not a library)

Completing the framework?

  • Static analysis (Coverity?)
  • Formal documentation (Doxygen?)
  • Automatic cross-compiling?
  • Automatic on-screen serialization?

Thoughts dump

  • Huge literature on the subject and extremely developed existing software. What does this project bring?

Memory allocation with Valgrind (2017-09-17 Epholys)

valgrind --tool\=massif --time-unit\=B --peak-inaccuracy=0.1

Memory usage is directly linked to the size of the L-Systems calculated. These sizes grow exponentialy, so does the memory. As an example, with a simple L-System and 16 iterations, the resulting string is composed of tens of million of symbols. Saving these symbols and the 20-bytes-long vertices associated takes at least hundreds of MB in memory. Moreover, during the execution of logo::computes_vertices, we use a std::vector as data structure. Its allocation strategy (in g++ and MSVC) is to multiply the capacity by a number. As a consequence, this vector is at most “factor” times too large. In our case of hundreds of MB, it can be a serious toll. Fortunately, this vector is truncated when returned by the function.

I don’t see an obvious way to reduce memory consumption. Symbols and vertices are already very small. We could reduce the size of the aforementioned vector by reserving just enough bytes for the vertices. But that means we would have to approximate a small upper-bound of the result of the L-System and also how much of its symbols will produce a new vertex. A whole mathematical problem.

For now, I’ll do nothing: I see no reasonable case to computes and display so much iterations of a L-System. I’ll concentrate on optimizing execution time (with memory consumption in mind).

(Res)sources

Procedural content generation: L-Systems (by Rabidgremlin)

The Algorithmic Beauty of Plants

/r/lsystem

Job Talle – Lindermayer systems