# Questions tagged [algorithm]

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.

167 questions
14k views

### How does A* pathfinding work?

I would like to understand on a fundamental level the way in which A* pathfinding works. Any code or psuedo-code implementations as well as visualizations would be helpful.
20k views

### Calculating minimum velocity of the projectile needed to hit target in parabolic arc

If I have a point which I want to hit at the end or during a parabolic arc, how would I calculate the needed x and y velocity?
6k views

### Choose tile based on adjacent tiles

I am working on a tiled map editor, and I need to choose tiles automatically, based on the adjacent tiles. For example, when placing a road tile, next to another road tile, the two need to be oriented ...
7k views

### What's the best way of transforming a 2D vector into the closest 8-way compass direction?

If you have a 2D vector expressed as x and y, what's a good way of transforming that into the closest compass direction? e.g. ...
16k views

### In 2D, how do I efficiently find the nearest object to a point?

I have a sizable game engine and I'd like a feature for finding the nearest of a list of points. I could simply use the Pythagorean theorem to find each distance and choose the minimum one, but that ...
8k views

### Predicting enemy position in order to have an object lead its target

In my 2D game I have AI turrets that should assist the player by automatically firing towards enemies. I would like to make them fire intelligently and lead their target instead of just targeting an ...
3k views

### How do I generate a smooth random horizontal 2D tunnel? [duplicate]

I'd like to create a smoother version of the navigable and quite natural-looking random tunnel found in this classic helicopter game. It should ideally be... infinite, so more can be generated as ...
2k views

### Documentation on 2D space partitioning

I am looking for documentation that explains the different kinds of (well the major ones anyway) 2D space partitioning algorithms & data structures. Any pointers besides 'Google it and sift ...
8k views

### How can I generate Worms-style terrain?

I'm working on a Worms-styled game and want to generate some terrain procedurally. I've previously done a lot of terrain generation using perlin noise, and this is what I started out using for this ...
39k views

### How can I create a random “world” in a tile engine?

I am designing a game that is working on a classic tile engine, but whose world is generated randomly. Are there existing games or algorithms that do this? The procedural generation algorithms I have ...
8k views

### How to convert mouse coordinates to isometric indexes?

I draw isometric map with tile 64x32: ...
6k views

### Which is the best approach to make a 2D character to be able to use tons of different equipments when in action?

I want to create a 2D game but I'd like to have the character to wear tons of different equipments on different combinations, like a RPG or something. So let's say the user changes his/her shoulders ...
1k views

### How do I calculate paths for objects with limited acceleration?

For example, say I have a car and a car has a specific minimum turning radius and I want to drive that car from point a to point b, but the car isn't facing point b. How do I compute a path to point ...
37k views

### Texture packing algorithm

What is a good texture packing algorithm? Technically, bin packing is NP-hard, so a heuristic is what I'm really after.
6k views

### How can I make A* finish faster when the destination is impassable?

I am making a simple tile-based 2D game, which uses the A* ("A star") pathfinding algorithm. I've got all working right, but I have a performance problem with the search. Simply put, when I click an ...
7k views

### Algorithm for determining random events [duplicate]

I'm struggling with coming up with an elegant solution to generating random events in the game that I'm working on. Say there are 4 classes of events that can happen, with varying events in those ...
22k views

### Procedural… house with rooms generator

I've been looking at some algorithms and articles about procedurally generating a dungeon. The problem is, I'm trying to generate a house with rooms, and they don't seem to fit my requirements. For ...
25k views

### Understanding Perlin Noise

I'm toying with Perlin Noise after some work with Diamond Square. I followed the implementation by Hugo Elias that basically, makes a series of functions with x,y as input to throw each coordinate ...
11k views

### When should vector/list be used?

I can understand when to use lists, but I don't understand when it is better to use vectors than using lists in video games: when it is better to have fast random access ? (And I understand why it's ...
3k views

### How do I avoid “too” lucky / unlucky streaks in random number generation?

I'm currently dealing with a multiplayer combat system where the damage dealt by the players is always multiplied by a random factor between 0.8 and 1.2. In theory, a truly random RNG may eventually ...
2k views

### Finding out which tile a mouse click landed in

I am working on an isometric grid based game and im having an issue trying to link a mouse click from the user to a tile. I have been able to split the problem into 2 parts : Finding a rectangle that ...
14k views

### Road / river generation on 2d grid map

This is a newbie question, but here it goes: My map is a 2d grid, and I want to generate roads and rivers. The route from the starting to ending point must not be the optimal route in number of tiles....
2k views

### finding a path from one point to another with obstacles help

Im building a tile based game and im implementing my path finding algorithm. Currently, it can find a path from point A to point B with no problems. However, if there are obstacles between point A and ...
32k 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 ...
13k views

### Real Time Dynamic Pathfinding?

I'm currently doing some pathfinding research and my simulation is the following: I have a 3d scene with a start and end point represented, I'm capable of creating navigational meshes, waypoints and ...
20k views

