with this data structure, i can't find any algorithm better than A*. but there're many way to find path in a map.

like this one

http://www.david-gouveia.com/portfolio/pathfinding-on-a-2d-polygonal-map/

I didn't think of that, you are right. It takes about 10 secs for worst-case-no-path on a 512*512 map. Much too slow, obviously.
So, I somehow need to make the maps that needs to be computed smaller. First thing I would think of is subdividing the map in like 16*16 chunks.
But I have no clue on how to implement that with A*.
I would need to have information if one chunk can be accessed from his neighbours or something like that ... but I can't think of a way to make that work properly

Do you know any articles on that question? I couldn't find anything with googleing over an hour now.

More than 1 second is almost unacceptable for game!
Your thinking is very intuitive! And it's what come to my mind when i have to solve this problem!
In this case there should be 2 search. Short search for close range, long search for long range use regions as node! Short search should be fast, so the range should be 100-150. Divide the map in to clusters of NxN size. In each cluster do breath first search to detect regions and its connection. The cluster size is make sure the region is not too large so we can search path from 1 region to other with short search! But not too small, so the number of regions are not too many. In my current setup, Cluster size is 40, number of regions is about 270!

Long search : use simple search from region start to region goal. It's very fast. If it's reachable, we do short search from region start to its neighbour region. So each time there will be only 1 long search and 1 short search!

The main problem is doing region divide for all map is slow! it's just like running A* on whole map in worst case. So it should be update only clusters that changed. Like obstacle disappear(we update only the cluster that the obstacle is inside, or maybe not if it doesn't affect the connectivity at all) , if your map is quite static, it's very easy!

I did a lot of google search like u. There are some variations of A* that can be used like Hierarchical Abstraction and its family (HPA*...there are many upgrade,optimize...) : This link is good : http://aigamedev.com/open/tutorials/clearance-based-pathfinding/ and this one : http://www.ru.is/~yngvi/pdf/BjornssonH06.pdf

I also think a bout another idea. Using steering option. It's just like how people move in real life, a unit will just heading to the direction of it's location, if it's stuck, it will choose to steer left or right to avoid the obstacle very human-like ! It will be lighting fast this way. But decide to move left or right is trouble some, some time move left is openroad, and move right is deadEnd. If we cant choose the right way, when we reach deadEnd, we must running back all the way !

I didn't think of that, you are right. It takes about 10 secs for worst-case-no-path on a 512*512 map. Much too slow, obviously.

So, I somehow need to make the maps that needs to be computed smaller. First thing I would think of is subdividing the map in like 16*16 chunks.

But I have no clue on how to implement that with A*.

I would need to have information if one chunk can be accessed from his neighbours or something like that ... but I can't think of a way to make that work properly

Do you know any articles on that question? I couldn't find anything with googleing over an hour now.

You could split your map up into regions. Keep track of region entrances/exits. For example, in your last picture of pathfinding, you have these very large rectangular areas, and they only have one or two entrances/exits to each region. If you know you are in region 1, and want to get to region 4, you simply iterate over the regions first to see if you can get to region 4 from region 1, and in addition, you can pare down the pathfinding as well, as you can have your agent find the path to the exit of region 1 and start moving before finding the entire path to the goal.

Also, if the costs are not dynamic, you could pre-calculate them or cache path results between nodes and use the nearest point on the path as the starting node, etc.