bbox astar for critters with variable radius seems to be working just fine.

instead of checking a single node when determining impassable, you check a bbox of a specified radius around the node. if any nodes in the bbox are impassable, the node in question is considered impassable, and is not expanded. this leaves nice buffer zones of the specified radius around all obstacles.

but now i have a path with nodes 1 foot apart, not one critter diameter apart. i've been using "move to owner" for pets to test astar, and dogs now have a diameter of 3, not 5 feet.

1. i suppose i should use the smallest dimension for critter radius when pathing, right? a dog may be 3-5 feet long, but its only a foot wide, so it should be able to fit though a 1 foot gap. i'm using a radius of 1 right now, which works out to a 3x3 bbox size. using center and radius, vs UL and LR corners to specify a bbox, you can only have odd size bboxes. OTOH, even sized bboxes don't center on a tile nicely. at the moment, critter rad is used for both entity vs entity collisions, and pathing. using smallest dimension would mean i'd need two radii for a critter: one for collisions, and one for "astar pathing width".

2. when nodes were 5 feet apart, a dog would only move to node zero or one before the path got recalculated. but now i have a path with nodes 1 foot apart, and a dog can move at speeds up to 1.4 feet per update (21 feet/sec) at sprint speeds so the current algo of "if within 5 feet of node zero, goto node 1, else goto node zero" won't exactly work anymore. so if i have a path with nodes every foot, what's a good algo for choosing which node to move to next? find the closest node, if its not less than the distance you'll move before re-pathing, move there, else skip to the next node in the path until the node is at least one-repathing away, and move there? right now i re-path every update, so that would degenerate to move to closest node that's at least one update worth of movement away.

just need this last little bit to get it all hooked up and running correctly.

this is basically the "chasing breadcrumbs" problem (steering AI for pursuit in driving sims), with closely spaced breadcrumbs and a fast vehicle.

thinking about it a bit, it would seem the critter must move from the center of one tile (node) to the next, to avoid clipping corners.

since it may be able to move more than one node per update, it seems i will have to move it from node to node until its used up all its movement for the current update.

turning speed is also a factor. critters have a limited turning speed. i'm pretty sure most critters require more than one update to turn 45 degrees to the next node center.

so it looks like i'll have to move from one node center to the next, tracking how much i move and turn as i go, until i've used up all the movement or turning for that update.

somewhat similar to stepped movement for fast projectiles.

and you start by moving to the center of node zero (the tile/node the critter is in).

I'd take a more abstract perspective. All considerations about clearance, tiles, widths and lengths, corners and centers, turning speed, and time steps/dog velocities are subordinate to the graph on which you perform pathfinding calculations.

• If you have a regular grid, you need to tell whether a dog of a given height, width and facing can stand in each cell and which adjacent grid cells it can enter and with what facing, In any case, a bigger/clumsier dog will navigate on a smaller subset of the whole grid. This graph can be mostly precomputed (for each cell, a flag of whether each monster size in use can stand there and with what facing, plus simple rules or an explicitly extended graph for facing changes (which facings are allowed in a cell given the facing in the previous cell and the obstructions in nearby cells).
• The dog doesn't move in two dimensions, it moves on a graph. You might want to interpolate its movement between two graph nodes at an arbitrary point to render it without jittering and to perform collision detection, but the dog doesn't leave and reenter the navigation graph, and it doesn't need special rules to do so.

This graph can be mostly precomputed

this sounds like clearance based pathing.

the game has a procedurally generated world. no long pre-processing possible. all has to be done in realtime on the fly, or quickly at new game start when the world map is generated. and the game world is 2500x2500 miles in size (with no loadscreens!). so its not really practical to generate all the terrain chunks, ground meshes, and collision and astar maps for the entire game world. what is where in the world is stored in underlying data structures, and terrain chunks, ground meshes, atsar maps, and collision maps are generated on the fly as needed from the underlying data structures.

and with what facing, plus simple rules or an explicitly extended graph for facing changes

the game is a FPSRPG like skyrim, not a turn based tile based game.

dogs have a turn rate of 0.3 radians per update at 15Hz update as i recall.

location in a map square is stored as a float in the range 0-26400 feet. at 7 digits accuracy, that gives an accuracy of 0.01 feet. collision and astar maps use ints, not floats, at a scale of 1 foot per tile. base movement rate for a dog is 0.35 ft per update (at 15Hz). run speed doubles that, and sprint quadruples it. so at sprint speed, a dog moves 1.4 feet per update. but node centers are only 1 foot apart. so a dog may have to turn to node zero, sprint, turn to node 1, sprint, then turn to node 2 and sprint some more before its used up all its "movement points" for the update. but if it actually has to turn, odds are it will use up all of its "turning points" for that update before it uses up its "movement points" for that update.

Postmortem: The algo described in post #2 above seems to work just fine.

I start by calculating the move points and turn points left for the critter for this update. I then turn and move towards the next node, limiting the turn or movement to the turn points or move points left. I then subtract the turn points or move points used from those remaining. If I run out of turn or move points, I'm done. If I reach the node, I set the next node as the target and continue the process.