dcc_lsystem/
turtle.rs

1use std::cmp::{max, min};
2use std::collections::HashMap;
3use std::f32::consts::FRAC_PI_2;
4
5use rand::Rng;
6use regex::Regex;
7
8use dcc_lsystem_derive::TurtleContainer;
9use lazy_static::lazy_static;
10
11use crate::renderer::TurtleRenderer;
12use crate::{ArenaId, LSystem, LSystemBuilder};
13
14/// A simple trait for an integer-valued Turtle.
15///
16/// Any implementation of this trait should contain a `BaseTurtle` struct which
17/// is referred to by the `inner` and `inner_mut` methods.  This BaseTurtle deals
18/// with storing the turtle's current position, and drawing lines as appropriate.
19///
20/// The real meat and potatoes of this trait is the `forward` method, which is
21/// how someone would actually move your turtle.  Your implementation should be responsible
22/// for keeping track of the turtle's heading, and `forward` should move your turtle
23/// in that direction (using `self.inner_mut().delta_move(dx, dy)`).
24///
25/// # Example
26/// The following `DumbTurtle` only moves to the right.
27///
28/// ```rust
29/// use dcc_lsystem::turtle::{BaseTurtle, MovingTurtle};
30///
31/// struct DumbTurtle {
32///     inner: BaseTurtle,
33/// }
34///
35/// impl MovingTurtle for DumbTurtle {
36///     type Item = i32;
37///
38///     fn inner(&self) -> &BaseTurtle {
39///         &self.inner
40///     }
41///
42///     fn inner_mut(&mut self) -> &mut BaseTurtle {
43///         &mut self.inner
44///     }
45///
46///     fn forward(&mut self, distance: i32) {
47///         self.inner_mut().delta_move(distance, 0);
48///     }
49/// }
50/// ```
51///
52pub trait MovingTurtle {
53    type Item;
54
55    /// Returns a reference to the wrapped `BaseTurtle`.
56    fn inner(&self) -> &BaseTurtle;
57
58    /// Returns a mutable reference to the wrapped `BaseTurtle`.
59    fn inner_mut(&mut self) -> &mut BaseTurtle;
60
61    /// Moves the turtle forward by `distance`.
62    fn forward(&mut self, distance: Self::Item);
63}
64
65/// This trait indicates that the implementor contains a turtle for us to play with.
66///
67/// It's a bit annoying to have to implement this trait everywhere, so using the `dcc-lsystem-derive`
68/// crate you can do the following:
69///
70/// ```rust
71/// use dcc_lsystem::turtle::{SimpleTurtle, TurtleContainer};
72/// use dcc_lsystem_derive::TurtleContainer;
73///
74/// #[derive(TurtleContainer)]
75/// struct BasicContainer {
76///     #[turtle]
77///     inner : SimpleTurtle,
78///
79///     /* <----- some other fields ----- */
80/// }
81/// ```
82///
83/// which is roughly equivalent to the following:
84///
85/// ```rust
86/// use dcc_lsystem::turtle::{SimpleTurtle, TurtleContainer, MovingTurtle};
87///
88/// struct BasicContainer {
89///     inner : SimpleTurtle,
90///
91///     /* <----- some other fields ----- */
92/// }
93///
94/// impl TurtleContainer for BasicContainer {
95///     type Item = <SimpleTurtle as MovingTurtle>::Item;
96///
97///     fn inner(&self) -> &MovingTurtle<Item = Self::Item> {
98///         &self.inner
99///     }
100/// }
101///```
102pub trait TurtleContainer {
103    type Item;
104
105    fn inner(&self) -> &dyn MovingTurtle<Item = Self::Item>;
106}
107
108/// Every turtle contains a turtle.
109impl<T> TurtleContainer for dyn MovingTurtle<Item = T> {
110    type Item = T;
111
112    fn inner(&self) -> &dyn MovingTurtle<Item = Self::Item> {
113        self
114    }
115}
116
117pub trait Stack: MovingTurtle {
118    /// Push the current state of this turtle onto a stack.
119    fn push(&mut self);
120
121    /// Pop the current state of this turtle onto a stack.
122    fn pop(&mut self);
123}
124
125#[derive(Clone, Debug)]
126pub struct BaseTurtle {
127    x: i32,
128    y: i32,
129    lines: Vec<(i32, i32, i32, i32)>,
130    max_x: i32,
131    max_y: i32,
132    min_x: i32,
133    min_y: i32,
134    pen_down: bool,
135}
136
137impl BaseTurtle {
138    /// Creates a new `BaseTurtle` instance.
139    pub fn new() -> Self {
140        Self {
141            x: 0,
142            y: 0,
143            lines: Vec::new(),
144            max_x: 0,
145            max_y: 0,
146            min_x: 0,
147            min_y: 0,
148            pen_down: true,
149        }
150    }
151
152    /// Returns the current `x` coordinate of the turtle.
153    pub fn x(&self) -> i32 {
154        self.x
155    }
156
157    /// Returns the current `y` coordinate of the turtle.
158    pub fn y(&self) -> i32 {
159        self.y
160    }
161
162    /// Returns a slice containing all the lines `(x1, y1, x2, y2)` traversed by the turtle.
163    pub fn lines(&self) -> &[(i32, i32, i32, i32)] {
164        &self.lines
165    }
166
167    /// Set the current position of this turtle to `(x,y)`.
168    pub fn set_position(&mut self, x: i32, y: i32) {
169        self.x = x;
170        self.y = y;
171        self.update_bounds();
172    }
173
174    fn update_bounds(&mut self) {
175        self.min_x = min(self.min_x, self.x);
176        self.min_y = min(self.min_y, self.y);
177        self.max_x = max(self.max_x, self.x);
178        self.max_y = max(self.max_y, self.y);
179    }
180
181    /// Moves the turtle by `(dx,dy)`.
182    pub fn delta_move(&mut self, dx: i32, dy: i32) {
183        let x2 = self.x + dx;
184        let y2 = self.y + dy;
185
186        if self.pen_down {
187            self.lines.push((self.x, self.y, x2, y2));
188        }
189
190        self.x = x2;
191        self.y = y2;
192
193        self.update_bounds();
194    }
195
196    /// Returns `(total_width, total_height, min_x, min_y)`, where
197    /// `total_width` (respectively `total_height) is the largest horizontal (respectively vertical) distance between any two points
198    /// that the turtle visited, `min_x` (respectively `min_y`) is the smallest horizontal (respectively vertical) position that
199    /// the turtle visited.
200    ///
201    /// This is useful for converting from turtle coordinates to a new coordinate system starting at `(0,0)`
202    /// with width `total_width`, height `total_height`, and all positions have positive `x` and `y` coordinates.
203    pub fn bounds(&self) -> (u32, u32, i32, i32) {
204        (
205            (self.max_x + self.min_x.abs()) as u32,
206            (self.max_y + self.min_y.abs()) as u32,
207            self.min_x,
208            self.min_y,
209        )
210    }
211
212    /// Puts the turtles pen down.
213    pub fn pen_down(&mut self) {
214        self.pen_down = true;
215    }
216
217    /// Pulls the turtles pen up.
218    pub fn pen_up(&mut self) {
219        self.pen_down = false;
220    }
221}
222
223impl Default for BaseTurtle {
224    fn default() -> Self {
225        Self::new()
226    }
227}
228
229/// Represents the cardinal directions.
230#[derive(Debug, Copy, Clone, Eq, PartialEq)]
231pub enum Heading {
232    North,
233    South,
234    East,
235    West,
236}
237
238impl Heading {
239    /// Returns the `Heading` that is 90 degrees left of this one.
240    pub fn left(self) -> Self {
241        match self {
242            Heading::North => Heading::West,
243            Heading::West => Heading::South,
244            Heading::South => Heading::East,
245            Heading::East => Heading::North,
246        }
247    }
248
249    /// Returns the `Heading` that is 90 degrees right of this one.
250    pub fn right(self) -> Self {
251        // Don't judge me...
252        self.left().left().left()
253    }
254
255    pub fn dx(self) -> i32 {
256        match self {
257            Heading::West => -1,
258            Heading::East => 1,
259            _ => 0,
260        }
261    }
262
263    pub fn dy(self) -> i32 {
264        match self {
265            Heading::North => 1,
266            Heading::South => -1,
267            _ => 0,
268        }
269    }
270}
271
272/// A simple turtle implementation.  It has the following features:
273///
274/// * You can change direction! (`turtle.set_heading(f32)`, `turtle.left(f32)`, and `turtle.right(f32)`)
275/// * You can make it move! (`turtle.forward(i32)`)
276/// * Stacks! (`turtle.push()` and `turtle.pop()`)
277///
278/// and some other features.
279#[derive(Clone, Debug)]
280pub struct SimpleTurtle {
281    turtle: BaseTurtle,
282    heading: f32,
283    stack: Vec<(i32, i32, f32)>,
284    pen_down: bool,
285}
286
287impl SimpleTurtle {
288    /// Return a new `StackTurtle` instance.
289    pub fn new() -> Self {
290        Self {
291            turtle: BaseTurtle::new(),
292            heading: FRAC_PI_2,
293            stack: Vec::new(),
294            pen_down: true,
295        }
296    }
297
298    /// Turns the turtle left by the given angle (in radians).
299    pub fn left(&mut self, angle: f32) {
300        self.heading += angle;
301    }
302
303    /// Turns the turtle right by the given angle (in radians).
304    pub fn right(&mut self, angle: f32) {
305        self.heading -= angle;
306    }
307
308    /// Set the current heading of the turtle (in radians).
309    pub fn set_heading(&mut self, heading: f32) {
310        self.heading = heading;
311    }
312}
313
314impl Stack for SimpleTurtle {
315    /// Pushes the current position and heading of the turtle onto the stack.
316    fn push(&mut self) {
317        self.stack
318            .push((self.turtle.x(), self.turtle.y(), self.heading));
319    }
320
321    /// Pops the position and heading off the stack.
322    fn pop(&mut self) {
323        let (x, y, heading) = self.stack.pop().expect("Called pop on empty stack");
324
325        self.turtle.set_position(x, y);
326        self.heading = heading;
327    }
328}
329
330impl MovingTurtle for SimpleTurtle {
331    type Item = i32;
332
333    fn inner(&self) -> &BaseTurtle {
334        &self.turtle
335    }
336
337    fn inner_mut(&mut self) -> &mut BaseTurtle {
338        &mut self.turtle
339    }
340
341    fn forward(&mut self, distance: i32) {
342        let dx = self.heading.cos() * distance as f32;
343        let dy = self.heading.sin() * distance as f32;
344
345        if self.pen_down {
346            self.turtle.delta_move(dx as i32, dy as i32);
347        }
348    }
349}
350
351impl Default for SimpleTurtle {
352    fn default() -> Self {
353        Self::new()
354    }
355}
356
357/// The state modified by a `TurtleLSystemRenderer`.  Each `TurtleAction` corresponds
358/// to a modifier of the form `Fn(&mut TurtleLSystemState)`.
359#[derive(TurtleContainer)]
360pub struct TurtleLSystemState {
361    angle: i32,
362    angle_stack: Vec<i32>,
363
364    #[turtle]
365    turtle: SimpleTurtle,
366}
367
368impl TurtleLSystemState {
369    /// Create a new state.
370    pub fn new() -> Self {
371        Self {
372            angle: 0,
373            angle_stack: Vec::new(),
374            turtle: SimpleTurtle::new(),
375        }
376    }
377}
378
379impl Default for TurtleLSystemState {
380    fn default() -> Self {
381        Self::new()
382    }
383}
384
385/// A `TurtleLSystemBuilder` is used to generate an L-system and a turtle
386/// based renderer based don this L-system.
387#[derive(Clone)]
388pub struct TurtleLSystemBuilder {
389    builder: LSystemBuilder,
390    actions: HashMap<ArenaId, TurtleAction>,
391    tokens: HashMap<String, ArenaId>,
392    global_rotate: i32,
393}
394
395impl TurtleLSystemBuilder {
396    /// Create a new `TurtleLSystemBuilder` instance.
397    pub fn new() -> Self {
398        Self {
399            builder: LSystemBuilder::new(),
400            actions: HashMap::new(),
401            tokens: HashMap::new(),
402            global_rotate: 0,
403        }
404    }
405
406    /// Apply a global rotation to the builder.  This is useful for modifying the orientation
407    /// of the data passed to a `Renderer`.
408    pub fn rotate(&mut self, angle: i32) -> &mut Self {
409        self.global_rotate = angle;
410
411        self
412    }
413
414    /// Associate a token and corresponding action to this builder.
415    pub fn token<S: Into<String>>(&mut self, token: S, action: TurtleAction) -> &mut Self {
416        let ident = token.into();
417
418        let token = self.builder.token(ident.clone());
419
420        self.tokens.insert(ident, token);
421        self.actions.insert(token, action);
422
423        self
424    }
425
426    /// Set the axiom  for this builder.
427    pub fn axiom(&mut self, ident: &str) -> &mut Self {
428        let mut axiom = Vec::new();
429
430        for part in ident.split_whitespace() {
431            let token = self.get_token(part).expect("Invalid axiom");
432
433            axiom.push(token);
434        }
435
436        assert_ne!(axiom.len(), 0);
437
438        self.builder.axiom(axiom);
439
440        self
441    }
442
443    fn get_token(&self, token: &str) -> Option<ArenaId> {
444        self.tokens.get(token).cloned()
445    }
446
447    /// Add a transformation rule to the builder.
448    pub fn rule<'a, S: Into<&'a str>>(&mut self, rule: S) -> &mut Self {
449        let rule = rule.into();
450
451        lazy_static! {
452            static ref RE: Regex = Regex::new(r"\s*(\w)\s*=>\s*((?:\s*\S+\s*)*)\s*").unwrap();
453        }
454
455        let cap = RE.captures(rule).expect("Invalid rule");
456
457        // The LHS of our rule
458        let lhs = self
459            .get_token(&cap[1])
460            .unwrap_or_else(|| panic!("Invalid token: {}", &cap[1]));
461
462        // Construct the RHS of our rule
463        let mut rule = Vec::new();
464
465        for token in cap[2].split_whitespace() {
466            let token = self
467                .get_token(token)
468                .unwrap_or_else(|| panic!("Invalid token: {}", token));
469
470            rule.push(token);
471        }
472
473        // Add the rule to our builder
474        self.builder.transformation_rule(lhs, rule);
475
476        self
477    }
478
479    /// Consumes the builder, returning the generated `LSystem` and a `Renderer`
480    /// which can associate tokens in the `LSystem` to turtle actions.
481    pub fn finish(self) -> (LSystem, TurtleRenderer<TurtleLSystemState>) {
482        let mut renderer = TurtleRenderer::new(TurtleLSystemState::new());
483
484        // Register the processing functions for each action
485        for (id, action) in self.actions.into_iter() {
486            match action {
487                TurtleAction::Push => {
488                    renderer.register(id, |state| {
489                        state.turtle.push();
490                        state.angle_stack.push(state.angle);
491                    });
492                }
493                TurtleAction::Pop => {
494                    renderer.register(id, |state| {
495                        state.turtle.pop();
496                        state.angle = state.angle_stack.pop().expect("Popped with empty stack");
497                    });
498                }
499                TurtleAction::Forward(distance) => {
500                    let current_global_rotate = self.global_rotate;
501
502                    renderer.register(id, move |state| {
503                        state.turtle.set_heading(
504                            ((current_global_rotate + state.angle) as f32).to_radians(),
505                        );
506                        state.turtle.forward(distance);
507                    });
508                }
509                TurtleAction::Rotate(angle) => {
510                    renderer.register(id, move |state| {
511                        state.angle = (state.angle + angle) % 360;
512                    });
513                }
514                TurtleAction::StochasticRotate(distribution) => {
515                    renderer.register(id, move |state| {
516                        state.angle = (state.angle + distribution.sample()) % 360;
517                    });
518                }
519                TurtleAction::StochasticForward(distribution) => {
520                    let current_global_rotate = self.global_rotate;
521
522                    renderer.register(id, move |state| {
523                        state.turtle.set_heading(
524                            ((current_global_rotate + state.angle) as f32).to_radians(),
525                        );
526                        state.turtle.forward(distribution.sample());
527                    });
528                }
529                TurtleAction::Nothing => {}
530            }
531        }
532
533        (self.builder.finish(), renderer)
534    }
535}
536
537impl Default for TurtleLSystemBuilder {
538    fn default() -> Self {
539        Self::new()
540    }
541}
542
543/// An integer-valued probability distribution.
544///
545/// We need to be able to clone Box<dyn Distribution>, so we use the wonderful
546/// `dyn_clone` crate to allow for this.
547pub trait Distribution: dyn_clone::DynClone {
548    /// Take a sample from this distribution.
549    fn sample(&self) -> i32;
550}
551
552dyn_clone::clone_trait_object!(Distribution);
553
554/// A uniform distribution on a closed interval.
555#[derive(Clone)]
556pub struct Uniform {
557    lower: i32,
558    upper: i32,
559}
560
561impl Uniform {
562    /// Creates a new uniform distribution on the interval [lower, upper].
563    ///
564    /// # Panics
565    /// Will panic is `lower` > `upper`
566    pub fn new(lower: i32, upper: i32) -> Self {
567        assert!(lower <= upper);
568        Self { lower, upper }
569    }
570}
571
572impl Distribution for Uniform {
573    fn sample(&self) -> i32 {
574        let mut rng = rand::thread_rng();
575        rng.gen_range(self.lower..=self.upper)
576    }
577}
578
579/// A constant distribution
580impl Distribution for i32 {
581    fn sample(&self) -> i32 {
582        *self
583    }
584}
585
586/// The possible actions we can associate to tokens in our `LSystem`.
587#[derive(Clone)]
588pub enum TurtleAction {
589    Nothing,
590    Rotate(i32),
591    Forward(i32),
592    StochasticRotate(Box<dyn Distribution>),
593    StochasticForward(Box<dyn Distribution>),
594    Push,
595    Pop,
596}
dcc_lsystem/turtle.rs

dcc_lsystem/
turtle.rs
