Where to start with pathfinding AI?

crisp

So I'm currently working on a 2d rpg where NPC's to go through daily routines. Really just to move about as the day goes on and then return home at night. (Think Harvest Moon or Stardew Valley)

I thought about just using some waypoints that they could move to, one after the other. The reason this won't is that the player can ask an NPCto follow him/her. When they are done following they could be anywhere on the map, and i'd like them to resume their daily routine one they finish following.

I'm really just looking for some high level strategy, what things should I be looking up and stuff like that. I don't know very much about pathfinding yet so any advice would be greatly appreciated!

Thanks for reading this far!

Mouledoux

The 2 main ones you should look at are:

A* -> https://en.wikipedia.org/wiki/A*_search_algorithm

here is a helpful example someone made -> https://gigi.nullneuron.net/gigilabs/a-pathfinding-example-in-c/

and Dijkstra's ->https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

an example by someone else -> https://www.geeksforgeeks.org/csharp-program-for-dijkstras-shortest-path-algorithm-greedy-algo-7/

Both of these are very common in game dev, and both have their advantages. They are also very similar to each other under the hood, the only difference is speed.

Dijkstra's will give you the shortest path from A->B, but it will have to check EVERY path to get there.

A* will find you a path much quicker (in terms of computer processing) than Dijkstra's, but it may not necessarily be the shortest.