Thursday, November 4, 2021

Butterflies

I showed some images of new clothing and hanger models in closets in the last post. While I was looking for clothing models, I came across a monarch butterfly model created by Paul Spooner and decided to add that to 3DWorld. This somewhat fits with my "animals" module, which previously included only birds and fish. So, surprise! This isn't another update on buildings or cities. I'm going back and working on procedural generation in nature.

Butterflies, like birds, are flying animals. Flying and swimming animals such as fish are easier to implement than animals walking on the ground in some ways, and more difficult in other ways. Their physics tends to be more complex because it's all in 3D with a vertical elevation component. On the other hand, collision detection is easier since there aren't as many objects to collide with in the air and water. In fact, the probability of two animals colliding is low enough that I can basically ignore it.

Butterflies inherit from my animal C++ class and share some of the code with birds and fish. For example, they share code for random spawning within a terrain tile, logic to allow them to cross between tiles, per-frame physics updates, visibility queries, and drawing. What else can I share with the existing code? Let's see, I can reuse the 3D model drawing code with all of the orientation transform code from fish. (Birds are drawn as three flattened spheres rather than 3D models.) I can reuse the simple wing animation logic from birds. The steering behavior can be somewhat reused from the random walk of both fish and birds, though I certainly have to extend this system. I suppose I need logic to choose destinations and fly to them as well, because butterflies tend to land on plants and other objects. I don't have any code for that in the fish or birds system, but I can use a similar model to cars and pedestrians. So it looks like all the major components are there. I just have to copy/paste the right pieces and/or factor out the reusable parts.

The first task was to list all of the features I planned to add, in the order I planned to add them:

  • Loading and drawing of butterfly 3D model
  • Spawning in appropriate areas of tiles (over grass, avoiding water/rock/snow/cities)
  • Flight logic with random walk
  • Collision detection with scene objects (terrain, trees, plants, buildings, etc.)
  • Wing animation (model split into body + two rotating wings)
  • Choice of destination and logic to fly to destination
  • Optimizations
  • Color and wing pattern variations

Loading the model, drawing, and setting spawn points was pretty easy. Of course I had the size scale way off on my first attempt:

My first attempt: The Attack of the Giant Butterflies

At least the butterflies aren't hard to find! One side effect was that it was pretty easy to tune the model drawing and animation code when they're this large and easy to see.

It took me a few attempts to animate these models. I eventually decided to use a sine wave to rotate the wings 45 degrees about the body in opposite directions for each side. This isn't perfect as the wings clip slightly through each other and through the body. I watched a video showing butterflies moving in slow motion for reference. It seems like their wings don't quite rotate about a point as a rigid body as I was attempting to imitate. Instead, they flop around and bend like stiff cloth or paper. While my solution doesn't look great when viewing a stationary butterfly close up, it's actually difficult to spot the self intersections once the butterfly is small and moving in erratic patterns.

Flight logic was an interesting topic, and probably the one I spent the most total time on. Real butterflies don't fly in straight lines; their paths are much more random. This applies to their altitude as well as their heading. I decided to keep the butterfly model level with the ground and split the movement into an XY component parallel to the ground and a vertical (Z) altitude component. The variables controlling motion are:

  • Speed (affects movement speed, turn rate, and wing flap rate; tied to realtime)
  • Rotation angle about vertical/Z axis / in XY plane to control direction
  • Vertical acceleration to change altitude

I wanted to ensure very smooth movement, so I chose to add a random value to an accumulator for each of these variables each frame. The accumulator is then integrated over time to calculate an acceleration, which is then multiplied by time to get velocity, which is then multiplied by time again to update the position and direction of the butterfly. This should guarantee the path is second order continuous. All variables are clamped to a reasonable value at the end of a physics update. This includes caps for min and max altitude, max speed, max turn rate, etc. There are lots of constants I had to keep adjusting to get reasonable behavior, and now butterflies fly around in crazy random paths in an unpredictable way. Just like in real life!

