WEBVTT

0
00:11.460 --> 00:15.400
It would be impossible to begin talking about the ins-and-outs of A.I.

1
00:15.420 --> 00:21.770
without a brief background in 'Graph Theory'. Almost all A.I. techniques using games rely on the programmers

2
00:21.770 --> 00:27.870
having an understanding of graphs. Graphs in this context refer to a collection of nodes and edges.

3
00:28.470 --> 00:31.950
Nodes are represented graphically as circles...and edges

4
00:31.950 --> 00:38.430
are the lines that connect them. A graph can be visualized as nodes representing locations and edges as

5
00:38.430 --> 00:40.490
paths connecting them.

6
00:40.650 --> 00:47.220
A graph can be undirected (which means that the paths between nodes can be traversed in both directions)

7
00:47.490 --> 00:51.480
or directed (in which case the paths are one way).

8
00:51.540 --> 00:54.260
Think of this as a difference between two-way streets

9
00:54.300 --> 01:00.810
and one-way streets. Nodes and edges can be drawn where nodes represent coordinates, such as those on

10
01:00.810 --> 01:06.520
a flight plan, or as symbolic states where the physical location in the graph is meaningless.

11
01:06.990 --> 01:09.930
Both nodes and edges can have associated values.

12
01:10.110 --> 01:15.720
These values could be the distance between nodes (such as those representing distances in the flightplan)

13
01:16.320 --> 01:20.850
or the time it takes to complete an action (such as a node in the action plan).

14
01:21.180 --> 01:26.910
The ways in which graphs are useful in game A.I. will become evident as we progress through this course.

15
01:27.630 --> 01:30.580
If you think graphs look familiar, it's because they are.

16
01:30.900 --> 01:36.990
We've already made a graph of waypoints and had our NPC traverse between them. Graphs are so flexible that

17
01:36.990 --> 01:43.080
they can be used for a plethora of applications where you need to traverse from one state to another, whether

18
01:43.080 --> 01:46.830
that be a real state or a conceptual state.

19
01:46.830 --> 01:52.710
In this example, a graph is being used to define the locations in a tile-based game and the amount of

20
01:52.710 --> 01:59.130
effort to move from one tile to another. Values placed on the edges are generally referred to as

21
01:59.130 --> 02:02.140
'Utility Values', whether they represent times, distances,

22
02:02.160 --> 02:08.790
effort, costs or any other value an NPC might use to make a decision. Let's consider the situation where

23
02:08.790 --> 02:13.300
an NPC wants to move from tile C2 to A2.

24
02:13.590 --> 02:17.760
There are 2 possible paths. To decide which path to take,

25
02:17.760 --> 02:22.700
the NPC can add up all the utility values along each path.

26
02:22.730 --> 02:29.090
In this case, the utility values aren't about distance, they are about terrain difficulty. Adding up the

27
02:29.090 --> 02:35.240
values along each path reveals that the longer path (over the bridge) will be less effort. In order to work

28
02:35.240 --> 02:39.650
with a graph, there needs to be an efficient method of searching through the nodes.

29
02:39.650 --> 02:43.540
There are two basic high level algorithms for searching through nodes.

30
02:43.760 --> 02:51.350
The first is called a 'Breadth-First Search'. In a breadth-first search, the NPC marks its current location

31
02:51.410 --> 02:59.480
(or node) as 1, then it numbers all adjacent nodes to that as 2, then all the adjacent nodes to them

32
02:59.560 --> 03:04.590
as 3 etc. until the destination node has been reached.

33
03:04.610 --> 03:09.470
It then counts backwards, in 1s, to the start, to find a path to the goal.

34
03:09.680 --> 03:16.280
Breadth-first search examines all possible nodes in the graph to find the best path, but due to its thoroughness,

35
03:16.340 --> 03:23.630
it's time consuming and not optimal. A 'Depth-First Search' is much simpler and quicker, but less effective.

36
03:23.780 --> 03:31.250
Instead of finding the BEST path, it finds A path. Beginning at the NPC position, an adjacent node is found

37
03:31.250 --> 03:33.770
and numbered. Then an adjacent node

38
03:33.800 --> 03:35.390
to this is found and numbered.

39
03:35.390 --> 03:41.630
This continues until a dead-end is reached, at which time we return to the last node where there was

40
03:41.630 --> 03:45.390
another direction to try and we head off in THAT direction.

41
03:45.860 --> 03:51.560
It's like the approach you might take to get out of a labyrinth. When the destination is found, the nodes

42
03:51.560 --> 03:57.770
are then counted backwards again, to give the path. The most popular algorithm used to find paths in graphs

43
03:57.770 --> 04:03.300
that is used in games because of its efficiency in being able to find the shortest path, is the

44
04:03.350 --> 04:04.360
A* algorithm.

45
04:04.370 --> 04:08.230
It's a little more complex than the other two methods and works like this...

46
04:08.240 --> 04:10.780
First, all the nodes in the graph are numbered.

47
04:10.800 --> 04:15.050
We then create two lists: an 'open' list and a 'closed' list.

48
04:15.170 --> 04:18.620
These will keep track of the nodes that we've visited and processed.

