16 May ’08

Wandering Algorithms

In a previous weblog, I had started to work on different algorithms by which craas could steer themselves through empty space. Spending time on this now seems something like a folly to me, as the algorithm I use now lets the animal steer themselves based on previous experiences. There is still some use in the older algorithms, for example if a certain group of animals isn't your focus of interest, and you just want to have them move around in your artificial world. I'll describe the different algorithms I used here, and refer to some of the literature.

Part of them are in ruby / OpenGL (the previous language / graphics engine I used), and part of them are described in words.



There are many many ways you could device a wandering algorithm, the most simple being perhaps the venerable random walk in which your entities are randomly moved into one of the available directions.

The biological equivalent for animals of the random walk is the forward random walk (although it might often be called different). Its basic rule is that animal moves forward, and occasionally shifts into a random new direction.

If turning at straight angles is not what you seek in your artificial life, then you can smoothen the angles in a random forward walk pattern by limiting the number of degrees your animals can turn in a single timestep. A few timesteps after a direction change, they'll have turned enough to be again aligned with the direction they were aiming for. An example of this algorithm, and how it looks is given below. The full code of the program is at the bottom of the page.

#smoothed random forward walk

#

@aim = rand(360) if rand < 0.001

@angle = ((250 * @angle + angle_diff(@angle,@aim)) / 250.0) % 360

A variant on the smoothed random forward walk is to let the direction of the animal change slightly every single timestep, rather than having a large change in direction ever so often. This approach doesn't have the straight lines of the random forward walk algorithms, and might be something you desire when you design a wandering algorithm.

# wandering aim forward walk

#

# if the difference between the direction (angle) of the bird and its goal (aim) is

# larger than 6 degrees, then the bird corrects for it (but slowly by 1-200th)

diff = angle_diff(@angle,@aim).abs

if diff > 6 then @angle = ((200 * @angle + diff) / 200.0) % 360 end

# the aim is drifting randomly between 0 and 360 degrees

@aim += 3 * (rand(3) - 1) #33% chance of not changing

@aim = @aim % 360

With these small alterations you can device a large number of wandering algorithms, but the these algorithms are mainly suitable for slow-moving animals, which do not experience inertia; for animals that always move at a constant speed; or for some obscure reason, houseflies which tend to ignore physics and just turn at straight angles while buzzing around ;). If we add inertia and a variable moving speed, then we get behaviour which seem suitable for modelling animals that chase each other, or move fast in general (like birds).

# acceleration/inertia random forward walk

#

# Every 700 timesteps pick a random direction, translate it to a vector, and

# make sure that the amplitude of the vector is between 0.5 and 1, so that

# the bird isn't flying at snail speed

# (this example isn't really clear code-wise, apologies)

if @passedsincelast > 700

           begin

              @accel  = rand(360).to_vector 

              end until @accel[0].abs > 0.5 and @accel[1].abs > 0.5          

           @passedsincelast = 0

        end



        # moving

        @vector[0] = (1000 * @vector[0] + @accel[0]) / 1001.0  # I'm not sure if it is still acceleration

        @vector[1] = (1000 * @vector[1] + @accel[1]) / 1001.0  # when I describe it like this. it's more like a new vector

Hanno Hildenbrandt, of the university of groningen, netherlands, has been doing something similar (but far more impressive) as this acceleration/inertia algorithm, by applying these basic physics, as well as gravity to a 3d swarm of flocking sterling birds, and combined these physics with crowd behaviour of large swarms of entities, as was previously done by the boids of Craig W. Reynolds.

The code for the three ruby programs is included here:
first and second:

third: