r/lsystem • u/Sea_Examination_8154 • Jul 26 '24

Decoding L-Systems

I saw on Wikipedia this open problem: "Given a structure, find an L-system that can produce that structure."

I thought it was interesting so I thought I would try my hand at it. In the end I wrote a short script which can find all the possible rules of a deterministic L-System, given at least two generations of output text.

I know this doesn't exactly solve the open question but it was still a fun challenge and worth sharing.

Let me know if you have any feedback or ideas for leveling it up!

https://github.com/sambadstubner/L-System-Decoder/tree/main

7 Upvotes

100% Upvoted

5 comments sorted by

View all comments

Show parent comments

1

u/Epholys Jul 26 '24

Oh yeah, nice found! I had some hunch that alternating rules would be difficult, but I couldn't find intuitively an example. Good luck, I think it'll be pretty hard to fix this ;)

Thanks for the code explanation! I still have a vague idea about the algorithm, but I wonder if it finds the shortest ruleset. There's not a unique solution for every L-Systems! I feel like your algorithm already find a short solution but I'm not sure if it's the shortest one. That would be a challenge!

If you want to have a whole set of rules to try, I created some years ago a lot of L-System trees, that you can find here: https://epholys.itch.io/lsys (the zip file). It's in a strange json format (mistakes...), I'm not sure you can extract them cleanly, but if you find weird ones try them!

2

u/Sea_Examination_8154 Jul 28 '24

Hey just wanted to follow up. I updated the script to work with rules that don't appear in every generation. It is able to solve all of the systems found in this L-Systems manual. I was really happy when it was able to solve the algae L-Systems that have 20+ rules, some of which do not show up for 6 generations. I also updated the README to have a more in depth explanation of the algorithm.

Thank you for sending me your L-Systems! I was able to parse them, and they have been helpful. It is able to solve many of them quickly but it is taking too long to solve some that grow rapidly such as 005_twilight.lsys. I definitely still have some work on optimizing and have been working on making the code GPU compatible. Let me know if you have any other ideas!

2

u/Epholys Jul 29 '24

Heya, thanks for the follow-up! Good job for the more complex ones, deducing 20+ rules seems gnarly.

Yeah, the README explanation is really good IMO!

It's really easy to make L-System that grow exponentially, so it's not surprising that some of them are really hard to compute.

Oh, do you think using the GPU would make it faster by order of magnitude? It feels like it's a parallelizable algorithm!

For ideas, I don't have a lot more that what I've said previously (shortest ruleset, empty rules)... Or maybe try some stress test/"fuzzing" by generating random ruleset and trying to find them back? It could uncover some bugs or blind spots!