Header image
 
Ph.D. Student  
 
 

Terrain generation and flocking simulation

Motivation and results

This simulation shows the suppression of the red squirrel by the grey squirrel, as happend in large areas of Europe, especially in the United Kingdom. The squirrels are represented as flocks of boids and move on a realistic looking 3D terrain, that is randomly generated. It is separated in 3 zones, while two of them (sea and mountain) are prohibted to the boids. To achieve real-time performance a polygonal representation of the prohibited area is computed and the boids use collision avoidance to assure legal movements.
The image below shows an example of the application:

Used approach

Terrain generation

I used the well-known mid point square algorithm to generate the terrain. The algorithm works as follows:
  • Seed 4 corners of a rectangle by random numbers
  • Compute mid-point by averaging corners + random offset --> diamonds
  • Compute mid-points of squares by averaging + random offset --> squares again
  • Decrease random offset ( I used multiplication by 0.6 )

The basic algorithms generated terrains as the following:

In order to generate more realistic looking terrains I used three additions:

  • Multiply two terrains (values in [0,1] ) --> smoothens valleys, sharpen mountains
  • Smooth terrain by filtering with a gaussion (sigma = 0.8)
  • Add random noise to mountains only and smoothen again

These additions generate terrains as the following:

I used two levels for water and mountains and computed a occupancy grid (determine valid positions) by thresholding height map:

Occupancy grid

After computing and dilatong the occupancy grid (in order to place boids on valid regions and avoid borders ) a polygonal representation of the contour is computed to achieve real-time performance. Firstly the occupancy grid is filtered with a Laplace-filter thin polygons, secondly adjacent lines are iteratively merged based on angle and length.

The thresholded height map:

The extracted polygons:

The final contour result:

Flocking

Initially the flock is randomly placed on non-occupied grid cells. During movement the height of the boids is obtained by interpolating the height=map. Each boid is moving and influenced by 6 different forces:
  • Steering force - force pointing in normal direction of boundary, if collision is present
  • Collision force - force in opposite direction of nearby boids
  • Flocking force - force pointing to center of mass of nearby boids
  • Matching force - force to move velocity to average velocity of nearby boids
  • Border force - force in normal direction of world's surrounding border to make boids stay away from border
  • Wander force - 1% of current velocity's norm random noise to make movement look more realistic
The boids are in two different modes. If they observe a collision with a border or a different boid the flocking and matching force will be greatly reduced to ensure collision free movement.
Furthermore the normal of the border is interpolated, otherwise concave border segments would lead to unnatural behavior because the calculated steering force is oscillating between two segments and lead the boid into the obstacle instead of away.

The flocking in action

Limitations

If you save the images, the overhead will greatly reduce the frames per second. This has a negative impact on the euler integration, which becomes unstable and you will experience that the boids are not steering away from obstacles anymore.

Videos

Short in-game movie

Demonstration of Simulator

Thanks a lot to Samantha for her wonderful pronounciation and beautiful voice.

Source Code

To compile and to execute the code the following libraries need to be installed and the environment variables (in brackets) have to be setup accordingly:

  • Intel Performance Primitives 5.1 [IPP]
  • Intel Math Kernel Library 9.1 [MKL]
  • openCV [openCV]
  • boost C++ libraries
  • Qt 4.2 [Qt]

[ source ]

References

Class webpage
Greg Turk's homepage
Information about flocking by Craig Reynolds
Information about steering behavior by Craig Reynolds
Other useful information about flocks by Craig Reynolds

 

 

 



Navigation