Crowd simulation or IA agents from c++ to typescript with Emscripten to TS/JS for babylon.js

[Samuel Girardin]

Hi,

 

For the short story , I'm really interested about 'IA' for games, so I'm familiar with IA concepts and in this case about 'collision avoidance'. So here is a demo of a cool algorithm (first write in c++ by  University of North Carolina, RVO ) managing IA agents (multiple characters moving with a kind of IA), converted to JS with Emscripten to reach typescript/JS.

 

One year ago, I made a try to convert this algorithm from c++ to pure typescript/js, but with bad performances (I made a post in this forum).

 

I talked with @lo.th #oimo.js 's guy  ; and he said me : do you know Emscripten. This can compiled c++ to Js with high end perfs. So I made a try, and that 's right perfs are really good compared to my first typescript/js  port ! I have already worked with this kind of library with alchemy/Flascc from Adobe, converting c++ to as3(rip).

 

Few words about Emscripten ( http://kripken.github.io/emscripten-site/ ). It 's a really cool open source project.. You can read that on their homepage :

« Emscripten is an LLVM-based project that compiles C and C++ into highly-optimizable JavaScript in asm.js format. This lets you run C and C++ on the web at near-native speed, without plugins. ». You can read that on their homepage.

 

So here is a really alpha preview, the demo counts 11 differents scenes. For each I try to explain what's the purpose (black div on the left).

 

If you want to play with agents, selecting, moving, changing goals, it's in the last case, scene 11.

 

I test this demo with chrome and ie (faster with chrome). Maybe some guys from the forum could test it with spartan (feedback would be appreciated ! ).

 

Here is the a pseudo code for the first scene -typescript  :

private case1(): void {       // number of agents        Main.n = 128;             this.meshes = this.basis.createAgentsMesh(Main.n);        //  ini Crowd Simu        this.crowd = new BABYLON.CrowdPlugin(this.scene);           for (var i = 0; i < Main.n; i++) {            this.crowd.addAgent(this.meshes[i],0);            this.crowd.addAgentGoal(i, new BABYLON.Vector2(-this.meshes[i].position.x, -this.meshes[i].position.z));                          }              }public loop(): void {             this.crowd.run();    }

So this library could be usefull to manage characters behaviors with babylon.js. Maybe a plugin for babylon ?

 

The demo : http://visualiser.fr/babylon/crowd/

 

I need to clean up few things before publishing this. It works with babylonjs 1.14, I need to fix a strange behavior with the 2.0 alpha..

 

Sam

 

 

 

[davrous]

Very cool. As usual!

 

David

[reddozen]

Yea, Emscripten is awesome. It's where things like ammo.js, and the first unreal demos came from.

[GameMonetize]

You rocks!

[Samuel Girardin]

Next step :

 

 

[GameMonetize]

OMG. I love it:)

[Wingnut]

Sam, you're a GOD!  sigh!  Great demos and a super-interesting subject of study!  And some real fine mouse clicking and highlighting, too... some of the best I've seen in a webGL scene.

 

I was curious about the "Dijkstra ON" comment on demo #11.

 

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

 

Amazing!

 

These things can be used for MANY applications.  One thing that came to mind for me... was war simulations.  Another... was racing.  In another thread, I talked about mechanical horse racing, and making a race-anything demo (mostly for party fun - betting on horses for shots of booze)   But can you imagine creating a "forest of obstacles" and then send one of Sam's crowds... seeking the finish line on the far side of the forest?  TOO FUN!  Great betting opportunity!    Getting drunk with Dijkstra!  How cool is that?!

 

And, sigh, although weighing more racing factors will slow the simulation a bit, I know its possible.  Factors... like... is there snow?  Mud?  Is the crowd exhausted?  Are they carrying wounded agents?  How much of a tendency do they have... to claw and elbow (each other) to get to their seek-target?  Is it Black Friday and is the crowd trying to enter a shopping mall? 

 

Mix-in your fantastic ragdolls, and boom, we have some real knock-down, drag-out people-racing. 

 

TOO FUN!!!

 

Is there ANY chance that demo #11 could be put into a BJS playground scene?  No gui is fine.  Maybe you could just place some variables at the top of the code... where we could set timestep, iterations, target, etc.  We wouldn't necessarily need any selecting, dragging, or highlighting of scene items.  We (I) just want to play-with Dijkstra racing and watch things happen.

 

Ok, ok, really I want to steal all of your code.    (just kidding).

 

SamG, we don't get to talk very often, and therefore, I don't get to tell you that you are seriously one of my heroes!  Applying Dijkstra and possibly your own crowd-moving code... in a BJS scene... is just super cool.  Keep up the great work.  Way good!  Drooooool. 

[Samuel Girardin]

Hi Wingnut, 

 

Thanks to disturb me in my work   , anyway I need a brake ! I'm actually working on a density algorithm. As you saw in the scene 11  when agents pass through the main exit, they ignore the two others exits. It results in a heavy traffic jam around the main door. They just want to take the shortest path to reach their goals (silly agents ! ). So now, and I hope I can achieve that tonight. I calculate  for some hot points, agent's density (number of agents in a specific area), all other agents outside this area but who wants to access to this area are invited to recalculate a new path excluding in our example the main exit option (defines as a 'hot' point). I hope this will work. I can't wait to see that working ! 

 

I made too a big change, the crowd plugin runs now in a separate thread, so Babylonjs is no more impacted by the computing of the simulation. About implementing webworkers I feel like a juggler.... My main thread have to communicate with the crowdplugin thread who itself communicates with crowd.js (the c++ compiled to js with emscripten). It's a story of passing bytesArray(like) in all directions ! 

 

For  the moment, during the simulation you can add or delete agent, add or delete obstacle (obstacle must be closed polygon). Obstacles can't move. Tune your agent with properties like max speed or the maximal number of other agents the agent takes into account in the navigation, the size of the living area of the agent.

 

So yes we can do great thing with that. For the playground I'm not sure how to do that. I only use typescript.  I will release the source code soon, with a basic example, so maybe you can give a try. (webworker are supported in play ground ? ) .

 

My break is over. Let's see that density points   

[Wingnut]

Hi Samuel (and others)... thanks for the update.

 

Umm... ahem... I just had-to try to get a home version of the crowd demo.  So, I stole it with a "save entire webpage" and then I fixed some things that I broke, and then I installed a 1-piece babylon.js, and and and... 

 

http://urbanproductions.com/wingy/babylon/samG/samG_crowds.zip

 

I'll delete it and this post if you wish, Sam.  But it will be too late, then.   Thousands will have DL'd it.  (no, but really, if you have an issue with me giving-out this quick home version, just say so, and I'll pull it out of public view.  No probs.)

 

Folks, this zip is not an official Samuel Girardin release.  I wanted to try some home experimenting with this.  I hope it's ok to do this.

[Samuel Girardin]

So, I test your zip, in fact this code was for  bjs 1.14, that's why some features are broken. My new version runs on 2.0. 

[Wingnut]

Ahh, ok, thanks!  Zipped version fixed (using version 1.14 now) and file renamed.  Works great!  Thanks for being tolerant of my un-authorized bootleg-release activity, too.  I appreciate that.

 

If you would like to host that zip on YOUR server/domain, feel free.  I will adjust these link addresses to target it.

 

Ragdoll racing.  haha.  Can you imagine it?  I can't seem to stop laughing at the thought.  I bet crowds of ragdolls would REALLY bog the ol' FPS, though.

[Samuel Girardin]

Don't worry, but I would recommend to wait for the official version   with comment in code. My js outpout delete comment so... And without other developpers sources I would have newer learned code. So enjoy.

[Wingnut]

Wingnut is being goofy, but, I wanted to inform others that SamG is doing serious things, here.  The title of one of the github repositories is...

 

"Reciprocal Collision Avoidance for Real-Time Multi-Agent Simulation"

 

That sounds serious.  Shapes that can think and deduce.  Pretty cool.

 

Sam, if you don't mind me interrupting your work yet again, do you have some reason other than killing sky-farm sheep... that got you interested in "RCP"?  What made you pursue this subject?  (if/when you have a moment)  (thx)

 

PS: If you want to zip-up your Assets folder for the ragdoll thing, I wouldn't mind having that.  My "save entire webpage" didn't reach into that directory very well... because the SAVE couldn't look at the urls in dev.js.  Only if you want-to, and have time.  thx either way.

[Samuel Girardin]

Tanks wingnut, but the original algorithm came from  University of North Carolina, RVO, not from me ! My only contribution here,  is that I'm not afraid by oop, adding features to this library, and put this in a strange box where you put c++ and outup some cool js. I learned only by myself, except a 2 months algorithm course, I ran  away, when I had my first  course about financial things and computing (20 years ago).. Sometime it's cool to feel free (I live in a sail boat, in south of france, but we have a great wifi !) My interest about RCP, is just because this kind of library are used in high end game, and I'm pretty sure we can have that in a browser tomorrow... 

[reddozen]

I've thought about using Emscription to convert recast and recast navigation. This is what we use on our game server engine to handle monster pathing, Z height look ups etc.

 

https://code.google.com/p/recastnavigation/

 

Examples from one of our old maps:

http://www.diviniaro.com/files/RecastDemo_Prt_d01_1.png

http://www.diviniaro.com/files/RecastDemo_Prt_d01_2.png

[Wingnut]

@SamG - Have you ever thought about modeling your sail boat?  Maybe building a scene around it?  I'd tour it... especially if it had lots of fun surprises on-board. 

 

 

Readers, if you've never been to SG's website, then go go go.  http://www.visualiser.fr/index.php  .  Sam has experimented with... EVERYTHING, I think. 

 

What a portfolio!  whew!  Nice work, SG.

 

@reddozen, you are kicking butt, too!  Check this out...

 

http://www.diviniaro.com/forum/viewtopic.php?f=189&t=6556&sid=223ffe059339c0cd523cab98e84d3d3a

 

Click the picture.

 

Niiiiiiiiice!

[GameMonetize]

Hey Reddozen, we neeeeed a demo too!!!!

[reddozen]

What kind of demo DK?

 

The recast thing was in our old map export tool from unreal to simulate what our server code was doing.

 

The town from the link Wingnut posted isn't quite optimized as much as I want. I have to restrict the view range a lot to keep frame rates high enough. We've also scrapped this map in favor of a different layout / design closer to the original Ragnarok Online home city.

 

We've been working on a script to build our sub maps in 3DS so that they can exported to babylon and have predictable world locations. All the map objects are being loaded into a database and I'm using PHP to build the javascript loader file in real time on request.

[GameMonetize]

A demo of the town actually

[Wingnut]

Me too.  The models/scenery are quite inviting.  If I may quote the great Polygonian Indian Chief - Running Vector...

 

"Me wantum flyum scene."

 

And if your webGL version of RO2 smells like Korean kimchee, we're cool with that.  I happen to know that kimchee is WAY better than sauerkraut... when served with hot dogs.  I fell in love with hot dogs and kimchee when I was stationed in South Korea during my time in the U.S. Air Farce.

 

Plus, it's fun to hijack Sam's thread, like we are doing.  I wonder how far he will let us run away with it... before he has us arrested. 

 

Yep, those are some seriously detailed textures, reddozen.  Map tour! 

[jerome]

"US Air Farce"

[reddozen]

Ok, I'll work on some more inclusion / exclusion stuff and try to package it up. The files are pretty monstrous though as DK knows from some of my support threads.

[Wingnut]

Don't let us be a hassle for your project, R.  We can wait for the grand opening, too.  We are (I am) just scene junkies.  We (I) snort pixels. 

[Wingnut]

Sam?  You still here/hear?  Can I ask for a status of Transhumance?  

 

(man, that's a cool pic!)

 

I have always been interested in herding tendencies.  My dad has asked me often... "If all of your friends walked-off a cliff, would you do the same?"

 

45 years have passed, and my dad is still waiting for my answer.  So, I need Transhumance... to test, under what circumstances,  would I walk off the cliff with my friends. 

 

Are we going to have a sheep AND cow version?  I hope so.  I grew up in Wisconsin USA, and we are 'into' dairy stuff. 

 

I was running your crowd sim last night, yet again.  It's SO cool.  I'm going to use it to make a drinking/gambling game... racing crowds thru obstacle courses... see who can get to the target, first.  Then later, maybe we'll weaponize each agent, pour in some booze, re-calculate for percentages of "angry" drunks and blurred vision (agent can't find its obstacle, or its cigarettes, car keys, or wallet), etc.   

 

Okay, maybe not all that, but, there's fun to be had with these things.  I love them.  Thanks for making them, SG!

 

I hope everyone is well!

[Samuel Girardin]

It always a pleasure to read you wingy !

Yes, I still live on earth.. I missed my spaceship fly for this really cool new planet where sheeps live on strange floating island !. In fact, I wanted to bring with me my boat, but the crew informed me that there is no water on this planet. I will not go into details but I learnt that they produce water with a strange mechanic where sheeps are involved.. Really stange world !

More seriously, I left my boat for a 5 months 'babylon" contract. It's quite intense. I come back to my boat at the end of july. I still want to work on transhumance (I had a web worker version of the crowd sim, and one dealing agent density area) , and I have a new game project in my head. I will let you know !