• Create Account

## Advice to someone learning pathfinding?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1Aspirer  Members

544
Like
0Likes
Like

Posted 28 November 2013 - 08:41 AM

Just found out Unity's NavMeshes, etc. aren't available in the free edition, so I'm going to have to take to pathfinding the old fashion way--coding it myself.  This is going to be an entirely new endeavor for me.

Any advice?  Like things to avoid doing, what topics are basics/which are advanced pathfinding topics, what I should definitely have an understanding of before jumping into it (theories, programming aspects, etc.)?

Also, just out of curiosity, is this the hardest part of AI programming? If not, what do you think is?

### #2KnolanCross  Members

1940
Like
1Likes
Like

Posted 28 November 2013 - 09:28 AM

All depends on how much performance/precision you need.

Notice that a pathfinding algorithm is one thing and navmesh is another entirely different thing.

The most popular pathfinding algorithm (and the fastest known) is A*, you may find a very detailed tutorial of how it works here:

A* algorithm is a little complicated, but you will be able to code it yourself without any major issue if you dedicate some time to it. You will also find it coded in a lot of places (my own blog has a C version of it). Most versions are not top optimized, but they may be fast enough for your needs.

About the navmesh, A* works on any graph and navmesh is just a graph very well known for being efficient in the representation of game spaces. It is also pretty complicated to create. There is an opensource program that creates navmeshes, its name is recast, you may find it here:

And a great study of how it works here:

You should keep in mind that you can use much simpler approachs, such as A* with a grid (which is a matrix telling where your character can move and where it can't). It is a very simple solution that may be fast enough for your needs.

Of your last question, depends on what AI/pathfinding you want to implement. If your AI is a monster that walk to a character, attacks and use a spell with 30% chance per second, and you want to use Heap optimized A* with navmeshs then yes, this will be the worst part. If you want your monster to adapt to 30 different character behaviors, analizing possibilities with heuristics and you plan to use a simple A* implementation with grids, then no, it won't be.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).

### #3colonycapture  Members

110
Like
0Likes
Like

Posted 29 November 2013 - 02:48 AM

Ooo nice. The previous poster all had great stuff for your pathfinding problem. What I'd mention for advice is that Unity has LOTS of stuff in the asset store for pathfinding (You are NOT the first person to have this problem). And the most difficult AI I've ever had to learn about and use in games is probably neural networking.

http://en.wikipedia.org/wiki/Artificial_neural_network

Ps. If you want some AI Tutorials we actually did a huge AI tutorial (Using the Strategy AI pattern) for promoting our project whose goal is to teach people game development. Myself and one of my lead programmers focused on AI in school and in the industry so it's something we really enjoy =).

Edit: I thought Unity supported NavMesh obstacles for the free version. Can you not use these:

http://docs.unity3d.com/Documentation/Components/class-NavMeshObstacle.html

Edited by colonycapture, 29 November 2013 - 02:49 AM.

Check us out at:

339
Like
0Likes
Like

Posted 29 November 2013 - 10:27 AM

No there isn't NavMesh in free but there are alternatives.

http://arongranberg.com/astar/ for a start.

Just look around the Asset Store.

### #5ferrous  Members

5773
Like
1Likes
Like

Posted 03 December 2013 - 05:17 PM

Basic pathfinding is actually fairly easy, and mostly agnostic to what you are navigating on (Navmesh, grid, hexes)

If you're worried about it being complex, or just want to get something running and have it be fairly fast, just use aron granberg's stuff.  I was able to get it running really quickly with the documentation and samples he has, and had 30+ things pathfinding in real time without issue.  You may find that the tile/grid stuff will work just fine for you.

If you end up wanting a more complicated motion planning scheme (Directional or turn radius, physics constrained, etc), you'll end up needing to do it yourself.  But that's probably way more than you need, depending on what you're doing.  (I've done this too, and if you want me to expand on it I can)

Edited by ferrous, 03 December 2013 - 05:18 PM.

### #6Aspirer  Members

544
Like
0Likes
Like

Posted 07 December 2013 - 06:21 PM

Feel free to expand on anything that may help.

### #7ferrous  Members

5773
Like
1Likes
Like

Posted 11 December 2013 - 05:29 PM

Well, honestly, unless you really want to have an object with a turn radius, I would shy away from it, as the code is much more complex than other stuff out there.

http://www.gamasutra.com/blogs/MatthewKlingensmith/20130907/199787/Overview_of_Motion_Planning.php has a good overview of the various methods, but if you just want to do a game like Final Fantasy Tactics, or X-com, that's all overkill.  Heck, even a lot of RTS games don't go that far.  (Notably, SupCom uses flow fields, and the Relic vehicles use a form of Dubin's Car I believe.)  But Starcraft, for example, doesn't do anything fancy beyond a tilegrid.  EDIT:  Not to imply that the pathfinding and AI in SC is simple.

A directional component, on the other hand, isn't all that bad.  For example, in Space Hulk (Tabletop or recent PC/iOS release), the direction that the character faces matters, and turning a square facing costs a point.  To add that, all you really have to do is add that to the cost function, and keep track of what facing the character would be in at a tile/node in addition to the position.

Edited by ferrous, 11 December 2013 - 05:32 PM.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.