### Simple noise generation

I'm looking to generate noise that looks like this: (images courtesy of Understanding Perlin Noise) I'm basically looking for noise with lots of small "ripples". The following is undesirable: Are ...
25k views

### Algorithm for generating a 2d maze

What algorithm have you used in the past to generate a simple 2d maze?
8k views

### How can I generate a lightning bolt effect?

Is there an algorithm to generate a lightning bolt? I would like an algorithm that generates a list of segment or point objects specifying where the bolt will land. The method would need a start ...
2k views

### Determine position of a rotated element in Tetris

Tetris-Tiles are stored as a 4x4 boolean matrix. Each rotation step has it's own matrix, the representation of the T-Block would look like this: ...
6k views

### Dynamic pathing algorithm for tower defense game

I'm making a Tower Defense and I need a good pathing algorithm for it. I have thought about Dijkstra but I need one that can be dynamic; it must be able to update itself when one edge is removed or ...
4k views

### Reduce the number of edges of a graph, keeping it connected

I'm designing a game with random generated dungeons. I'd like to view this as a connected, undirected graph in which nodes are rooms and edges are doors or corridors. Then I choose a "side" node as ...
2k views

### Algorithm for “healing” multiple rectangles into a smaller number of rectangles?

Say I have a grid of rectangles of different shapes and colors and I want to reduce (reasonably close to optimal is fine, optimal is not necessary) the number of rectangles to represent the same ...
1k views

### Factors to consider when building an algorithm for gun recoil

What would be a good algorithm for calculating the recoil of a shooting guns cross-hairs? What I've got now, is something like this: Define min/max recoil based on weapon size Generate random ...
20k views

### How do I shuffle cards for a card game?

I am trying to develop an card game for Android Can anyone suggest me how to write code for effectively shuffling the playing cards?
2k views

### Algorithm to see if two voxels are interconnected

I'm looking for a good algorithms for the following problem: Given a 3D grid of voxels (which may be either empty or filled), if I pick two non-adjacent voxels, I want to know if they are connected to ...
1k views

### Making a symbol appear on any colour

I'm developing an RPG/roguelike-style game. Instead of having maps like: ......... ......... ....@.... ...h..... Oh look, a dwarf. I was having solid background ...
804 views

### Creating non-rectangular hotspots and detecting clicks

Say for a game with irregular hotspots (say Risk, or a strategy game like Paradox's Hearts of Iron or Crusader Kings), how do you Define a non-rectangular hotspot of irregular shape (much like a ...
14k views

### How to decompose sprite sheet

I have a lot of spritesheets that are poorly formatted that I want to decompose, or split out into many small images, one for each sprite. If I can do that, I can use my custom texture packer tool to ...
558 views

### Determining if removal of a voxel will break up a group

I have the following situation: I have a 3d grid of voxels (on/off, the max size is probably 128x128x128). I know in advance that inside the grid, all the voxels that are turned on are interconnected, ...
767 views

### Help me please to choose proper path-finding algorithm

I am new to game development and just want to ask for advice. I need to know which path-finding algoritm will be suitable for my scenario: Units - any shape. But in most cases rectangles of different ...
39k views

### How to generate random level from a seed? [closed]

How would I go about using a random seed to generate a game level? The same seed should always generate the exact same level. For this example it would be a Worms style level. So each level would ...
3k views

### Elegant way to simulate large amounts of entities within a game world

Assume you have a game in which there are many (many many) entities serving some functions, not all of which are constantly needed or need to be considered in every frame. The concrete problem I am ...
10k views

### How can I generate a navigation mesh for a tile grid?

I haven't actually started programming for this one yet, but I wanted to see how I would go about doing this anyway. Say I have a grid of tiles, all of the same size, some traversable and some not. ...
15k views

### Quad tree vs Grid based collision detection

I'm making a 4 player co-op r-type game, and I'm about to implement the collision detection code. I've read a lot of articles and stuff about how to handle collision detection, but I'm having a hard ...
4k views

### How could you parallelise a 2D boids simulation

How could you program a 2D boids simulation in such a way that it could use processing power from different sources (clusters, gpu). In the above example, the non-coloured particles move around ...
9k views

### How to quickly calculate the sight area in a 2D tiled game?

I have a matrix of tiles, on some of that tiles there are objects. I want to calculate which tiles are visible to player, and which are not, and I need to do it quite efficiently (so it would compute ...
4k views

### Is there an algorithm to detect the “mainland” on a 2D map?

On this map, the "mainland" is all the land that can be connected to the center of the map in the four cardinal directions (north, south, east, west -- not diagonally). I would like to detect the ...
10k views

### Calculate random points (pixel) within a circle (image)

I have an image that contains a circles at a specific location, and of a specific diameter. What I need to do is to be able to calculate random points within the circle, and then manipulate the pixels ...