Implementing pathfinding in tiled 2d world

Question

I have a 2d world made of tiles. Tiles are either passable, non-passable or have some sort of movement penalty.

All entities and tiles have their own hitboxes and sizes for collision detection. Each tile tile has dimensions of 16x16px.

Most examples I've read seem to suggest that we're moving from center of one tile to the center of another tile. And as we see from the picture below, that red part looks hardly optimal nor it doesn't take entity size into account. Also pathding nodes are also placed into 2d array, with only 8 possible directions from each node.

But wouldn't actually shortest path be something like this?

How should I implement pathfinding? Should tiles be splitted into smaller nodes for pathfinding or is there some other way to get more accurate routes? Even if I splitted each tile to have 10x10 pathfinding nodes, It still wouldn't find shortest line between 2 points.

Should there be more than 8 directions and if so, how should that be implemented?

For example if my world was 50x50 tiles big, how should the pathfinding map look like and how it should be generated?

Answer 1

It depends on your definition of "shortest path" and what you plan to do with it.

In your example, it appears that you consider a valid move to be from the center of one tile to the center of any other tile in unobstructed view. How you'd validate moves to partially obstructed tiles is not clear. This differs from the geometrically shortest path, which would obviously hug the wall, and the realistic shortest path, would would use a unit width and turn radius to avoid walls and sudden changes in direction.

A common approach is to use A* as usual, and then post-process the path in a number of ways to optimize and smooth it. This works both for grid based worlds like yours, and for more general navmeshes.

Gamasutra had a nice overview of this called Toward More Realistic Pathfinding, with a variety of ideas and techniques from smoothing zigzags and adding curves, to optimizing paths for units with acceleration and direction.