OK, I've developed a navigation system and ...

OK, I've developed a navigation system and I am thinking of open sourcing it to get people to use it and hopefully improve it.

Why did I develop another nav system, well I found that the default system and even other systems online were good but not great at large crowds or in my case hordes of zombies. I had seen World War Z and wanted to do a game in Unity that would allow thousands of zombies to move and attack the player.

So I did what I recommend other people to do prototype a simple setting in Unity and try the solutions you have available. Unity's navmesh (this was a while ago Unity 4.x) did not perform so well and I had purchased and used the rather good A*Pathfinding solutions which was better with large Unit counts but nowhere near the level I wanted.

So I looked around and found a potential pathfinding solution that could be massively better for large crowds, and I implemented it and it worked.

My game evolved changed and got sidelined then I thought should I improve and release my navigation system on the Asset store?

It's not at the level where I could in all honesty push it onto the Asset Store (for sale) as it would need someone with coding skills to use it.

But what if I the 'complainer' on the Unity forums released it under an open source license so we as a community could use it and improve it?

PS it also works in 2D (with a few code changes).

Video of Zombie Horde Test 02

1 run PC standalone (with Fraps running), Quality setting Fastest
3,645- None
3,626 - Unity's
3,065 - A*
6,384 - Arowx's

Video of Zombie Horde Test 01

Hmm, well things did not go as well as I had hoped (see the video in the first post).

Running on my PC the scores were:
1918 - None
1882 - Unity's
1909 - A*
1755 - Arowx's

I think it might have been FRAPS as on a run without it I got these results.
5237 - None
3311 - Unity's
3308 - A*
3581 - Arowx's

But look at how well my solution does a better Zombie horde, it's not just the quantity look at the quality!

Zombie Quality comparison:
None - Well they don't even crowd.
Unity's - Not much better really.
A*'s - Much too organised and deadly for a Zombie Horde.
Arowx's - Yay dumb crowding Zombies and nice and slow.

Uploaded Video 0733 so it only took about 12 hours give or take a couple of hours for food/drink/breaks.

 

Which algorithm?

 

How about a demonstration of some kind?

 

How about a demonstration of some kind?

 

And/or some stats. We don't actually know anything about it yet.

When you say "large crowds" what are you talking about? Dozens of agents? Hundreds? Thousands? Tens of thousands? On what hardware?

Dynamic or static nav data? How is the nav data generated?

 

There's no vote option for "who cares since you show us nothing"

 

Yea demo/stats please. No offense, but the OP's technical knowledge/ability in prior threads doesn't inspire confidence. This could alter that impression (and hopefully not reinforce it)

 

Definetely release it for free. You'd be surprised how much value having other people read your code will bring.

And if it turns out to be a hit, simply release a pro version with a couple more features.

 

You should sell it on the asset store so the UnitZ clones will have better navigation.

 

The zombies in UnitZ have no built in navigation. It's just straight walk towards the player and jump every few seconds.

Despite this the zombies perform pretty poorly. Pulling out all of the zombie character controllers and replacing them with nav mesh agents actually improves performance.

That's not a trivial piece of work. UnitZ has a pretty messy code base. Adding in any substantial improvements isn't easy. Which is possibly why no one ever does.

 

I wonder if jim sterling knows how to read code. It'd probably be pretty eye opening if he read the source and realized that, sure... it's a jumping off point, but it's a mess.

 

OK, I'll put together a test on my PC that compares my nav system, A*Pathfindings and Unity's in Unity 5.2 and then video it for you. Also last time I tested it was using 4.x so maybe my nav system is not needed.

Expect hordes of red capsules chasing yellow capsules and green capsules shooting the red horde.

It may take a bit of time on my marks go... 17:11 BST off for a quick coffee!

I'll be back.

 

use robot kyle

 

Release it for free and I have a feeling it won't be as good. Definitely hand out a demonstration... free webplayer demo or mini-package.

 

Confirmation that @Ryiah and @Meltdown are controlled by one person.

 

Hmm, well things did not go as well as I had hoped (see the video in the first post).

Running on my PC the scores were:
1918 - None
1882 - Unity's
1909 - A*
1755 - Arowx's

I think it might have been FRAPS as on a run without it I got these results.
5237 - None
3311 - Unity's
3308 - A*
3581 - Arowx's

But look at how well my solution does a better Zombie horde, it's not just the quantity look at the quality!

Zombie Quality comparison:
None - Well they don't even crowd.
Unity's - Not much better really.
A*'s - Much too organised and deadly for a Zombie Horde.
Arowx's - Yay dumb crowding Zombies and nice and slow.

Uploaded Video 0733 so it only took about 12 hours give or take a couple of hours for food/drink/breaks.

 

Heh! I agree with you on the quality. An organized zombie horde is an unwanted (and frankly, disturbing) result.

 

Can I recommend you take a look at Mikko Memomonen's Recast and Detour libraries? They're open source, written in C++ and the Detour library has crowd pathfinding. It might give you some inspiration. I'm using it to write a bot for CS 1.6 and it works well.

Libraries at:

