4

I'm trying to design data structure for an implementation of L-System rewriting engine in C++ and I just can't seem to get anywhere :(.

I need to store a string of symbols (characters). There are be several types of symbols (that's specified by the LSystem's alphabet). Let's say we have types "A", "B", "C". Now each type of symbol can have different parameters. For example symbol of type A will have some distance and symbol B an angle. C symbol has no parameters. The string then could look like "ABABC".

Then I need to iterate through the string and do some actions that are also connected to each type of symbol. "A" could mean "draw line of 'distance' length" (distance is parameter of A), B "turn 'angle' degrees" and C finish painting.

I tried to have class Symbol and a child for each symbol type (class SymbolA, class SymbolB, class SymbolC), but I don't know how to create the string. I would like to avoid type casts and stuff like that.

Is there somebody who had a similar problem or has an idea that can help me, please?

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
terrible_software_designer
  • 41
  • 2
  • You can do a lot with L-systems using just fixed length line segments and right angles. For that matter you can get by with just L for turn left. Use a `std::string` for that. Get a C curve or Dragon curve up running. Or some Hilbert curve. – Cheers and hth. - Alf Mar 10 '11 at 19:17
  • Thanks for your advice! It made me threw the old design away and start over (now I see that the previous idea was pretty crazy). The symbols don't need to have those parameters after all and that let me use std::string, like you said :). Thanks again, finally some progress! – terrible_software_designer Mar 12 '11 at 15:56

2 Answers2

1

If you want to implement something as complicated as full L-systems, I'd suggest using a higher-level language than C++, such as Python or Common Lisp. Then you can profile the entire piece of code and implement the speed bottlenecks in C/C++.

I implemented L-systems a long time ago for a course in Chaos Theory and Fractals, using Common Lisp. It wasn't too hard to do - just used a list of symbols. I've been trying to find the code for it, but it's been more than 7 years, so no luck so far.

Anyway, this seems like a much more reasonable approach to me. Even if you make a slow implementation in a high-level language, it will give you a better idea of how to implement it in C++, which takes a lot more developer time to do.

nybbles
  • 111
  • 2
  • I'd definitely go higher-level with this. You need to maintain 2 distinct mappings (symbol->expansion, symbol->graphics_command) and apply them in a controlled manner. In a sense, classes are too "concrete", and heterogeneous containers are really useful. – luser droog Sep 25 '12 at 16:26
0

Seems to me you're on the right track: You need a SymbolBase class that define pure virtual functions for the kind of operations that need to be implemented, and then have SymbolA, SymbolB, etc. derived classes that each implement the specific functionality. For painting the elements to the screen, each class would implement some function that takes a graphics object or similar as argument and paints itself to the graphics object.

In order to represent these in a 'string', you need a linear collection of some kind, STL vector or linked list most likely, a linked list is more efficient if you're going to rearrange the symbols using the L-system productions. You will then be able to iterate over the list in order to display it on the screen. You'll get into the usual problem of holding instances of various classes in a collection, where the element type is pointers to the base class. You can usually get it working without too many type cast (and always use dynamic_cast when you do need it). If you design your base class correctly, then the calling code should be able to call the pure abstract functions in the base class without ever caring which particular symbol class it's actually interacting with.

Rasmus Storjohann
  • 128
  • 7