I definitely think anytime planning is underused in games. It's like a modified A* planner with a weighted heuristic, but which reduces this weighting factor after every successful iteration. The Anytime-D* algorithm then efficiently re-uses calculations to make subsequent plans faster. I'm not a games programmer, but I used this in a tech-demo planning paths for >5000 agents in a constantly changing map.
The biggest win in my opinion is that it devolves gracefully. If you're low on CPU time, you get worse paths. When CPU is readily available, they get better again.
FWIW, if you're reading this Valve, I'm still waiting for your call... ;-)
I definitely think anytime planning is underused in games. It's like a modified A* planner with a weighted heuristic, but which reduces this weighting factor after every successful iteration. The Anytime-D* algorithm then efficiently re-uses calculations to make subsequent plans faster. I'm not a games programmer, but I used this in a tech-demo planning paths for >5000 agents in a constantly changing map.
The biggest win in my opinion is that it devolves gracefully. If you're low on CPU time, you get worse paths. When CPU is readily available, they get better again.
FWIW, if you're reading this Valve, I'm still waiting for your call... ;-)