Gamestudio Links
Zorro Links
Newest Posts
Gracefully closing a panel
by Zheka. 07/17/19 15:02
MaxDD in %
by Zheka. 07/17/19 14:51
New Zorro version 2.15
by jcl. 07/17/19 12:21
Issues with converting .csv to .t6
by jcl. 07/16/19 14:46
IG plugin initial release
by YG8. 07/16/19 10:02
First Steps for backtesting with ASCII data
by Charttrader. 07/16/19 08:50
Beginners Workshop
by jcl. 07/15/19 06:29
Dukascopy plugin (yet another version)
by dh85. 07/15/19 05:03
AUM Magazine
Latest Screens
The Space Between
Pogostuck: Rage With Your Friends
Worst Case Z
AckCon'18 - Lotter vs the World 2 - Preview Release
Who's Online Now
12 registered members (jyd, kvm, Peeyotch, Grat, AndrewAMD, FLD, TradingMax, Quad, Matt_Aufderheide, 1 invisible), 705 guests, and 6 spiders.
Key: Admin, Global Mod, Mod
Newest Members
Charttrader, bjomu, catharticlapse, carmyss121, Evox
18255 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
Pathfinding for crowds? #462697
10/22/16 00:40
10/22/16 00:40
Joined: Aug 2011
Posts: 133
Germany, Supergeheimes Hinter-...
G
gameplan Offline OP
Member
gameplan  Offline OP
Member
G

Joined: Aug 2011
Posts: 133
Germany, Supergeheimes Hinter-...
Hi,

I want to implement a pathfindung solution for a big crwod of dynamically moving entites. Every entity should avoid contact with each other entity while finding a path through a moving crowd of entities over a unevan surface.

I just want to ask, if someone does know a good starting point? Does there exist a specific algorithm, that suits best for this excercise? What do you recommend?

Thanks.


Version: A8 free
OS: Windows 10
Re: Pathfinding for crowds? [Re: gameplan] #462700
10/22/16 07:26
10/22/16 07:26
Joined: Mar 2011
Posts: 3,150
Budapest
sivan Offline
Expert
sivan  Offline
Expert

Joined: Mar 2011
Posts: 3,150
Budapest
WJBender made a navmesh plugin called Peragro of the Recast/Detour/DetourCrowd. By the way, it is available in Unity and UE4 by default. I don't know whether it is still available or not, he switched to Unity. It has good performance I think only max 100 characters. To make your own plugin:
http://masagroup.github.io/recastdetour/
https://github.com/recastnavigation/recastnavigation

another open source solution is RVO2:
http://gamma.cs.unc.edu/RVO2/

by the way if you need larger crowd, you can implement a vector field pathfinding and movement system, or use simply a potential field. I have recently implemented my solution based on this, but it does not deal with avoidance (but possible to add little repulsion to the heat map around units):
https://gamedevelopment.tutsplus.com/tut...g--gamedev-9007

But it really depends on you what you mean by crowd, and what is the exact purpose, what limitations you can accept on quality and performance...


Free world editor for 3D Gamestudio: MapBuilder Editor
Re: Pathfinding for crowds? [Re: sivan] #462709
10/22/16 13:25
10/22/16 13:25
Joined: Jul 2008
Posts: 1,963
Germany
rayp Offline

X
rayp  Offline

X

Joined: Jul 2008
Posts: 1,963
Germany
To keep performance high use a single while that controlls all ents stored in a array.
this mass ai tip changed my life.

My mass ai project
http://www.opserver.de/ubb7/ubbthreads.php?ubb=showflat&Number=460893#Post460893

Greets

Last edited by rayp; 10/22/16 13:27.

My entry...your exits
Zombies dont like pink glow slime, fact!
"We gonna rock down to electric avenue" "One way ... or anotha ..."
"Hey Griswold ... where u gonna put a tree that big ?"
1998 i married my loved wife ... Sheeva from Mortal Kombat, not Evil-Lyn as might have been expected
-=GOOGLE IS SKYNET=-
rayp.flags |= UNTOUCHABLE;
Re: Pathfinding for crowds? [Re: rayp] #462718
10/22/16 19:49
10/22/16 19:49
Joined: Aug 2011
Posts: 133
Germany, Supergeheimes Hinter-...
G
gameplan Offline OP
Member
gameplan  Offline OP
Member
G

Joined: Aug 2011
Posts: 133
Germany, Supergeheimes Hinter-...
Hm, most of the implementations that I have locked at, seem to need a navmesh or nodes, that need to be placed by hand. I would appreciate a solution, that works without manually setting navmeshes, nodes or similar things.

I want to implement a navigation / pathfinding for around 500 NPCs, that works for a dynamically changing enviroment (many moving objects). Examples for similar implementations are Picmin, Age of Empires or Left4Dead.


