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.
45
votes
11answers
3k 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.
42
votes
2answers
2k views
How can I get textures on edge of walls like in Super Metroid and Aquaria?
Games like Super Metroid and Aquaria present the terrain with the other facing parts having rocks and stuff while deeper behind them (i.e. underground) there's different detail or just black.
I ...
35
votes
2answers
1k 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 ...
30
votes
7answers
7k views
How to generate random level from a seed?
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 ...
29
votes
7answers
1k 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 ...
27
votes
4answers
2k 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 ...
25
votes
11answers
2k views
What are your favourite game-specific coding gems? [closed]
I'll start off with John Carmack's the Fast Inverse Square Root in Quake III:
float Q_rsqrt(float number) {
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = ...
23
votes
2answers
575 views
Algorithm for spreading labels in a visually appealing and intuitive way
Short version
Is there a design pattern for distributing vehicle labels in a non-overlapping fashion, placing them as close as possible to the vehicle they refer to? If not, is any of the method I ...
23
votes
1answer
2k views
Methods for generating a map
I'm looking to create a simple, "randomly" generated map for a small game.
The game consists of a top-down view of a world, with land-mass and ocean areas. Think of a simple outline map of the world ...
21
votes
9answers
11k 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.
21
votes
2answers
5k 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 ...
21
votes
6answers
842 views
Spell casting - How to optimize damage per second
Imagine we have a wizard that knows a few spells. Each spell has 3 attributes: Damage, cool down time, and a cast time. Pretty standard RPG stuff.
Cooldown time: the amount of time (t) it takes ...
21
votes
1answer
828 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:
[
0, 0, 0, 0,
0, 1, 1, 1,
0, 0, 1, 0,
...
21
votes
3answers
7k views
How does Navigation Mesh path-finding work?
I want to understand how navmeshes work, how to implement them and why it is better than other types of pathing systems.
18
votes
7answers
2k views
Optimizing gravity calculations
I've got a bunch of objects of varying size and velocity which gravitate towards each other. On every update, I have to go over every object and add up the forces due to gravity of every other object. ...
18
votes
4answers
2k views
Find Nearest Object
I have a fairly sizable game engine created, and I'm adding some needed features, such as this, how do I find the nearest object from a list of points?
In this case, I could simply use the ...
18
votes
6answers
377 views
Finding direction of travel in a world with wrapped edges
I need to find the shortest distance direction from one point in my 2D world to another point where the edges are wrapped (like asteroids etc). I know how to find the shortest distance but am ...
17
votes
6answers
5k views
What is the simplest method to generate smooth terrain for a 2d game?
What is the simplest method to generate smooth terrain for a 2d game like "Moon Buggy" or "Route 960"?
I got an answer at stackoverflow.com about generate an array of random heights and blur them ...
17
votes
5answers
863 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 ...
16
votes
14answers
1k views
Does Big O really matter?
In academia worst case Big O is taught over everything else. Compared to space complexity, normal case analysis, simplicity over complexity, etc.
In particular to game programming and industry, what ...
16
votes
5answers
3k 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 ...
16
votes
3answers
2k views
How can I generate floating land masses for a Minecraft-like engine?
I am creating a Minecraft-like engine in XNA. What I want to do is create floating islands similar to the one shown in this video:
http://www.youtube.com/watch?v=gqHVOEPQK5g&feature=related
...
16
votes
2answers
2k 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 ...
16
votes
7answers
5k views
Algorithm for generating a 2d maze
What algorithm have you used in the past to generate a simple 2d maze?
15
votes
2answers
754 views
How do I produce “enjoyably” random, as opposed to pseudo-random?
I'm making a game which presents a number of different kinds of puzzles in sequence. I choose each puzzle with a pseudorandom number. For each puzzle, there are a number of variations. I choose the ...
15
votes
2answers
367 views
Why is my sky color calculation in Mathematica incorrect?
I'm trying to implement an algorithm to calculate sky color based on this paper (Perez' model). Before I start programming the shader I wanted to test the concept in Mathematica. There are already ...
14
votes
3answers
755 views
How do history generation algorithms work?
I heard of the game Dwarf Fortress, but only now one of the people I follow on Youtube made a commentary on it... I was more than surprised when I noticed how Dwarf Fortress actually generates a ...
14
votes
4answers
453 views
Algorithm for creating adjacent triangles
I have a system where you can click once to place a node in a scene. When you place 3 nodes, it forms a triangle. When you place any future nodes, it creates a new triangle by joining that node to the ...
14
votes
4answers
3k 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:
...
14
votes
1answer
1k views
How to convert mouse coordinates to isometric indexes?
I draw isometric map with tile 64x32:
const Offset = 160;
int X, Y;
for (int a=0; a < 6; a++)
for (int b=0; b < 6; b++) {
X = a * 32 - b * 32 + Offset;
Y = a * 16 + b * 16;
...
14
votes
3answers
527 views
Solids as high viscocity Liquids
A friend of mine and I were discussing different idea for allow materials in a world to be destroyed in a very piecemeal fashion and he proposed the idea of representing solids as very viscious ...
13
votes
9answers
4k 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 ...
13
votes
2answers
685 views
Partially observable game map — is A* appropriate?
I know very little about game development and I'm trying to wrap my head around pathfinding algorithms.
Consider this setup: an agent is on a 2D map and must find the shortest path to a globally know ...
13
votes
1answer
5k 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 ...
13
votes
5answers
2k views
boolean operations on meshes
given a set of vertices and triangles for each mesh. Does anyone know of an algorithm, or a place to start looking( I tried google first but haven't found a good place to get started) to perform ...
13
votes
2answers
569 views
AI to move custom-shaped spaceships (shape affecting movement behaviour)
I'm designing a networked turn based 3D-6DOF space fleet combat strategy game which relies heavily on ship customization. Let me explain the game a bit, since you need to know a bit about it to set ...
13
votes
1answer
685 views
What are pros and cons of Voronoi shatter?
I have seen some Voronoi shatter videos on Youtube.
What is your experience with it?
What are the pros and cons in time complexity, resource complexity, implementation difficulty...?
Does it ...
12
votes
2answers
316 views
Scrambling word into least recognizable form
My goal is to present the player with a scrambled word that should be reordered back into the original form:
OELHL --> HELLO
I want a scrambling algorithm that takes any given word(>3or4 letters, ...
12
votes
2answers
406 views
Fades in older games. Need some help figuring out how the algorithm was derived
Sorry, this question is a bit esoteric, but I just can't get it out of my head!
I'm looking at the fade algorithm used in the arcade game DoDonPachi (as well as many other older games):
I wrote a ...
12
votes
1answer
338 views
Get ring of tiles in hexagon grid
Thanks to this post I'm able to collect adjacent tiles to a given tile.
But I'm pretty much stuck on an algorithm that gives me only a "ring" of tiles specified by an offset. The algorithm given in ...
12
votes
1answer
260 views
Detecting a sequence of nodes in a grid
Given the image below, I need to detect the most optimal sequence on the board (the green line). The blue/red lines represent possible, but not the best moves.
Here are the rules:
You can move to ...
11
votes
3answers
7k 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 ...
11
votes
4answers
1k 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 ...
11
votes
3answers
3k views
Beat detection and FFT
I am working on a platformer game which includes music with beat detection. I am currently detecting beats by checking for when the current amplitude exceeds a historical sample. This doesn't work ...
11
votes
4answers
409 views
Fastest way to group units that can see each other?
In the 2D game I'm working with, the game engine is able to give me, for each unit, the list of other units that are in its view range.
I would like to know if there is an established algorithm to ...
11
votes
1answer
851 views
How to gain accurate results with Painter's algorithm?
A while ago I asked how to determine when a face is overlapping another. The advice was to use a Z-buffer.
However, I cannot use a Z-buffer in my current project and hence I would like to use the ...
11
votes
4answers
530 views
How do I get AI Agents to move along a curve?
Currently my very basic AI framework has agents that move along a a jagged path made up of a series of points.
They do this by simply moving their position from one point to the next. When they ...
11
votes
4answers
977 views
How do I determine the draw order in an isometric view flash game?
This is for a flash game, with isometric view. I need to know how to sort object so that there is no need for z-buffer checking when drawing. This might seem easy but there is another restriction, a ...
10
votes
5answers
521 views
How would one determine the length of a path?
I have a game that requires each player to move along one specified path. I draw the path using Bézier curves. How can I determine the total real (not linear) length of the path and the distance that ...
10
votes
3answers
374 views
Having a list of rooms with theirs connection to each other, how do I find isolated room groups?
I'm trying to create a small roguelike and went as far as random generating rooms and corridors. Each room is an instanced object and contain an arraylist of the others rooms connected by a corridor.
...
