Behavioural Simulation in Blender

aothms · May 14, 2009, 4:17am

Hi,

I’m not really an active member of the Blender community (yet, that is). I’d just like to inform you that I’ve created something that may be of some benefit for others or is at least fun to play with.

It’s basically a combination of two great open source software packages: Blender and OpenSteer. I won’t elaborate on Blender as you’re probably familiar with it. OpenSteer is a framework for behavioural simulation. My effort was to convert it into some sort of daemon application and write a couple of Python scripts to communicate with it.

The fun thing is that it remains completely interactive. Modelling and simulation take place simultaneously and the actors in the simulation respond directly to the modelling decisions in real-time! Which makes it (potentially) a great design tool or is at least a great way to spend some time.

If you’re curious you’d have to google yourself though, as this is my first post here. There is a video on youtube with the title Blender Behavioural Simulation that tries to visualise the basics and has a link to the source.

Kind regards,
Thomas

Meta-Androcto · May 14, 2009, 7:25am

that looks really cool.
well done.

Vassilios · May 14, 2009, 8:25am

Really Great!
i made some tests, very Funny to play with it!
but i have a problem …The moving Objects not avoiding the Obstacle Object !
I have a Cube as Obstacle and a Path and a Plane!
here you can Download a very short video …you can see the Orange moving Objects goes Inside the Blue Cube (Obstacle)!
Obstacle:A Blender Mesh the actors try to avoid.
A section is computed at the Z=1 plane???can you explain it better

http://www.2shared.com/file/5775099/49350ff7/0200_0351.html

aothms · May 14, 2009, 9:20am

Vassilios, thanks for trying! My guess is that you didn’t go into and leave editmode after you set the cube to be an obstacle.
Now that I write this down I realise that this sounds quite absurd, and I’ll probably have to change that in the script.

I’ll explain: when you set an object to act as the obstacle all that happens is that a scriptlink is assigned to the object.
Only when the mesh data of the object is changed (it must already have this scriptlink assigned) only then the obstacle is sent to the opensteer daemon.

A section is computed at the Z=1 plane

OpenSteer doesn’t support all shapes of obstacles. So we must approximate them. A horizontal section of the mesh at Z=1 is used to compute this approximation. So everything above or below doesn’t do anything.

Btw, could someone post the relevant links to my vid and site as a reply, as I can’t post them. Allthough I’ve been trying to earn my way up by posting around the forum.

Vassilios · May 14, 2009, 9:32am

aothms: Thanks for the Infos i try it again !
About horizontal section of the mesh at Z=1 is used to compute this approximation. So everything above or below doesn’t do anything.
I dit this correct and not works beacause later i found out what you mean with this!

Thanks

littleneo · May 16, 2009, 7:49pm

download :
http://www.thomaskrijnen.com/bbs/
the aothms video :

opensteer projcect page :
http://opensteer.sourceforge.net/
great resource about autonomous behaviour
java captivating examples about this library
http://www.red3d.com/cwr/steer/

it’s really cool.
it doesn’t use the game engine possibilities, it’s a frame-linked script ?
(will try it)

Atom · May 17, 2009, 5:38am

Dang, it is one of those things where you have to compile crap.

pildanovak · May 17, 2009, 11:37am

This is TOTALLY awesome . I’d really love to see this connected to the game engine…

PapaSmurf · May 17, 2009, 7:15pm

how does this compare/contrast with Boids in the particle engine?

UglyMike · May 18, 2009, 12:06am

Oooh, I can see those little guys on littleneo’s sidewalks with small cars on his roads…
Suicidator comes alive…

aothms · May 18, 2009, 12:40am

Thanks for posting the links littleneo. It would indeed be a fun combo with the citygen script you guys wrote, great idea UglyMike. It would require some code for pathfinding in the city and a network of nodes and edges from the generated cityscape (and of course some spare time). Two kinds of vehicles wouldn’t be a problem though.

pildanovak, I might look into the GE, this daemon idea originally started as a simulator for a python based VR toolkit, so I understand your point.

PapaSmurf, good question. To give a short answer, it doesn’t. It originally wasn’t intended for use with blender and thus blender isn’t the only possible use of the opensteer daemon. I guess both opensteer and the blender boids are based on Craig Reynolds’ work, so they’re very comparable. This script can be seen as a proof of concept about real-time design evaluation and making adjustments with immediate feedback from the actors. But with some knowledge of C++ you can easily write you’re own plugins for the simulation daemon and prototype you’re own behaviour. Such as cars and pedestrians in a computer generated city or a soccer match. For more examples of opensteer plugins take a look at the original OpenSteerDemo, it has some great examples.

littleneo · May 18, 2009, 2:54am

It would require some code for pathfinding in the city and a network of nodes and edges from the generated cityscape

