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.
190
questions
68
votes
7
answers
20k
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.
- 1,775
11
votes
3
answers
3k
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 ...
- 484
21
votes
4
answers
23k
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?
- 453
19
votes
8
answers
12k
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.
...
- 860
10
votes
2
answers
7k
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 ...
- 641
7
votes
1
answer
5k
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 ...
- 173
60
votes
9
answers
53k
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.
- 7,602
38
votes
5
answers
26k
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 ...
- 1,912
14
votes
2
answers
10k
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 ...
- 315
9
votes
1
answer
3k
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 ...
- 93
50
votes
3
answers
11k
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 ...
- 1,162
30
votes
5
answers
4k
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 ...
- 1,030
24
votes
3
answers
45k
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 ...
- 1,402
21
votes
1
answer
10k
views
How to convert mouse coordinates to isometric indexes?
I draw isometric map with tile 64x32:
...
- 313
14
votes
5
answers
9k
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 ...
- 143
79
votes
5
answers
35k
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 ...
- 2,787
56
votes
1
answer
40k
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 ...
- 2,099
34
votes
12
answers
9k
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 ...
- 559
22
votes
2
answers
16k
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. ...
- 487
18
votes
1
answer
4k
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 ...
- 484
13
votes
3
answers
10k
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 ...
- 1,378
7
votes
3
answers
6k
views
Path finding in grid for objects that occupy more than one tile
In a grid-based game I am working on, I want to add objects that occupy more than one tile of the grid. Are there any algorithms or techniques to find paths for this kind of objects?
- 595
37
votes
5
answers
35k
views
How to generate caves that resemble those of Minecraft?
I've been working on a 3D procedural world for a while now and am wanting to start adding cave systems. I'm currently using 2D/3D Perlin Noise for the terrain generation in combination with Marching ...
- 1,496
32
votes
2
answers
29k
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 ...
- 1,143
17
votes
5
answers
13k
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 ...
- 5,243
13
votes
3
answers
19k
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....
- 233
10
votes
3
answers
6k
views
Determine if a set of tiles on a grid forms an enclosed shape
Given a set of tiles on a grid, I want to determine:
If the tiles make an enclosed figure
If the tiles make an enclosed figure when you count the sides of the board as an edge of the figure
If either ...
- 201
9
votes
1
answer
3k
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 ...
- 201
5
votes
1
answer
1k
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 ...
- 161
1
vote
1
answer
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 ...
- 33
32
votes
2
answers
13k
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 point ...
- 485
29
votes
4
answers
25k
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 ...
- 1,162
28
votes
7
answers
30k
views
Algorithm for generating a 2d maze [closed]
What algorithm have you used in the past to generate a simple 2d maze?
- 1,021
24
votes
1
answer
3k
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:
...
- 22.6k
19
votes
3
answers
17k
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 ...
- 191
16
votes
9
answers
8k
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 ...
- 549
13
votes
6
answers
21k
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?
- 131
11
votes
3
answers
5k
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 ...
- 736
11
votes
3
answers
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 ...
- 195
9
votes
3
answers
18k
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 ...
- 205
8
votes
3
answers
2k
views
How can I check if a player-drawn line follows a path?
I want to draw an invisible path that the user must follow. I've stored that path as points. When a player draws a line, how can I test if it follows the path I've stored?
Here's an example for ...
- 85
8
votes
2
answers
842
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, ...
- 195
8
votes
2
answers
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 ...
- 10.3k
7
votes
4
answers
10k
views
Smoothing found path on grid
I implemented several approaches such as A* and Potential fields for my tower defense game. But I want smooth paths, first I tried to find path on very small grid ( 5x5 pixels per tile) but it is ...
- 242
7
votes
4
answers
886
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 ...
- 2,742
4
votes
2
answers
2k
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 ...
- 5,054
49
votes
3
answers
45k
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 ...
- 2,444
33
votes
7
answers
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 ...
- 997
29
votes
2
answers
23k
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 ...
- 1,627
28
votes
4
answers
5k
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 ...
- 1,143