### Welcome to the Forum Archive!

Years of conversation fill a ton of digital pages, and we've kept all of it accessible to browse or copy over. Whether you're looking for reveal articles for older champions, or the first time that Rammus rolled into an "OK" thread, or anything in between, you can find it here. When you're finished, check out the boards to join in the latest League of Legends discussions.

### @WhattayaBrian What is your job?

LightEcho

Senior Member

Quote:
WhattayaBrian:
Ugh fine. "...by which I mean a comparison sort on generalized data."

I can do this too as long as we generalize generalized data as a set with two elements.
...I'm just giving you hard time.
At any rate never expected my first response from a rioter to be about sorting algorithms.

AtlaStar

Senior Member

So Whattaya, my question is this since I want to get a job at Riot eventually as an Engineer as well, but am fairly new to programming imo, how advanced is a custom written Binary Sort Tree that auto links, and balances itself, each time a new node is created? it just uses some fancy namespace workarounds and stuff in the classes constructor to do it since linking stuff manually is lame lol...Just really curious because I want to get an idea of what I need to work on as a C++ programmer in general

EDIT: it's also most efficient if it's used on another data-structure that is pre-sorted, since frankly writing a sort method for my BST proved to be quite inefficient in terms of O(n)

Basically each element added auto sorts, but it takes n recursions where n equals the insertion point + the remaining nodes until the end, plus one for each node added...so very inefficient at sorting things itself during run time, but able to parse an existing data structure using a total of n recursions where n equals the total node count of the structure

And it was K

Member

Explain what you do to a simpleton like me. You walk into the office, bow to Jesse Perring, and then...

WhattayaBrian

Engineer

Quote:
AtlaStar:
So Whattaya, my question is this since I want to get a job at Riot eventually as an Engineer as well, but am fairly new to programming imo, how advanced is a custom written Binary Sort Tree that auto links, and balances itself, each time a new node is created? it just uses some fancy namespace workarounds and stuff in the classes constructor to do it since linking stuff manually is lame lol...Just really curious because I want to get an idea of what I need to work on as a C++ programmer in general

There's actually a very diverse answer to that, depending on your preferences. There are some of here that are very specialized; for example, you may love graphics programming, and you know how to utilize DirectX to a wide degree.

I am not one of those people. I focus a lot more on the gameplay aspects of code, creating features for designers and exposing those to them.

Regarding your Binary Tree, there's not actually a lot of value in making data structures. I mean, don't get me wrong, it's much better to know what a binary tree is than not (especially since it goes hand-in-hand with so much algorithmic theory), but that won't impress most people.

What's important is understanding why you would or would not want to use it in a given scenarios.

What's good about a binary tree?
What are the different ways you can implement the binary tree functionality, and why would you want to do one over the other?

It's sort of a common misconception (at least I know I had it) that game programming is about constantly programming the most complicated stuff every day. That is about as far from the truth as you can possibly be. We love simplicity, because simple stuff is maintainable stuff. And when I need to hold a list of a variable, but small, number of objects, I do what everyone else does:

std::vector

Sprelf

Senior Member

Hey Brian. I'm going to be getting my Associate's Degree in Computer Languages after this upcoming spring semester. The degree is more of a formality, as I am 22 and have been programming since I was 16. Would this generally be sufficient if I were able to demonstrate my proficiency? Or would you recommend going through to a full Bachelor's?

AtlaStar

Senior Member

Quote:
WhattayaBrian:
There's actually a very diverse answer to that, depending on your preferences. There are some of here that are very specialized; for example, you may love graphics programming, and you know how to utilize DirectX to a wide degree.

I am not one of those people. I focus a lot more on the gameplay aspects of code, creating features for designers and exposing those to them.

Regarding your Binary Tree, there's not actually a lot of value in making data structures. I mean, don't get me wrong, it's much better to know what a binary tree is than not (especially since it goes hand-in-hand with so much algorithmic theory), but that won't impress most people.

What's important is understanding why you would or would not want to use it in a given scenarios.

What's good about a binary tree?
What are the different ways you can implement the binary tree functionality, and why would you want to do one over the other?

It's sort of a common misconception (at least I know I had it) that game programming is about constantly programming the most complicated stuff every day. That is about as far from the truth as you can possibly be. We love simplicity, because simple stuff is maintainable stuff. And when I need to hold a list of a variable, but small, number of objects, I do what everyone else does:

std::vector

Well the structure is pretty simple, and I definitely see what you are saying about where it would have strengths vs weaknesses.

It's strength would probably be best used in something like a very large data structure that needs sorted data, but a quick way to access the data since it's search has a O(log n) efficiency

What's bad about it is that it does add complexity to the program if it isn't balanced, making it to where you might not be getting an efficiency gain over std::vector, or very little gain

And it would be worst used in my opinion for graphics, just because loading each vector to create your polygons would require just as many recursions as a linear node based structure

More or less I made the structure with the idea that I could use it to parse code in another file, for something like say a level for a game that is going to change, so that I could free up space in ram and not have to load all the resources until I needed them, but I am very aware that it is best used with very large amounts of data and only better suited when you need to rapidly search through that data to use it somewhere else in the code...and if I'm mistaken feel free to correct me lol, because I do wish to become a better programmer...and btw I like the back end stuff, not so much into graphics or anything like that...if that makes sense

