[00:00:07]
>> Well in this lecture we're going to explore different search algorithms that we
can use for path planning in our games so we have previously talked a little little
brief introduction to path planning just to really set up the notion of creating a
discretized space and that is.
[00:00:36]
Allowing us to define a graph structure with nudes and edges on which will perform
our search so in this lecture we're going to talk more about the search. There's a
little bit of review here so we have previously looked at how has planning is part
of formal. Planning in the sense that we have to find a state or our problem and
then we can apply operators to our state in England current condition of say case
of path planning current condition of the agent being at location a and the goal
being at locations be so we can manipulate our state representation which is our
disputed space and ultimately a graph we can manipulate that through operators.
[00:01:50]
That moved through the graph not actually doing the movement in the simulation in
the game world but just performing the planning and that if that successful you end
up with a path that your agent can follow so what we are wanting is an algorithm
that will make the appropriate selection of operators which basically what are the
different routes or small pieces of the route that the agent should take.
[00:02:32]
Representing our world with the disc ties space so far we've learned about the grid
lattice we briefly mentioned other possibilities like. Defining waypoints and with
edges so the grid lettuces has a structure and the waypoints are is an unstructured
graph with edges potentially very ng length and then there is of course other
possibilities we just as well but the operators generally are always the same it's
wherever you have a graph node you can.
[00:03:15]
Follow that. From a node follow whatever edges it has to other nodes and hopefully
into at the right point. And there's 2 main techniques that we could apply one is
the blind or uninformed search this is where you have no domain knowledge you just
have you know you have a graph that it's defined structure of nodes and edges that
connect the nudes so you know you know is was a star What's the goal you know
nothing about.
[00:03:56]
The relationship between the nodes in edges until you start to parse through the
graph. Now in the case of a heuristic or an informed search we do have this domain
knowledge that this is typically information that draws from the problem that the
graph structure is applied to so the fact that we have discretized.
[00:04:25]
From a to d. vector space is Euclidean space that. Provides for us the opportunity
to leverage that information and will help us to have more efficient searches as we
will see so in terms of our look at Path planning this is going to be a bit
constrained compared to maybe a more general Ai study we're going to focus more on
what's most applicable to video games so that means that where we're going to be
interested in.
[00:05:14]
Worlds that is virtual worlds that are static and finite size now that videogames
can break both of these requirements but this this is a good place to start so and
certainly we could have worlds that are not static. But. There is usually elements
of most games that use a large static world with just a few moving objects maybe
like doors drug bridges.
[00:05:50]
But you tend not to see drastically changing roles the use certainly exceptions and
then also in regards to the size it tends to be as the world's only as big as the
artist design it but. Based on current trends we've seen. Procedural content
generation that could effectively be infinite it might not actually be but in terms
of the impact on our past search algorithms that that would be the case potentially
but we're not going to consider the cases we're going to we're going to think that
we're going to have a.
[00:06:33]
Stagnant static world with a finite size. And also that our operators that we're
performing as part of this formalized planning they're all just agent movements and
not anything that changes state for instance. That means we're not considering like
pressure plates to open passageways in a castle or needing to pick up he's or a
push push blocks around make a staircase in any anything like that and some of
those sorts of things are possible and can be addressed in planning systems for
games but you know we're going to focus on stat I so we're going to stop here but
then in the next video we're going to take a look at Brett 1st search to get you
started in our look at algorithms.