Hello there, I implemented my own A* a few months ago, it is grid based an uses an unordered list to keep the open list, in other words, it is pretty much the worst implementation performance-wise. It is fast enough for my needs, but I want to improve it, I implemented a heap for it and I also wanted to use a region approach.

So far my algorithm converts reagions, those regions turn into a graph, and the A* will operate on this graph. For instance, this input (where 0 means that the tile is not walkable and . means that it is):

000000000
0.......0
0..0....0
0.......0
0.....0.0
0000000.0

Will be converted to this region map:

00 00 00 00 00 00 00 00 00 
00 01 01 02 03 03 03 04 00 
00 01 01 00 03 03 03 05 00 
00 06 06 07 03 03 03 08 00 
00 06 06 09 10 11 00 12 00 
00 00 00 00 00 00 00 13 00 

This is a visual representation of the graph, all the same numbers (but the 00) are a region (every region is a square of size N) that are converted to a node in the graph. Each neighbor region has an edge with the cost so I can run the A* on the graph. The problem is, once I got the A* path, how do I navigate to it?

For instance, If I want to go from region 03 to region 02, I can go directly, but if I am at the botton left part of region 03 and try to go to region 02, I would cross a wall trying to go in a straight line.

Any ideas on how to use this approach? I was trying to do something similar to a navmesh (my game is 2d), to reduce the node number, but I am pretty stuck now.

I would avoid using regions if you can get the more naive solution to run fast enough. How big is your map?

Right now they are very small, I limited to 100x100 and haven't reached the limit yet.

This is a simplified form of navmesh pathing; you can probably draw some inspiration from the way navmesh pathfinding + steering are typically implemented.

However, as Alvaro suggested, it may be worth just doing the simple thing. You can easily path through hundreds of thousands of nodes in realtime if necessary with a good A* implementation.

Yes, I thought that this should be similar to a navmesh navigation, but I couldn't find any good material on that, the best I could find was this one:

http://blenderartists.org/forum/showthread.php?231535-How-Navigation-Meshes-%28NavMesh%29-work-compared-to-WayPoint-graphs

Most of the other say you can simply walk from one point to another, which is not truth in my case. If anyone got a good link, I am curious to read some more about it.

If your region allocation is done correctly, it should just be a matter of projecting a ray from the current position to the nearest edge of the next region on the path, and steering along that ray. There are of course a host of issues around path smoothing and realistic turning you can consider later, but that should get you started.