Math254 Final Project
Flocking Applet, a Markov Chain Example
John Kavanaugh
Brian Jackson
Slider Information
 Amount  These control the number of creatures of a species
 Speed  These control the speed at which the creatures move (there is a random "jitter" that is not controlled by this slider)
 Coherence  These control how much the creatures want to be near creatures of the same species ( left is indifferent, right is extreme)
 Avoidance  These are the "personal space" factor of how much a creature must keep its distance for creatures of the same species ( left is indifferent, right is extreme)
 Interaction  These control how a creature "feels" about creatures of a different species (left is flee/prey, right is fight/predator)
Brief Overview
Each creature takes into account three factors, coherence, avoidance and interaction. Coherence is the factor of wanting to group with other creatures like itself. Avoidance is the factor that each creature needs its own personal space relative to creatures of the same species. Interaction is the factor that a creature may either flee from creatures of a different species, run to creatures of a different species or a range in between. In this applet each creature takes these factors into account for every other creature in the "world" and averages these factors to find which direction to go in and how far. This is done in every timeslice for every creature. This "individual" thought that each creature gives based on where it currently is, regardless of where it has been, can be shown to be a Markov Chain and will also cause the creatures to exhibit flocking patterns.
How is this a Markov Chain?
Each creature has different probabilities that it will move either toward, away from, to the left or right of another creature. There are three matrices of probabilities that each creature has. Below is show the initial matrices of our Red species in the applet.
Key 
Cohesion 
Avoidance 
Interaction 





You can see that the cohesion factor will always press the creature to go toward like creatures with 50/50 chance of veering left or right of that creature. It is important to understand that this left and right terms are relative to the creature moving and facing directly at the other creature. The avoidance factor will always press the creature to go away from the like creatures with a 50/50 chance of side motion. The red is the "antagonist" or hunter/predator in the scenario so the interaction factor will always press the creature to go toward creatures of different species with a 50/50 chance of side motion again.
Now to actually calculate where this creature will go next we use the cohesion probability and avoidance probability with a random number generator in the following algorithm
coh_factor = get_direction(coh_prob); // toward = 1, away = 1
avd_factor = get_direction(avd_prob); // toward = 1, away = 1
dir = speed*(coh_factor*distance + avd_factor/distance^2);
This will return dir which will be postive if the creature is to go toward the other creature and negative if the creature is to head away from the other creature. The size of dir will dictate how much to move in that direction. The same idea will be used if the creature is of another species but this "vector" would be based on interaction multiplied by distance.
All of these "vectors" are found compared to all other creatures in the world and they are averaged together to find a final "vector" for which the creature will move.