OK, I think I get the idea of the region search. Only problem is, what happens when the path from one region to another is totally blocked by dynamic units?
Also, how would you calculate the arrow paths from each region to the surrounding ones if the regions aren''t convex?
Hey! I''ve got an idea. If your map is divided into regions, you only have to store the paths to each of the SURROUNDING regions, and store the paths (in regions) for the farther paths. That way, you would have to do maybe 3 memory checks (oh darn) per iteration, but you wouldn''t have to store all 500 values for arrows, just, say, 15. that would be 256x256x15, or less than a meg, plus a little for the paths to each region, 500x500 array (for the next region to go to from one region traveling to the destination region). You get my vision?
One way to do it would be to compute paths around obstacles as lines. Then store all the lines in a structure that has waypoints (points along the line) and connections to other lines. Then, to make something move anywhere in your world tell it to move along the lines. Doing it for all obstacles may be a bit excessive so my suggestion would be to compute the lines only around objects of a given (larger) size and use another solution for actually reaching the waypoints, because there may be a small obstacle between the thing you want to move and the nearest way-point.