Pathfinding in a City

Unity Engine
,
1

Hello,
I am currently building up a city in Unity3D and wonder how I would efficiently build up some sort of movement for NPCs walking around the city.
I have tried a lot on my own with own pathfinding scripts which turned out to be neither efficient nor really good.

So this is what I came up on my own without NavMesh:

[gypwc

The problem is of course that the pathfinding is crappy and that the character does “calculate” dynamically the next path so it stands still for some milliseconds upon reaching the destination.

The idea I had to fix this was using NavMesh which uses points.
I am not really sure whether this is good for this case or rather bad.
My idea was to create a dynamic environment, meaning the script applies for every type of city without using points.
Currently I get all the sphere overlaps and choose a path randomly, I tried to never access the previous destination to prevent this sort of back and forth, but it does not really work out well.

My setup is that I would tag every walkable prefab and the character searches for these around him to pick the next destination.

This is, in my opinion, quite dynamic. NavMesh though has a rather not dynamic system where I would have to define points for characters to travel, so what is your idea on that?
1. Improve my own script
2. Set up paths individually ( How would I go for a 100 npcs where I would like to achieve some sort of random flow like in a city? )
3. Does navMesh maybe have some sort of thing I try to achieve?

Furthermore I would like the characters to be dynamically capable of interacting with other objects, such as benches to sit on (by chance) or I don’t know, sit on a bus stop and get on a queue to step into the bus and get out somewhere else.

2

NavMesh in Unity does not rely on static paths. Instead you simply “tag” surfaces as walkable by adding them as sources to a NavMesh Component and bake out a NavMesh, which can even be done on runtime (though this requires extensive tweaking and testing, and still has some tricky edge cases like offmesh links being diffcult to place).
Then you simply let your agents pick a destination as a point in 3D space, and they will calculate a path contained by the NavMesh which they then follow.

For interactions and such you could simply tag objects like benches and such with separate scripts, then have your agents simply consider what they “want” to do (like sit down, buy a drink, …) and search for the nearest object that can fullfill that need, take that object’s position, and set it as the destination for your agent. Simple as that.

3

If I would choose the “find nearest bench” solution, wouldn’t that be cost inefficient if I got a lot of benches and also a lot of objects around the npc?

4

That depends how you implement it. If you first search for all the objects in the scene and then check which one’s the closest, then it will get inefficient more quickly yes. However, it is perfectly possible to cache all the benches beforehand (at scene start for example) in a static list. Then you only need to iterate over the benches and check which one’s closest.
You can even optimize that further by, instead of checking Vector3.Distance(character, bench), you can check for squared distance, this avoids an expensive squareroot calculation for each distance check, and since they’ll all be squared the closest bench will still come out as closest.