Version: A8 free
OS: Windows 10
Re: Pathfinding for crowds? [Re: gameplan] #462719
10/22/16 20:58
10/22/16 20:58
Joined: Oct 2007
Posts: 5,166
İstanbul, Turkey
Quad Online
Senior Expert
Quad  Online
Senior Expert

Joined: Oct 2007
Posts: 5,166
İstanbul, Turkey
Recast is for autogenerating navmeshes from level geometry.


3333333333
Re: Pathfinding for crowds? [Re: Quad] #462722
10/23/16 00:46
10/23/16 00:46
Joined: Jul 2008
Posts: 1,963
Germany
rayp Offline

X
rayp  Offline

X

Joined: Jul 2008
Posts: 1,963
Germany
500 npcs with acknex?
that is not realistic. Even left4dead source engine cant handle such amount of ents. Dead rising maybe. That was the reason why capcom was impressed an bought bluecastle.
It took me years to have 50 pathfinding moving and animated ents with 60fps.
anyway good luck wink

Greets

Last edited by rayp; 10/23/16 01:03.

My entry...your exits
Zombies dont like pink glow slime, fact!
"We gonna rock down to electric avenue" "One way ... or anotha ..."
"Hey Griswold ... where u gonna put a tree that big ?"
1998 i married my loved wife ... Sheeva from Mortal Kombat, not Evil-Lyn as might have been expected
-=GOOGLE IS SKYNET=-
rayp.flags |= UNTOUCHABLE;
Re: Pathfinding for crowds? [Re: gameplan] #462725
10/23/16 08:45
10/23/16 08:45
Joined: May 2009
Posts: 5,107
Caucasus
3run Offline
Senior Expert
3run  Offline
Senior Expert

Joined: May 2009
Posts: 5,107
Caucasus
Hi!
Originally Posted By: gameplan
I want to implement a navigation / pathfinding for around 500 NPCs, that works for a dynamically changing enviroment (many moving objects). Examples for similar implementations are Picmin, Age of Empires or Left4Dead.
Well, it may work but don't forget about models, bone animations, shaders etc... They will probably ruin the whole thing and at the end you'll get around 15-25 fps (that's what rayp is talking about I think). Maybe if it's going to be hardly optimized (well, it depends on the type of the game you make), well, I can't guess, let's see how it turns our, I'm curious.

Best regards!


Looking for free stuff?? Take a look here: http://badcom.at.ua
Re: Pathfinding for crowds? [Re: rayp] #462729
10/23/16 13:33
10/23/16 13:33
Joined: Sep 2009
Posts: 926
Budapest
Aku_Aku Offline
User
Aku_Aku  Offline
User

Joined: Sep 2009
Posts: 926
Budapest
The Conitec had a demo that showed hundreds of animated models in an infinite loop.
As i remember it was cca. 6 years ago.
Here: MMO test you can download a special version of A7 what aimed exactly the same, showing 500 animated models at 60 fps.
Maybe A8 can give more performance nowadays.
In the zip there are two test executables.
1. for testing crowd.
2. for testing terrain.
Good luck!

Re: Pathfinding for crowds? [Re: Aku_Aku] #462731
10/23/16 14:51
10/23/16 14:51
Joined: Jul 2008
Posts: 1,963
Germany
rayp Offline

X
rayp  Offline

X

Joined: Jul 2008
Posts: 1,963
Germany
Standing animated models is one thing. Pathfinding moving and animated another thing.
looking forward to this.
greets


My entry...your exits
Zombies dont like pink glow slime, fact!
"We gonna rock down to electric avenue" "One way ... or anotha ..."
"Hey Griswold ... where u gonna put a tree that big ?"
1998 i married my loved wife ... Sheeva from Mortal Kombat, not Evil-Lyn as might have been expected
-=GOOGLE IS SKYNET=-
rayp.flags |= UNTOUCHABLE;
Re: Pathfinding for crowds? [Re: rayp] #462737
10/23/16 21:23
10/23/16 21:23
Joined: Mar 2011
Posts: 3,150
Budapest
sivan Offline
Expert
sivan  Offline
Expert

Joined: Mar 2011
Posts: 3,150
Budapest
the best to check what other games use in the similar genre you want to make. probably most of them select different methods not accidentally.

With 3DGS, I could achieve only 25 FPS as an average, handling about 400 characters (moving in group formations) in my RTS testbed level (filled with buildings, trees, and using shaders like water, shadowmapping etc.), when reached a good enough quality, after many-many optimizations. It required to implement my own complex pathfinder and movement system... with A8 Pro edition where I have terrain LOD and GPU animation.

But a lot depends on what quality you need, how many of units are visible, their bone and vertex number etc. If the behavior is very simple you can have more, but game engines are in general not for this purpose, rather for something like an FPS.


Free world editor for 3D Gamestudio: MapBuilder Editor

Moderated by  HeelX, Spirit 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1