YES say me what inputs the behavioural sim. needs for the network
I’m just doing something about that - a nodal crossroads/streets parser -
It would be great if the internal sce street network was compatible with the behavioural sim. pathfinding.

here’s the list formats it outputs so far :

. a list of xyz 3d coords for significative (I mean a new angle, a new width) road segments (blender units)
coordsList

coordsList=[ [101,56,0,[some metas]], [56,17,0,[some metas]] ...]

. a list of roads. each road is a link between two crossroads or a dead-end and a crossroad.
roadsList. it’s a list of coords id’s.

roadsList=[ [ coordsList[0] ], [ coordsList[5] ], [ coordsList[3] ], ...]

roadsList[2]=[0,5,3]
means the road id2 is made with coordsList[0], coordsList[5] then  coordsList[3].

each end (0 and 3 above) correspond to a node coordinates*

*maybe I could add a node id field in this list, maybe faster to parse after but redundant, I don’t know yet

. a list of nodes : node are crossroads or deadends
nodesList


nodesList=[ [ node0 coordsList[n] of crossroad , [list of neighbour nodes],[list of neighbours roads] ] [ node1,.... ]

example :
nodesList[0]=[3,[17,8,5],[89,50,60]]
means
node id 0 is located at coordsList[3]. 
it has 3 nodes as neighbours, with id 17,8 and 5.
it has 3 roads 89,50 and 60.
take road id 89 to go to node id 17
road id 50 to go to node id 8
road id 60 to to node id 5

len(nodesList[0][1]) always equal to len(nodesList[0][2])
a node can have itself as a neighbour :
nodesList[0]=[3,[17,3],[89,45]]
road 45 has the same crossroad at both end, node 0

a node can have several path to the same neighbour road:
nodesList[0]=[3,[17,17,5],[89,45,67]]

. a list of sidewalk blocks (building areas). blocks are shapes closed by roads and nodes.
blocksList

blocksList=[ [nodesList[5],nodesList[3],...]
blocksList[2]=[5,6,7]
this block is surrounded by 3 nodes with id 5,6 and 7

blocksList[2]=[8]
this one has just one neighbour node, one of its road surrounds the block.

I could add a road metric, or some properties (one or two ways)…

please let me know, I’ve no background about nodes (but my former job was network engineer/consultant !). my need until now was only a best way to draw non-squared city map.

aothms · May 18, 2009, 12:03pm

Hi littleneo, I’m no pathfinding expert, but a colleague explained the basics. For the pathfinding algorithm all that is of interest are nodes and edges.
Edges are one way only and only connect two nodes, so if a road segment allows for both directions to be travelled it consists of two edges a->b and b->a.
The optimal route through the network is calculated based on the cost of travel associated with an edge, cost is most often the edge length, but this can be any arbitrary value. Another possibility is to multiply/divide the length with a factor (e.g. the width, number of people on edge) so broader roads are used more.
The pathfinding algorithm doesn’t take intersections of edges into account. So crossings, dead-ends and corners should be nodes.

So, concluding, the minimal information to make this work would be:

Nodes = [
[x,y,(z)],
...
]

Edges = [
[startNodeId,endNodeId], #Id is just index in Nodes
...
]

For example a one way square with a two way diagonal:

(0,1) (1,1)
   --&lt;--
   |\  |
   v \ ^
   |  \|
   --&gt;--
(0,0) (1,0)

Nodes = [
[0,0],
[1,0],
[1,1],
[0,1]
]

Edges = [
[0,1],
[1,2],
[2,3],
[3,0],
[1,3],
[3,1]
]

I guess this doesn’t differ much from what you’ve written above. But I don’t really understand how a node can be be neighbour of herself. And all roads have to be cut into segments.
To keep things simple in the beginning, I think it would be best to take this as a starting point and maybe extend it with additional meta-data later on.

littleneo · May 18, 2009, 6:58pm

thanks for the infos.

I don’t really understand how a node can be be neighbour of herself

that’s because the goal, and our definitions of a node are not the same.



 _______
 |     ^
 |     |
 |_&lt;___n___
       |
       |

for me a node a three possible paths. if it has two, it’s part of a road.
the 2 roads with arrows start from node n and go to node n.
also if there’s an isolated, closed path somewhere, it needs a ‘fake’ node with 2 in/out
I need this at least for one step, when defining the shape of each sidewalk blocks.

briefly my need are : discover an image or a mesh as a network, smooth road edges, create roads geometry, create sidewalks ,create crossing meshes, etc… I don’t need a node between each edge.
so I have : node for crossing/dead ends (their coords will stay in place), and roads list of edge (coords/edges will change after being arranged/smoothed)

please let me know if I understand your need :

(0,1) (1,1)
   --&lt;--
   |\  |
   v \ ^
   |  \|
   --&gt;--
(0,0) (1,0)

I understand 0,1 and 1,0 which have 3 possibilities (same for me)
0,0 and 1,1, the ‘corners’, have 2 possibilities. but all of the other positions have 2 possibilities…

so I suppose the reason to define 0,0 and 1,1 as nodes is about a new angle that the avatar AI has to know, like here :
http://www.red3d.com/cwr/steer/PathFollow.html
I though avatars were more autonomous while in a road, whatever its shape (when there’s no crossing)

in your example roads have only 2 straight edges max, but one can have long curved roads, or roads with a lot of straight edges in the city.
in fact one would have a ‘node’ at every edge extremities, in a road (no crossings), in this case.
in fact one need every coordinate as a node in this model, supposing there’s no aligned coords in a same path. did I get it ?

I have a simple function that returns a lenght and a global orientation, when one gives a vector to it :
lenght, degree=readVec([x,y,(z)])



 a______
 |     |
 |     |
 |     b_____
 |____/

for further discussions, I propose to define some vocabulary :

if each coord is a node in your scheme, I propose to call it coords
edge is an edge like in blender, 2 coords linked by a straight line,
nodes are coords but with more than two possible paths, or just one (dead end)
road is a one-way path of several edges with 1 node at each extremity.
so road a-b-c is not road b-a-c. here I suppose there’s no edges with different directions inside one road.

about the ‘keep it simple’ : in fact I need more informations to build my mesh anyway, so don’t hesitate to ‘make it harder’ about your need.

anyway my new parser is not finished and the actual one is not nodal…:no:

aothms · May 19, 2009, 12:41am

I though avatars were more autonomous while in a road, whatever its shape (when there’s no crossing)
Well, the algorithm on my part consists of two distinct parts: The pathfinding and the steering.

Pathfinding A->B:

                           B 
 o---o---o------o--o   o---o
     |   |     /   |   |   |
     v   v    o-&lt;--o   |   |
     |   |   /     |   |   |
 o---o---o--o      o---o---o
 A


               -----   -----
               /   |   |
              /    |   |
             /     |   |
 ------------      -----

Pathfinding isn’t implemented in opensteer. For pathfinding coord/node location isn’t of interest since it’s basically very abstract,
but for the steering (path following) it is. So opensteer can only take this second path as input which never has any intersections or one/two way thingies etc.

about the ‘keep it simple’ : in fact I need more informations to build my mesh anyway, so don’t hesitate to ‘make it harder’ about your need
Yes you’re right, I think the info I proposed was way too limited for both our needs.

for further discussions, I propose to define some vocabulary
agreed! So basically all that is of interest for me are coords and edges.

anyway my new parser is not finished and the actual one is not nodal…
Please, take your time, I have two very important deadline’s coming up!

littleneo · May 19, 2009, 5:17am

hey thanks for the additionnal infos about your needs, it’s more clear to me now.

I made a little mistake in my last post, and I don’t speak about my english :-/ :

road a-b-c is not road b-a-c. here I suppose there’s no edges with different directions inside one road.

I mean road a-b-c is not road c-a-b.

about the way you could use the city info, what do you think ?
my idea is that the script does its network then write the different lists you need on a text file that you can parse latter. it’s also useful for the city itself, to store the mgeometry
I have some include functions ready to use.

littleneo · May 19, 2009, 7:14pm

nodal compliant citymap running
http://blenderartists.org/forum/showthread.php?p=1382476#post1382476

aothms · May 20, 2009, 5:41am

Great to see your progress littleneo. I’ve implemented MicroPather (http://www.grinninglizard.com/MicroPather/) A* pathfinding in the simulation code and it seems to work reasonably well.
I’ve created a little test simulation and it seems ok. Here: http://thomaskrijnen.com/bbs/opensteercity.avi. Three obvious problems:
1 Actors travel from (in our vocabulary) coord to coord, so in coord-denser area’s (corner) there’s a lot more activity.
2 The actors just walk in the middle of the road.
3 The actors don’t follow ‘our rules of behaviour in a city’ like walking on the right, not walking too much like a drunk.

But he, it’s a start. That said, I’m very short on my time at the moment, so I probably will not check in for about a week or so, I hope that’s okay with you littleneo.

I zipped it all up if someone wants to experiment further: http://thomaskrijnen.com/bbs/opensteercity.zip

about the way you could use the city info, what do you think ?
You mean how we’ll connect the scripts? That depends, the python script to send nodes and edges to the simulator and gets the simdata back are just a few lines, so could be easily pasted in your script if you want.

Atom · May 20, 2009, 12:06pm

Interesting, so you are using a port to communicate with OpenSteer.

If you post another ZIP file could you just include the BLEND as well?

I read the notes, but I’m not sure what this means?

Active mesh should be the nodal network of vertices and edges (Remove Doubles!)

C_Wynn · May 20, 2009, 1:12pm

I downloaded all the components but, I keep getting an error message whenever I try to run it that says “could not find glut32.dll.” Has anyone else run into this?

-C. Wynn-