MetalSparty

Senior Member

I love how willing this guy is to answer everyone's questions in detail. He sounds legitimately interested in his responses.

F5 Zarozz Mid

Senior Member

How much exposure to the Java dev's at riot having to the gaming side of development at riot?
I'm currently doing a year of industry based learning for Uni ( my 3rd year out of 4). and would love to work at riot one day.

I work with JEE, spring, hibernate, maven, jenkins, mercurial, jquery. Using Rad and Websphere.
Are these technologies used within Riot?

steelfirez

Senior Member

Quote:
Method512:
Python is actually used? I had a friend that learned that language but I never bothered thinking it wasn't used...

Ha, that's why Google uses Python for a large part of it's infrastructure. I hear Python is also fairly popular among many startups, as is Ruby, Javascript, and PHP. In the words of Alex Martelli, "Python where we can. C++ where we must."

Quote:
WhattayaBrian:

Well, you won't find any commercial games made it in, but that's not its purpose. You use it to write scripts to automate mundane tasks.

I'm pretty sure the Civilization series is written in Python.

WhattayaBrian

Engineer

Regarding commercial games using Python, what I meant was that the codebase would not be done in Python. I'm sure many games use Python as their scripting language, just as they would Lua.

That said, I'm aware that you can actually make entire games out of Python. I've just never seen a commercial one that did so. I'd be intrigued if there were.

Quote:
Sprelf:
Hey Brian. I'm going to be getting my Associate's Degree in Computer Languages after this upcoming spring semester. The degree is more of a formality, as I am 22 and have been programming since I was 16. Would this generally be sufficient if I were able to demonstrate my proficiency? Or would you recommend going through to a full Bachelor's?

Your objective should be to get an interview--if you know your stuff, the interview process will be an awesome way to show your proficiency. What you need is a way to sell yourself so that you get the interview.

In general, having completed (or showable) projects is really, really good. If they're games, they're even better. It also gives you something to talk about during your interview.

Quote:
AtlaStar:
Well the structure is pretty simple, and I definitely see what you are saying about where it would have strengths vs weaknesses.

It's strength would probably be best used in something like a very large data structure that needs sorted data, but a quick way to access the data since it's search has a O(log n) efficiency

What's bad about it is that it does add complexity to the program if it isn't balanced, making it to where you might not be getting an efficiency gain over std::vector, or very little gain

And it would be worst used in my opinion for graphics, just because loading each vector to create your polygons would require just as many recursions as a linear node based structure

More or less I made the structure with the idea that I could use it to parse code in another file, for something like say a level for a game that is going to change, so that I could free up space in ram and not have to load all the resources until I needed them, but I am very aware that it is best used with very large amounts of data and only better suited when you need to rapidly search through that data to use it somewhere else in the code...and if I'm mistaken feel free to correct me lol, because I do wish to become a better programmer...and btw I like the back end stuff, not so much into graphics or anything like that...if that makes sense

So, in school, you're generally taught about time and space complexity of algorithms, but those are not the only aspects that determine a data structure's or algorithm's runtime speed. Another huge part of those determinations is Locality of Reference. That is to say, contiguous data is best data.

So the "classic" definition of a binary tree involves something like this:

struct Node
{
MyData data;
Node * left;
Node * right;
};

And whenever you need a new child, you do something like:

node->left = new Node;

But, barring overloading operator new(), these allocations are fragmenting your data. If you're traversing through a tree, you may repeatedly cache miss as you go from child to child, heavily impacting your runtime.

One alternative is to use an array to hold your binary tree. The parent is index 0, and the children of any index follow this pattern:

left = 2n + 1
right = 2n + 2

As a natural consequence of this, a breadth-first search is just an iteration from beginning to end of the entire array. That's pretty neat.

But do you want to do that? Well, what are we using this tree for? Is it used a lot, or a little? Is it a heap? Is it being used for breadth-first or depth-first searches? Are things being removed from it constantly?

The algorithms are extremely important, but so are the underlying data structures. In some situations, you may want to resize this "array-based binary tree" just like a vector would when it hits its cap. But if "MyData" is large, maybe that's to large a cost. Maybe instead we implement blocks of memory like a deque, so that we never have to move things and we still get lots of locality of reference. But if we're doing depth-first searches, we could be jumping blocks all the time, which is bad...

My lesson to you is this: programming is about using the right tool for the job, but the reason it's so hard is that there's a lot of stuff to consider. :P

(Also you can pretty much always use vector because locality of reference is that powerful.)

Quote:
Zarozz:
How much exposure to the Java dev's at riot having to the gaming side of development at riot?
I'm currently doing a year of industry based learning for Uni ( my 3rd year out of 4). and would love to work at riot one day.

I work with JEE, spring, hibernate, maven, jenkins, mercurial, jquery. Using Rad and Websphere.
Are these technologies used within Riot?

Hmm...

We use Jenkins and Maven for our build processes, but I'm not sure about the rest. I actually know very little about our Java codebase and utilities. Soz, yo. :[