So, a new course has begun. Game Programming 3. This course focuses on 3D programming, with some networking too. This first week was about templates, linked lists and binary search trees.
Templates were something I had not worked with before and I must say that I start to like them. Instead of having to create a new function for each of type of parameters (int, float, double, etc) it should be able to take, I could just make a template function. The compiler takes care of the rest, creating multiple functions from that one template. The drawback with this is that the time it takes to compile the code can increase drastically.
We also got an assignment in three parts to do before this course is over. Part one is to create a linked list and a binary search tree. Part two is to create a web server using bsd sockets Application Protocol Interface (API) and Transmission Control Protocol (TCP). Finally, we are to create a 3D game. Part one and two are individual work while part three is to be done either alone or in a small group of up to three persons.
So, this week I have begun on the first part. The linked list is done and the work with the binary search tree is about halfway done and I will finish it this weekend.
How does the linked list work, or rather, a double linked list? It consists of nodes. Each node holds data together with two pointers, one pointing to the next node in the list, and the other pointing to the previous one. This means that if one node would be lost, the list after that node would also be lost. It also means that the list can grow and shrink without moving the entire list. All that is needed to insert a node in the middle is to redirect the next pointer of the one before, and the previous pointer of the next one. Instead of them pointing at each other they will instead point to the new node and the new nodes pointers pointing at the old ones. So, the only thing the list has to know is where the list begins and from there it can access the other nodes by going through nodes, one by one.
The binary search tree is similar to a linked list with nodes and pointers. The difference is that instead of one pointer to the next node, it has two, one pointing to a higher value node and the other pointing to a lower value node. So, to find the node you are searching for you start at the beginning of the tree, the node that was added first. You check to see if it is the value you are looking for. If it is the right one, you are done with the search and you now know that it exists. If it was not the right one, you check to see if the value you are searching for it higher or lower than that node and follow the right pointer to the next node where you repeat the same process until you find the node you are searching for, or ends up at a null pointer, a pointer that does not points to another node. In that case you know that the value you are searching for does not exist in this tree.
Next week we will start with network programming and the second part of the assignment.
Spörk 