Ghehe, is someone finally making Heroes of Might and Magic 3 for MSX?

It was about time

Finding the best path or route is an NPC (read: very hard to solve) problem. A* is indeed one of the best approaches, but it cannot guarantee that the solution found is the best possible solution!

You could try a different approach: split up your map into rectangular "rooms" which interconnect through doors. Obstacles in your map need to stay *outside* of any room. The rooms don"t need to be all equal - thay just need to be rectangular and you need to know which rooms connect through which door. Then getting from A to B is a matter of finding a path through the rooms, from door to door. You still might want to use A* for that, but since you're not operating on map-cell level but on room-level, it will be a lot faster. Needless to say that getting from one door in a room to another is just a matter of drawing a straight line :-)
Again, this may not give you the shortest path but it will find a path considerably faster than having to A* over the complete map.