Friday, July 4, 2008

Project 'Loco', a low level animation AI 'project'


I don't know where it will go ... but I realized it is better to write down the stuff I think about while sitting bored in the train (or other places) than to simply think, forget a part, think again ... and eventually forget the whole thing because of lack of time. So it even might never reach the level of a demo or even source code ... but still ... as I decided, better document it.

Also of note is that I unfortunately do not need this in any of the game development projects I am currently involved in, and I never worked on anything similar before, so why am I doing this? because I wish I was involved in anything of this kind ...

'Loco' is our human like character and the first goal I thought, would be to make him be able to move (or locomote) in a 3D environment, credibly moving through obstacles: climbing stairs, climbing smaller obstacles (crates), jumping, crawling under obstacles, and so on.
The only input coming from the user would in this case be the movement direction (or a target point) and possibly speed.

Here are my first thoughts on this (boring 1.5h. train ride)
as a note, I will present here just the summary (not full details) of a chain of thought, and even though I am sure all of this is probably covered in the 1st chapter of many robotics books (but maybe I'm wrong), or that many people will just laugh when reading it, I still am documenting it here, for myself if for no one else, and absolutely prepared for the very probable fact that it will sink down into blog oblivion the minute I click the 'publish post' button.

Why do we stand on 2 feet?

Because based on our skeletal structure (feeding back into locomotion, feeding back into structure in a loop called evolution), a good, stable and fast way for us to move is to walk on 2 feet.
When we cannot walk, we can crawl as an alternative.

Irrespective of what state we choose (walk, crawl, stand, ...) we need a way to maintain that state, stay balanced, if per example, there is a small bump is in our way.

Basic Loco thoughts

so Loco basically would have a repertoire of locomotion states we will call moves:
stand, walk, jump, crawl, sit, lean, ...

Higher level AI of Loco would plan what combination of states to choose to achieve its locomotive goals.

but what exactly is a move? how does a 'stand' differ from a walk? the definition of a move is therefore important! because it will give us the constraints we need to maintain in order to maintain the move.
We have to watch out that states can be dynamic, so this might get complicated.

Plan Of Attack
  1. figure out how to define moves (constraints on skeletal points)
  2. can loco mathematically figure out how to achieve a move and keep it balanced?
  3. test moves
  4. level AI uses moves to achieve high level goals
  5. add a mesh for loco, this would be achieved with the mesh animation trying to 'follow' the skeleton using probably some form of parametric animation blending.

How to define a move

The first version of Loco will be a 'simple' skeleton in 3D, that is points with weights connected with joints, so a 3D stickman (think robotics...).

now let's try to think about what defines a 'stand' move:
a simple definition that comes to my mind is: 2 feet on their constrained targets and head at the highest position achievable by the skeleton (on the gravity axis). this should also be stable.
Stable probably always means that the center of gravity's projection should be inside the 'area' created by our feet.

how will loco achieve a move

On first thought, solving this mathematically could be real slow, but let's ignore that and think about it a bit.
to solve we would
  1. constrain the requested move constraints (feet, head)
  2. figure out what to do with all other points while staying balanced
now if we solve this this would be a big step.

next we would try to move loco's feet and see him readjust, this would definitely not look human, but much more robotic, since this is how they probably do it in robotics (think Inverse kinematics).

but that's no problem for now, we might try to humanize this later by:
  1. using precomputed solution
  2. or precomputed parts of solutions
  3. adding more constraints, so solver must be able to handles those as well, probably making the whole thing even slower (CUDA?)
so how would we go about solving the targets for all our skeleton points to achieve a move?
  • the first way of doing this would be of course, some kind of a tree search.
  • the second would be of course solving analytically, this is definitely not a new topic... inverse kinematics, rag dolls, ...
we could also use the computed solution to warm start when we need to rebalance (loco's foot was moved by us to disbalance him)
  • the third is to predefine the solution for loco.

Doubts already...

there is also one big issue, we need to handle dynamics, when we run per example, we are not balanced the whole time (try running in slow motion, or even walking, there is a moment where u are in disbalance just before you put your next foot on the floor), we use inertia and dynamics to stay balanced, which makes the solution even more complex with an explosion of valid solutions, which is also the case for static moves.

but, this is normal!! we humans can do a huge amount of moves!
this means that 'solving' for the move is actually a stupid thing to do... and not only from the point of view that it would definitely be very slow, I can't really estimate it at all for now, but more importantly because of the fact that there are MANY ways to achieve a move.

but let's think some more...

Imagine you suddenly forgot all your locomotion instincts and had to sit down and plan how to move every muscle in order to walk... a daunting task!!

Reducing a million years

at this point I realize it is all too easy to forget the amount of evolution-hours (like man-hours in a project) that have gone into the development of our moves...
it is easy to forget because we take it for granted, but it really is a humongous million year effort, it is like being in some post-apocalyptic world, back to very basic technology and wanting to develop a game! you would have to invent electricity, electronics, and all what's needed for that, materials, processing, ... even though we use those everyday, we really couldn't be able to achieve it at all ... a humongous million year effort.

so going back to Loco, is it really ok to expect to be able to solve this with some trivial mathematical algorithm? (trivial compared to the work done by evolution), I now start to doubt this and think it is also a stupid way to approach the problem.

a better approach now i think is is to give Loco our instincts, a set of moves (dynamic as well), and give him a simpler task, try to keep them balanced when faced with deviations from the ideal case, a small bump on the floor, road going down instead of being straight, getting a small push ... that is probably more manageable. which is what Natural Motion probably does, and it is then clear why they had to use a neural network, controlling those muscles with math is probably an impossible task, I am trying to think about how many neurons do we use for locomotion, and if current computers even have the necessary computational power to do this at least in real time...

ok, the train ride is over, continue next time.


are you already laughing at my naivety? (yes I keep repeating this, but I guess this is a normal feeling of fear that naturally emerges and haunts one's psychology when making one's ideas naked and public for the first time) I expect yes and secretly hope no, and that eventually this 'will have been' a useful mind exercise looking back some months in the future at hopefully a series of posts building on this one.

1 comment:

Anonymous said...

FWIW I quite enjoyed reading this.