How to write a basic pathfinding script

Archived Forums Questions & Answers
1

What are the basic principles involved in writing a pathfinding script? In my case, I'm confined to a hexagon grid, and want units to be able to move from one position to another on the grid.

If the grid is composed of separate gameObjects and each tile knows its neighbors, how would I be able to calculate the path from a starting position to the ending position taking into account blocked tiles?

Thanks for taking the time to answer this, Elliot Bonneville

FYI Have a look at this example it demonstrates the strengths and weaknesses of different pathfinding algorithms

 –

5 Answers

5
3

For node based graphs or grids I would recommend A* (A star). It's maybe a bit advanced but it's one of the easiest and quickest algorithm and not that hard to understand. Almost every "simpler" algorithm will have problems at least if you have special cases like dead ends.

I can’t post a full example because that would be a very long post and I don’t have an A* implentation for Unity at the moment.

ps. A lot (if not all) RTS games use A* for the AI. It's a very very common algorithm. You should find tons of implementations and examples.

Hope that helps.

Aron Granberg has a A* plug-in which is free for non-commercial projects: http://www.arongranberg.com/unity/a-pathfinding/ You can find more pathfinding solutions here: http://answers.unity3d.com/questions/1523/pathfinding-tools-in-unity

 –

Thanks a lot. I will look into A*, Bunny83.

 –
2

well if you want a basic pathfinding, i would recommend that check your position and the distance to the objective, then check your neighbor position and its distance to the objective, compare the neighbors distance to see wich one is closer to the objective then move or change the current to the neighbor that had the less distance

if you want to get more complex and better algorithms you will need to check Operational Research, closest path.

4

I made a quick tutorial for those interested in learning how to setup a basic AI pathfinding using NavMeshes in unity 3.5

5

A* (AStar) Unity3D OpenSource (download My A* PathFinding OpenSource Project and open in Unity3D). Do Not Forget to read README.txt file ! Enjoy it !

Best Regards !

6

https://www.udemy.com/course/turn-based-strategy-game-development/

Pathfinding in action.