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.
201 questions
69
votes
7
answers
22k
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,785
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
21
votes
8
answers
14k
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.
...
- 890
10
votes
2
answers
8k
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 ...
- 651
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 the ...
- 173
38
votes
5
answers
28k
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
11k
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
18
votes
1
answer
5k
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
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
62
votes
9
answers
58k
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,642
49
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,152
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
46k
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,422
21
votes
1
answer
11k
views
How to convert mouse coordinates to isometric indexes?
I draw isometric map with tile 64x32:
...
- 313