What's up with Pathfinding?

News & General Discussion
1

Hello folks,

I know this topic has been covered multiple times, but fact is, Pathfinding and Waypoints are still an issue. Now of course there is an A* implementation from a 3rd party for Unity and I achieved nice results with it while testing it. However I encountered issues - essential issues, that cannot be ignored if you ever want to achieve a decent game. While the A* worked on single units, it will not work on multiple units anymore:
Either units will walk through themselves, or happen to start endless rotation-movements (like a carousel) while trying to reach the target point, or a moving obstacle/unit will have its original position (invisibly) blocked, although he already moved to another place. I can repeat that anytime.

Now, why am I mentioning this?
Why don’t I just ask the one person who provided this script? Because I have already read that this topic is very complex for himself. Because he is only a hobby programmer. And because you’ll never know when and if he works on it again! Don’t get me wrong, I appreciate such helpful scripts very much, but it’s unreliable.

So now what? Why is it so important anyway?
Behavior and steering of multiple units, and the ability to evade each other is needed everywhere! There exists almost no gametype without multiple units. Unity is a game engine and what kind of games can we create if pathfinding/waypoint-artificial intelligence lacks essentially? Is it puzzle games we have to stick with? :expressionless:

There seems to be a vote in the feedback section about it http://feedback.unity3d.com/forums/15792-unity/suggestions/565223-editor-unity-ai-support- which I hope gets lots of voices. I realized that this feature is much much more important than any other. Even more important than Voxel Terrain, Terrain Shader, Linux Player, or anything else…

AFAIK Kynpase is able to evade dynamic objects anytime. I’m afraid this solution might be too expensive for Unity, but there must be something usable. And such a system must be integrated into the game engine and needs official support.
I’m sorry if this sounds like a rant, but now I understand why people have requested a decent Waypoint/AI System for a long time in the forums.

2

Pathfinding is difficult to design in a generic way that is also optimal for all use-cases.

For example, a pathfinding algorithm for a real-time strategy game would be very different from one designed for an MMORPG, or a racing game, or a resource-management sim, or… you get the idea. (I hope.)

It is possible to build templates and libraries of useful pathfinding tools. It’s also possible to build, say, an RTS-specific pathfinding script. But a single, unified, one-size-fits-all, “Ultimate” pathfinder script? That’s a hell of a lot of work, and arguably not particularly useful.

I suspect someone will eventually build a suite of pathfinder scripts, perhaps based on a core library, and sold through the Asset Store. Each script would be optimised for a particular use-case, such as a game genre. You’d only need to buy the script you need.

3

There’s few good middlewares for pathfinding, covering almost any kind of situation/game to solve paths.
Kynogon, Xaitment, Ai-implant, etc.

4

None of which are integrated into Unity, so it’s a moot point.

The OP was discussing a particular Unity script library and whether it would be possible to fix its apparent flaws and extend it into a one-size-fits-all script (or, more likely, a library of scripts). I didn’t say it wasn’t possible, but it would be very, very hard to do. It’s not something you can throw together in an afternoon, as the very existence of those middleware packages you mention proves.

5

Unless you payed $50’000 per game its no mood point, its just the consequence that $0 to $1500 don’t pay millions for middleware nor give any ground to raise such expectations.
After all even $200’000 technologies don’t implement such middleware, they at very best offer you the possibility to put in your own license.

6

I agree with Marctro.

Shiva, UDK etc etc all offer built-in pathfinding solutions. The Unity pathfinding solutions are provided by the community - and get
some loving, but little, support.

UT seem to focus on other features, which I feel are of less importance than a good pathfinding solution.

7

Unity already has Beast lightmapping, PhysX for physics, FMOD for audio…

There’s no shortage of built-in middleware included in Unity, and much of it is offered for free in the Indie release.

