Crowd/ Battle simulation

[nerddogs]

While watching the second LOTRs dvd the other night I was inspired to try my hand at a crowd/combat simulator like Massive. Massive is a program that lets you place two different armies on a battlefield and the program figures out how they will fight each other. They base thier movements on fuzzy logic and mocap files. The mocap files rewrite themselves based on what type of terrain they are fighting on and the personality of each "actor".

I have very little knowlege in Python but that didn't stop me from hacking my way thru a very simple AI type script. The script I wrote involves two different set of objects: orc's right foot and left foot and a human's right foot and left foot. These feet will find each other where ever you place them and step thier way to each other. In other words the orc will find the human and move to his location.

I have a small video of just the orc's feet moving to the human. I used planes to represent the feet for this test right now. The movement of the planes look like a penguin walking right now but fixing that won't be hard. The hardest part for me was to have the feet "take turns" stepping, so this was a test to see if I could get them to do that.

To the more experienced programmers: Am I on the right track? Should I look into the .bvh format and maybe write a script that would change the bvh data like Massive does ( I have some ideas on how to do this). I have a degree in Mathematics and have taught math including Calculus for the last 12 years so the math part I can handle pretty well. I don't know how to write data to a separate file for Blender to read or how to write/read ipos so any tuts on this would be of great help.

Any way please go easy on me, for I am quite a newbie when it comes to python. Movie link (right click save as/ 158 k with divx: 5.0.2): http://www.geocities.com/nerddogs/walktest.avi

[LethalSideP]

Hi Nerddogs!
Neat idea...I got stuck into a crowd simulation script for a bit, until I found out how difficult it was to make one object to track another, anyway...It's bloody hard work, AI not withstanding .

