what are the specific Mathematics and physics concepts a programmer should know to develop a game engine?

Question

Being a programmer (web applications and DB centered applications) I got knowledge in data structures (lists, trees, graphs etc.,). Honestly I used very little of these data structure algorithms in my coding (except the sorting things in plain arrays) as I worked almost with client oriented frameworks where all the core stuff built-in. Now I want start with game development. I had seen other SO questions regarding suggestions/tips/approaches on game development for beginners. I understand those point and am clear with those answers. Still I got few more questions [think not answered in SO I guess]. They are,

1. Is it valid to ask which data structures/algorithms are the most used in game development?
2. Which mathematical areas the game development demands from the programmer?
3. Is it mandatory to read some physics stuff? If so any specific list?

Well, my top priorities/aim is to,

1. Improve my core level programming skills [ I mean using data structure algorithms, mathematics and physics concepts etc.,]

2. Implement a good game engine [not to market it or to become rich ... completely to indulge myself into core level coding... to get that 'AHA' feeling]

3. To pave my way to A.I. research field [ It's always my dream field ]

My current skills are, C, PHP, core java, HTML, PL/SQL, MySQL.

currently learning, Python.

Edit: sorry I found this link for my 2nd question(mathematics), What math should all game programmers know?. But didn't find any links to 1st (data structures) and 3rd(physics) algorithms.

Edit: After few days of my post I realized I should implement a game first before I do with game engine. I got this link from some other SO question. It is an eye-opener for me. Posting this as others viewers of my category should also know this, Write Games, Not Engines

Thanks

Answer 1

Data Structures: It is certainly a valid question. However, while some Data Structures are useful for any sort of Game (like the ones you've already mentioned, Lists, Trees...), there are others that are very specific. For Example, Octrees can be very useful in 3D Programming, but in a pure 2D environment you will probably not be needing those.

Algorithms: The same rule of thumb applies. Example, in a pure 2D environment, Collision detection works very very differently than in 3D.

Important Mathematical Areas: THE Most important Area for a Engine Dev to be familiar with is Linear Algebra and more advanced Algebra Topics (Quaternions). Quite simple really, if you're comfortable with Linear Algebra (and I mean beyond simple Matrix multiplication), your off to a good start.

Next ist Geometry, which connects well to Linear Algebra in Engine Dev anyways, and probably doesn't need a mention anyways.

Further, it never hurts to have a solid understanding of Basic Calculus. This comes in Handy when dealing with the Physics Engine or more advanced Shading Topics.

Other Topics of Interest should be: Combinatorics, Statistics

Physics: It's not mandatory, IF you are intending to make simple games. Doesn't hurt, but you will get by fine with high-school physics in this case.

If you're thinking of writing a physics Engine, or implementing an existing Architecture, then yes, it's mandatory. But fear not, there are many Physics Books written specifically for Game-Devs. Just keep in mind, read these BEFORE you start coding a game with physics. If your game should have physics, these Engines will tie in deeply into your core architecture.

AI: To be entirely honest, if AI is your main Interest, I wouldn't bother with writing an entire Engine. AI is alot more fun to do when you have an existing Architecture to play with. Writing an Engine will be a pain, and will be quite a while until you are able to implement fun AI Algorithms.

What Type of Game do you wish to be developing? Perhaps I can elaborate more on these Points with this information.

Answer 2

While it may be valid to ask which data structures are most used in game development, it's way more valid to ask which data structures are used for specific problems. I can easily state that hash tables are super common in games, but that wouldn't tell you anything useful in terms of when and where to use (and not to use!) a hash table in your own code. :)

In terms of math, you need to have a very strong grasp of linear algebra (vectors, matrices, linear systems solving, etc.), a very strong grasp of trigonometry, and at least a basic understanding of calculus (simple derivatives and integration). Any introductory college-level linear algebra course should set you on the right path, if not teach you about all you need to know to start working with common 3D graphics principles. I also link a book below which you may find quite helpful.

For physics, you're in for a ride. Physics can be broken into two different categories: collision detection and collision response. You absolutely must know the math behind collision detection, as that math is more or less identical to what you need to do graphics (especially for building the trees and maps you need for occlusion), and you're going to use that stuff for a lot of your game logic as well.

Collision response can vary from "simple" to ridiculous levels of intricacy, and even the simple stuff can be non-intuitive at first. I would highly, highly recommend that you leave that stuff to an existing library like Bullet, Havok, PhysX, or so on (or Box2D if you're working on 2D gameplay) until and unless you're comfortable with your existing math and algorithm knowledge and decide you want to learn how physics engines work. I would then recommend you build a very simple 2D physics engine as your first attempt. 3D physics engines are insanely complex beasts, and are (arguably) by far the most complicated and difficult part of game programming, which is why physics engines are the most commonly licensed third-party tech used in games. You just don't see very many games that aren't using Havok or PhysX in the professional world, despite how many games have from-scratch home-grown graphics engines and core engine code. Even companies that do nothing but build game engines typically license a physics engine, e.g. Unreal just uses PhysX rather than including its own physics engine.

I would recommend the following books to get you started. The first is an introductory level book on the basic math you need to know as a 3D game programmer:

http://www.amazon.com/Mathematics-Programming-Computer-Graphics-Third/dp/1435458869

The second is a book detected to collision detection algorithms (not collision response!) which will help with both your graphics coding and your physics coding:

http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323