Beginner needs help with Pathfinding

Questions & Answers
1

Ok, what I have currently is a “Chess Board” type level, in which I can click each tile of the board to move my character. This all works fine. What I now need is some sort of path finding so that my character moves from tile to tile, rather than just making a straight line through everything to where I’ve asked it to move.

To better explain, imagine you’ve just started a game of Chess. You can’t move your knight, because a pawn stands in front of it. The problem I have is that if I select my knight, and attempt to move, my knight would just pass right through my pawn to wherever I’ve clicked. (I’m not making Chess this is just the best example I could think of to explain my problem without taking video)

My board has other “cubes” in the middle, but instead of going around them, my character clips right through them.

[x, x,  x,  x,  x, x, x]
[x, x,  x,  x,  x, x, x]
[x, o,  o, \/,  x, x, x]
[x, o, [], [], [], x, x]
[x, o,  o, (),  x, x, x]
[x, x,  x,  x,  x, x, x]
[x, x,  x,  x,  x, x, x]

Rather than the array’s path below. (The o’s represent the path taken, () represents my character, and the s represent an obstacle in the way)

[x, x,  x,  x,  x, x, x]
[x, x,  x,  x,  x, x, x]
[x, x,  x, \/,  x, x, x]
[x, x, [], [o], [], x, x]
[x, x,  x, (),  x, x, x]
[x, x,  x,  x,  x, x, x]
[x, x,  x,  x,  x, x, x]

I’ve taken a brief look at a tutorial on UnityGems I saw recommended to another user on A*, but as a beginner I found the tutorial out of my depth, or at least now explained in a way a beginner would understand. Does anyone know of a tutorial, or a something along the same lines, that could be helpful to me in my goal?

2

I’d recommend starting here - http://www.policyalmanac.org/games/aStarTutorial.htm

A* is pretty much the gold standard in pathfinding for games today and you should really understand the idea behind it before going further. When I first tried coding pathfinding I used this tutorial and I found it explained everything far and away better than any of the other tutorials I looked at. Once you have an idea of how to implement this in a general sense, you can probably either follow the unitygems tutorial, or implement it in your own way. Apart from this, you could take a look at using navmeshes and such, which I think is a unity pro option only and may not really solve your particular issue.

3

One of the most optimal general path finding search is A star, without a doubt. If you’re just a beginner at programming, creating your own implementation of A star is going to be tricky, because it requires knowledge of graphs and graph theory, priority queues, etc.

I suggest you find a solution that’s already created. Unity Pro has a pathfinding solution with NavMesh, and there are plenty of pathing plugins on the Asset Store, some are quite cheap (Simply A* - $10).

Though, if you really want to implement A* yourself (or have no choice), I suggest you read up on the following topics (roughly in this order, give or take):

  • graph data structures, what types there are(acyclic graphs, etc.), and how they can be constructed (adjacency lists, etc.)
  • graph edges and what types there are (weighted, directed, undirected, etc.).
  • common graph traversals (depth-first search, breadth-first search)
  • min heaps, and how you can make priority queues with them (C# does not come with a standard one)
  • Dijkstra’s algorithm: how it works (its a modified breadth-first search!)
  • heuristics: what they are and some common ones for A* (Eudlidean, Diagonal Shortcut, Manhattan Distance, etc.)
  • A* algorithm: how it works (its a modified Dijkstra!)