Even inadmissible heuristics can have their place, and it is easy to reason about how suboptimal they can be: you might want to trade off optimal results for performance (i.e. ignoring some part of the search space that should be searched) or to make an agent in a game a little stupid or stylized (e.g. prone to zig-zagging).
A* isn't how you get there, it's how you decide how to get there. The output is the shortest path, and that's what you actually follow.
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.
It works really wells for many situations. If I am making a top down strategy game (Think Civilization) then A* is exactly what I need, a fast performance hack that gives me the shortest path without anything weird going on. For different kind of environments, then yes it doesn't work. A* isn't very useful in a racing game.
It took me 3 hours to implement A* with hex tiles, got it working on first attempt (land tiles only), specifically for Civ type game. It gets complex when you want to group units so that they travel together. Adding water crossings with cargo ships and war ships is a different challenge.
If you want cohesion between entities pathfinding, adjust the cost when you do the pathfinding for tiles that has friendlies on them to be lower than their base cost.
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.
See the target/know which direction it is? Go that direction unless you see an obstacle, in that case go around the obstacle, eventually even backtracking if it turns out the obstacle was worse than you could see. Don't see/know the target? Brownian motion until you do or get tired. Have pathfinded to the target previously? The shortest path you saw while walking there.
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.
But humans do quite intelligently pathfind around objects they're aware of, and update their mental models with new information. The front door is locked? I'll go around the back.
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.
I'm not sure your complaint is actually that A* is bad, it's that the heuristic function is unfair (to the player, by giving the mob data they shouldn't have). A more sophisticated game could use a more interesting function like an estimate as to what direction the player's movement sound would be heard from.
Optimal pathfinding isn't always the right objective: for a good looking game agent reasonable pathfinding can often be enough, or even better.
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).
> See the target/know which direction it is? Go that direction unless you see an obstacle, in that case go around the obstacle, eventually even backtracking if it turns out the obstacle was worse than you could see. Don't see/know the target? Brownian motion until you do or get tired.
What a long and convoluted way to try to reinvent the A* algorithm...
This isn't an actual solution. Video Games have to do things fast. You can't just sit there and wait for a minute as you try brownian motion on hundreds of units. There are plenty of different solutions to get more realistic and natural pathfinding, typically navmeshes and then local node based movement. But you still need to go from a to b, somehow.
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.
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.
Everything you mentioned (Aside from Brownian motion, which is certainly the wrong solution) could be implemented with A* but with an incomplete graph.
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.
It's a performance hack, not how entities trying to get somewhere behave.