Hmmm I would take a different approach. I watch a video of Tibia and it’s true that it doesn’t look good. I would go with the way that I think RTS pathfinding is made. Ok never read it anywhere but here is my guess.
If you observe carefully how RTS map are made you see that there seems to be 2 different grid. One grid for the buildings and the ‘‘doodad’’ (ex.: tree). These elements can only be place on a grid with big cell. The second grid is the grid for the unit where the cells are much smaller to allow the unit to move more freely.
When come the time to find a path between two very close points you just need to use the unit’s grid and check if you can go directly (in a straight line) to your destination. That way you get very good movement that dont feel like if you are moving around a tiled map. Anyway, the cell of the unit’s grid should be small enough that the player don’t notice it.
Now if you need to go to a very distant point, you use the building’s grid. There is a lot fewer cells to check so you will find a path much faster. If there is no path in the building’s grid there is no path in the unit’s grid either. When you get near your destination you can simply use the unit’s grid to find a straight path to the end.
Ok, all that is well but one problem will occurs. What happen if you have a building is build in your path while you are traveling amongst it? You need to detect this sort of thing to get a new path as soon as possible. The chance are that this building will stay there for a long moment so you can’t just continue and hope it will disappear when you will have to pass through it.
Finally, the biggest problem what to do about unit that are moving around the map and might block or disturb the movement of your unit. Well, there is no easy or optimal solution. If you check an RTS like Warcraft III you will see that the way they handle this problem is very stupid. Your unit won’t try to find another path unless it really hit the unit block the way or crossing the way. Even worst, since the pathfinding is mostly made using the building’s grid, it won’t even try to find another path if some unit are blocking the way and there is no other really really obvious path he could take really close to the point he is block. Ok that seems bad but do I ever realized that it was a problem when I play? Not at all so it’s good enough even for commercial quality game.
The general idea about avoiding other moving unit is to click look a bit overhead when you are moving to see if the path is still free, if it’s free continue walking otherwise get a small new path to avoid the moving unit and continue following the big path.
If you really want to go overkill, you can check how they solve that problem in Starcraft II. Your unit can push your other unit and ally’s unit if they need to pass. But that may become way harder.