49
04:18.710 --> 04:22.940
Each node is given 4 values that are used in calculating the path.

50
04:22.940 --> 04:26.750
First they are given a 'Heuristic' value represented by 'H'.

51
04:26.870 --> 04:32.320
The 'heuristic' is the estimated cost of getting from an individual node to the destination.

52
04:32.540 --> 04:35.980
You can use any method you like for calculating that value.

53
04:36.260 --> 04:42.060
You might use a 'linear distance' or count the 'number of rows and columns'.

54
04:42.190 --> 04:46.180
The second value is 'Movement Cost' represented by 'G'.

55
04:46.450 --> 04:51.370
This value is essentially the utility in moving to the node from another node.

56
04:51.370 --> 04:55.140
This could be based on the actual distance from one node to another

57
04:55.480 --> 05:02.660
or the cost of traversing a train type, like the tile example we looked at with the bridge. We then store

58
05:02.660 --> 05:09.650
a calculation that adds together the H and G values and call that 'F' and store the nodes parent, which

59
05:09.650 --> 05:12.240
is the closest node along the path.

60
05:12.470 --> 05:14.490
Let's take a look at an example.

61
05:14.510 --> 05:16.490
We begin by placing the starting node

62
05:16.550 --> 05:23.180
(in this case, 50) into the 'Closed' list, as this is the location we have visited. We then look for any neighbors

63
05:23.180 --> 05:28.250
that aren't blocked and aren't in the closed list and add them to the 'Open' list.

64
05:29.070 --> 05:35.640
We then calculate the heuristic for each node in the open list. In this case, we will use the linear distance

65
05:35.640 --> 05:39.830
from the node to the destination.

66
05:39.920 --> 05:43.820
Then we work out our movement cost to go from the starting node to the neighbor.

67
05:44.060 --> 05:50.450
Again, we use a linear distance. Horizontal and vertical neighbors are a distance of 1 away, with diagonal

68
05:50.450 --> 05:57.230
neighbors a distance of 1.4. The cost of moving to those nodes becomes their G value. From that,

69
05:57.320 --> 06:00.340
'F', which is H+G, is calculated.

70
06:00.410 --> 06:05.120
Whilst we're doing this, all the neighbors are linked back to the current node, thus making the starting

71
06:05.120 --> 06:11.420
node their parent. With no more nodes to examine in the open list, we now get the node in the open list with

72
06:11.420 --> 06:13.340
the lowest F value.

73
06:13.370 --> 06:18.860
This becomes a new location to start searching the neighbors again. The new location node is added to

74
06:18.860 --> 06:25.880
the closed list as having been visited. Any neighbors not blocked, closed or already on the open list are added

75
06:26.000 --> 06:27.350
to the open list.

76
06:27.350 --> 06:31.850
The H value is calculated for any new nodes in the open list.

77
06:31.850 --> 06:38.380
The G value is also calculated but this time it is the 'cost of movement+the previous cost of movement'.

78
06:38.660 --> 06:48.170
So in this case, node 32 gets the 'G movement' of 41 + the 'cost of moving' from 41 to 32, which is also

79
06:48.170 --> 06:48.790
1.

80
06:49.010 --> 06:57.680
This gives a final G value of 2...and for 32, its F value will be 7. For any of the neighbors of the current

81
06:57.680 --> 07:06.050
location still in the open list (in this case, 40) a new G value is calculated. If the new G value is less

82
07:06.050 --> 07:07.720
than the current G value,

83
07:07.970 --> 07:13.880
the nodes G value is changed and its parent is updated to the current location.

84
07:13.970 --> 07:23.450
In this example, a new G value coming from node 41 would be 1, plus a horizontal

85
07:23.450 --> 07:29.020
movement cost of 1, thus resulting in a value of 2.

86
07:29.150 --> 07:32.530
2 is not less than 40s current G value

87
07:32.690 --> 07:35.220
and so the node remains unchanged.

88
07:35.330 --> 07:41.840
Any neighbor without a parent is assigned to the current location and the process begins again, by looking

89
07:41.840 --> 07:45.650
for the node with the smallest F value in the open list to visit

90
07:45.640 --> 07:50.360
next. The process ends when we are one node away from the end.

91
07:50.480 --> 07:55.710
At this point, we have a link of parents that lead all the way back to the start, which when reversed,

92
07:55.710 --> 08:02.440
provide a path from the start location to the destination. Unity uses the A* algorithm for pathfinding

93
08:02.510 --> 08:03.980
in its navmesh.

94
08:03.980 --> 08:09.590
This construct provides a powerful way for us to program navigation and avoidance into our projects.

95
08:09.590 --> 08:15.340
When you think about it, graphs and their nodes and edges are really a very simple thing. As we progress

96
08:15.680 --> 08:20.840
through the course, you're going to see them pop up all over the place as they are a staple in artificial

97
08:20.840 --> 08:22.110
intelligence.

98
08:22.340 --> 08:28.140
While there are numerous algorithms to traverse graphs, when it comes to games, nothing beats A*

99
08:28.370 --> 08:31.060
and you'll find plenty of resources to support it.