Then I added code to choose destination points. I have flowers in the grass, but there are thousands of them per tile. Flowers are drawn using instancing and aren't actual game objects. This means I can't easily choose them as destinations. I went with using the tops of various types of plants as destinations instead, since butterflies often land on leaves. Butterflies in cities will choose to land on the grass in parks, if there's a park nearby. Otherwise they simply fly around randomly and try to avoid the buildings.

Their behavior finite state machine actually has four states: explore, find destination, approach, and rest. Butterflies start out in the "explore" state. After some time has elapsed, they will enter the "find destination" state and every so often will consider a random plant or park. If they find one that's close by and visible, they will enter the "approach" state. After landing at their destination they enter the "rest" state for a few seconds, then take off with a vertical ascent and transition back to the "explore" state. This logic results in butterflies moving from plant to plant in a slow, winding path.

Choosing destinations was easy; actually getting them to fly there was much more difficult. How exactly is this crazy random flight path supposed to end the butterfly at a particular location? After some experimenting, I decided to use the distance to the destination to blend between "explore" and "approach" behaviors. The approach force increases as the distance to the destination decreases. At first, when they're far away, there will be a weak force pulling them toward the destination. The random behavior will mostly override this force, but they will slowly drift toward the destination over time. As they get closer, the approach force will increase in strength, allowing them to eventually home in on their target. They may take a very roundabout path, but they do eventually get there. It could be in tens of seconds or a few minutes. It took many attempts to avoid the oscillation behavior during these state transitions, especially when they're very close to the destination but have the wrong altitude.

When I first implemented this I had no idea why the butterflies [mis-]behaved the way they did. I had to add debug visualization to show their flight path as a string of spheres, their destination point, and the line to their destination. The line color reflects the magnitude of the approach force: blue for weak, red for strong. These debug visuals also helped me find the butterflies in the scene, which are super tiny compared to the mountains, buildings, and trees. Here's an example where I have the debug visualization turned on but the trees and grass turned off.

Butterfly path and destination debug visualizations helped me get the logic right. It's obvious how their paths are nowhere near a straight line.

You can see just how wavy some of those paths are. This debug mode definitely helped, and I was eventually able to get everything working. Here's a video where I follow a butterfly around for a minute or so as it lands on a plant and takes off again.

I had to add a LOD (level of detail) optimization where the body and legs weren't draw unless the butterfly was close to the player. The only other optimization that was needed was better early rejection of trees and plants during collision detection. I reused the code I had for player sphere collisions, and it was never optimized for use with a thousand actors.

The final step was adding wing color and texture variation. The initial texture had the wing colors baked into the same texture atlas as the body. Paul sent me a texture with white wings that I was able to recolor in my code by overriding the model's material color per butterfly instance. I added a mix of monarchs and butterflies with white, yellow, orange, blue, and violet wing markings. These single colors don't look as nice as the multiple colors in the monarchs, but at least they add more color variety. I've taken a screenshot of a three butterflies here: monarch, yellow, and violet.

I added some other butterfly colors mixed in with the monarchs. Do you see the violet one on the right?

I created a second video with a large number of butterflies. There are thousands in this scene. The player is free to move anywhere in the world and new tiles with new butterflies will be generated around them.


I'm pretty happy with how this mini project turned out. It was a week well spent. Is it time to add other animals or insects, or time to get back to cities and buildings? I don't know, I guess we'll have to wait and see.

If I do decide to continue with butterflies, I might add a mating dance between males and females. I'm sure that getting the motion correct for a pair of them should be trivial. Right?

The source code for butterflies can be found here if you're interested.

2 comments:

  1. Fantastic. I thought the video of the butterfly looked great.

    Start: "I'm going to do procedural generation of cities"
    Now: "I'm now working on butterfly mating dances"

    I had to laugh because I do this all the time myself :-)

    ReplyDelete
    Replies
    1. Thanks! I work on all aspects of procedural generation. I eventually want to have a fully generated world for the player to explore. I want both natural (including things like butterflies) and man-made objects (including cities with buildings).

      Delete