Pathfinding Algorithm, grid to regions

You might want to look up rectangulation and rectangular partitioning algorithms. It has actively been researched in other areas, specifically for VLSI and chip manufacturing, so you may need to look up some literature with those terms. But this is a very active area of research (basically anything that has to do with computation geometry is). In the general case, rectangulation can be quite difficult and most of those algorithms are probably not fast enough for your needs, and quite frankly, you probably don't need something that general or optimal. Check out http://www.math.unl.edu/~s-dstolee1/Presentations/Sto08-MinRectPart.pdf

I think you'll find that an optimal solution will be quite difficult to achieve. Without going into a lot of digging and careful reading of the literature, I suspect this problem is NP-complete. http://mathoverflow.net/questions/132603/algorithms-for-covering-a-rectilinear-polygon-using-the-same-multiple-rectangles not exactly the same problem, but very similar to yours.

Am I correct in understanding that your search space is 16 * 16 * 64 = 16384? If that's the number of nodes you have in your A* search space, it's large but still manageable without significant optimization... My game currently has some levels which can have 10000 nodes if I force a very fine nav mesh resolution and with ~80 agents I still have ~300 FPS (can't tell you the A* search time since I haven't instrumented that). It's not completely smooth, but it definitely isn't as bad as 30 ms, so I don't agree with your assertion that "this is of course to be expected". My A* implementation isn't hyper optimized or anything.

I think your best strategy right now is to drop the quest of "minimum" or optimality and go for a reasonable reduction in the search space. Try something dead simple first, like trying to build the largest cube/square and just go in the same direction every time. Perhaps before even that, make sure your A* search is reasonably performant. It doesn't sound like you have a very good implementation to me, but I need a lot more context to be able to know. Are your data structures designed for good cache locality? Are you using a decent priority queue to maintain your open set?

I've found that in my own A* implementation, the biggest gains were in simply making the initialization of the graph faster. My first implementation had this terrible Array of Structs format where each node contained all of its A* state information. For me to initialize the whole graph required individual setting of f, g, and parent states on each node. Very bad for memory performance. I rearranged the data structures to be a Struct of Arrays format where the graph now contains an entire array of f, g, and parent values and now initialization of the graph are very fast memsets() on entire blocks of memory. There are some other clever ways to make the initialization closer to O(1) time but I didn't want to deal with that.

This was a very simple transformation for me to make and yielded enormous performance improvements, so much so that I basically have come to a point where I just don't have to worry about A* performance in my game.

If you are running A* on a grid, the "Jump Point Search" algorithm is something that allegedly can speed things up dramatically. I suggest you look into that first.

Yeah, jump point doesn't expand every intermediate node in a straight line path, it tries to move as far as it can in each cardinal direction.

There is a major limitation with jumppoint search, and that is if you have different costs for your terrain. (Ie a muddy region that units can move through, but it's slower, as opposed to binary passable/impassable -- it doesn't handle those kind of cases very well)

I've done something similar before. It is by no means an algorithm of creating a guaranteed minimal amount of rectangles, but it did a pretty good job. What I did was to calculate distance to walls in one pass. Nodes next to walls/solids are 1, nodes next to them are 2, etc. This basically maps a gradient to the free space of the node. Then I did a 2nd pass and started from the node with the highest distance value, expand a rectangle from there in each 4 direction 1 step at a time until it can't expand anymore. Mark those nodes processed, choose the next unprocessed node with the highest distance value and repeat.

That said, I would agree with the other people that I would probably not go down this rabbit hole for an optimization. You can probably get it working fast enough with simpler means. I would probably even consider influence map style flood fill pathing before I went through the trouble of merging into rectangles.

It might be advantegeous to work out a method of having individual units (or groups using a 'path') NOT have to recalculate their path to target constantly (save path and recalculate only when a significant change calls for it). That deals with whether the terrain is dynamic (minecraft it can be) and then whether the change effects a particular unit. It also may deal with units blocking each other (crowd control) and having contingencies (waiting or 'going around') without having to recalculate. A most often recalculation is when the unit's target moves, but even that may not be cause for the previously calculated path to have to be recalculated (or only be partially recalculated).

Your game mechanics will determine whether such higher level decisions start costing more (crossover point) than a simple brute force reuse of your full pathfinder.

Another aspect is : are the units supposed to be omniconscious of terrain they cannot see otherwise to require generating an optimal path every time, or could they make use of more dead reckoning (hierarchical nodes pathfinding useful for this generalization) until getting close or having a clear view of the terrain towards the target.