This video demonstrates path-finding algorithms in the context of a maze game and introduces the graphical user interface you are using in the course. Being familiar with this GUI will be helpful in understanding how the algorithms and data structures discussed in the course function.
- In this video, we're going to take a look at the GUI, that's graphical user interface, we've provided for this course. The aim of the GUI is to give you a high-level conceptual understanding of pathfinding algorithms, which use the data structures you're going to learn about. There are two modes for the GUI, game and explore. In game mode, you can simply play a fun maze game, a bit like Pac-Man, and get a sense of how your virtual opponent uses three different pathfinding algorithms to beat you in finding a piece of treasure. In explore mode, you can see the path taken from an individual position to a goal position using those same algorithms in several different mazes we've provided for you as text files. So the first thing I'm going to do is to create a PyCharm project. Now, it's by no means obligatory to use PyCharm, It just happens to be my preferred IDE for this kind of project. You can use whatever IDE you prefer. So I'm going to create a project, because in PyCharm, you can't work without a project, so I'm going to create a new project. And I'm going to navigate using this little folder icon. And I'm going to go to my desktop. And I'm going to select exercise files as the top level folder in my project, so that would then be the root of my project. And then I get some options for which interpreter. I'm going to use my already-installed Python 3.8. And create the project. And it says here, do I want to create it from sources, because there's already files there, so it's not an empty project, so I select yes. Okay, and then I'm just going to do a couple of things to set up. I prefer to have slightly less space taken up by my project directory over there, so I'm going to shrink the size of that area on the left. And then I'm going to click on the arrow where it says exercise files, and that will open up the top level folder. And you can see we've got, at the moment, just two other folders, which we'll be adding to as we progress. But the one we want to open is GUI code. And let's look at the game first. So that's maze_gui_game.py, I'll double click on that. And you can see it opens up in the main window here. Now the keyboard shortcut I use to run the file that I'm in is control shift F10. That may vary on your system. And you can also do it by using the run menu at the top. Okay, so this is the maze GUI. It's basically a bit like Pac-Man, but it's not actually Pac-Man, because Pac-Man uses different algorithms to this. So you can see few things on the screen. Let me just talk you through them. So we've got some buttons at the top, so we can reset. We can decide whether we want the path to be shown or not, and I'll demonstrate that in a moment. And then we have a choice of three algorithms, depth-first search, breadth-first search, and A star. So probably just easier if I just show you how it works. So I press S, and the opponents start looking for the treasure, you can see that yellow treasure at the top. And I'm also looking for the treasure, and I'm racing my opponent to it, who is currently using depth-first search, which is not great for him in this context. Okay, let's try a different algorithm. Breadth-first search. Press S to start, and just notice the pattern of exploration that my opponent is using. It's different from what he was doing, or he/she/it it was doing for depth-first search. And again, let's look at another one, which is A star. Now, this is the most effective one, where the opponent goes straight for the goal, and it's quite hard to beat. If the opponent is closer than you, then he's likely to get there before you. Start again. Okay, so that's how the game works. and I set it so that... I think that first to three is how I've set it. You can change that in the configuration. So let me talk about configuration now. So that's the basic idea. You've got this maze game, and you're trying to beat your opponent to find the treasure. And, then looking at the code. Very important file here is config, okay? So first of all, we can change our maze. So at the moment, I'm using Pac-Man maze, let's looking at a different one. Let's look at, for example... I've got one called wide maze. We'll use that one. And then there's just a few other constants here that are used throughout the GUI. So we can change the speed, for example. That's the number of milliseconds between frames. Target score. Okay, so I set it to three, the first to three will win. And then just a few other things, most of which you don't want to touch. Sound, we've got some sound in there, some retro sound effects, which you can play if you install the playsound module, which... Let me just show you where that is in the code. In my imports. Okay, so import playsound. Now this does not come with Python as standard, so you would have to, if you want the sounds, you would have to import that module using pip by doing pip install playsound. So if you run it again, now, you'll see the maze will have changed. So we've got a different maze, but everything else is the same. So we can press S to start. And I'm going to, I'm the green one, green block up there, and I'm trying to find the yellow coin, or the yellow treasure. And of course, because my opponent was closer, they got there first. Breadth-first search. As well as playing the game, you also want to be trying to think about the pattern of the particular search that your opponent is using. So breadth-first search is a little bit like flood fill. It's like moving out from a central point to all of the other squares within a certain distance from the initial square, according to what's possible with the various obstacles, and we're going to go into a lot more detail about how that works. A star is the most direct, like I said before. So if we started with A star... So using A star, that's going to be the most effective opponent, the most likely to beat you. So spend a bit of time playing with this, have some fun, but also, you know, use it as a way to get a very kind of high-level conceptual understanding of the algorithms. And later on, we'll give you a much more kind of nuts and bolts description of how they work.