On decision trees and goal oriented planning

I like to do a lot of research before I actually start coding so I read up on the latest in AI gaming theory and it turns out that the most lifelike NPCs utilize something called goal oriented planning. I kind of know what this is: it's a sequence of steps to get to a goal i.e. a decision tree.

Where it differs from a decision tree is that a decision tree is typically a hard coded best-estimate of the route to get from where you are now to a planned goal (whether it's a physical location or a state or an action or whatever).

But if we switch it up a little bit and allow competing sub-goals to compete for the fastest path to the goal and update the subgoals-in-running and various choices of paths to the goal then we have something more interesting and this is in fact the goal oriented planning situation I'm reading about.

What's interesting about this is that it means effectively that pathfinding and goal oriented planning are exactly the same thing. In other words A Star (or A*). So I need to dig into A* a little more.

Interestingly, Christy Lock has been bending my ear about A* for pathfinding already and she has already coded some A* into the code, so maybe it could be switched up a little to handle pathfinding to a goal.

But that's for later. For now I'm going to stick to a simplified attack decision tree for the first step.

Any case, here is pseudo code (from wikipedia) for the A* algorithm in case anyone is interested.

function A*(start,goal)
closedset := the empty set // The set of nodes already evaluated.
openset := set containing the initial node // The set of tentative nodes to be evaluated.
came_from := the empty map // The map of navigated nodes.

g_score[start] := 0 // Cost from start along best known path.
h_score[start] := heuristic_cost_estimate(start, goal)
f_score[start] := h_score[start] // Estimated total cost from start to goal through y.

while openset is not empty
x := the node in openset having the lowest f_score[] value
if x = goal
return reconstruct_path(came_from, came_from[goal])

remove x from openset
add x to closedset
foreach y in neighbor_nodes(x)
if y in closedset
continue
tentative_g_score := g_score[x] + dist_between(x,y)

if y not in openset
add y to openset
tentative_is_better := true
else if tentative_g_score < g_score[y]
tentative_is_better := true
else
tentative_is_better := false

if tentative_is_better = true
came_from[y] := x
g_score[y] := tentative_g_score
h_score[y] := heuristic_cost_estimate(y, goal)
f_score[y] := g_score[y] + h_score[y]

return failure


function reconstruct_path(came_from, current_node)
if came_from[current_node] is set
p = reconstruct_path(came_from, came_from[current_node])
return (p + current_node)
else
return current_node