Maze Basics

---

Using only these symbols I should be able to generate a text file of any size that defines a maze. If we were to convert the previous nodes we've been using in the last sections into a text file, then it would look like the following image on the right.  Create a new file called mazetest.txt and copy the values below into that file.  Please note that there is a space between each character.  

There are a few things we need to understand about this text file, in case you want to make your own.  

• Two nodes are equal if and only if they are located in the same row and the same column. This is important to remember as we're writing the code because the computer may generate the same node twice as it's reading this file.  You'll see why when we get to the code, but if it does generate the same node we need to check for node equality.  The only way to do that is to define what it means to be equal. Remember, two nodes are equal if and only if they have the same x and y values.  The bottom line is that we don't want to generate the same node multiple times.
• It's ok to have deadends.  Pacman mazes generally don't have dead ends (except in a few special cases).  But there's no reason not to have them in your game.  Besides, if you do have dead ends, you can always link them up later as portals.  
• Remember, that nodes that are connected together have a '.' between them.  Think of '.' as cookie crumbs that lead you from one node to the next node.

Open up the nodes.py file.  The first line we'll add is importing numpy.  Numpy makes a few things that we want to do a bit easier.  For example, we'll use it to read out text file and place it into an array.  Then we can do things to that array like transpose it.  That's all we really need numpy for.  Also go ahead and delete the entire setupTestNodes method.  There's no going back now.

We want to read in our text file when we create an object from this class.  The 'level' input is just the text file.  I named it 'level', because you'll eventually have a different text file for different levels.  

We'll get rid of our nodeList and create a nodesLUT instead.  This is a dictionary which will contain our nodes, it just makes it easier to look up our nodes based on some value.  LUT stands for "Look Up Table".  

Also, we're putting our symbols for our nodes and paths in a list because we may need to use other symbols to represent different kinds of nodes and paths later.  (Spoiler Alert!:  we will).

There are 4 new methods that we'll need to create.  Let's go over them next.

So here we'll read in the text file using numpy's loadtxt function.  We need to set the dtype to '<U1' or else it will try to read in the data as floats and create an error when it encounters non-float characters like the '.' character.  This will return a 2d numpy array.

At this point we're entering in a Numpy 2d numpy array which is what data is.  It contains all of the symbols we described above.  So we're just going to go through it row by row and anytime we find a '+' character, we'll create an entry in the lookup table with the row and column that node was found and create a Node object.  So the dictionary keys will be a (x,y) tuple, then the values will be a Node object.  We'll pass in the (x,y) location to that Node object as well.  Having a dictionary makes it easy to look up a node if all we have is it's (x,y) position.  We could just have a list of Node objects, but then we would have to loop through them anytime we wanted to find a specific node.  So dictionaries are useful if you just want to look stuff up, hence the name "Look Up Table" or LUT.

The constructKey method simply converts a row and column in a text file to actual pixel values on the screen by multiplying them by whatever values we set for the tile sizes.  

At this point we have a dictionary of Node objects, however, none of the nodes are connected together.  To connect the nodes together we're going to follow a 2-step process.  We're going to first connect the nodes horizontally.  Then we'll connect them vertically.  

We do that by going one row at a time and looking for a '+' character.  When we find one we need to know if the key value is None or not.  We initially set it to None anytime we start on a new row.  The key can also contain a key to our dictionary we created above.  That's why I named it key.  It allows us to know if two nodes need to be connected horizontally or not.  

The idea is that if we encounter a '+' symbol then we take a look at the value of the key variable.  If the key variable contains a value of None then we simply need to set it to the key of that node in the dictionary.  It's basically a way of seeing if it connects to another node later down the line.  If we encounter a '+' symbol again and the value of key is not None, but rather a key value then that means we need to connect those two nodes together.  Since we're moving left to right, the new node we encountered is to the right of the previous node we encountered.  And the previous node is to the left of the new node.  Anytime we encounter any characters that are not in the pathSymbols list (which only contains '.' for now), then set the key to None again.

This is similar to how we connected the nodes horizontally.  However, this time we're going to transpose the data array.  What that basically means is that the columns become rows and the rows become columns.  That way we can basically follow the same logic when connecting up the nodes vertically.

The main difference here is when we connect the nodes we need to reference UP and DOWN instead of LEFT and RIGHT.  Also, the key needs to be flipped to read (j, i) instead of (i, j).  That's because of the transpose.  If we have an array that has shape (m, n), then the shape of the transposed array is (n, m).  

Other than that it's basically the same as the previous code.

Also included are 2 methods that will allow us to get a node if we give either the (x, y) pixel location or the (column, row) tile location.  Useful to have for later on.