WEBVTT

00:02.610 --> 00:03.680
Welcome back.

00:03.690 --> 00:10.680
Let's get stuck right in and continue coding with our build graph method, which is a little bit more

00:10.680 --> 00:18.540
complex than this because we have to build that multi branched structure of all of the nodes.

00:18.540 --> 00:23.430
It's not just one great big long line and for that we're going to use.

00:23.820 --> 00:32.220
So I hope you're all up to date on your use of recursion because it's a complicated thing to get straight

00:32.220 --> 00:36.240
in your mind, but it's a very, very powerful programming concept.

00:36.240 --> 00:40.260
And basically it's when a method calls itself.

00:40.260 --> 00:47.100
And so you end up with all these versions of the method running on top of each other in memory.

00:47.100 --> 00:51.570
And at some point you have to sort of dig your way back out of them.

00:51.570 --> 00:54.390
But I'm going to show you how to do this, so don't panic.

00:54.600 --> 01:02.100
So we're going to create a private bool build graph and it's going to take our parent node.

01:02.100 --> 01:06.660
So node parent list of.

01:07.550 --> 01:08.900
And leaves.

01:11.050 --> 01:16.030
A list of g actions which are usable actions.

01:16.840 --> 01:25.990
And our dictionary with our goal in a dictionary which is a remember it's a string int and that will

01:25.990 --> 01:27.130
have goal.

01:30.570 --> 01:30.960
Okay.

01:30.960 --> 01:32.220
So this is Bill Groff.

01:32.220 --> 01:36.600
So the first thing we're going to do is bool found path.

01:37.360 --> 01:42.820
Equals false because at this point we haven't found a path and we need to keep track of whether we have

01:42.820 --> 01:43.300
or not.

01:43.480 --> 01:46.660
Then we're going to do a four each through each of our actions.

01:46.660 --> 01:54.550
So for each g action, action in usable actions we're passing through.

01:54.790 --> 02:00.130
And I think I've spelt that wrong, but I'm going to keep the wrong spelling in there.

02:01.060 --> 02:11.830
And now if action is achievable, given the parent state.

02:16.200 --> 02:19.470
Then this action is definitely one that we're looking for.

02:19.500 --> 02:22.350
So at this point, we'll go dictionary.

02:23.370 --> 02:38.220
String int of the current state equals a new dictionary of string int, but it is being copied from

02:38.220 --> 02:39.300
the parent state.

02:40.680 --> 02:48.360
So the first time we come in here, the list of states, remember they come from the very first node

02:48.360 --> 02:54.210
and that first node is the starting node and it has a list of all of the world states in it.

02:54.210 --> 03:00.480
So the first time we come through into this current state is going to be filled up with the states of

03:00.480 --> 03:01.200
the world.

03:01.200 --> 03:08.700
Now the idea with current state is as we go through all of our actions and build up our branch, is

03:08.700 --> 03:14.010
that we keep track of everything that's being satisfied and all the conditions that are changing as

03:14.010 --> 03:14.760
we're going through.

03:14.760 --> 03:22.740
So it's kind of like doing a sort of pre test run through the branch and because this current state

03:22.740 --> 03:29.250
has all of the states that are going to be achieved before you get to that action, it helps to match

03:29.250 --> 03:30.780
them as we're going along.

03:30.900 --> 03:31.220
Okay.

03:31.230 --> 03:40.440
So we've got this is achievable parent state, we've got our current and now we're going to create a

03:40.470 --> 03:41.730
for each.

03:43.790 --> 03:47.150
Key value pair, which will.

03:48.770 --> 03:51.710
Match up string and int.

03:51.710 --> 03:59.030
So the key values of the effects in action effect.

04:01.600 --> 04:12.970
And then if not current state contains key in the effects dot key.

04:15.320 --> 04:16.970
Current state.

04:18.520 --> 04:19.870
Don't add.

04:22.080 --> 04:27.510
A fixed key and a fix dot value.

04:28.260 --> 04:36.180
So now current state is going to have not only the state of the world, but we're also adding to it

04:36.180 --> 04:39.090
the effects of the current action.

04:39.090 --> 04:44.040
And then as we move on, the effects from the next action will be added and the next.

04:44.040 --> 04:46.620
So it is keeping that really long list.

04:46.860 --> 04:47.220
All right.

04:47.220 --> 04:50.010
So we're going to finish our for each loop there.

04:50.040 --> 04:55.860
Then we're going to go node and node equals new node.

04:55.860 --> 05:07.770
So we now create the next node along and its parent and the parent cost plus the action cost.

05:07.770 --> 05:12.930
So the cost value here, you can see that we're getting each cost of the individual actions.

05:12.930 --> 05:19.350
But as we move through all of our nodes, it accumulates and that's how we can do that.

05:19.350 --> 05:26.070
Get cheapest node up the top in the code here and know that we've found the plan by just looking at

05:26.070 --> 05:28.020
the very last node on the end.

05:28.020 --> 05:29.670
That is the cheapest.

05:30.480 --> 05:30.760
Okay.

05:30.780 --> 05:33.390
And we're also going to set the current state here.

05:33.390 --> 05:41.460
So we're giving it to our new node or passing along this accumulation of states and then also the action.

05:41.700 --> 05:43.590
And then if.

05:45.000 --> 05:50.850
Goal achieved, which we're yet to write, where we're going to match up the goal that we're looking

05:50.850 --> 05:52.260
for with the current state.

05:52.260 --> 05:58.560
So somewhere in the current state, if we have achieved our goal, then we are in fact finished.

05:58.560 --> 06:03.180
So leaves add our node.

06:05.490 --> 06:10.440
And then found path equals true.

06:13.700 --> 06:18.050
Now else we haven't found a path.

