Autonomous behavior

[djo]

Hello Everyone,

This is my first Post. This forum is Great and I've been leeching a lot of information from it. So I decided to contribute a little.

I'm currently working on a set of VEX POP nodes to be able to easily create Autonomous behavior in a jiffy. It's been in WIP for quite some time as this is taking me a lot of work and I do have a work and social life.

Anyway I've based these nodes on Craig Reynolds's work on Boids and Autonomous behavior, it's a "sort of" port of his Opensteer library to VEX as I'm not at all familiar with HDK. It's pretty challenging as VEX simultaneously computes each particles, and I've encountered many problems because of this. Anyway I'm just at the begining of creating all the necessary nodes so I'm going from one example to another and write each node as I need them. These nodes are quite greedy as most of the nodes require to loop all the particles, so the more nodes the slower cooking time gets. I chose flexibility. My aim is to add a node after another to easily create a behavior but if it gets to slow, we could rewrite everything to one node once we get a good behavior going and keep everything in just a single loop.

There is still plenty of work to be done but I would like to share with you some examples I've managed to get through.

The first example is mainly based on Unaligned collision avoidance. Each agent(particle) detects its future position, computes every other agents future position and see wether or not a collision is boud to happen with another agent. If so it then steers away from the potential collision position. They also steer away from static obstacles. This example uses 5000 mites which are of course not all visible.

Here's the example I've used with mites :

http://www.pixel-addict.com/videos/houdini/mites.mov

Here's an overview of what is really going on :

http://www.pixel-addict.com/videos/houdini/mitesGL.mov

Here's a snapshot of my POP tree using my custom VEX nodes :

The second example I've worked on is a school of fish. I wanted to get boids and flock behavior. This example is a school of 10,000 fish being crossed by a GIGANTIC manta ray.

All of the fishes use boids behavior to stick together. They are also driven by a curve in space following the curve's normals. They see the manta ray as an obstacle so they avoid it before coming in contact with it and all the fish that are too close from it, flee.

This behavior would be achieved so many other ways but I do like the fact that the fish try to anticipate the incoming Manta Ray.

Here's the example video :

http://www.pixel-addict.com/videos/houdini/fish.mov

and here's my POP tree :

That's about it for now.

As for my next example I would continue the Boids and Flock behavior, working more on the Chasing/Evasion and eventually make a procedural Space Opera.

Eventually I'll be glad to share this set of Nodes once all the major ones have been properly written and cleaned for sharing purposes as well as some digital assets for automatic setups.