https://github.com/memononen/recastnavigation

 

Might work for a hive mind, but in most cases zombies are disorganized and falling apart so yea. Good work @Arowx .

 

Very cool. I sincerely hope you will opensource it on some liberal license like MIT or BSD.

Does this check on that?

 

@darkhog
It does scan the level on the first frame (it does not run from baked data at the moment) so could work well with procedural levels (but it is a slow process).

Updating dynamically is not a feature at the moment it would take a level re-scan and this would probably be too slow for frequent updates, it should be possible in theory with more work.

It is a top-down '2.5D' scan of the level so currently does not support multiple levels, e.g. bridges will work but you could not get a troll to hide under the bridge. Would probably need a major overhaul to do a full voxel scan of the level and a 3D nav system (currently 2D).

 

OK I'm going to go over the test again, not to happy with the movement patterns of my Zombies and also I want to add LOS tests for the troopers and see if I can improve it a bit.

The test is in 3D, so how about I try a 2D sprites only version as well?

I also have an idea I'm thinking of trying that could massively improve my approach, but that will take a bit longer to implement and test.

 

How often are the zombies pathfinding? Are they pathfinding in groups? Depending on the resolution of the grid, you can cache paths or give all zombies on the same node going to the same target, the same path.

Maybe:

Code (CSharp):

1. Dictionary<Node,List<Zombie>> zombieGroups;
2. foreach (Zombie zom in ZombiesGoingToPlayer1) {
3.     if (!zombieGroups.ContainsKey (zom.CurrentNode)) {
4.         zombieGroups.Add (zom.CurrentNode, new List<Zombie> () {zom});
5.     }
6.     else {
7.         zombieGroups[zom.CurrentNode].Add (zom);
8.     }
9. }
10. foreach (KeyValuePair<Node,List<Zombie>> group in zombieGroups) {
11.     Path path = GetPath (group.Key, DestinationNode);
12.     foreach (Zombie zom in group.Value) {
13.         zom.GivePath (path);
14.     }
15. }
16.  

This would work especially well for zombies because they tend to clump up and a lot of pathfinding becomes redundant. If 50 zombies were standing on the same node, 49 less paths would have to be calculated.

 

Not sure about Unit's but A* pathfinding caches and reuses paths, not sure how clever it is but judging from the in IDE debug GUI the pathfinding does overlap well.

 

A* is an algorithm that pathfinds (caching paths is extra and often impractical... I.e. it loses all benefit when the map changes). Which implementation are you using?

 

Apologies, A*, in this case, is Arongranbergs multi-threaded A-Star pathfinding solution, as you can see from the test it is very good link

 

How about a demonstration of some kind?

 

See the 1440p 60fps video comparing 4 versions of pathfinding

 

Can I just apologize to Unity, my bad, my code had a bug.

But I have also had to raise a bug as running the test 3 times always crashes and on the test using the Unity navmesh???

With my bug fixed and tweaks to my navigation system and an improvement to the troopers via LOS checks the scores on the door are:

2 Runs PC Standalone
7168 - None
7080 - Unity's
3836 - A*
6976 - Arowx's

Not sure why A* has dropped so much the code fix for Unity should also have sped up A*?

The sim uses a simple Unit component overloaded for each pathfinding solution.
Zombies just try to move in the direction of civilians(yellow) and troops(green) or random move
Civilians just try and move away from zombies or random move.
Troopers just shoot zombies they have line of sight on and random move.

 

You are not going to believe this but I changed the Quality setting to Fastest and here are the scores:

1 run PC standalone
30,927- None
6,675 - Unity's
2,049 - A*
26,805 - Arowx's

Higher is better.

The test uses the Application.targetFrameRate = -1; option but previously used the Fantastic Quality Setting (which I believe sets vSync to on).

Actually the No-Pathfinding Zombies do too well here.

I must have some bug in my A* test approach as it should be much better than this???

 

PS still working on that potential speed up, need to finish implementing it and then test it.

Will look into fixing the A* test as I'm sure the solution I am using is multi-threaded so should be way faster than this.

 

I videoed the benchmark with Fraps but as stated before this does impact performance.

1 run PC standalone (with Fraps running)
3,645- None
3,626 - Unity's
3,065 - A*
6,384 - Arowx's

 

nice progress. It's interesting that setting your quality to fastest made this run faster. How does that work if this is running on its own thread?

 

It's the Unity Quality setting, it turns off vSync and the waiting for FPS target that unity has in Fantastic mode.

It also reduces rendering quality to maximise performance over quality e.g. shadows.

The tests run as fast as they can within Unity, so it should provide a better idea of each pathfinding systems performance.

Although I might need a larger test area and more units to really stress test Unity now?

 

Does yours allow for dynamic runtime solving so you dont have to bake it because I could see people paying for that

 

Not at the moment. You can re-scan but at the moment you would have to do it for the entire level, that's a lot of sphere casting.

I'm working on an improvement that I hope should increase performance and make it easier to dynamically adjust the levels pathfinding.

Once developed, I will add the updated version to the test lineup for comparison. This could take a while though.