DD Week 2

This week I have learned: A* & GOAP (and a little bit of D*)

A*

I spent a long time trying to implement a pathNode generation system. That honestly turned into a pile of crap. But that’s how first attempts go. All it all it looked good:

After I had this thing working I begun to try to implement A* base off the class presentation. But quickly realised that the way I had done the grid implementation did not work effectively enough for a good implementation of A* as the two systems generated problems that I did not understand in their entirety. So I decided to make use of a previous tutorial(Sebastian Lague A*), that I have worked through before, this was a good result as I gained a better understanding of each part and its function.

GOAP – Goal Oriented Action Planning

Basically just read this and watch your horizons expand: Three States and a Plan: The A.I. of F.E.A.R. – Jeff Orkin

But in case you are to lazy to read it(Seriously, take the time to read it!) The gist of it is: Their are goals and actions. Entities have their own internal understanding of the world, and how it can effect that state to complete a goal. To do this goals are generalized to a desired world state. This means that any entity in the game can be given the same goal. And it must use its own abilities to attempt to shift the current world state to the goal state. To do this it has a range of actions that it is able to take. These actions can be anything that is relevant to the entity, the actions have prerequisites, and effects. And the system calculates the cosings of each action to stack them in an order that will hopefully result in goal state.

The little bit of D*

D star is a path originally based off A* pathing, it is designed to be able to handle the possibility of unknown path data. And to be able to improve the efficiency of repathingas the pathData is updated. To do this it makes use of propagation waves that are used on repathing as the propagation waves make it less likely or more likely to plan paths through areas based on the result of the previous pathing attempts. This alongside the fact that It plots its from target to current location make it able to update the path from a position up the chain allowing the entity to continue to Navigate along the old path while a new path is planned from the updated PathData. This can then be spliced into the current Path, allowing a continuous flow.

Advertisements