That we don’t also get Kynogon or AI-Implant is a shame, but Unity is only on version 3.x, and has only even been available with a Windows editor since version 2.5! Give 'em a chance, folks. Rome wasn’t built in a day*!

  • (Okay, technically, Rome was built in a day. The alternative is that all those would-be settlers commuted to the Palatine Hill every morning from their original homes, and built an entire city, complete with palace, forums, walls, gates, etc. first, before anyone was allowed to move in!)
8

You are right, but it would be nice to know if a decent pathfinding AI system will be implemented in the near future, say in the next 1-2 years.

The fact that Shiva3D (which I don’t like because of different reasons) has pathfinding included puts Unity to shame. Without pathfinding you are stuck on almost any gameplay mechanism you want to achieve. To be honest I don’t know how good the pathfinding in Shiva really is and specifically the case whether a moving subject is able to avoid another moving subject. Does someone know anything about that?

9

Shiva pathfinding its quite basic, static, obstacle avoidance is up to you. Same as the Unity (community) ones. The difference is that Unity do not comes with a build-in pathfinding solution and Shiva does.
UE and CryEngine build-in pathfinding are pretty awesome and dynamic.

10

That might have to do that obth are shooter engines at their heart which are useless without path finding :wink:

None the less, the path finding you get in unity competition can easily be overtaken with Aron Granbergs path finding and behave is just a powerfull addition on top :slight_smile:

11

Quite simple…

Obviously it makes a lot of sense having such a component inside Unity but as they can’t do everything at once it will take some time. Could be already part of the V3 update cycle but will for sure be part of Unity 4.

12

Aron Granbers pathfinding is awesome, but still a non-build-in solution and to be honest, it does not come any closer to the ones featured on big players as (UE and CryE).

13

I tried out the Demo of Shiva3D and it seems that pathfinding works ‘halfway’ in their Technical Demo (the zombies). It’s by no means perfect, but it’s at least a stable tested base for starters. Obviously pathfinding is calculated via a Navmesh that can be created with very few clicks within the editor. In their Demo:

  • the zombies avoid obstacles
  • they don’t line up in a single row too obviously; some of them do, but others take paths sideways making it look much better
  • they rarely get stuck on walls or corners
  • they don’t “stack together” on the same position although they are sometimes standing side by side very tight; i guess its because the nodemesh is tight, however I have never ever seen 2 zombies on the same position
  • I also didn’t experience any “carousel movement”.

Some of these issues I experienced in either Aron Granbergs approach or in AngryAnt’s “Path” or bothof them… unfortunately. This is what I mean with “messing around with basics” and the difference between hobbyprogrammers or the official stuff integrates a solution…

14

But ants would probably walk right over them…

But you’d actually want formations in an RTS game. Especially one depicting the more formal warfare of old…

But some, presumably, do. In an RTS, this would be considered a bug. In an FPS, it’s less of an issue if your cannon fodder isn’t particularly intelligent. These are, after all, zombies…

Again, sometimes, you may actually want this behaviour.

(Also, it’s worth pointing out that doing pathfinding that takes full account of 3D space isn’t any easier. What if your enemies are spacecraft flying through a particularly dense asteroid belt?)

And yet, people who are trying to find their way around Milton Keynes (a deliberately planned and designed new town in the UK famous for its roundabouts) are prone to going round and round in circles.

Humans are fallible, but gamers expect perfection when their (virtual) lives are on the line.

Professionals are just hobbyists who get paid. The only meaningful differentiators between two teams of developers are skill and time. Good pathfinding is hard. Nobody’s denying this. My point is that perfect pathfinding that works for every single conceivable application, without any tweaking or optimisation, is damned near impossible. Even for the likes of Kynogon.

The first successful version of the 3D graphics middleware known as “Renderware”—you’ll see its logo when firing up GTA3—was the third iteration of that engine! AI middleware is a lot younger and therefore less mature. The R&D is still ongoing.

