# Tagged Questions

Algorithms are used for calculation, data processing, and automated reasoning. More precisely, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function.

1answer
795 views

### Pipe connection game algorithm - Java/Andengine

I am creating a game based on Pipe Dream/Pipe Mania using java/andengine for android. I have a square grid of tiles each representing a type of pipe. The player needs to swap tiles to connect the ...
3answers
281 views

### Simulating (Human) Needs? [closed]

How can I simulate the vegetation (of a human being)? To simulate Hunger for example, I use some kind of saturation based system now. Means that every food-object saturates differently and the ...
3answers
579 views

### In a semi-infinite procedural (chunk based) map, how do you handle objects larger than a single chunk?

I'll use an example to try and be more specific. Assume this is for a 2D top-down game. Chunks in this are made up of 32x32 tiles. If procedural buildings were to be generated based on some kind of ...
3answers
1k views

### Algorithm for game difficulty/pacing curve generation in single player RPG

I'm looking at this article about pacing in entertainment and games. It suggests that all good entertainment roughly follows a pacing/engagement curve like Star Wars(below). I'm interested in how I ...
1answer
231 views

### Tennis game algorithm and maths

Tennis courts are real dimensions and game is 3D Ball has position (x,y,z), speed(vx,vy,vz) and acceleration (ax,ay,az) Game has 30 fps and on each update (1/30sec) it has these properties vx +=ax; ...
1answer
1k views

### How can I optimize this flood fill algorithm?

I'm creating a sprite and animation editor like this one. I'm having performance issues with my flood-fill algorithm. Basically, I open an image with the different modules that are part of a frame of ...
1answer
16k views

### How do Raymarch shaders work?

I have been looking at shaders found here shadertoy.com and most of the cool ones have noise and raymarch in common. I do not understand the source code at all but I really want to. How do these ...
2answers
317 views

### Filling in gaps in a grid

I have a set of terrain sprites available to represent terrain: Flat North-South Straight Cliff (x 2 allowing for slope direction either way) West-East Straight Cliff (x 2 allowing for slope ...
1answer
147 views

### Where can I find info on grid based algorithms for stateless AI? [closed]

There seems to be an overwhelming amount of info out there on AI of all kinds, and it's kind hard to digest at once. For my testing purposes, I'm creating a "typical stateless AI", as described in ...
3answers
535 views

### Randomly generating the hallways between a network of rooms [duplicate]

So here's my base map: (It won't necessarily be 5x5, just using this as an example.) It's kinda boring the way it is with all the rooms connected. I want it to be more of a randomly generated ...
1answer
666 views

### How should I generate the board for a match-3-style game?

I am trying to create a "match 3" game. I'm stuck figuring out a good algorithm to fill up the game board. My game's board is 8x8. EDIT: A few things: The board should always be solvable. for ...
2answers
400 views

### How to find a free patch of area in a tiled map?

I've been trying to formulate the question and try to find some information on Google, but didn't managed to, so here it is... We've got a nice tropic-themed game that is about to be released soon, ...
0answers
37 views

### Sprite rotation algorithm [duplicate]

I'm making a game where you have to plot a function to hit certain objectives. I already made the plotting function and the animation to display a tiny missile that travels above the function. My ...
3answers
611 views

### Why can't my A* implementation find a path out of an open room?

I tried to follow this article with the following example, but in my attempts it always ends up with a dead end. If we take G being 10 in a straight line or 14 in a diagonal, and H the distance in ...
5answers
925 views

### Goalkeeper Jumping Algorithm?

This may be a "best way to" question, so may be susceptible to opinion-based answers (which is ok for me). But I would also like if there are any tutorials , research papers , etc. I'm trying to make ...
3answers
245 views

### Divide rectangular image into fixed number of random sized rectangles + 1 fixed size rectangle

I'm trying to divide a rectangular image into a fixed number of smaller rectangular image parts (of random but bounded width / height), with the exception of 1 rectangle which is predefined in ...
3answers
368 views

