Game Programming III – Blog Post 1 (For real this time)
|
Okay, let’s be serious…
This week has been mainly about learning about new concepts such as linked lists, binary trees and templates in C++, and how to use them, so this post is mostly gonna be about what I’ve learned and what holes I need to fill in the future. Oh, and I wrote some code.
The first thing we looked at was templates. Templates are declared as follows:
Template
In this case the template is a class of any type. It seems like they can be used as a sort of wild card for different methods, that said; it’s not very easy to use. The errors you get are usually rather long and hard to decode as well as not very specific in some cases, having said that: they seem invaluable in order to make a linked list or a binary tree (more on that later). A method using a template can look like this:
Template
void Method(T &p_trParameter){
//…
}
Basically, the template has to be declared before every method that uses it. I do know that there are ways around this, but I’ve yet to properly research or try any of them properly. What I also learned in my code-typing was that when you introduce a template in a class the class changes into classname, so if I write a class that looks like this:
//.h
template class
class Alice {
public:
Alice* Bob();
T Cecil();
private:
T m_t;
Alice *m_xp;
}
And I then declare the methods in the .cpp file like this:
//.cpp
template
Alice* Alice::Bob(){
//…
}
template
T* Alice::Cecil(){
//…
}
I am going to get an error. The thing is, once I declare template T to be a part of Alice, Alice is no longer a class in this instance and I have to write Alice instead, so:
//.cpp
template
Alice* Alice::Bob(){ // ß This is the part that was fixed!
//…
}
template
T* Alice::Cecil(){
//…
}
…works just fine.
The next thing we learned about was linked lists. I’ve worked with a simple linked list in the past so I know the basic idea behind them. Basically you have several nodes, each and every one consisting of one item and a pointer. The item could be pretty much anything (this is where templates comes in handy). The pointer holds the memory address of the next item in the list. Using this system you could create a long row of items (a list if you so will) that the program can go over and check individually. Sometimes the nodes in a linked list are made of one item and two nodes, one for the next and one for the previous one. Finally, there is a pointer in the list itself that points towards the first node in the list. The advantages of linked lists are that it doesn’t take much memory and it’s easy to add and remove items to the list. The downsides are that there are a lot of memory allocations, it can get rather slow when the list is huge and you can’t optimize the search.
The third important thing we went over was binary trees. I’ve heard about these things before but never actually had the concept explained to me in a comprehensible manner. It’s a lot like the linked list but instead of every item having a pointer leading to the next one each item also has a pointer that leads to another next item. So a node in a binary search tree has two references as a standard.
When a new node is added and there isn’t a root node already the new node becomes the root node (i.e. the very first node). When the next node is added depending on if its value is higher or lower than the root node it moves either to the left or to the right and then it keeps that up.
Just like the linked list there are several advantages to using a binary tree. The first advantage is that it becomes a lot easier to search for a specific item since you need to go through fewer items every time you look through the tree. The second advantage is the same as the linked list, it doesn’t take a lot of memory to set up, though, at minimum it might take a little more than the linked list but that shouldn’t really matter too much (it’s not that big of a difference, it’s just one extra pointer per item). Finally, it becomes easier to search for items in the tree.
In the case of the disadvantages on the other hand there are a few as well, first of all, it’s harder to remove items from the tree, of course, this depends on how many children the item has (the more children the harder it becomes). The second disadvantage is related to how items are added to the tree, since items that have a higher value are placed on the right while items that have a lower value are placed on the left, this means that if all items added are lower than the initial root then it just becomes a linked list instead. Some trees will try to fix this by changing the tree around every once in a while but this means that adding items now takes more power if it isn’t done really well (also it requires a lot of memory allocations).
The final thing is the idea of TDD’s. that is, Test Driven Development which is where you make a test program to see if your idea works and then implement it. It seems really interesting and useful but I haven’t actually done any research about it yet. I plan on doing it in the upcoming week.
Speaking of the upcoming week, I started out with the first assignment of the course. Basically I used pretty much everything I learned from the above (except binary trees and TDD, so just half of it, then…) to make the beginning of a linked list. I plan on continuing the work this Monday and I hope to be done by Tuesday, but I’m planning for Wednesday. It is possible that I’m done by Monday but that’s me being really optimistic. Once I’m done with that I’m going to start building a binary tree which should be done by the next weekend if I don’t spend too much time with the linked list. Anyway, that’s just me planning.
Finally, I know I was supposed to write this thing earlier but things kept getting in my way and I wasn’t feeling to well, yesterday night. Either way, I’ll get back to working tomorrow.
~♪
|