Anyway I would be glad to know what you think of it, in anyway, good or bad (it's constuctive).

Thanks

J.

[michael]

wow...very impressive work...

I like how your example movs are super high quality

please keep us up to date on your progress!

[ihab]

Great stuff !! That's the best First post i have ever seen on this forum!!

Cheers

[carstenkolve]

this looks sweet - having tinkered with this sort of stuff a bit in the past in Maya (if you're interested, have a look here http://kolve.blogspot.com/2004/03/brainbugz.html ) this is def. interesting stuff.

some thoughts: you mention that it's quite slow as you looping through the whole pack of boids to find the nearest ones. while kd-trees etc would speed up this computation a lot (hello hdk), you could also do something easier where you calculate interparticle distances once beforehand for each timestep (or only every 2nd of 3rd timestep) and use that information in all subsequent nodes (also you could have a look at finding nearest neighbours using metaballs instead)

how are you combining the different behaviours? weighting their influence for each node, or doing some sort of arbitration to only take the most pressing desires into account?

uhh, and something I read recently: apparently scientists found out by analyzing flight behaviour that birds actually don't take the nearest neighbours into account when navigating, but up 7 or 8 other birds that they memorize. which would be a combination of a field of view computation mixed with a lookup of memorized neighbours per bird.... (can't find the pdf, but will post it if I do)

anyhow, cool stuff - please keep posting your results!

cheers,

carsten

[almatea]

awesome work

[sibarrick]

some thoughts: you mention that it's quite slow as you looping through the whole pack of boids to find the nearest ones. while kd-trees etc would speed up this computation a lot (hello hdk)

Do you not have access to point clouds in pops? I don't use particles much so I don't know but if not maybe you could bounce into sops to do the nearest neighbour with a PC sooo much quicker.

[petz]

some time ago i played around with pops too and realized a huge speed loss from houdini 9.5 to 10 for my scene. while i could play the sim in realtime with 9 and 9.5, houdini 10 needs more than 20 times as long as houdini 9.5 on my machine for around 1000 agents. first i thought that the problem is the viewport performance and there are some incompatibilties between houdini 10 and my hardware but strangely the speed loss seems to be the voppop. the cooking time in 9.5 is around 30 ms while houdini 10 starts by around 300 ms and increases from frame to frame up to 1200 ms.

i don´t know if this is a houdini problem or just something thats happens on my computer but try to open your scene in houdini 9.5.

please let us know if it makes some difference so i know if i have to buy a new computer

petz

[djo]

Thank you everyone for the heads up

I like how your example movs are super high quality

I just don't like crappy quality videos that pixelize. like most videos you see on day to day basis on YouTube. It's enough for the never ending videos of babies laughing, cats etc.. I just like to have more detail. I also want to use these videos in my demoreel. French like rendered stuff, the TD position here in Paris is inexistent, most of the time you must be able to do everything. Hence the rendered works.

this looks sweet - having tinkered with this sort of stuff a bit in the past in Maya (if you're interested, have a look here http://kolve.blogspot.com/2004/03/brainbugz.html ) this is def. interesting stuff.

As a matter of Fact I came from Maya before using Houdini. And at the time I tried doing similar stuff in MEL (what a terrible language that is) and came across your blog already

some thoughts: you mention that it's quite slow as you looping through the whole pack of boids to find the nearest ones. while kd-trees etc would speed up this computation a lot (hello hdk)

My fish example which was the slowest takes around 1 second per frame so it's not that slow but definitely not real time. But It would get slower and slower if I added more nodes.

I've looked into HDK a little bit, but it seems pretty complicated to understand without a lot of trial and errors as there isn't a lot of documentation. I'm still currently trying to understand a Node's structure with the sample HDK source codes in the POP section. It doesn't make sense to me yet, The constructor launches a method and in that method another method is launched and so on for a couple more times ? I find it complicated for just a simple example. But there must be a good reason. I'm not familiar with C++'s Object oriented programming. Do you have any good documentation on houdini's HDK ? The Doxygen is a pain to read, maybe some other time, I'll take the courage to dig in it. This could help me with some collision nodes, as I was saying vex computes each particle simultaneously, so for example when I update particle 1's position, particle 10 won't see the changes of particle 1 until next frame. But I would love to convert them into compiled HDK nodes some day.

you could also do something easier where you calculate interparticle distances once beforehand for each timestep (or only every 2nd of 3rd timestep) and use that information in all subsequent nodes

That's a very good Idea but it would be a huge amount of data to store per particle and I would still need to loop the Data again as each nodes uses different distances but would it really improve performances as I calculate squared distances for the particle and match it with the squared value of the nodes parameters, thus leaving out the square root calculation entirely.

how are you combining the different behaviours? weighting their influence for each node, or doing some sort of arbitration to only take the most pressing desires into account?

Actually its just a simple weight that each node has as a parameter, and some nodes only affect a certain group of particles that are dynamically created by other nodes.

uhh, and something I read recently: apparently scientists found out by analyzing flight behaviour that birds actually don't take the nearest neighbours into account when navigating, but up 7 or 8 other birds that they memorize. which would be a combination of a field of view computation mixed with a lookup of memorized neighbours per bird.... (can't find the pdf, but will post it if I do)

What do you mean by memorized neighbours ? like at some point each agent would memorize their neighbours and just keep using that info during the whole sim ? (hope you find the pdf)

Do you not have access to point clouds in pops? I don't use particles much so I don't know but if not maybe you could bounce into sops to do the nearest neighbour with a PC sooo much quicker.

Yes we do have acces to point coulds in POPs but the thing is, it only works with a PC file and not the op:path to particle operator. Don't know why ? but it doesn't. Ive read on this forum somewhere that some guy has had this problem. I've tried it myself. That could have been faster indeed

some time ago i played around with pops too and realized a huge speed loss from houdini 9.5 to 10 for my scene. while i could play the sim in realtime with 9 and 9.5, houdini 10 needs more than 20 times as long as houdini 9.5 [...]

Actually I don't see any difference in performance between the two version .... ? that's a strange problem indeed

-Update-

I'm actually working on some formation nodes, the best approach I have at the moment is to feed a PC file, point 0 of the PC file is where the leader should be in the formation and the others will try and position themselves relatively to the leader using the PC file as a guide(the formation facing the same way as the leader). And have some catching up and slowing down if they are far away from their formation's position.

Anyway I'll keep you guys updated when I have more.

[carstenkolve]

> so for example when I update particle 1's position, particle 10 won't see the changes of particle 1 until next frame.

isn't this the required behaviour for each frame?

check all neighbours - compute steering force - update position by applying steering force

if you update particle 1 position prior to 10 having the chance of checking the neighbours, wouldn't that mean that 10 would check his surrounds in the future frame and not in the current one?

Storing distances

> That's a very good Idea but it would be a huge amount of data to store per particle and I would still need to loop the Data again as each nodes uses different distances but would it really improve performances as I calculate squared distances for the particle and match it with the squared value of the nodes parameters, thus leaving out the square root calculation entirely.

well, if you store all possible distances prior, that would be a huge amount of data. i thought more about limiting the number it by either a maximum distance per particle, or a maximum number of neighbours (based on the max amount needed in any of your behaviours)

if your particle speed is not very fast, you wouldn't need to rebuild this lookup at every frame, too

combination of forces

> Actually its just a simple weight that each node has as a parameter, and some nodes only affect a certain group of particles that are dynamically created by other nodes.

a suggestion: you could make the behaviour look more dynamic by taking into account how many behaviours can contribute to a steering force (say, only take the 2 forces that are the most pressing and ignore the rest). or only allow a maximum force in total when adding up individual forces.

flocking behaviour

> What do you mean by memorized neighbours ? like at some point each agent would memorize their neighbours and just keep using that info during the whole sim ? (hope you find the pdf)

exactly, you'd store in an initialization step a n neighbour id's of agents in the fov and then reuse that during the sim.

[carstenkolve]

I found the article I was referring to above - a bunch of scientist tracked whole swarms of starling over Rome, reconstructed them in 3d and then analyzed the data

http://www.smc.infm.it/index.php?option=com_content&view=category&layout=blog&id=45&Itemid=103

the interesting part talks about the 6/7 neighbour interaction based on topological (NOT metric) distance and the effect this has on the cohesion of the flock. so to mimick this in your simulation you'd probably try to track 6 to 7 agents in your fov for as long as possible and add a new agent to track once you fall below that number. I'd probably try in a first approach to choose those neighbours randomly (but other approaches like "nearest neighbour", "furthest neighbour" might work, too).

how to you approach the fov calculation? are you distance limiting it?

[edward]

some thoughts: you mention that it's quite slow as you looping through the whole pack of boids to find the nearest ones. while kd-trees etc would speed up this computation a lot (hello hdk), you could also do something easier where you calculate interparticle distances once beforehand for each timestep (or only every 2nd of 3rd timestep) and use that information in all subsequent nodes (also you could have a look at finding nearest neighbours using metaballs instead)

Doesn't the Proximity POP help with this?

[djo]

isn't this the required behaviour for each frame?

check all neighbours - compute steering force - update position by applying steering force

if you update particle 1 position prior to 10 having the chance of checking the neighbours, wouldn't that mean that 10 would check his surrounds in the future frame and not in the current one?

Well its a good behavior for most nodes but the problem comes for collisions between them. Let's say for example at a certain frame particle 1 and particle 10 collides with particle 5, but not together. At the next frame I would have moved particle 1 and 10 away from particle 5 and particle 5 away from 1 and 10. Nothing garentees me that when I moved particle 1 away it doesn't come in contact with the new position of particle 10, I'll only know this at next frame. I was thinking HDK is a way to go for this but then I'll want to rewrite everything in HDK

well, if you store all possible distances prior, that would be a huge amount of data. i thought more about limiting the number it by either a maximum distance per particle, or a maximum number of neighbours (based on the max amount needed in any of your behaviours)

if your particle speed is not very fast, you wouldn't need to rebuild this lookup at every frame, too

The best solution it to store a global 3D grid array what represents space divided up into boxes like voxels and each particle updates that grid based on their position. Then I could just lookup a couple of those values from my grid to get the neighboring particles. But I have no Idea how to achieve that in VEX, that's why HDK could come in handy, but i'm really lost on HDK for now, it seems to huge of a thing to be just jumping in like that, but I'll have to someday

a suggestion: you could make the behaviour look more dynamic by taking into account how many behaviours can contribute to a steering force (say, only take the 2 forces that are the most pressing and ignore the rest). or only allow a maximum force in total when adding up individual forces.

Good suggestion, i'll try it out, and thanks for the doc i'm reading it now

Doesn't the Proximity POP help with this?

Well I'm reformatting my computer now getting ready for Karmic Koala (1 Day Left), I like starting fresh.Anyway I'll check it out when my computer's back up and running, but I fear its an additional node, and I wish to keep each behavior in a single node. but Anyway I'll eventually have to get my hands on HDK, I can't persuade myself around it forever.

Anyway Thanks guys

J.

[pclaes]

just as a thought:

Would it be useful to do the entire thing in sops in combination with a sopsolver in dops? You are having so many vex nodes anyways.. It might be too slow, but you would then be able to access all your data and have extra python sops at your disposal. Python would probably be to slow - but would allow you to add and destroy points. But in terms of underlying grid structure you could probably use the pointclouds in vex as they are multithreaded and quite fast.

Very interesting work and discussion!

[ranxerox]

hey djo, I wanted to ask how you were coming along with this project, as I have been very interested in using such an OTL with houdini.

thanks

-ranxx

[djo]

hey djo, I wanted to ask how you were coming along with this project, as I have been very interested in using such an OTL with houdini.

thanks

-ranxx

Hey ranxerox I haven't been checking odforce in a long while, unfortunately my professional life has made me extremely busy, I've changed country and do not have my computer with me any more (I should have to buy a laptop) :'( plus most of my professional work is in Maya at the moment so I haven't touched Houdini in a long time. I've managed to add a few more behaviours to this but nothing concrete rendered to show (formation stuff). I'll come back on this as soon as I have some spare time a personal computer and a bit of my social life back.

Cheers

Edited July 29, 2010 by djo