### Send info about gun shots via UDP

I am writing a small multiplayer game in C++. But I am confused about how to send info about gun shots to achieve best performance. I am thinking of different ways to do that: Let's say we have a gun ...
1answer
325 views

### Algorithm to produce 'Lady or Tiger' puzzles?

What my problem is: There is a puzzle by Raymond Smullyan that works something like this: You are in a room with many doors. Behind some of those doors, there are ladies; behind the others, there are ...
3answers
532 views

### How to divide hex grid evenly among n players?

I'm making a simple hex-based game, and I want the map to be divided evenly among the players. The map is created randomly, and I want the players to have about equal amount of cells, with relatively ...
1answer
560 views

### Problem with SAT collision detection overlap checking code

I'm trying to implement a script that detects whether two rotated rectangles collide for my game, using SAT (Separating Axis Theorem). I used the method explained in the following article for my ...
1answer
459 views

### About the A* algorith(pathfinding)

We have a formula of f=g+h wherein g is the path cost and h is the distance left to the goal. Given that I only want to move my unit in 4 direction (N,S,E,W), my question is: Can we consider h as ...
3answers
3k views

### A-Star Pathfinding Not Giving Shortest Path

I'm attempting to implement the A* pathfinding algorithm in Java. I thought it was working well, but then I found instances where it doesn't follow the shortest path Green = start, red = target, ...
0answers
352 views

### Pathfinding with portals? [closed]

I'm not making a game with portals in it (one way or bidirectional). These portals instantly teleport characters from one location to another. How would I implement pathfinding? Here's an animation ...
3answers
398 views

### Algorithm for creating tree-like network structures

I'm trying to procedurally model tree-like network structures with the following properties: A root with variable number of nodes A variable depth of nodes When graphically laid out, edges or nodes ...
1answer
531 views

### Placing nodes in a graph in a random but readable way

I'd like to create a simple map from vertices and lines - you know, like a usual graph. A tree, to be precise. To select the location of the next point that comes from one, I use a simple circle-...
1answer
829 views

### Implementing David Silver's Cooperative Pathfinding in Real-Time

I'm currently implementing David Silver's Cooperative Pathfinding algorithm for a 2D game with grid-based movement (all eight directions). The issue I'm having trouble wrapping my mind around is the ...
3answers
1k views

### Need ideas for an algorithm to draw irregular blotchy shapes

I'm looking to draw irregular shapes on an x,y grid, and I'd like to come up with a simple, fast method if possible. My only idea so far is to draw a bunch of circles of random sizes very near each ...
1answer
2k views

### Path finding in hex grid based game

I'm making a TBS with hex grid. Player can move units from one hex to another using bridges, which will be randomly generated. I'm using cubic and axial coordinate system for my grid, it's well ...
1answer
1k views

### How to simulate cylinder shape in collision detection?

AFAIK, many physics engines like Physx and Havok don't incorporate cylinder as basic shape because it is expensive than sphere, box and capsule. But bullet engine does incorporate cylinder as a basic ...
1answer
245 views

### What to change when neural network is not classifying correctly?

I'm designing a learning algorithm for a simulation. In this simulation, there are minesweepers/tanks and also mines. Tanks are supposed to avoid collisions with mines, I'm using a neural network for ...
2answers
427 views

### Canting of track in a racing game

I am trying to create a small racing game in which the track would be modeled using a BSpline curve for the path's center line and directional vectors to define the canting of the track at each point. ...
2answers
2k views

### Building triangle adjacency data

Given a list of triangle indices, how exactly does one go about converting that to a list of indices with adjacency for a geometry shader? Note that we're strictly talking about indices here - ...
2answers
445 views

### How to choose inputs to an artifial neural network?

I have to implement, as part of an assignment, a learning method that enables minesweepers to avoid colliding with mines. I have been given the choice to choose between a supervised/unsupervised/...
2answers
137 views

### Decomposing a collision grid into a set of boxes

