As well all know, DF's connectivity map works great for walkin dwarves, but not so great for flying or amphibious creatures. This is because of the Connectivity Map, which determines whether the A* pathfinding system should be run at all. If the spot can't be walked to, the game assumes it can't be reached, even if it could be reached via flying.
This problem gets worse the more movement types you have, such as tunneling, or climbing. Because you'd not only have to make a connectivity map for each movement type, but also for each COMBINATION of movement types, which is the harsh part.
I'm not sure if Toady has considered methods by which multiple movement types could be implemented, but here's one. It would likely require a couple days of coding, and more days optimizing, but it's a method, and I'd like to see what people think.
Assume we have 8 different movement types requiring continuous movement (thus, removing teleportation). We don't have eight right now, but maybe one day. Let's say Walking, Swimming, Magma Swimming, Flying, Climbing, Jumping, Tunneling, and Demolishing. Eight is convenient because it's one byte. We can add more bytes too, for example "Trap Avoid" or some such.
Step one utilizes the current system for making connectivity types, except this time we do it 8 times, a linear increase in processor requirement, so we're pretty safe. Each tile is thus flagged with a number like 10011100, which means that if you can walk, fly, climb(aka crawl), or jump, you can move through the square.
Then, the game must find all adjacent numbers, that is, all adjacent tiles with 10011100, and mark that as one continuous region. From this region, create a nodal graph of the map. This must be done once every time the map changes-- otherwise, you just need to keep the same map. Remember, this is a linear increase in processor time, so it's expandable.
Now, for connectivity checking, first the game sees whether you are within the same exact region, just like now. If not, however, it then checks to see if there is a path utilizing all your movement types. If each character is assigned a byte determining how they can move... such as 11000001 (for a troll perhaps), just do a Logical AND with each node of the connectivity map, then use a flood fill technique to see if it is possible to get to point A to point B. After that, A* to your heart's content.
Here's an example.
Aribtrary Map:
01101100 10110011 11111110
11010100 11100111 00110110
00111011 10101010 01010101
Our creature's movement: 01001000
AND map:
01001000 00000000 01001000
01000000 01000000 00000000
00001000 00001000 01000000
Truth map:
101
110
111
And there's our connectivity map!
EDIT: If this is too slow, you could even cache such a map for each movement type possessed by a creature on the map.