Most of cyphers have some kind of decryption key, mostly between 256 to 4098 bits long. That means the (256 bit) key is 256 ones or zeroes (where order is important), so there's 2^256 combinations you have to try. To quote a stack overflow question about it:

You'd expect to find it after going through (on average) half of the keys, so average expected number of attempts would be 2^255. This is a Really Big Number. If every atom on earth (about 1.3 * 10^50 atoms) was a computer that could try ten billion keys a second, it would still take about 2.84 billion years.

But, remembering and imputing 256 ones or zeroes (or one number between 0-2^255, if you convert it from binary to decimal, which is around 78 digits) is really difficult and infeasible in practice. Due to that, when you want to encrypt something for example with a password that is easier to remember, you somehow have to generate the 256b key from the password, usually using a hash function. Because hash functions are designed to convert mostly any input into a 256b (or other size) bit keys, while making sure that the 256b are randomly distributed - so if you for example change one letter in the password, the hash will be absolutely random (but still the same for the same input), with no way to tell that it has anything in common with the hash of the previous password.

However, this introduces a problem - if for example you only used 4 digit PINs for the password, all anyone needs to do now is to 1) figure out how you generate the 256b encryption key from the PIN (which is usually doable by reverse-engineering the code), and 2) try every 4 digit combination, generate a key from it and then see if that key decrypts the data. That's only 6561 combinations, and can be done pretty quickly. So, by using the password that's limited to 4 digit PIN, even though you are using a 256b key for encryption, you have reduced the number of keys that can be valid - because there's only 6561 valid passwords, which only map to 6561 encryption keys out of the 2^256.

EDIT: I've realized that I've explained something you didn't ask for, I'll just keep it up for others, I didn't read your question properly, sorry about that :D

For the game development, assuming the author wants to use AES, it would mean that either there is some kind of "password", be it having to input a number, interact with game objects in certain order, or do some actions in order, out of which the key is generated. But then the answer has to be really complex (super-large number, or interacting with tens to hundreds of objects, or a long string), so the number of possible answers is large-enough that it can't be brute-forced - which would make for a really hard puzzle. Even if you for example required the player to input a text password of some kind, it could get frustrating, since it would have to be pretty long to not be bruteforcable.

The other solution I was thinking about is that you would have 256 objects or puzzles, where represents one "digit" in the key. If you solved the puzzle, the digit would flip to 1. However, it would be easy to check from code which puzzles are connected to the key - because that's what you are generating the key from. That would mean that unless you want the key to be all 1, some of the puzzles that are connected would have to be unreachable by the player (which can also be data-mined with some effort) or intended to NOT be solved, which does add more complexity and makes the puzzle even harder - those would be the red herrings.

could the game designed in theory put those 256 bits of key into 256 puzzles - with several hundred more puzzle pieces being red herrings?

Not exactly, because if you wanted to generate the key by solving 256 puzzles, it would mean that either the key is 256 ones, or each puzzle has a value - one or zero - it adds to the key. If that's the case, then you can simply take the values from the puzzle code and generate the key like that. Having more red herrings wouldn't help, because in code (which you can dissasemble and reverse-engineer with enough skill), there will have to be a function "UnlockSecret(key)", and probably something like "key = CreateKey()". And in the CreateKey function, you have to have only the puzzles that are not red herrings - otherwise the code has no way of knowing which puzzles to use for building the key. So a dataminer would just check the CreateKey function, and then check what exact puzzles are used for the key. That's why the only option in this case is to have a 256 puzzles, where each is either completed (1) or uncomplete(0), and out of the 256 puzzles, some are red herrings that should not be completed (and stay at 0), and some that should be - and those add 1s into the key.

However, now that I think about, just having some kind of a cypher puzzle which gets you a password of 10-20 characters (that's 10^29 options) would probably be enough. But then again - that's not that much fun, and it greatly limits what you can actually design.