research: pathfinding - Githubissues

Have been using godot's built-in navigation so far, which works, but I think we can refine some details. Specifically, the way a player chooses where to stand when going over to talk to an npc -- current implementation feels a little clunky and could be refined.

@Batbro tagging you to help out on this one - any information you can find about pathfinding strategies, specifically for 2d top-down or isometric games, please add links/explanations/etc as comments on this ticket. Same goes for any thoughts, questions, concerns, whatever -- you have more knowledge in this domain (both games and vector math) than me, so please share!

I'm especially in need of anything you can find about the specific problem of walking over to something, facing it, optionally making it face you, and interacting. You see this in pokemon, undertale, etc - where the player character can walk over to an NPC from any direction, stop in an appropriate place, and orient themselves (and maybe the NPC) to interact. If you walk over from the left, you stop at the NPC's left. If you walk from below them, you stop below them. Etc.

The way our game currently works, each NPC node has a sub-node that acts as a marker for where the player should stand if they come over to chat. This works, but what I'd ideally like is for it to work more like it did in Pokemon et al. Smarter navigation based on where you start relative to the NPC, and probably making use of tile coordinates rather than on general points in space.

Note that we can do things like query the coordinates of the tile under an npc and use that to get the adjacent tiles; I also recommend reading up on Godot's Navigation2D and NavigationPolygon2D classes, which we're currently using. You can see how they're implemented in our game in the /game/systems/environment folder.

jackmakesthings / game-dev

research: pathfinding #104