Questions tagged [computer-games]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-2 votes
0 answers
46 views

struggling to prove the C-competitiveness of MTS

i need to show that if a MTS algorithm α is C-competitive against sequences of elementary cost vectors, then its C-competitive against any sequence of (non-negative) cost vectors. i tried to describe ...
amy's user avatar
  • 1
1 vote
1 answer
54 views

Memory efficient undo data structure

I was playing a puzzle game and started wondering how they implemented their undo feature. The game only has five possible moves, and only when the player does a move does the game state change, but ...
SmileyCraft's user avatar
0 votes
1 answer
33 views

Calculate odds that cards drawn from deck sum to at least some number ("Across the Obelisk" problem)

Here is a problem inspired by the game Across the Obelisk. 4 players have decks of cards. Each card has an integer value between 0-9 on it. The decks can be any size, and there's no other restriction ...
BlueRaja - Danny Pflughoeft's user avatar
1 vote
1 answer
40 views

Are there already Neural Network AIs that can play object-finding games?

Neural networks are good at image analysis. They are also being used in video games which could outperform professional human players. I wonder if they can also play a purely object-finding game where ...
Software Carpenter's user avatar
2 votes
1 answer
43 views

How can I best represent my 2D thrust problem as a linear programming problem?

While my question stems from game dev, the problem itself isn't as much about the game, but more about correctly representing my problem as a linear programming problem that I can solve with a linear ...
Nathan K's user avatar
  • 123
2 votes
0 answers
35 views

How do video games like Age of Empires code how a soldier spots an enemy soldier and decides to attack?

I was just curious how do RTS games actually implement this. There are usually thousands of units on the whole map. They all have usually unique range of sight and then there's also settings for ...
Manas's user avatar
  • 21
2 votes
1 answer
28 views

Comparing various ways to move a game actor having time-dependent velocity

Assume I have a game actor (name it MyActor for further references) to be moved up and down according to $z=f(t)=A\sin \omega t$ (or any non constant velocity). The ...
Display Name's user avatar
1 vote
0 answers
162 views

What algorithm is best for resource gathering in an RTS game in quickest time?

Though the concept can be for many RTS games but lets use the specific system of 'age of empires'. For simplicity one resource will be considered. Food. So in the game there are villagers who gather ...
Uchiha Madara's user avatar
2 votes
1 answer
94 views

Finding an optimal solution in a tile painting game

The Problem Find the shortest sequence of moves that makes up the optimal solution of a level. If there is more than one optimal solution, just find one of them. Game Rules The game level is made up ...
Grzybojad's user avatar
2 votes
0 answers
174 views

How computationally hard are the battle systems of Paper Mario and Paper Mario: The Thousand Year Door?

What is the time complexity and space complexity of working out, in suitably generalised versions of the battle systems of both Paper Mario 64 and Paper Mario: The Thousand Year Door: The minimum ...
David Tyas's user avatar
1 vote
2 answers
357 views

Complexity of simulating idle games (pt1)

An idle game (Cookie Clicker is a well-known example) is a game where you set up automatic resource production, and most of reasonable human play is then waiting as resources accumulate. Typical ...
Zachary Vance's user avatar
3 votes
2 answers
207 views

Playing video games to solve SAT instances

This paper shows that computer games, such as Super Mario, are NP-hard, by reduction from SAT. It may be possible to use this reduction to help solve hard instances of SAT: use the reduction to ...
Erel Segal-Halevi's user avatar
2 votes
2 answers
311 views

How is CPU different from GPU?

A central processing unit offers to handle various operations like calculating, watching movies, making presentation etc. While a graphics processing unit is majorly used for the purpose of video ...
Tejal Barnwal's user avatar
1 vote
1 answer
53 views

Where is the theory about "binary toggling games"?

Let us -- using parameters $M, N$ and $L$ -- create an ordered set of size $M$ of $N$-bit long vectors $V$ and initialize them randomly: $V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in \{0\ ..\ N-1\}...
Captain Trojan's user avatar
5 votes
2 answers
124 views

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

Suppose we're designing a game like Minecraft where we have lots of items $i_1,i_2,...,i_n\in I$ and a bunch of recipes $r_1,r_2,...,r_m\in R$. Recipes are functions $r:(I\times\mathbb{N})^n\...
flinty's user avatar
  • 153
2 votes
1 answer
564 views

What is the best solving algorithm for a game with stacks?

