I don't like A*
It's a performance hack, not how entities trying to get somewhere behave.
It's a performance hack, not how entities trying to get somewhere behave.
It is complete and optimal, with provable properties.
Whenever there exists an admissible heuristic, you should use A* over Dijkstra's algorithm.
It's pretty similar to how people find the shortest path in an unfamiliar environment. If you're looking at a map for the shortest route to a city to the north of your current position, you probably won't spend a lot of time looking at roads going south, and you'll concentrate on road segments that get you crow-flies closer to your destination.
The way to think about water crossing with naval transports, is to consider those things to be conditions. You already have a set of condition when pathfinding. Just add another case for water. Make it so the requirement is that you’re either on a ship or there is a ship on the adjacent tile you checked previously, e.g N-1. If valid, set a flag and now every tile check that is water should be appropriate.
Al these require deep and complicated simulation of the entity though instead of solving a graph problem from omniscient perspective. Many topdown games really break my immersion when I see things just blatantly a-staring places.
Basically, things usually have limited information and it's weird to see them behave as if they don't. Plus on grids there's the cringe "diagonal and then straight" movement pattern.
For example, in a RTS making units follow a leader in formation can be more natural and less expensive than performing independent optimal pathfinding for all of them, while in environments with many obstacles staying away from walls (on a simplified graph of good positions) is usually more elegant than hugging corners (on a much more complex graph).
Your example also fails in several really obvious ways. What if there is a pool of mud or water in the middle of the path, it IS traversable but doing so is not ideal? A* you give this a high traversal cost and you'll naturally path around it. Your solution will have the object going through high cost but traversable areas in strange ways. This is going to be worse, as players will just kite and exploit this fact.
You can achieve exactly what you're describing by hiding information entities do not have from their pathfinding.
Graphs aren't the problem, and thinking along those lines won't get you where you're trying to go.
The point of movement for npcs in a videogame isn't to behave realistically (or to be simulated fully), it's to produce engaging and challenging behavior to the player. In 99% of cases giving characters, like enemies in an action game, some extra information to enable them moving towards the player is the correct choice, people are fine with suspending their disbelief if the alternative is npcs giving up or running around like brownian particles, which does not make for a good experience.
Almost all the time the correct choice in game design is that it's fun and interesting, unless for the exception where you're literally building a real world simulator.
What a long and convoluted way to try to reinvent the A* algorithm...
I've seen it work that way in an RTS before. Fog of war will make a unit unaware of what the terrain actually looks like and the unit will head straight in the direction of where I told it to go until it finds a cliff, then it starts trying to go around it.
Welcome to game development, where fun and performance tends to be more important than realism :)