It may not even be possible to achieve absolute perfection: As with speech recognition, the simple fact is that we humans aren’t 100% accurate ourselves. We can recognise the problem and compensate for it, but how do you design a generic AI library to deal with pathfinding problems in a game-specific way?

15

I don’t know why you are quoting each phrase. Maybe you have missed my point. I hinted that the base of Shiva3D’s pathfinding is a good base to get started with and it has less flaws than both pathfinding hobbyist-projects in Unity. It also provides a nice integration into the game engine and easy access via the API. Once such a feature is officially and seemingless integrated into the engine it needs to be maintained and supported by official staff. A pure hobbyist can’t provide this service on the long run.

Also most games developed are not space games, but games in which it’s essential that multiple characters can walk on ground and find their ways to the target via different algorithms. UT provides literally nothing for that case, and this is absurd for a game engine.

Unfortunately however other reasons prevent me from switching to Shiva3D…

16

From the sounds of the issues you are finding with the “hobbyist” pathfinding frameworks out there now doesn’t sound to me like it’s a pathfinding issue…but rather a steering issue.

Pathfinding is simply a way to represent your game geometry in a virtual fashion that will allow your pathfinding algorithm(s) to find a path from point A to B (sometimes it’s the shortest path, or optimized by some other means… depends on which algorithm and what mods the user has made).

When the unit is actual moving along that path… that is no longer pathfinding but is instead an Autonomous Game Agent Steering problem. Things like formations, flocking, circling around a waypoint… all of these are definitely steering issues. While I must admit I’d love to see pathfinding in Unity as a stock… the packages out there currently definitely get the job done. I urge you to check out the UnitySteer package as this package will serve as a strong starting point to solve your issues.

Also stimarco makes a good point… pathfinding is something that is darn near impossible to optimize and smooth out for an arbitrary scenario. As far as I’ve learned (I’ve been into this stuff over the past year), it’s almost always going to boil down to a custom programming job at some point. But don’t kid yourself, there are some really good bases to go off of in the community already until of course Unity decides that it needs to be a stock feature.

Anyways cheers and good luck.

17

I’ve used the A* Pathfinding available here and it’s great.
The issues you are describing in your first post are more about how an “Agent” navigates around the path.
The pathfinding it self is fast and solid!

Maybe you DO want objects to pass through each other? (clouds moving around in a fun puzzle game?)
Maybe you want objects to “hop” along the path? The example code doesn’t do that either!
Maybe you wanted the ‘agent’ to follow a catmulrom spline path? The example code doesn’t to that either!

These are preferences for your project and it’s up to you to decide what you need.

I would prefer Unity didn’t implement a path finding soution as they’ll need to make it so generic and scalable that it won’t really hold up against others (and we’ll get threads like this asking why it doesn’t do explicitly what one project needs it to do). Unity should focus on the core technology of their engine.

Path finding, believe it or not, is an exotic gameplay feature that not all games need. In fact, in the broader scale of things and the hundred of thousands of Unity developers, I’d say path finding is a minimal aspect of the games out there.

If YOU need this exotic feature for your game… then write it! (as Aron did with the A* Star project) Unity has provided excellent solutions to very hard problems such as cross platform and ‘one click’ deployment and super easy workflow pipelines… that’s hard to get right and smooth but they’ve done it for you, that’s their service, not implementing exotic game mechanics and features. …but that’s my take on it anyway. :stuck_out_tongue:

All you need to do is write your game! :slight_smile:

18

I’d say DavidB is correct - you’re not looking for just pathfinding, but for local obstacle avoidance. Pathfinding finds routes, but it doesn’t tell you how to follow them. Should your agents go to the center of the the first area on the path, then proceed to the next; or should they follow a curve defined by the points in the path? What happens if they run into temporary obstacles which occlude part of their navigation route? How quickly does the agent turn?

None of those are pathfinding problems. On the other hand, considering this example:

