Sign in to follow this  
kaktusas2598

Data Structures and Algorithms for Game Programming

Recommended Posts

Data structures and algorithms are overemphasized.

In 95% of cases, you're better off using a standard container in the language you're using (a hashmap, an array list, a linked list, whatever).

It's only when you are well into making your game and you're trying to squeeze out those last few frames per second do you need to resort to fancy structures.

Wikipedia is a good place to start. What kind of data structures in particular are you looking for information on?

Share this post


Link to post
Share on other sites
Quote:
Original post by Tac-Tics
Data structures and algorithms are overemphasized.

In 95% of cases, you're better off using a standard container in the language you're using (a hashmap, an array list, a linked list, whatever).


If you don't know the basic principles behind the data structures that the containers use, how will you know which container is more appropriate in a particular situation?

Share this post


Link to post
Share on other sites
Quote:
Original post by Gage64
If you don't know the basic principles behind the data structures that the containers use, how will you know which container is more appropriate in a particular situation?


If you need a way to look up an object by a string identifier, you use a hash.

If you need a way to look up an object by an integer identifier, you use an array list.

If you need to look up an object by something else, you use hashes if your language supports it or a linear search on an array list otherwise.

These three rules will give you the best solution most of the time.

I'm not saying that binary trees or red-black trees or skip lists or heaps aren't at all useful. They just aren't useful most of the time. They are optimizations. You fall back on them only after your code fails to scale with naive methods.

Share this post


Link to post
Share on other sites
You didn't answer his question.

If you don't know about the data structures (just aware of their existence and their use; completely ignore implementation) then how will you know what container to use (which is based on and implemented from said data structures) properly?

Share this post


Link to post
Share on other sites
Quote:
Original post by Alpha_ProgDes
You didn't answer his question.


The answer was check Wikipedia.

Here's more than you'll ever need:

http://en.wikipedia.org/wiki/List_of_data_structures

Share this post


