Pathfinding with arbitrary boxes

#1 A few clarifying questions:

Are these rects defining something like platforms, or areas that can be moved on/over? Do the rects overlap or how does an agent get from one to another? Is the area enclosed by the various rects the only areas that are navigable? Are there static obstacles within a rect or are they free to move about (not counting dynamic obstacles)?

#2 Hi James.

Yeah, looking at my post again it's not very clear, sorry about that ;)

An "empty" level would be a level which an agent could move around at will. An entry into the RectF list defines an area which an Agent cannot move through. The action is top-down and an agent is free to move in the x,y plane as long as he doesn't hit a block.

Ian

#3 Oh ok then. So if you want to use a nav-node based system (as apposed to nav-meshes), you would start at the top left corner of your scene, and iteratively step from there to the bottom right corner of your scene. At each step place a navigation node, but first check if it is within one of your "avoid rects" and if so, do not place it. Since your rects aren't necessarily placed to line up perfectly with your node step size, your agents may not be able to move directly flush with any particular one of your avoid rects, but the solution for this using nodes is just to increase your node-resolution.

Note that these nodes do not need to be objects actually placed "in" the scene at that position. It can just be a big-flat vector of structs or simple storage classes. Each node keeps pointers to its neighboring nodes, (and some other things like bools for open and closed for use in the A* algorithm ). So the only time you need to actually iterate through the flat node vector is to find one at a particular position (like the start or end position of your path), which if you want to optimize you can implement a quad-tree or something like that for faster lookups.

#4 Great stuff James, thank you. Do you have any advice on what a good grid resolution is? Well, I guess I'll just increase it until it becomes too slow.

#5 That would depend on the scale of your game. And if your agent movement appears smooth enough for you. It will probably be a fine tuning process so its good to have some debug rendering for nodes / paths and a way to regenerate the grid with new parameters without restarting the game (I used a ton of global variables which were accessed both by script and C++ to control nav-grid generation).

#6 Oh, if you haven't come across this yet, I wrote a doc on working on the BeTheDinosaur AI and it has some notes on pathfinding. Its mostly general info and hints/tips.

www.garagegames.com/blogs/63486/14783