A* pathfinding around axis-aligned rectangle obstacles
One solution would be to have a 2D grid of cells covering your entire play area, and use each cell as an A* node. When it's time to do a pathfind it should be pretty easy to work out which cells are blocked due to being underneath one of your axis aligned rectangles.
The only tricky bit is getting the resolution of your grid good enough that you strike a decent balance between having far too many cells to do the pathfind quickly, and having too few so that small gaps are missed.
It looks like you implement only certain part of the whole pathfinding ? That is not a good idea, since it seems like the redesign of the problem is due, but you can only propose the change (and not enforce it).
What happens if you break down those 200 rectangles into actual nodes and set them as non-walkable ? I'd start with that.
One solution would be to have a 2D grid of cells covering your entire play area, and use each cell as an A* node. When it's time to do a pathfind it should be pretty easy to work out which cells are blocked due to being underneath one of your axis aligned rectangles.
The only tricky bit is getting the resolution of your grid good enough that you strike a decent balance between having far too many cells to do the pathfind quickly, and having too few so that small gaps are missed.
Hmm, this sounds like a fairly easy solution. But it would be ideal to have the path have as few turns or joints as possible, as each time I make a turn, I have to stop for a split second. Making very small moves and then moving in another direction will probably make traversing the path take a very long time; is there a way in which I can smooth out the path after finding it?
It looks like you implement only certain part of the whole pathfinding ? That is not a good idea, since it seems like the redesign of the problem is due, but you can only propose the change (and not enforce it).
What happens if you break down those 200 rectangles into actual nodes and set them as non-walkable ? I'd start with that.
Unfortunately, due to certain circumstances, I can't change anything about the problem I've been given, only the way in which I choose to solve it. I'm not sure what you mean by breaking down rectangles into nodes and setting them as non-walkable?
- Treat each corner, your starting position and the destination as nodes (= 802 nodes).
- select the starting position
- find all nodes in direct sight of the current position and add them to the open-list
- while finding the nodes you should also calculate their price (distance + H) (and perform regular A* stuff - add current node as previous if unvisited or cheaper)
- jump to cheapest node on the open-list and goto step 3) if this is not the destination.
Since all the rectangles are axis aligned ray tracing shouldn't make that big of an impact, as long as you only move one step at a time (don't calculate the connections between all 802 nodes, only calculate the connections between your current position and all other 801 nodes) assuming you only need 10 steps from end to end, that's ~ 10*801 as compared to 802^2 as I suspect you are doing.
Also don't use a grid. The 802 nodes are the ones you should use 
You could try to use the method that Mercenaries 2: World in Flames shipped with, that works rather badly in a 3d game, but would work nicely it sounds in your situation. It involves no preprocessing or building of data.
It's basically just an A* search with the nodes determined dynamically.
- Push the start position to the open list
- Grab next best node from the open list(using normal g and h costs)
- Shape cast from the node position to the goal position, if there is a direct open path, you are done, walk the path back to the start to build your path.
- If you hit a rectangle, push only the silouette corners on the side of the rectangle that might be visible to the current node
- loop
This technique works pretty well in 2d and might be worth considering for your needs. The idea is that every iteration of the search tries to see if the next best open node can go straight at the goal. In situations that the start and end have direct line of sight, it completes with a straight line path right away. Otherwise it functions by finding its way around objects by exploring silouette corners of the object. Works best if the object is convex but technically not required if you have a way to quickly determine what corners are 'visible' from some relative position.
All that said, it sounds as though your rectangles change a lot, in which case it may not be recommended to even do pathfinding. If you have a situation where rectangles are moving all about dynamically constantly I would perhaps advise against doing typical pathfinding because it will likely require you to run it constantly to compensate for an ever changing obstacle set. I would potentially consider doing a more influence map style approach where you can update a gridded weighting of the obstacle set with influences and simplify your agent pathfinding to just following the influences, though this technique depends on other aspect of your requirements that you haven't mentioned yet, such as whether there can be multiple destinations, how large the environment is, how many agents may be active and needing to pathfind at once, etc.
Perhaps I should have mentioned some more details: the player character walks around a 2D area with rectangle obstacles that don't move (or rather, very few obstacles are able to move around, and they're always player-sized or smaller, so if we collide with something, we can just run the pathfinding again). The reason why I said that the rectangles move around a lot is that the player can only see a certain area of the map (which is huge), and because the player is constantly moving whenever it paths around, rectangles move around, get placed in the area of sight, fall out of the area of sight, etc, all the time. However, while pathfinding, they're definitely mostly stationary. The player is the only agent that needs to pathfind. Also, when I pathfind, I'm only looking to go from the starting point to wherever I want to go to, no more. The environment to path in is typically medium-sized (I know that's a poor description but I'm not sure how else to explain it). Also, the rectangle obstacles are allowed to overlap each other, which I hope will not affect the algorithm (at least, it doesn't seem to me like it should affect a great deal).
There's also something else I should have added. Sometimes, it's not possible to find a path from A to B (ie, when B is inside an obstacle or enclosed by rectangle obstacles). Would I have to search through all points, then?
It sounds like the rectangles are only dynamic in the sense that they come in and out of some active set due to proximity. Even if the world is huge I would definitely still calculate the static navigation of the world and split it into tiles if you really need to only load a subset of the data. I think that in the context of a 2d game, even with a huge world, I would likely still load the entire worlds worth of 2d navigation, which should be pretty small. Even with the full data set loaded in, it shouldn't adversely affect pathfinding very much if basically all the player movement is all done in close proximity to the start point. In other words i would suggest that I doubt its worth the trouble to chunk the navigation up. Not only does it simplify things, but it leaves open the possibility to pathfind with A.I., or to implement a minimap or path 'plotter' as some rpg games have, to lead you to the next objectives, etc.
The cost of shape casts in the technique I describe is going to be slower than using prebuilt navigation. It's sole benefit is that it doesn't have any preprocessing requirements, but the runtime cost is more than you would get out of a preprocessed navigation mesh. Do you have an example of the size world and density of obstacles you are targeting?
I'm actually using a couple 2d open source libraries to do my real time obstacle baking in a 3d game
">
Going on the information you have mentioned so far, and assuming c++, if I was going to build navigation for a huge 2d environment I would probably use the exact same libraries.
http://www.angusj.com/delphi/clipper.php
https://code.google.com/p/polypartition/
With these 2 libraries, you can use a single gigantic rectangular polygon the size of your world, and then feed all the obstacle rectangles in to boolean them from the rectangle, which would provide you with a set of polygons that are then input into the polypartition to generate optimal convex regions. I think you would be surprised how optimal such a resulting mesh would be. It's fast enough to build to update at load time and small enough that you can easily keep the navigation set resident all the time. It even supports polygon offsetting, allowing you to automatically build navigation sets for variable sized entities.