Link to post
Share on other sites
Get a good book on data structures or take a class (really only available in college). It's definitely something you want to know about if only to be able to get a job: data structure questions are the singular biggest bucket of questions you'll get asked (whether you think it's important or not is irrelevant)

The list that TicTac posted is a good place to start for sure.

-me

Share this post


Link to post
Share on other sites
Quote:

It's definitely something you want to know about if only to be able to get a job: data structure questions are the singular biggest bucket of questions you'll get asked (whether you think it's important or not is irrelevant)


Not in my experience. I've seen very few data structure questions in interviews (from both sides of the fence), mostly for the reason Tac-Tics pointed out originally. You have maybe 2-3 major structures that are part of the standard library that are good enough for almost everything.

They're still useful to learn, but not exactly a primary concern if I were going into an interview tomorrow.

Share this post


Link to post
Share on other sites
Quote:
Original post by Telastyn
They're still useful to learn, but not exactly a primary concern if I were going into an interview tomorrow.


Yeah.

Data structures and algorithms belong to the academic domain. They are mathematically interesting and there are enough variations on each of them to keep PhDs employed.

In a job interview, though, you're in an industrial domain. The interviewer will typically be more interested in what technologies you know and what professional work you've done.

Even the really keen employers won't really care if you can tell a Red-Black tree from an AVL tree. They'll just want to see if you can reason about a hard problem.

Share this post


Link to post
Share on other sites
Quote:
Original post by Tac-Tics
Data structures and algorithms belong to the academic domain. They are mathematically interesting and there are enough variations on each of them to keep PhDs employed.
What?!

When you create a class or a struct, you are creating a data structure.

Every line of code you write is part of an algorithm, or else it is dead code.

So I'm going to have to disagree with that. Data structures and algorithms are the foundation of computer programming.


I don't know why when the OP wrote "algorithm" you interpreted it as "container". Containers are an infinitesimally small subset of algorithms.

Share this post


Link to post
Share on other sites
Quote:
They'll just want to see if you can reason about a hard problem.


What do you consider a hard problem?

Share this post


Link to post
Share on other sites
Quote:
Original post by Tac-Tics
Quote:
Original post by Telastyn
They're still useful to learn, but not exactly a primary concern if I were going into an interview tomorrow.


Yeah.

Data structures and algorithms belong to the academic domain.


No. That's definitely not what I meant.

Quote:

In a job interview, though, you're in an industrial domain. The interviewer will typically be more interested in what technologies you know and what professional work you've done.


Only if they're rather dim, or expect you to do code monkey work. Data structures aren't typically asked because they don't really provide much insight into your ability to solve problems. What technologies you know doesn't really answer that either, but knowing what technologies you know allows the interviewer to ask questions in terms the interviewee knows. It also serves as a baseline to judge if the interviewee has enough self awareness to know how much they know.

Share this post


Link to post
Share on other sites
Quote:
Original post by frob
Quote:
Original post by Tac-Tics
Data structures and algorithms belong to the academic domain. They are mathematically interesting and there are enough variations on each of them to keep PhDs employed.
What?!

When you create a class or a struct, you are creating a data structure.

Every line of code you write is part of an algorithm, or else it is dead code.

So I'm going to have to disagree with that. Data structures and algorithms are the foundation of computer programming.


I don't know why when the OP wrote "algorithm" you interpreted it as "container". Containers are an infinitesimally small subset of algorithms.


Everything you say is true, but when the phrase "Data structures and algorithms" is used, it typically refers to what you learned in your CS "Data Structures and Algorithms" class, which consists largely of the things everyone has claimed are mostly irrelevant to game development.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dragon88
Everything you say is true, but when the phrase "Data structures and algorithms" is used, it typically refers to what you learned in your CS "Data Structures and Algorithms" class, which consists largely of the things everyone has claimed are mostly irrelevant to game development.


Then what would be relevant?

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Original post by Dragon88
Everything you say is true, but when the phrase "Data structures and algorithms" is used, it typically refers to what you learned in your CS "Data Structures and Algorithms" class, which consists largely of the things everyone has claimed are mostly irrelevant to game development.


Then what would be relevant?


The types of "data structures and algorithms" frob was referencing, such as all the various classes you create, and the algorithms you use to achieve whatever it is your game does. Unfortunately those tend to vary widely depending on your specific game, so there aren't nice canned examples to give. Ultimately, that's why "data structures and algorithms" gets associated with linked lists, trees, binary searches, and the like. They're nice canned examples that you can point to.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dragon88

Unfortunately those tend to vary widely depending on your specific game, so there aren't nice canned examples to give.


So one should do pole vaulting, but refusing to learn how to crawl, walk and run first?

Quote:
Ultimately, that's why "data structures and algorithms" gets associated with linked lists, trees, binary searches, and the like. They're nice canned examples that you can point to.


They are the fundamental alphabet. There's only 7 or so of basic ADTs, and in 101 course they are used to teach O(n), space complexity and recursion.

Algorithmic fundamentals include depth- vs. breadth- first, dynamic programming, graph optimization and recursion. In light of a CS course, these cover the basics of languages.

In longer term, they provide the common grammar through which databases, file systems, network organizations and graphic stacks and algorithms are explained.

In context of university, in ideal world (not much so in reality), someone going for the whole 9 yards should have no problem understanding and evaluating the individual characteristics of various APIs, regardless of language, and should be able to provide adequately competent educated guess about which to choose and which trade-offs to make even without previous experience.

In reality, most of Java Schools do not teach that, so there most of technology choices are based on what's popular on reddit, or what was written in latest IT journal.

Perhaps something that is not obvious is that anyone who wants to go beyond trivial stuff needs to learn this. Not just because it would benefit them, but the lack of this knowledge makes it impossible to scale beyond the most elementary programming tasks. Not knowing what List, Stack, Tree or Graph are makes it impossible to do anything. Material in 101 course is just a proven way of how the fundamentals are taught. They are not there to teach how to code a Linked List in Java.

And then they come up with useful abstractions, such as Composite or Adapter or Visitor.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dragon88
when the phrase "Data structures and algorithms" is used, it typically refers to what you learned in your CS "Data Structures and Algorithms" class, which consists largely of the things everyone has claimed are mostly irrelevant to game development.
...
Ultimately, that's why "data structures and algorithms" gets associated with linked lists, trees, binary searches, and the like. They're nice canned examples that you can point to.
I really hope that's not what gets taught these days, but based on the interviews, there are a few schools who do just that. Fortunately my local Universities (which are highly ranked nationally in CS) don't have that problem.

I just pulled my 20-year-old book from my Data Structures and Algorithms class off my shelf. Yes, it really was within arms reach of my desk. These are the things I learned about in the class:



It starts out with the basics of data types. Basically how it is nothing more than a structure that contains fields, and so on.

It only spends 66 pages on the basic containers: arrays, linked lists, stacks, queues, trees, and general digraphs. That includes examples for implementations, and general homework assignments. As Antheus said, the containers are just a very common building block.

The remaining nearly 500 pages of the text covered the fundamentals of algorithms.

Assorted sorting algorithms -- 27 varieties, ranging from the basic sequential, binary, and tree searches, up through b-trees and the polyphase merge sort, useful for extremely huge data sets. It covers analysis of each one. Again, with homework assignments. All this in just over 100 pages.

Assorted searching algorithms -- 22 variations on ways to search for data, each with their own performance analysis. Many of them are coupled with their corresponding sorting algorithm, covered earlier. This is 60 pages, just as much as the containers.


String and data processing -- Including optimized string-specific searches, pattern matching, parsing, and an introduction to grammars and compiler theory. Also included in the section are the basics of file compression (from run length code to Huffman tables with optimized token generation) and the basics of cryptography, including the algorithms and theory behind public-key crypto.

I remember that last chapter well because we had to implement our own cipher engine based on some wonderfully tricky math the instructor presented.

Graph algorithms -- An analysis of the searches in terms of depth-first and breadth-first algorithms. Then it goes through another 25 algorithms from spanning trees and shortest paths to network flows and bipartite graphs. 90 pages.

Geometric algorithms -- from basic points, lines, and polys, through convex hulls, spatial trees, assorted geometrical intersections in multiple dimensions, and more. Another 60 pages.

Numerical algorithms -- An assortment of random number generators. Polynomial arithmetic. Large integers. Gaussian elimination and other matrix-based algorithms, curve fitting and spline interpolation. Integration, symbolic integration, quadrature and adaptive quadrature methods for mathematical analysis. This is 70 pages.

Finally, it covers assorted other algorithm notes. It has some formal algorithm analysis intro material such as P vs NP, NP-hard, NP-complete, unsolvable problems, BPP, ZPP, IP, and more. The section includes parallel and distributed algorithms, dynamic processing, linear and geometric programming, signal processing, audio processing, and finishes off on a bunch of unfinished and unproven algorithm theories.

I recall covering the entire book in the course, in addition to some pet projects from the instructor.



I consider those basic, fundamental topics. I have asked questions about several of those topics, which I assume is part of the reason we can screen out so many unskilled and undereducated people. These are not topics you can cram for before an interview. They are broad topics that you either understand or not.

Quote:
Unfortunately those tend to vary widely depending on your specific game, so there aren't nice canned examples to give.
If you understand the theory behind the core algorithms, many of which are listed above, then you should have no problem with any algorithm needed for game programming.

Those items above encompass the theory behind game-centric algorithms like path finding, lots of kinds of AI, spatial trees, animations and animation blending, the algorithmic portions of rendering, storage, rapid retrieval from slow media (I wish more games took advantage of this on their discs!) audio processing, task scheduling, and everything else I can think of.




To the OP: If you want good books, go find a current version of "Algorithms", by Robert Sedgewick, or the more definitive (and expensive) series of books "The Art of Computer Programming" by Donald Knuth. The first has several editions focusing on individual languages. The second uses Knuth's own extremely simple language to explain what amounts to an introduction of the full breadth of computer science topics.

Share this post


Link to post
Share on other sites
Quote:
Original post by Tac-Tics
In a job interview, though, you're in an industrial domain. The interviewer will typically be more interested in what technologies you know and what professional work you've done.

Even the really keen employers won't really care if you can tell a Red-Black tree. [...]

I guess it depends on the kind of job you're interviewing for. I've never had an interview in which they were overly concerned with "what technologies" I know, if by that you mean programming languages and development environments. And on the other hand I think I've been asked to explain how a hash table works (in one way or another) in about half of the interviews I've had.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this