06:18.320 --> 06:22.370
So what we do is we go to the next node along.

06:23.420 --> 06:26.930
So we've created our next node along already here.

06:27.860 --> 06:37.100
But now what we're going to do is to create a subset of the usable actions to take out the current action

06:37.100 --> 06:38.580
that we've already got in our node.

06:38.600 --> 06:43.070
So first of all, list G action subset.

06:44.860 --> 06:52.300
A class action subset, another method that we're yet to write usable actions.

06:54.380 --> 06:55.400
Action.

06:56.840 --> 07:04.940
And this is going to take out of our usable actions the action that we've already created a node in

07:04.940 --> 07:11.240
our graph for, so that as we go along the branches, this list of usable actions becomes smaller and

07:11.240 --> 07:16.490
smaller, which means that you can't create a circular path anywhere.

07:16.490 --> 07:21.800
So you're not going to end up with some kind of endless circle that you're searching through for creating

07:21.860 --> 07:23.120
a plan.

07:23.240 --> 07:29.210
Okay, so ball found and that's going to equal build graph.

07:29.210 --> 07:34.100
And here you can see our recursive call where we now send through the next node.

07:34.400 --> 07:39.470
We still give it our leaves, but instead of usable actions, all of them we're just sending through

07:39.470 --> 07:42.950
our subset and again, we're sending through the goal.

07:43.160 --> 07:48.950
So as bill graph keeps getting called over and over again, we're sending it the next node and then

07:48.950 --> 07:51.680
the next node, the next node that have been attached.

07:51.680 --> 07:57.080
And this usable action set that's getting smaller and smaller and smaller into subset.

07:57.740 --> 08:01.850
And at some point if found.

08:03.460 --> 08:08.440
Happens to be true from this then found path equals true.

08:10.740 --> 08:13.560
And that then finishes out else.

08:14.960 --> 08:20.870
And we can finish our if our four h at the top.

08:21.050 --> 08:26.930
And before we finish our method we can return found.

08:27.690 --> 08:29.700
Path back.

08:30.370 --> 08:31.900
To our planner.

08:32.760 --> 08:34.840
Okay, so that's our recursive function.

08:34.840 --> 08:39.310
That's doing all of the work for building up our graph.

08:40.630 --> 08:41.050
Right.

08:41.050 --> 08:48.040
The last thing we need to do in this code file and I promise, well, it's not the last thing.

08:48.040 --> 08:52.810
It's the last thing you get to do for now, before we can kind of get started on creating something

08:52.810 --> 09:00.460
is to declare these two methods for you want goal achieved and action subset, right?

09:00.460 --> 09:03.910
So we're going to put that underneath here.

09:03.910 --> 09:09.190
So make sure that you're still inside your class but outside of the previous method.

09:09.190 --> 09:20.170
So this is going to be our private bool goal achieved and it's going to use the dictionary again.

09:20.170 --> 09:22.960
Surprise, surprise int.

09:25.240 --> 09:27.730
Go and then dictionary.

09:29.450 --> 09:32.300
INT State.

09:34.940 --> 09:46.220
And in here for each key value pair which will be again our string and int.

09:48.260 --> 09:50.360
A G in goal.

09:50.360 --> 09:58.220
So looping through all of our goals and making sure that they exist in the effects.

09:58.550 --> 09:59.600
So if.

10:00.720 --> 10:04.020
Not State contains key.

10:05.180 --> 10:06.680
G dot key.

10:08.550 --> 10:11.380
Then we will return false.

10:11.400 --> 10:16.680
Otherwise, if we make it all the way through looping and checking, then we're returning true that

10:16.680 --> 10:20.430
we're able to satisfy all of the goals.

10:20.430 --> 10:25.350
So that's a goal achieved straight forward as far as checking.

10:25.350 --> 10:33.060
And then we need our action subset up here, which gets rid of the current action that we've just assigned

10:33.060 --> 10:36.180
to a node out of the usable actions.

10:36.180 --> 10:38.760
So this again will be a private.

10:41.320 --> 10:43.780
And list of.

10:45.240 --> 10:45.660
G.

10:45.660 --> 10:51.710
Action Action Subset List.

10:52.350 --> 10:53.760
G Action.

10:56.090 --> 10:59.030
Actions and action.

10:59.660 --> 11:00.920
Remove me.

11:00.920 --> 11:03.050
So that'll be the action that we're passing through.

11:03.080 --> 11:08.540
We're looking for it as we loop through, and then we're just going to get rid of it out of this particular

11:08.540 --> 11:09.360
list case.

11:09.410 --> 11:11.840
So it's going to be list.

11:13.440 --> 11:15.000
G action.

11:17.530 --> 11:18.550
Subset.

11:18.910 --> 11:21.640
Equals new list.

11:21.910 --> 11:24.040
G action.

11:25.970 --> 11:34.700
And then for each g action a in actions we've passed through.

11:34.880 --> 11:43.320
If we find the one that we're going to remove, so if or if we don't find it should say if not action.

11:43.340 --> 11:48.030
Dot equals remove me.

11:48.050 --> 11:52.410
So the one that we've got to just leave out, then we kind of are just ignoring it.

11:52.430 --> 11:59.360
Otherwise subset add a and we'll put the action in to there.

11:59.630 --> 12:09.830
Then after we've done our loop, we will just return our subset and that basically is removing that

12:09.830 --> 12:12.710
action out of the usable actions.

12:13.190 --> 12:19.250
Okay, so you'll be relieved to know we've finished with our G planner for now.

12:19.880 --> 12:28.130
Right next we can actually start making some actions and start pressing that play button in unity to

12:28.160 --> 12:33.860
see things working and how they work and then start building on it from there.
