# Tag Info

Accepted

### Why are some games np-complete?

It just means that you can create levels or puzzles within these games that encode NP-Hard problems. You can take a graph coloring problem, create an associated Super Mario Bros. level, and that level ...
• 5,852

### Why are some games np-complete?

I honestly don't know exactly what kind of model is used by the people making those claims; however, what seems reasonable to me would be talking about the $\mathcal{NP}$-completeness of deciding ...
• 4,252

### Detecting conservation, loss, or gain in a crafting game with items and recipes

Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (...
• 5,479

### Finding an optimal solution in a tile painting game

This is the Hamiltonian path problem on partial grid graphs (i.e., graphs which are arbitrary subgraphs of grids) which is known to be NP-complete. Thus, no polynomial algorithm exists unless P = NP. ...
• 22.6k

### Playing video games to solve SAT instances

No. The gamer will basically have to work out the SAT problem in their head. Think of any video game puzzle you've solved that wasn't easy. You probably solved it by working out a simpler version of ...
• 1,739

### How is CPU different from GPU?

GPUs are highly specialized: they are very good at a very small number of things, but they are extremely bad at everything else. CPUs are general: they are mediocre at everything. GPUs are good at ...
• 6,140

### Why are some games np-complete?

For single player games, you can always ask the question "is there a winning strategy for the player", and that question often has a "YES" answer that can be verified in polynomial time, and may very ...
• 30k
Accepted

### Detecting conservation, loss, or gain in a crafting game with items and recipes

This should be solvable with linear programming. Background and setup Let the state vector be a vector of the count of number of each item you have. If the possible items are milk, wheat, sugar, ...
• 159k
Accepted

### What data structure might this game use?

A hashtable is asymptotically optimal. Your analysis led you astray. The relevant parameter is the number of rules that exist (where each rule specifies a combination of two elements and what new ...
• 159k
Accepted

### Why isn't the Generalized Super Mario Bros. obviously in NP?

One reason why it is not obvious that reachability of SMB is NP is that we would need a complete formalization of SMB, which the paper does not provide. This makes sense, as the purpose of the paper ...
• 8,248

### Algorithms for procedural generated mazes

If you have to create the maze: Without boundaries Generated uniformly Generated from a seed It is unfortunately impossible without risking an endless loop, but most times it is good enough to ...
• 121

### Why are some games np-complete?

Here's a simplistic hand-waving explanation: Such games are in NP because "running" a player's behavior over the course of a game and checking whether s/he wins or loses can be done efficiently (we ...
• 965
Accepted

• 159k
1 vote
Accepted

• 8,248
1 vote

### Why is the video game Braid Turing-complete?

Because Braid can simulate a variant of Rush Hour, which is at least PSPACE-hard. Additionally, Braid itself is undecidable because it can simulate a counter machine which is equivalent to a Turing ...
• 594
1 vote

### Extreme instancing for computer graphics

Yes, you are correct. What you suggest is a viable approach in 3D games. Popular game engines already do this, and have been doing this for some time. If you choose to do this through the vertex ...
• 251

Only top scored, non community-wiki answers of a minimum length are eligible