As for your questions...hmm...Yes, the BVH is probably a very good format to go with for the time being. It's open, there are free demos available, and it's a fairly good format (but believe me, you'd better be prepared to put that Maths of your to some good use ). I'm not sure how much you'd want to rewrite the BVHs themselves, though - it'll start to become messy very quickly. Can I suggest another way around this problem? I suggest that instead of tinkering with the BVHs themselves, you try a script that takes a selection of BVHs (eg walk, run, fight, die - on a simple level) and decides for each character what it wants to do at this particular point, and imports the BVH as required, as well as setting object attributes like position and rotation. This would be much easier to implement. Granted, the results won't be quite as spectacular as a script which generates the BVHs for you, but it'll save you the problems of trying to work out what type of character your end user is animating and creating the BVH that that particular setup needs (after all, everyone will be using a different armature system for their characters, so writing a BVH which takes the armature into account will be a nightmare).

As for writing a .blend file yourself...I think the format itself is closed at the moment, so you'll have to wait a few weeks until the sources are opened. but if you don't mind the wait.... I suggest you do something that runs from inside Blender though, and creates the crowd in the current scene. Again, less headaches in the long run.

Hope this helped.
LethalSideParting

__________________
Shades: $30
Shotgun: $100
Trenchcoat: $100
Matrix DVD: $15
The look on the face of that security guard as Neo opens his jacket...: priceless

[ilac]

Originally Posted by LethalSideP As for your questions...hmm...Yes, the BVH is probably a very good format to go with for the time being. It's open, there are free demos available, and it's a fairly good format (but believe me, you'd better be prepared to put that Maths of your to some good use ). I'm not sure how much you'd want to rewrite the BVHs themselves, though - it'll start to become messy very quickly. Can I suggest another way around this problem? I suggest that instead of tinkering with the BVHs themselves, you try a script that takes a selection of BVHs (eg walk, run, fight, die - on a simple level) and decides for each character what it wants to do at this particular point, and imports the BVH as required, as well as setting object attributes like position and rotation. This would be much easier to implement. Granted, the results won't be quite as spectacular as a script which generates the BVHs for you, but it'll save you the problems of trying to work out what type of character your end user is animating and creating the BVH that that particular setup needs (after all, everyone will be using a different armature system for their characters, so writing a BVH which takes the armature into account will be a nightmare).

WHy not get it to access the Actions in Blender? It would be like an 'on-the-fly' automated NLA.I once wanted to try doing that in Gameblender to get characters to automatically interact using a library of actions etc. Unfortunatly lack of time and a few personal problems over the past year meant one of several projects that had to be put on hold You could do things like give a character personality by setting biases for certain actions and then it would react to certain properties set in the other character. mumble mumble etc etc


Good luck Nerddogs!

[pato]

Originally Posted by nerddogs While watching the second LOTRs dvd the other night I was inspired to try my hand at a crowd/combat simulator like Massive.

I had thought about doing something like this at one time. Although not quite as realstic as the method you describe perhaps there is some room in your system for particle systems as soldiers? You could have a bunch of emitters which are all out of synch with one another? Its not as accurate a simulation but I'd bet with some jiggering one could get some satisfying results (esp w/really large crowds).

Just a thought...

-Pato

[nerddogs]

Thanks for all the ideas guys! I have a few walk test I made with my script with real biped models. I'll try posting them later this week. I thought about trying to do this using particles but I want more control over each actor. When I preview the animation with just two models finding each other and walk to meet, Blender really slows down (I have a slow computer anyway 400 mhz). But when I animate the scene it renders quite fast. So I can imagine the lag 100 different actors would create. I'll keep ya'll updated on the progress.

[harkyman]

Here's my two cents. I think you've going about this from the wrong scale. Moving the feet this way and that should all come later. What you need to figure out is the battle dynamics of a crowd. What you need is a sort of cellular automaton system, like this...

Each actor (warrior, whatever) follows this set of rules, reevaluated each frame:

Are you engaged with an opponent (within attack range) 
   yes { Are you currently in the middle of a combat technique?
      yes { continue that technique }
      no { combat logic and begin next technique }
      }
   no { move toward an opponent, using moveweight() }
   }

moveweight { //determine which direction to move
   take into account {
      the nearest unengaged opponent
      the average location of all opponents
      formation restrictions (unit coherence rules)
      personalstrategy()
      }
   return direction
   }

personalstrategy {
   seek out the following conditions {
      high ground
      physcial cover
      proximity to allies
      }
   return strategydirection
   }

Each actor can have different strategic capabilities, different weights and tolerance values to any of these (and more) parameters, giving you the ability to create armies with varying fighting styles, skills and strategies. A few simple rulesets can generate some awesomely complex behavior.

Once you can make two groups of dots swarm across the screen and engage each other in realistic battle formations, then you start putting in the mocap, the hand-to-hand combat simulation, etc. Just the other day I was wondering if WETA could be persuaded to release Massive as open source. Ha! This is a huge project, and I wish you luck.

[nerddogs]

That's a good idea harkyman. Would you go about this as one giant loop for each army and let the loop name them and create them? Then randomly assign each with fighting styles?

Here are a few test of the "orc" walking. He is walking to a "human" off screen. One of the test I had the legs in the wrong position so it looks like he's dragging a lame leg in one animation. I have correct this problem and will make a few more test tonight with both the orc and human meeting each other.


http://www.geocities.com/nerddogs/walktest2.avi

http://www.geocities.com/nerddogs/test3.avi

[ilac]

Originally Posted by nerddogs Here are a few test of the "orc" walking. He is walking to a "human" off screen. One of the test I had the legs in the wrong position so it looks like he's dragging a lame leg in one animation. I have correct this problem and will make a few more test tonight with both the orc and human meeting each other.

Mistake or not that lame leg animation still looks really good!

and so does the other animation! Looking forward to seeing more!

[SirDude]

You would probably want to just do one big huge foreach armyguy
loop.

(You could also split it up into two one for each army and or
even write more loops for each unit type depending on how involved
you want to get)

Also for the creating I'd start with just a random little generate 10
guys on X team.

But later you'll probably want to say generate a group of horsemen
a group of archers etc....

Basically you'll want to nail down your datastructures and go
from there.

Common stats you might consider for each troop:
Health, range(of attack), visual range, directional vector, position, team, typeofunit

You could do all kinds of stuff with this data, and you would probably want to package them into different types of units.
If I'm wounded and there are X more enemys in my visual range than there are of my own troops run...
If there is some guy close by who has his back to me get him.

You could also define types of attacks baised on the unit.
i.e. if I'm type fighter
50% chance head shot
25% torso
10% leg

etc...

[theeth]

I think SirDude's idea is really good, and I think this really calls for an oop structure.

I, for one, is really interested in crowd simulation, behavioral motion and boids, and I think it would be a good idea to maybe gather a team together and establish some code base and such.

I think this would be a great project for the future of Blender as an open source program.

Martin

[harkyman]

What!?? You mean my quoted code above doesn't work on your machine? What version of Python are you running? I hit alt-p in 2.25 and see the freaking LOTR Trailer in my display window.

[gorgan_almi]

Hi Guys! Yeah I was planning to design something like that for an RPG/1stShooter I'm making.

I think ilac, harkyman and SirDude are all on the right track there. you would want to start off with massing dots (cubes/empties) on the screen with one of harkyman's loops for each character in each army. If you were doing it for gameBlender then you you could have the AI loop in a python text block and you would use logic bricks in each character to continuously call that python script using an 'Always' sensor. The python script would decide how the character should move, and would activate an Action on the characters Armature accordingly.

You could make actor properties for each of the characters Health, range(of attack), visual range, team, etc.

I know having 1 loop for every character instead of every army sounds hard but I think it would be the easiest way to do it as it means you only ever have to treat it as a one character situation, you don't have to worry about for loops. Thats my view anyway.

Anyway have fun and good luck!

[harkyman]

Theeth's oop is the way to go. If you're doing this in Blender with Python, you'd want to create all of your actors beforehand (I suppose you could use a separate script to generate your armies if you wish), then object link them to your action script, using frame by frame update.

And really, you wouldn't even have to add the actual hand-to-hand combat mechanics or hit points or anything into the logic. Really all you would need once two opponents were engaged would be a simple, instant method to determine who would win, possibly based on a weighted random value calculated from a single combatStrength parameter that each class of actors (or individuals) has.

Then, once the outcome has been determined, you select a random number of movesToKill (2-8 or so), select generic combat actions from the action list, apply them sequentially, then select a kill move and apply it. Remove the dead actor and replace it with a static object.

You'd have to come up with a general use armature from all actors. Okay, you wouldn't HAVE to, but it would make things sooooo much easier and more reusable. Anyway, come up with some mocap for ten different combat moves, attacker and defender together, and make it applicable to the bone structure. Come up with as many killing moves as well.

This is starting to sound really interesting. Hmmmmm. I may start working on the actual movement rules and algorithms. Hmmmmm.....

[theeth]

class Army:
        def __init__(self):
                *definition code*
                self.Content = []

        def addSoldier(self, soldier):
                self.Content.append(soldier)

        def runSimulation(self):
                for Soldier in self.Content:
                        Soldier.calcMovement()
                for Soldier in self.Content:
                        Soldier.move()


class Character:
        *definition code*

class Archer(Character):
        *definition code*

class Footmen(Character):
        *definition code*

ArmyEvil = Army(*parameters*)
ArmyEvil.addSoldier(Archer(*parameters*))
ArmyEvil.runSimulation()

who said oop was hard?

Martin

[gorgan_almi]

Originally Posted by harkyman What!?? You mean my quoted code above doesn't work on your machine? What version of Python are you running? I hit alt-p in 2.25 and see the freaking LOTR Trailer in my display window.

Did u post that in the wrong thread or somethin? :-?

[harkyman]

Uh no - 'twas a joke.

[harkyman]

Crap - for this all to work, we're going to have to do terrain following/pathfinding. Anyone work on something like that before? Anyone have any code?

[SirDude]

Just an additional comment I thought of.

If I were doing it I would have two functions.
The first would just be for helping place troops and would go
like this:

create_troops(trooptype,count,x,y,z,team)
This function would basically create a block of troops at
the given location.

The additional thing would be that it should be designed so that
you can do this then tweak the troops and get them set the
way you initally want them placed. So maybe each troop object
would be named troop#, that way you can split creation and placement with the actuall figureing out the movement of the
troops.

Then you would probably want to set each movement to
x number of frames.
and then have a global function to update the troops which would
basically be

foreach troop:
if Im dead replace me with a dead object.
else if I'm busy doing a move continue it
else figure out my next move.

[harkyman]

You COULD do that - or you could generate the troops each with an object link to the action script, set to evaluate once per frame. That way, each one takes care of itself and you don't have to worry about naming conventions, global loops, etc.

Anyone know a way to determine the nearest object from an arbitrary object array without calculating the distance to each and every object? This NEEDS to be Object Oriented. Procedural just won't cut it.

The more I think about this script the more difficult (and interesting) it becomes.

[theeth]

if it is only for evaluating the nearest object, you can skip the square root operation from the distance formula. That way, the loop the calculate the nearest object is faster and more optimized.

Other than that, you could use bounding box to optimize this even more.

Martin