Game Explanation: Suppose there is a game with cards that have numbers from 1 to n. Each card has a different number so there are not two cards with the same number. The deck is scrambled. We chose ...
user avatar
3 votes
2 answers
573 views

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

It is shown in the paper: "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta that the Generalized Super Mario Bros. (SMB, for short) ...
hengxin's user avatar
  • 9,521
1 vote
0 answers
60 views

How to go about designing a quiz that changes difficulty based on user performance?

I thought about using a machine learning algorithm to learn the performance patterns of the quiz taker and model the next quiz based on how he/she performed. So each question will have a difficulty ...
Cogitabundus's user avatar
0 votes
1 answer
27 views

What is the name of the domain or theoretical problem of transmitting game states in an online game

For example, in chess (or any online game), you broadcast the game state to other players at certain times (every n-milliseconds or after a move is made). Thereupon, a player's game client renders the ...
Keenan Diggs's user avatar
2 votes
0 answers
244 views

Moon lander algorithm

Not talking about the actual moon lander, but an old game that was inspired by it (see screenshot). Suppose I wanted to write a program that "plays" this game: Can only operate the vertical thruster ...
user3002097's user avatar
2 votes
1 answer
111 views

The task of recognizing game units in the screenshot

I'm new to computer vision and I want to solve the task of recognizing the game units of the game Clash Royale in the screenshot. Briefly, there are about 70 different types of gaming units belonging ...
Tolsi's user avatar
  • 123
0 votes
0 answers
390 views

What is the best heuristic function for evaluating the state in game of sprouts?

We are developing game of sprouts bot using min-max algorithm. We need a good heuristic function for evaluating the state of the game/player. Can someone please suggest?
Saurabh Vemuri's user avatar
0 votes
0 answers
48 views

Reducing amount of possible states solving Pacman by searching

I consider simplified Pacman game: movement is discrete (on the grid), ghosts move deterministically based on difference between their and Pacmans coordinates, ghosts move every second turn, ghosts ...
user avatar
1 vote
1 answer
738 views

Which algorithm for game matchmaking in tournament

I organize amateur tournaments every week with random players. Every week, players sign up, and I get a list with: Name Rank (1, 2 or 3) Role (s) (DPS, TANK and HEALER) I need to get balanced teams ...
LightMan's user avatar
0 votes
0 answers
862 views

Board Game algorithms

I have to find an evaluation function in which we evaluate the state of the game in each round. The game is like " roborally " , it is 2 player-Game in which there are a board and cards ...
Mohbenay's user avatar
  • 319
3 votes
1 answer
827 views

How to validate a connect X game (Tick-Tak-Toe,Gomoku,...)?

Currently I am working on a Gomoku AI (or generally Connect-X games). Implementing the search tree was no problem, but then I got to the point where I had to implement the value function and was ...
Miemels's user avatar
  • 131
4 votes
3 answers
2k views

Algorithms for procedural generated mazes

For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important). There are many Maze generation algorithms, but they only work on a ...
Christopher King's user avatar
0 votes
0 answers
179 views

Neural Network Inputs For Video Game use (DotA 2)

I am currently working on a project to build and train a neural network to play DotA 2 (at least be able to play like a really bad human). The thing is all the neural network I have built before were ...
Nifil's user avatar
  • 1
0 votes
0 answers
175 views

Reversible 2D Shape Descriptor

This is a research problem and I am just wondering if there is any already existing answer in any computer vision related paper that may have skipped my notice since this is not my active area of ...
rajaditya_m's user avatar
54 votes
6 answers
15k views

Why are some games np-complete?

I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game? ...
racc44's user avatar
  • 657
0 votes
0 answers
60 views

How motion capture system works?

Can you explain in step-by-step basis of how motion capture system work? Especially the part, that enables the 3D models to mimic the movement of the actor.
Bla...'s user avatar
  • 101
2 votes
1 answer
1k views

Why is the video game Braid Turing-complete?

It's written in wikipedia https://en.wikipedia.org/wiki/Turing_completeness#Games that the video game Braid is Turing-complete. I've played Braid before but I can hardly reconcile it with Turing ...
dontloo's user avatar
  • 121
1 vote
0 answers
56 views

Bounded pairwise distance on moving points

Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and ...
Ed Krohne's user avatar
  • 111
1 vote
0 answers
199 views

Good language for introduction to self-modifying algorithms? [closed]

