Pathing for 2D, sprite-based game

Question

I'm making a 2D, oblique-styled sprite based RPG. My game does not live in a 2D matrix (like Tetris), rather it's sprites animating over a tilemap. I am trying to set pathing rules for NPCs. I've considered a few methods to do this but am not sure on the path I should take (no pun intended).

The NPC's trajectory is set by calculating the angle between origin coordinates and next coordinates and moves at that angle. I'm sure this will lead to blocky movements as they move along an array of coordinates along their path.

So, to set pathing rules, I was considering the following approaches and would like some direction given my style of game:

• Manually define coordinates: For each NPC, define a set of coordinates for a given destination (a destination location set in my game). This issue with this is it will get tedious to set all the coordinates along the path.

• Pathing algorithm: I'd rather simply set the destination coordinates once, and perhaps use a pathing algorithm, such as Dijkstra's Algorithm, that the NPC can use to navigate the map. I am not sure if this will have any ability/effect on smoothing out the movement.

It was also suggested using the Rapidly Exploring Random Tree algorithm, but again... not sure if this is overkill for my game... and what the performance hit would be.

Here is a snapshot of my map. The red arrow is a sample path. The blue lines are collision rules defined around map objects.

I would love some guidance on this. I am not sure if something like a pathing algorithm is a) overkill my game, b) doesn't fit with my game style

Answer 1

I'm not sure I completely understand what you are asking, as it's hard to tell what you mean by your "game style", but I will say that a path-finding algorithm is not necessarily overkill, especially if you would like your NPC's to find specific routes around obstacles.

From my own experience with AI navigation, there are a couple of very popular types of pathfinding that are used, some of which use a pathfinding algorithm such as A* (a very good explanation here: Link) or even just immediate obstacle avoidance (such as seen here), although that's more applicable when using a physics engine I think.

But from what I can tell you're really looking for a pathfinding algorithm, and it would probably be very useful for you. A* is a fairly fast algorithm, and there are other similar algorithms and numerous variations that can give you great performance. If you only have a few of NPC's navigating at a time, pathfinding is almost certainly not a performance bottleneck for you.

Thinking back on it, if you mean that your game is 2D when talking about your "style of game", you can still think of your map as a sort of 2D matrix, because from what I can see of your screenshot it exists on an XY plane and therefore pathfinding seems to be a completely viable option for you.

As an extra note, since you seem to be using Tiled, this SO post about pathfinding may also be of use to you (even if you're not programming in Java).

I hope I was able to help, though I'm sure there are people here with way more experience on this topic than I have...