/agdg/ - Amateur Game Development General

Game programming gems sounds like it, but it's more of a hit or miss

You probably should find out which conepts you really need and look for specific books or articles because most conepts are not specific to game development. It's hard to gather them all because you won't need them all.

What >>19832 said, GPG.

http://www.satori.org/game-programming-gems/

I'm sure you can find PDF versions online if you look hard enough. Do note that the later books become both more advanced and more narrow, book one for instance has stuff on A* and Quaternions. Basics, like what you seem to want.

There's also GPU Programming Gems, but that one might be more for the enginedevs here.

>>19832

>>19833

Ah yeah, I heard about Game Programming gems but did not try to look further. It seems really promising.

Any other useful books or websites?

>>19834

One other book I have personally I already mentioned in >>19814

It's focused on math, but covers everything from raycasting to physics and collisions, to fluid and cloth simulation.

The few other books I have are all language-specific ones though.

>>19849

looks like what spacex is doing

https://www.youtube.com/watch?v=txk-VO1hzBY

>>20214

>I applied to an internship

> I send my cover letter and resume

> In English and French (because in Switzerland)

> mfw I never have answer

I will look at this video. Thank you to share.

>>19849

I never understood trees.

Like I get they're super efficient, but why can buckets hold more than one item? If it gets dense enough, wouldn't it get into decimals values and break your implementation?

>>20248

>but why can buckets hold more than one item?

You mean points? Most implementations have an arbitrary number of points/entities each node can have, and it splits after that. This happens because there is nothing wrong with having more than one point in the same node, as long as the number is reasonable to avoid checking too many collisions between them.

Of course, that also means you could set 1 as the maximum number of points a node can hold so it splits as soon as another one enters the zone

>If it gets dense enough, wouldn't it get into decimals values and break your implementation?

Why? An int will always be an int.

Unless you are using some weird dynamically typed language, something you should never do.

Single-object quadtree:

https://www.youtube.com/watch?v=fuexOsLOfl0

Multiples object quadtree:

https://www.youtube.com/watch?v=TJzq_kjtGTc

I would say the first one is much more efficient with lots of objects if you pool the quadtree. If you are creating new nodes on the fly though, you might want to up the threshold.

rectrees > quadtrees for most purposes

>>19830

http://gameprogrammingpatterns.com/ ?

>>21880

>rectree

Quadtrees are recursive too, unless you are talking about something different altogether.

>>21927

rectrees generally have much less depth, and quadtrees will have regions where getting a neighbor requires a full walk, while rectrees almost never have that

>>21955

sadly its mostly research papers, though they aren't as intimidating if you just skim them

Make groups based off a heuristic, normally area of the node

>>21966

That'd win in sparsity and depth. What about performance? O(log N) that takes 2000 cycles per iteration is not the same as O(log N) that takes 50 cycles per iteration.

>>21970

Trees are always limited by cache misses. Doing a for over the bounds of child nodes is pretty insubstantial

>>21971

I don't mean search, I mean modification, and this is the important aspect - unless you only plan to deal with static objects. For quadtree, insertion is as simple as comparing against node coordinates to figure out quadrant, and put your object into that quadrant. When you create new node, you only compute half of its parent's dimensions and its coordinates which are parent coordinates plus half-dimensions. There aren't any other calculations involved. So for very close objects the tree may grow very deep, but it's compensated by the fact that it's very cheap to modify this tree - it barely costs anything at all - and search is still reasonably fast (for some really fucking big maps, is only 10-15 levels of depth at worst).

>>21974

You also dont have to make a tree from scratch, you can save nodes to the objects in them and do a walk, doing a parial reinsert only if changing nodes

Its really situationally dependent. For most purposes in simple games theres not a noticeable difference between quad and rect, but for large sims with lots of objects rect is the way to go.

>>21976

That's kinda out of question, comparison still stands though. And since quadtree doesn't uses any kind of sophisticated calculations, it has very little computational footprint. Recttree have to, at bare minimum, compute bounding areas of clustered objects, which requires finding clusters in beforehand. Cluster overlapping significantly reduces algorithm efficiency and therefore it has to run extra steps to determine optimal clustering. When an object moves across quadtree, it just jumps from one quad sector to another, and then to another quad node. In rectree it would continuously affect cluster dimensions and dynamic restructurizing of the tree would be at best suboptimal approximation, so periodically you'd have to re-build entire tree from scratch.

In short, just like any algorithm that attempts to optimize space, it suffers from very poor real-time performance since it has no place that allows taking advantage of simple deterministic rules. UTF-8 vs. 4-byte wide characters.