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?

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:

- http://www.policyalmanac.org/games/aStarTutorial.htm

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:

- https://github.com/memononen/recastnavigation

And a great study of how it works here:

- http://www.critterai.org/book/export/html/2

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.

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

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

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

Just look around the Asset Store.

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)

Feel free to expand on anything that may help.

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.