So I am trying to find a language with which i can write code to build/search through deductive reasoning 'nets', as well as self-modify it's search algorithms based on information learned from these ...
Battlefrisk's user avatar
5 votes
2 answers
229 views

What data structure might this game use?

This question is not about game development or about actual implementation details. I was playing Little Alchemy yesterday. (Warning: Productivity hazard.) You start with the four classical ...
JesseTG's user avatar
  • 325
5 votes
1 answer
920 views

Consensus protocols in multiplayer video games

I'm not 100% sure this appropriate for CS. Sorry. I'm looking for prior art on an idea I had, but either my Google fu is lacking, or it genuinely hasn't happened. In distributed systems, there are a ...
nfirvine's user avatar
  • 151
1 vote
0 answers
43 views

Voronoi game in discrete space

Here i want to discuss about Linear Voronoi game. The game consists of two players, and a finite set of users placed along a line. Each player has 2m facilities, where m>0 is a fixed integer. The ...
mehrj's user avatar
  • 11
2 votes
2 answers
109 views

How to sample random game input that looks similar to human control?

What I would like to do is improve upon projects like 'RNG plays pokemon'. There, a computer produces a random sequence of inputs that are transmitted to an emulator and played in-game. Though this ...
Maxime Lucas's user avatar
4 votes
2 answers
417 views

Can systems that prevent double-spending (e.g. crypto-currencies) be used to attach other unique data?

The Bitcoin-solution can be described as "[...] a solution to the double-spending problem using a peer-to-peer network. (official Bitcoin paper, PDF, abstract, first page). Now I wonder if a similar ...
nilshi's user avatar
  • 141
1 vote
0 answers
147 views

Any applications that need fast insert or delete for quadtrees?

I know that quadtree could be used in collision detection. But most articles I found are related with quadtree construction and retrieval. I wonder if there are some circumstances which involve both a ...
chain ro's user avatar
  • 111
3 votes
2 answers
133 views

Is it possible to "unshift" onto a queue using this theoretical "queue automaton"?

I have been playing Manufactoria, a game in which one has to build a production line that tests/modifies "robots". Each robot has a "tape" where each cell is colored either red, green, blue or yellow. ...
jameshfisher's user avatar
1 vote
1 answer
111 views

Isn't software needed from programs to run? [closed]

I am a student who has entered a game programming competition called FBLA at school, and I sent them an email because I had a few questions about how the competition is ran. The main question I had, ...
CoderMusgrove's user avatar
2 votes
1 answer
100 views

Whats the name of this search game?

I am struggling in finding the name of this game (in order to find research papers related to it in the literature). Given an initial word $X$ and a target word $Y$, what is the minimum number of (...
seteropere's user avatar
3 votes
2 answers
147 views

What's the value of this game (rebalancing counters)?

Suppose you have the following game: There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized to 0. In each step, you may choose a counter $c_i$ and increase it's value by 1. ...
R B's user avatar
  • 2,634
1 vote
0 answers
100 views

How hard is it to play 1-dimensional minesweeper optimally? [closed]

(This is based on my earlier MSE question that has been stagnant for just over a week, since the best answer only addresses the case of two mines and does not even completely resolve that.) What is ...
user avatar
16 votes
2 answers
263 views

A scoring approach to computer opponents that needs balancing

This question is about an approach to computer opponents that I have created and are either currently being used, or are planned to be used, in several computer games. Background Last year, when ...
Simon Forsberg's user avatar
6 votes
1 answer
953 views

Algorithms to play randomized game

I'm interested in building an AI algorithm to play a board game. This is a sequential two-player game, where they alternate taking turns, so minimax or alpha-beta algorithms sound natural. However, ...
D.W.'s user avatar
  • 158k
3 votes
4 answers
818 views

Speeding up a program solving Icosoku

I bought a great puzzle called Icosoku. Wikipedia describes it as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and ...
Craig Feinstein's user avatar
3 votes
1 answer
423 views

Can Real-Time Strategy games be ever solved?

With the advent of BWAPI, many AI enthusiasts have been making amazing AIs that can compete against top players in Starcraft. This led me to wonder if RTS (Real-Time Strategy) games can ever be solved ...
TtT23's user avatar
  • 131
1 vote
1 answer
194 views

Extreme instancing for computer graphics

Instancing in GPU's, from my little knowledge, simply draw the same object at multiple locations. Each "instance" is just a copy of the same model at a different location. Any local effects, such as ...
Archival's user avatar
  • 171