While I was refining the code for directional awareness, I removed the scriptlinks to the FollowTerrain script for simplicity’s sake. Upon putting them back in, things slowed to a crawl. FollowTerrain slows things down, much more than I realized, with only a moderately complex Ground mesh, by a factor of 20 or so. If you want a better Ground mesh, which would be essential for good final renders and smooth hilltops, etc., you’re going to have to bump up subsurf or subdivide the thing. FollowTerrain slows proportionally to the number of faces in the mesh.
FollowTerrain checked every face in sequence to see if the object was above it, then calculated the proper elevation when it found it. The main script of this whole thing calls FollowTerrain twice per Actor per calculated frame. A Ground Mesh with 3000 verts (not that many) with 800 actors had things running at about 1 actor every quarter second. Way tooooooo sloooooow for me.
Today I learned about quadtree and octree searches. So now, the script builds a quadtree of the ground mesh upon initialization and stores it in (you guessed it) a mySQL table. This lets you do lightening fast queries based upon your quadrant criteria. That same 3000 vert mesh now only has to four rounds of very simple math, followed by a simple query and the examination of 8 or 9 faces. Much much faster than searching all 3000 faces. I’m getting deformed trees as of now, but it’s moving significantly faster. I’ll probably spend the rest of the week working on this code, as it’s new to me, and recursive stuff has always made me feel a little wobbly.
Let me throw something at you… I had this long discussion one night with a guy that worked with Nano cells… anyways… he had an idea about creating huge numbers of nano cells to move on a forward path… he was stuck on how to “control” hundreds of thousands of these guys at once…
Here is where I came in… I had the idea to create a “controller” for a group of say 25-50 cells. The 25-50 “slave” cells would follow the order of the one controller… so now all he had to do was tell (1) controller what to do and 25-50 cells would follow… This way he could send out 4 commands and he would have 100 - 200 different movements (in your case animations)…
Does this make any sense? I’m wondering if you can setup the script to “communicate” to “controllers” that have 25+ “slaves”. This way the FollowTerrain wouldn’t look at “every” object, but just the “controllers”…
Heh. This is already done, but it doesn’t quite function the way you’re thinking.
Each Actor has a Command and Control level. Upon initialization, each Actor is chained to the nearest unit that is one level above it in the command structure (you can assign units manually as well, for finer control). Each Actor receives its orders from it’s immediate commander in the chain. You can have multiple levels in the structure. Thus, you can issue an instruction to the entire army by giving the order to the single top-level commander (or commanders). You can also give orders to any Actor anywhere in the chain, which will propogate down the chain.
The problem with FollowTerrain is the it is not responsible (much) for the intelligent motions of the Actors. Its job is to keep all Actors planted on the Ground mesh object, so no one flies or sinks. You give it your Actor’s x and y coordinates, and it returns the proper z value to place it on the Ground. Therefore, it needs to be evaluated for Actor individually, as they are each at a different location with respect to the Ground mesh, and at each frame, so you don’t get people cruising through hilltops or gliding over valleys due to IPO Curve smoothing.
Thanks for the input, though - I’m glad other people are interest in this besides myself.
This is my own thing. I’d been thinking about it for almost a year before the ARLS project started. The system I’m working on now still conforms pretty well to that original algorithm I came up with. I did kind of hijack mr_rob’s thread, though, and I’ve felt a little guilty about that for a couple of weeks now. Apologies, mr_rob! In addition to hating the bugs on blender.org, that’s one of the other reasons I moved my thread to elYsiun.
On another note - I got quad tree searching working for the FollowTerrain section. My at-work tests show that it’s 17x faster than the raw searching method (74 Actors, 5000 vert terrain. Raw: 38.7 secs.; Quadtree: 2.2 secs.). And that’s hitting the database over a network on PIIIs. I’m guessing that on my home machine where it all runs on the same box (AMD XP1800) that the terrain searching will now be next to negligible. I’ll try my 800 actor sim again tonight and see how it goes.
400 Actors. 4000 face ground mesh. 1 calculated turn every 12 frames. Each calculation turn: 12 seconds. That time descends as Actors die and no longer evaluate. Final frame calc times were down to 6 seconds a piece. Rendering (not like it’s anything great) with blue hemilight and orange sunlight with ray shadows (which I freaking love).
I know this doesn’t look much different to you guys, but it represents a massive (ha!) speed increase. Bugs fixed are that actors no longer get stuck for no reason (maximum turn radius for some Actors was less than 0) and actors don’t start randoming spinning nearly as often. They still do, but not as much as they were.
One thing left to do before I stick in the GUI (and I’ve had much help, so thanks to inciner8 and locash for the superfast help - you guys just saved me a weeks worth of work, at least). That one thing is that right now, when actors are trying to head up too much of a slope, they slow to a stop. I need to update things so that they alter their trajectory to run more parallel to the sloping area. Should be pretty simple.
Once I have the GUI put in, I’ll make a package with my IPOCurve Blender build, a test .blend, and instructions for mysql and the mySQLdb Python hooks, so you all can play with it.
Dumb question, are the cones that don’t move dead? I remember in your first video they would disappear, now do they just stand still? Oh and by the way what you are doing is incredible!
Right. As I’ve said before, the second pass of the the script suite builds the character animation, including being dead. I haven’t decided yet if it would be better to then add a barrier object at the death location so no one can move through the body, or to design a special case that allows actors to physically step over dead actors. Probably I’ll start with the former and add the latter in as an enhancement.
I think that is an awesome name. The usage of this script will probably not be limited to battle only. I think also city behaviour can be programmed with this kind of script - thus modelling group behaviour of people in a way.
One thing I’d like to see in battle-simulation is an awareness of the density of actors who are occupying a particular segment of the field. If you looked closely at the battle scenes in LOTR:3 (okay, how many times did you watch 'em? … …) you can see actors running into, and I think even through, their comrades. They’re packed into the battlefield so tightly… It seemed to me that the Massive software was very aware of what enemies were doing, but not as cognizant of what one’s fellow soldiers were doing.
The density of soldiers in an area, and particularly in-front of the actor, would help determine whether a soldier would advance and in which direction; or stand still. I think that this heuristic would help to “make waves” in crowd motion, which you typically see in crowd situations (such as the interstate highways).
Obviously, actors will have to be able to step over the corpses; otherwise the battle will stop because the opponents can’t reach each other. Can the problem of locating the dead-body you need to step over be solved using the same fast search?
You make some excellent points. I wouldn’t be surprised if characters are running through each other in LOTR. There’s so much to look at, and if you just spent 4 days rendering final production and your deadline is Tuesday and you notice some dude pass through another one - you’re probably going to let it go.
That said, my Actors have a preferred distance from and proximity to allied Actors. They also have a physical “no-touch” radius. This is one of the things I’m working on improving right now. One of the things that has made me happy when I look at some of my larger sims is seeing things like waves and moving columns develop where I hadn’t specifically set it up to do so.
As for stepping over dead bodies, I’ve been contemplating ways to do that. First, you simply add a Barrier entry when someone bites it, denying access to that small area of space altogether. That might work if the bodies start stacking up, but I don’t like it. Another solution would be to add the dead character’s mesh to the ground reference mesh. Once it’s part of the terrain, other Actors would be free to move over it as though it were a bump on the ground. Of course, this means regenerating the Ground search tree, which can take a while. I don’t want to be doing that every time someone dies. Maybe a new check could be in order when the script sticks an Actor to the ground - it could check within a small radius of the location of all dead Actors. If the moving Actor is within this radius, the Z-value would be modified slightly to approximate stepping on the body. It would ignore arms and legs - but if everything’s moving fast enough, this might be close enough for most cases. Of course, you could always tweak something by hand if it was in slo-mo, or right in front of the camera.
…) you can see actors running into, and I think even through, their comrades. They’re packed into the battlefield so tightly… It seemed to me that the Massive software was very aware of what enemies were doing, but not as cognizant of what one’s fellow soldiers were doing.