I'm looking for a decent algorithm to decompose a collision grid (e.g. bool[w,h])... ...into a non-overlapping set of boxes (e.g. List<Rectangle>). The solution does not have to be the ...
1answer
351 views

### What makes a path finding heuristic Monotonic vs. Non-monotonic?

I am currently working on an algorithm that solves a path through the maze. So far I have implemented a Manhattan and Pythagorean Heuristic. I was wondering what makes a heuristic monotonic and how ...
2answers
143 views

### How should I provide a navigation system for a world with infinite space?

The world is generated by perlin noise chunks and will only be saved once that chunk has been generated. It will also not necessarily have one obvious (to the user) central point anywhere in the world,...
1answer
828 views

### Painting terrain with a selection circle

I don't mean putting a circle under a unit like done in an RTS, that's fairly simply done with a scenegraph(-like structure). What I'm referring to is selection circles for things like Area of Effects ...
1answer
82 views

### Translate velocity to mouse curos position

I have particles, with a velocity (x and y) per tick. I would like to to make my cursor a gravity force, so particles fly to the cursor's position. How can I apply gravity (that is towards my cursor ...
1answer
814 views

### Multiplayer matchmaking algorithm

I'm building a game in which there are tournaments. During the tournaments we want players to play against each other in an efficient way. What I'm looking for is a generic algorithm that will match ...
0answers
55 views

### Tetris-like wall-kicking not working [duplicate]

So I'm making a falling-block puzzle game. It's not a Tetris clone, but the block clusters move in a similar fashion. I want to make it so that if you rotate against a wall, or against another piece,...
1answer
896 views

### How do you construct a node map for pathfinding in a non-tiled 2D environment? [duplicate]

A* and Dijkstra's pathfinding algorithms work by navigating a node map. In a tile-based 2D environment, these nodes could easily be inferred to be the literal x,y positions of the map. For example, ...
1answer
92 views

### Symmetry preserving path simplification

I'm using the Douglas peucker (DP) algorithm to simplify some (2d) closed paths forming a shape. This works pretty good, but not so much for closed paths that have some symmetry. Take for example a ...
1answer
84 views

### Locating point on a closed path to maximize sum of distances to a sample of weighted points

I'm doing AI for a simple puzzled game and need to solve the following problem efficiently (less than 1 sec for the range specified since I need to do many iterations in a game). A sample of N (1 ...
1answer
194 views

### What's wrong with reversing an action like this?

I'm working on an undo and redo system map editor and have come across a major issue. If I place a tile down, move right a tile, and then move back to that tile I previously placed everything works ...
1answer
210 views

### Square collision: Detect which side of the wall it collided [duplicate]

I'm using a standard square collision in my 2D game. The player shoots little balls, and when they hit any wall it should bounce. The problem is that I know when it hits a wall but I don't know if ...
1answer
363 views

### Triangulating a partially triangulated mesh (2D)

Referring to the above exhibits, this is the scenario I am working with: starting with a planar graph (in my case, a 2D mesh) with a given triangulation, based on a certain criterion, the graph ...
3answers
360 views

### How do I make something I flash/blink more frequently as it gets closer to disappearing?

In my game when you kill an enemy they may drop something like a health pack or gold. I want this to have a time limit so that it eventually disappears if you don't pick it up. I want the item to ...
1answer
156 views

### Tangent basis calculation problem

I have the problem with seams with calculating a tangent basis in my application. I'm using a seems to be right algorithm, but it gives wrong result on the seams. What am I doing wrong? Is there a ...
1answer
214 views

### Enumerating full game tree for small board game

I am trying to list all the possible positions in a small board game (nannon) (using C++) So far I have decided to split it into two parts, the pieces that are in home positions and end positions (...
1answer
152 views

### AI discover algorithm

I am curious as to what algorithm/logic game AI/NPCs would use when discovering information about their environment. There are two scenarios that I could envision. The NPCs are all knowing in ...