http://www.arges-systems.com/articles/49/unitysteer-20-multiple-agents-example

The agents pick a spot and walk to it, avoiding any obstacles they encounter in their way. Once they reach it, they pick a new one and repeat. There is no pathfinding whatsoever in the scene, but purely local obstacle avoidance.

Both solve different problems. In this case we can get away with the lack of pathfinding because the area is pretty much a wide open field with some obstacles peppered here and there, but for more complex scenarios (say, a series of connected tunnels) pathfinding would be fundamental.

If you’re seriously interested in the topic, I recommend you check out Mikko Mononen’s blog at http://digestingduck.blogspot.com He has a masterclass on RVO coming up at AIGameDev: http://aigamedev.com/premium/event/session-collision-avoidance/

Cheers,

19

You are correct, it’s also about some intelligence for the units. I watched the Unity Steering example (also saw the original opensteer applets), however as I searched through the Unity forum some people were claiming that this system only works because the agents move purely random. They couldn’t get it to work when they tried to apply a destination for the moving units. For that case it seems that both A* and UnitySteer need to be combined. I don’t know if this is possible, because UnitySteer takes a random path depending on the situation, and A* calculates 1 fixed path ignoring moving units. Can anyone tell from experience that this works or is there any tutorial availabe showing how both of them are combined?

@urgrund: well I think it’s not that exotic if you look at today’s games. Most of them have multiple units which are able to evade each other. But you are right that pathfinding/AI must be customised for each specific case. I would however say that at least 80% of today’s games are some shooter/rpg/rts in which you need units to evade each other and don’t want them to stack together on the exact same spot. Therefore a basic implementation of pathfinding/evading mechanism by the game engine would have been nice.

If someone is interested in my specific problem, here is a short explanation:
For my specific case I have realized that I need the ability that units can walk in groups and that they must be able to evade each other when trying to reach the destination. Definitely true, that this is steering behavior. Does anyone know the old game Wizardry8 (2001)? There were groups of monsters roaming in the wilds and moving around all the time as a pack. Once they spotted the player, they were able to surround him from all sides. These are the requirements I need for my prototype. No special formations or ubertaktiks, just the ability to stay together as a group and encircle the player once they come close enough. Sounds easier as it gets. I investigated this further in diverse papers from gamasutra discussing Age of Empires movement and others ;):
The group movement can be achieved if you set 1 leader for the group all other monster follow it using a steering mechanism with always the leaderposition as the final destination (the speed must be the same for all monsters in order to avoid outrunning the leader). Once a player is spotted all monsters can freely attack him. If the steering behaviour is correct they would surround the player by themselves. The AI would try to get as close as possible to the player and thereby evade each other unit and as a consequence encircling the player.

Now I guess it needs an A* pathfinding for the group leader to roam around randomly and then an appropriate steering mechanism for the followers. Is this doable and which components do I need for that? Is it better to use AngryAnt+UnitySteer or AronGranberg+UnitySteer, or a completely different approach?
And third: there needs to be a collision preventing the player from simply walking through the enemies. Unfortunately this wasn’t the case in Arn Granbergs A* pathfinder. Although I set up a collider for a “moving obstacle” the player passed through it. Sometimes he was stopped for half a second or a second but in the end he still walked through it. I don’t know how to fix this but I have read in anothe rgame engine this could be a result of the way Unity3D handles movement: movement is a simply change of the position, while in other game engines it is highly recommended to use “linear velocity” instead of translation to get movement and collisions done correctly. Now this is a little bit disturbing, since all tutorials in Unity are only using simple translation…

20

This should be doable just with UnitySteer. You might have to animate the targets or activate specific neighbor avoidance behaviors as the units approach the player.

It’s true that I have seen AI go through objects, but I have not needed to fix that yet because I was able to tweak the steering behaviors where it was not a problem for my implementation. UnitySteer is a really nicely done tool, just play around with it to get an idea of what it can do.