I need automatic grouping with my flocking algorithm.
April 5, 2015 2:13 PM Subscribe
I'm very familiar with boids and flocking; I implement the algorithm for Space Whales in my game, Artemis Spaceship Bridge Simulator. But I'm frustrated by my arbitrary code for sorting boids/whales into groups. Right now, I simply generate 10 whales assigned to group 1, and 10 whales assigned to group 2, and the whales move together in their groups.
I'd rather...
build code that lets the whales spontaneously form groups, and even merge groups if they get close enough, or if the groups lose enough members.
To an extent, the classic boids algo does this, by giving each boid a visibility range, and letting some boids fly alone if they get too far from the group. I don't want this behavior; my whales are social.
So I'm looking for help finding a flocking algo that makes spontaneous and natural groupings of boids. Any ideas?
build code that lets the whales spontaneously form groups, and even merge groups if they get close enough, or if the groups lose enough members.
To an extent, the classic boids algo does this, by giving each boid a visibility range, and letting some boids fly alone if they get too far from the group. I don't want this behavior; my whales are social.
So I'm looking for help finding a flocking algo that makes spontaneous and natural groupings of boids. Any ideas?
Might clustering algorithms be what you're after?
Do you want to disallow any possibility for any group to split into two? Or just avoid small groups or solitary whales?
posted by solitary dancer at 3:36 PM on April 5, 2015
Do you want to disallow any possibility for any group to split into two? Or just avoid small groups or solitary whales?
posted by solitary dancer at 3:36 PM on April 5, 2015
Best answer: idea: have a second, invisible map. every boid has a position on that map, and they slowly move around the map (in fixed lines, occasionally peturbed, perhaps?). run k-means occasionally on that to extract several clusters. those are your groups. you could consider the invisible map emotional or relationship territory.
this idea comes from spectral clustering, in which each object has a fairly large number of parameters. to reduce the dimensionality, you would take the eigenvectors or svm of the large number of dimensions to reduce to a lower number of dimensions, and then run k-means.
posted by joshu at 4:05 PM on April 5, 2015 [1 favorite]
this idea comes from spectral clustering, in which each object has a fairly large number of parameters. to reduce the dimensionality, you would take the eigenvectors or svm of the large number of dimensions to reduce to a lower number of dimensions, and then run k-means.
posted by joshu at 4:05 PM on April 5, 2015 [1 favorite]
I haven't tried this, but my first idea is to allow each whale to be either a "leader" or a "follower." The leaders don't follow the boids algorithm; instead they move in some random way that doesn't follow the group. Or maybe they do follow the algorithm but with very different parameters such that they don't tend to cluster as closely.
You could have a fixed number of leaders, or let individual whales randomly change from follower to leader and back. If you have two or three leaders at once, then each one may or may not attract some number of followers, and the followers might switch from one leader to another when they pass close together.
posted by mbrubeck at 4:14 PM on April 5, 2015
You could have a fixed number of leaders, or let individual whales randomly change from follower to leader and back. If you have two or three leaders at once, then each one may or may not attract some number of followers, and the followers might switch from one leader to another when they pass close together.
posted by mbrubeck at 4:14 PM on April 5, 2015
I've seen that type of behavior when a predator is added to the fancy version Reynolds' algorithm (the one with goals). A shark (or your flavor of local danger) will cause the flock to split into groups. If it (the shark) then swims away the fish's regular goals take back over and the group re-anneals. One reason a predator might swim away is that the fishies are the shark's goals if they are in sight but they're darn fast. If they scatter and get far enough away he'll lose contact with them.
Needless to say the predator can be invisible.
posted by cleroy at 4:26 PM on April 5, 2015
Needless to say the predator can be invisible.
posted by cleroy at 4:26 PM on April 5, 2015
I do something similar to what mbrubeck suggested, having a leader, and followers, for the fleets of ships in my game Space Nerds In Space, though they don't use the boids algorithm. You could have followers decide to switch leaders randomly, with the likelyhood of switching being greater when the number of whales in the pod grew larger. But, I gather you'd prefer emergent behavior, rather than programmed behavior.
Maybe something like... each whale scores every other whale on how well they "like" that whale, with say, -1.0 meaning they "hate" that whale and "1" meaning they love that whale and 0 meaning they're indifferent, and maybe whales have a different, uh, "strength" value, ranging from 0 to 1. Maybe if a whale has strength greater then, say, 0.85, then it doesn't follow any other whales, but just does it's own thing, otherwise, a whale will follow the whale that has the largest product of (like-value * strength-value). Maybe each whale's table of "whales I like/hate" varies stochastically over time, and each whales "strength" value varies over it's lifetime, which would cause whales to sometimes turn into leaders, and sometimes to switch which whale they were following, but this behavior wouldn't be so explicitly programmed in.
Probably a O(n^2) algorithm, but so long as n < ~200, probably not a big deal.
posted by smcameron at 4:52 PM on April 5, 2015 [1 favorite]
Maybe something like... each whale scores every other whale on how well they "like" that whale, with say, -1.0 meaning they "hate" that whale and "1" meaning they love that whale and 0 meaning they're indifferent, and maybe whales have a different, uh, "strength" value, ranging from 0 to 1. Maybe if a whale has strength greater then, say, 0.85, then it doesn't follow any other whales, but just does it's own thing, otherwise, a whale will follow the whale that has the largest product of (like-value * strength-value). Maybe each whale's table of "whales I like/hate" varies stochastically over time, and each whales "strength" value varies over it's lifetime, which would cause whales to sometimes turn into leaders, and sometimes to switch which whale they were following, but this behavior wouldn't be so explicitly programmed in.
Probably a O(n^2) algorithm, but so long as n < ~200, probably not a big deal.
posted by smcameron at 4:52 PM on April 5, 2015 [1 favorite]
So, some rough guesses (no idea if these would work or if you've thought of them already):
Individual approach: have a preferred pod size N. Each whale flocks with the closest N neighbors it can see, and avoids any others.
Family approach:
generate pods as you've been doing (with N whales per group), setting each whale in the group with the same randomly-generated pod_id; also define a global max_pod_size and min_pod_size (min_pod_size < max_pod_size/2).
When any two whales of different pod_ids see each other, if either family is below min_pod_size, change the family_id of all the whales in the smaller family to match the larger family. (Otherwise, respect the other pod's personal space.)
If a family is above max_pod_size, pick an arbitrary vector and bisect the pod perpendicular to it, setting the pod_id of one of the halves to a new value.
Expected result: Uncomfortably small/lonely groups will merge with larger ones they encounter; groups that become too large will split and diverge. For extra aesthetic appeal when a merge is immediately followed by a split, aim your split vector at the center of mass of the old pod, so it gives the effect of the larger pod donating some of its members to the lonely small one.
posted by NMcCoy at 6:25 PM on April 5, 2015
Individual approach: have a preferred pod size N. Each whale flocks with the closest N neighbors it can see, and avoids any others.
Family approach:
Expected result: Uncomfortably small/lonely groups will merge with larger ones they encounter; groups that become too large will split and diverge. For extra aesthetic appeal when a merge is immediately followed by a split, aim your split vector at the center of mass of the old pod, so it gives the effect of the larger pod donating some of its members to the lonely small one.
posted by NMcCoy at 6:25 PM on April 5, 2015
(changed some variable names in the process of making my post and missed one, read "family_id" as "pod_id")
posted by NMcCoy at 7:54 PM on April 5, 2015
posted by NMcCoy at 7:54 PM on April 5, 2015
You might set a semi-random timer at which point a % of a flock casts out for new company. (mating, foraging, etc). In that case the existing flock members would repel and more distant whales would attract.
posted by nickggully at 8:53 PM on April 5, 2015
posted by nickggully at 8:53 PM on April 5, 2015
Can you change the cohesion part of the algorithm? You can define your whales to be part of a group (as you did). They have very high cohesion values for their own group, and intermediate cohesion values for members of other groups. You may have to play around with the parameters, but this would allow the flocks to separate and rejoin naturally, and eliminate stray whales.
posted by turtle time at 1:45 AM on April 7, 2015
posted by turtle time at 1:45 AM on April 7, 2015
Response by poster: Thank you, everyone, for your help. After being prompted, I researched k-means. That made sense to me, since I was already imagining such a system, and I've decided to implement something like k-means with a weighting scheme to solve my problem.
posted by Techbear at 9:10 AM on April 7, 2015
posted by Techbear at 9:10 AM on April 7, 2015
« Older Stolen debit card used at ATM... how? | Where to forage (ramps, morels, etc) in Northwest... Newer »
This thread is closed to new comments.
That said, maybe leave in the odd solo Space Whale or two? It'd be unique and melancholy to randomly happen upon some loner, away from his pod.
posted by JauntyFedora at 3:17 PM on April 5, 2015