Plan for Luc Jordan
by Luc Jordan · 05/02/2001 (9:13 pm) · 5 comments
I just got done creating a 'flock' program in D3D similar to the one in the D3D SDK -- with the little flock of wedges flitting around, changing direction randomly but sticking together.
I couldn't help but wonder if this could apply to large groups of AIs.
I'm not talking about advanced AI, either -- I'm talknig some really, really stupid mofos. For things like crowds of nonviolent AIs. I was thinking up game ideas, and when considering a massive city environment, like Trantor (which Coruscant rips off in Star Wars). It would be really cool to see a huge-ass city in a game, with buildings making up all of the terrain. But aside from the other problems (like poly counts), I kept coming back to -- what about AIs? In pretty much all FPS games, stuff happens after people go to sleep, at night, etc -- and I don't think ANY multiplayer games are set in a living, breathing city, with AIs all over.
Now, the polycounts aren't that big of a problem -- I mean, you can make them low-poly to begin with (like the Thief AIs, lol, or the Tribes 1 models), and reduce them the further away you get, eventually using sprites.
But the problem is the strain on the CPU -- to say nothing of having the information for 200 AIs being sent to your computer 10 times per second for multiplayer.
So, what if the AIs used a kind of flock behavior? I'm not sure how many games implement this in multiplayer -- but since it's more of a dynamically generated effect, I'm sure you wouldn't have to send information about the state of each individual 'bird' in the flock.
I'm just kind of babbling right now; I'm pretty tired. But, I mean, people in groups don't have advanced AI anyway. :) Any crowd of people larger than 5 is stupider than the sum of its parts. I think that if you get a crowd larger than 1000, the group IQ is actually negative . . .
Anyway, this is all babbling, and at some point I'm sure I will regret having written it. For now -- good night all. I'm going to strike the frameless cloth container now.
vgb
I couldn't help but wonder if this could apply to large groups of AIs.
I'm not talking about advanced AI, either -- I'm talknig some really, really stupid mofos. For things like crowds of nonviolent AIs. I was thinking up game ideas, and when considering a massive city environment, like Trantor (which Coruscant rips off in Star Wars). It would be really cool to see a huge-ass city in a game, with buildings making up all of the terrain. But aside from the other problems (like poly counts), I kept coming back to -- what about AIs? In pretty much all FPS games, stuff happens after people go to sleep, at night, etc -- and I don't think ANY multiplayer games are set in a living, breathing city, with AIs all over.
Now, the polycounts aren't that big of a problem -- I mean, you can make them low-poly to begin with (like the Thief AIs, lol, or the Tribes 1 models), and reduce them the further away you get, eventually using sprites.
But the problem is the strain on the CPU -- to say nothing of having the information for 200 AIs being sent to your computer 10 times per second for multiplayer.
So, what if the AIs used a kind of flock behavior? I'm not sure how many games implement this in multiplayer -- but since it's more of a dynamically generated effect, I'm sure you wouldn't have to send information about the state of each individual 'bird' in the flock.
I'm just kind of babbling right now; I'm pretty tired. But, I mean, people in groups don't have advanced AI anyway. :) Any crowd of people larger than 5 is stupider than the sum of its parts. I think that if you get a crowd larger than 1000, the group IQ is actually negative . . .
Anyway, this is all babbling, and at some point I'm sure I will regret having written it. For now -- good night all. I'm going to strike the frameless cloth container now.
vgb
About the author
#2
While flocking is useful for simulating phenomenae like schools of fish or "flocks" of birds, it really doesn't apply quite the same to groups of humans (with a few exceptions). It's not really accurate as a means of modeling the behavior of individual humans in a city.
Human beings don't usually follow a particular crowd when going about their daily activities. They head towards their respective destinations, whether that be work or home or to a store. It just so happens that their are large numbers of humans and only a few cardinal directions, so we see a sort of emergent group behavior as a crowd heads in a particular direction. But this is not flocking.
In flocking, each boid tries to stay near the other boids in its group. This often results in what appears to be directed behavior, but in actuality it is just the reverse of what humans typically do. Humans don't care which group of people they happen to be walking with when heading to the grocery store. They won't continue to follow their group if it suddenly passes the grocery store and heads to the bank instead (well, most humans I know at least).
At most, you could use flocking as a short term solution to model humans as they group together along the intermediate steps along the route to their destination. But you could accomplish the same thing with individually directed behavior and simple avoidance algorithms.
Flocking CAN be very useful while modeling organized human formations, like military squads, mobs, and parades/marches, but this of course is not how things typically are in a city. One can certainly argue that a mob has a mentality and purpose of its own and thus simulate it with flocking, but if you look at a crowd of people caught in traffic or just heading to their jobs, they each have their own objectives and the flocking model quickly breaks down.
05/03/2001 (12:18 am)
There's actually a pretty good article in Game Programming Gems on flocking. However, I think its utility is more limited than you think.While flocking is useful for simulating phenomenae like schools of fish or "flocks" of birds, it really doesn't apply quite the same to groups of humans (with a few exceptions). It's not really accurate as a means of modeling the behavior of individual humans in a city.
Human beings don't usually follow a particular crowd when going about their daily activities. They head towards their respective destinations, whether that be work or home or to a store. It just so happens that their are large numbers of humans and only a few cardinal directions, so we see a sort of emergent group behavior as a crowd heads in a particular direction. But this is not flocking.
In flocking, each boid tries to stay near the other boids in its group. This often results in what appears to be directed behavior, but in actuality it is just the reverse of what humans typically do. Humans don't care which group of people they happen to be walking with when heading to the grocery store. They won't continue to follow their group if it suddenly passes the grocery store and heads to the bank instead (well, most humans I know at least).
At most, you could use flocking as a short term solution to model humans as they group together along the intermediate steps along the route to their destination. But you could accomplish the same thing with individually directed behavior and simple avoidance algorithms.
Flocking CAN be very useful while modeling organized human formations, like military squads, mobs, and parades/marches, but this of course is not how things typically are in a city. One can certainly argue that a mob has a mentality and purpose of its own and thus simulate it with flocking, but if you look at a crowd of people caught in traffic or just heading to their jobs, they each have their own objectives and the flocking model quickly breaks down.
#3
05/03/2001 (9:35 am)
Flocking is more than just objects trying to stay close together. That is -one- of the characteristics of traditional flocking, yes. But you can remove that element without losing the concept of flocking; that is a summation of weighted vectors to determine an objects motion. Usually the three vectors are coherence, avoidance, and going-in-the-same-direction (forget the name now). For a flock, or instead mob, of people, you could replace the same-direction vector with a destination vector, indicating where that person is going. Keep coherence and avoidance, and you should end up with mob-like behaviour. People heading in the same general direction would tend to group up and move together. It would probably need some tuning, of course, like you might need to add queueing behaviour. But basically, I think the concepts of flocking might be applicable here.
#4
But I think we're basically talking about the same thing here. I said,
"But you could accomplish the same thing with individually directed behavior and simple avoidance algorithms."
which is basically the sum of two vectors. I just wouldn't call it flocking anymore, since it really doesn't look or behave like a "flock" once you lose the cohesion. The essence of flocking seems to me to be the simulation of directed group behavior. Calling flocking the summation of vectors to determine an object's motion means that kinematics is flocking. ;)
One can argue semantics here all day, but that's not the real issue. My main point was that human beings don't typically act like they're in a flock when roaming throughout the city - there is no group mind to speak of. For short time intervals, it appears that people are all thinking the same thing, such as when a group of people board a subway. But if you wait a short time period, you'll see that people get off at their own stops and head to their own destinations. You don't really need the artificial (for humans at least) flocking concept to get this behavior, just give them avoidance and give them a purpose, and if there's enough human beings you will see this type of behavior emerge.
Once again, this does not necessarily apply to mobs or other formations where humans attempt to stay together.
Actually, I think you can create some simple rules-of-thumb as to when flocking is useful for simulating humans.
1) When groups of people are attempting to stay together for some purpose
Parades, military squads in combat, organized marches / protests, tours, etc.
Parades are usually a bit too organized for this purpose, but these examples usually occur when people try to stay together for some sort of organized ritual, or because they are seeking safety or strength in numbers.
2) When a group of pepole has a singular purpose
Mobs are about the only type of human group behavioral construct that seem to fit this one.
3) When a group of people have similar short-term AND medium-long term interests.
Refugees fleeing a war zone, trading caravans, expeditions.
This usually overlaps a bit with (1), and where it doesn't it's not quite accurate in the long-term, but if that's far enough away in the future you can get away with it. Refugees usually have different long term purposes in mind, but their immediate and medium term desires are the same as everyone else - get the hell away from the war. Now, if a player could actually watch refugees arrive at their eventual destination, this model would fall apart, which is why I stressed medium-term goals. It's only when individual interests are beyond the scope of the game that you can use flocking in this circumstance. In a busy city with tons of people, you'd quickly notice that the same group of people left the same city street, headed to the same subway station, got off at the same stop, headed to the same building, etc. Even if you did implement a queueing system, you couldn't make it fine-grained enough. There's no particular reason here why a single group of people should walk at the same rate or arrive at the subway station at the same time. Individuals don't usually consciously try and stay with the same group of people, unless it's their family or friends, and I'd be very impressed at a simulator that can also keep track of that at a large scale.
Flocking is fantastic at simulating animal behavior, like swarms of bees and schools of fish. But even fish have reasons to travel in a group - they are safer from their enemies (it's more difficult for a predator to single out a single one for attack), they allow the fish to find food more easily, and they often allow fish to protect territory they have claimed as their own.
I would just be wary about attempting to impose flocking on humans. Its applications are mainly limited to those I enumerated above (plus a few others I'm sure I missed). It is not the all-singing, all-dancing, end-all, be-all of human group behavioral algorithms. :)
You should understand its limitations as well as its benefits. When your only tool is a hammer, every problem seems like a nail.
05/03/2001 (11:56 am)
I'm not sure if coherence applies here either, at least for individuals. Nothing from my experience indicates the people TRY to stay in a group when heading to their destinations, it just happens. It's emergent behavior, in other words.But I think we're basically talking about the same thing here. I said,
"But you could accomplish the same thing with individually directed behavior and simple avoidance algorithms."
which is basically the sum of two vectors. I just wouldn't call it flocking anymore, since it really doesn't look or behave like a "flock" once you lose the cohesion. The essence of flocking seems to me to be the simulation of directed group behavior. Calling flocking the summation of vectors to determine an object's motion means that kinematics is flocking. ;)
One can argue semantics here all day, but that's not the real issue. My main point was that human beings don't typically act like they're in a flock when roaming throughout the city - there is no group mind to speak of. For short time intervals, it appears that people are all thinking the same thing, such as when a group of people board a subway. But if you wait a short time period, you'll see that people get off at their own stops and head to their own destinations. You don't really need the artificial (for humans at least) flocking concept to get this behavior, just give them avoidance and give them a purpose, and if there's enough human beings you will see this type of behavior emerge.
Once again, this does not necessarily apply to mobs or other formations where humans attempt to stay together.
Actually, I think you can create some simple rules-of-thumb as to when flocking is useful for simulating humans.
1) When groups of people are attempting to stay together for some purpose
Parades, military squads in combat, organized marches / protests, tours, etc.
Parades are usually a bit too organized for this purpose, but these examples usually occur when people try to stay together for some sort of organized ritual, or because they are seeking safety or strength in numbers.
2) When a group of pepole has a singular purpose
Mobs are about the only type of human group behavioral construct that seem to fit this one.
3) When a group of people have similar short-term AND medium-long term interests.
Refugees fleeing a war zone, trading caravans, expeditions.
This usually overlaps a bit with (1), and where it doesn't it's not quite accurate in the long-term, but if that's far enough away in the future you can get away with it. Refugees usually have different long term purposes in mind, but their immediate and medium term desires are the same as everyone else - get the hell away from the war. Now, if a player could actually watch refugees arrive at their eventual destination, this model would fall apart, which is why I stressed medium-term goals. It's only when individual interests are beyond the scope of the game that you can use flocking in this circumstance. In a busy city with tons of people, you'd quickly notice that the same group of people left the same city street, headed to the same subway station, got off at the same stop, headed to the same building, etc. Even if you did implement a queueing system, you couldn't make it fine-grained enough. There's no particular reason here why a single group of people should walk at the same rate or arrive at the subway station at the same time. Individuals don't usually consciously try and stay with the same group of people, unless it's their family or friends, and I'd be very impressed at a simulator that can also keep track of that at a large scale.
Flocking is fantastic at simulating animal behavior, like swarms of bees and schools of fish. But even fish have reasons to travel in a group - they are safer from their enemies (it's more difficult for a predator to single out a single one for attack), they allow the fish to find food more easily, and they often allow fish to protect territory they have claimed as their own.
I would just be wary about attempting to impose flocking on humans. Its applications are mainly limited to those I enumerated above (plus a few others I'm sure I missed). It is not the all-singing, all-dancing, end-all, be-all of human group behavioral algorithms. :)
You should understand its limitations as well as its benefits. When your only tool is a hammer, every problem seems like a nail.
#5
Actually, I already realized that flocks wouldn't work well for dealing with normal city behavior -- but for that, we don't need actual AI. The AIs just go their predefined routes to and from certain places on the map -- no actual 'thinking' involved as long as they aren't disturbed.
But I was thinking of flocking for dealing with AI reactions to the player -- for instance, having a 'crowd' scatter realistically (and economically, processor-wise) if the player drops into their midst weilding the flaming sword of Barad-Ur, for instance -- I've seen flocking demos for things like a group of fish that scatter when a stone is dropped in their midst, and then flee in small, random separate groups.
Or even for enemy AIs -- if you bust in on a group of 30 or 200 enemy units, the odds are that you won't notice many of the inconsistencies present using the flocking solution, although being pretty much a peasant in such matters (hehe 17 years old :P) I really wouldn't know if this solution would work well for actual combat.
Re the 'AI LOD' -- yeah, I thought of that myself while taking long walks, but I probably won't have the expertise to implement any of my ideas for about 5-10 years. Very depressing, actually.
05/05/2001 (10:20 pm)
Hehe. See, you guys actually understand this stuff. I was just throwing out ideas.Actually, I already realized that flocks wouldn't work well for dealing with normal city behavior -- but for that, we don't need actual AI. The AIs just go their predefined routes to and from certain places on the map -- no actual 'thinking' involved as long as they aren't disturbed.
But I was thinking of flocking for dealing with AI reactions to the player -- for instance, having a 'crowd' scatter realistically (and economically, processor-wise) if the player drops into their midst weilding the flaming sword of Barad-Ur, for instance -- I've seen flocking demos for things like a group of fish that scatter when a stone is dropped in their midst, and then flee in small, random separate groups.
Or even for enemy AIs -- if you bust in on a group of 30 or 200 enemy units, the odds are that you won't notice many of the inconsistencies present using the flocking solution, although being pretty much a peasant in such matters (hehe 17 years old :P) I really wouldn't know if this solution would work well for actual combat.
Re the 'AI LOD' -- yeah, I thought of that myself while taking long walks, but I probably won't have the expertise to implement any of my ideas for about 5-10 years. Very depressing, actually.
Torque Owner SR
It was also a big topic of conversation at the GDC this year, so I've heard. They referred to it as AI LOD. It's like polygonal LOD, but instead of drawing distant objects using less polygons, you use less processor time for distant, or less relevant, AIs. Flocking could be an interesting application of this. It's too true that groups tend to be stupider the more ppl you add. Why not take advantage of that? Just like televangelists do...
If you ran the simulation on each client, you wouldn't even have to send state information. Just make sure the simulations are the same (use syncronized seeds for pseudo-random and such). Then make the player try to wade his way through them...it's like a long weekend at the mall.