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.

learn more… | top users | synonyms

24
votes
4answers
3k views

Finding the nearest object

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 the distances. I know I can't simply add x and y, ...
8
votes
7answers
2k 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. x:+1, y:+1 => NE x:0, y:+3 => N x:+10, y:-2 => E // ...
15
votes
3answers
15k 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 ...
7
votes
2answers
1k 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 ...
26
votes
2answers
3k 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 ...
10
votes
4answers
4k views

Calculating velocity 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?
6
votes
1answer
729 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 ...
53
votes
11answers
4k 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.
22
votes
2answers
11k 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 ...
17
votes
1answer
4k 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; ...
5
votes
1answer
959 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 ...
10
votes
6answers
3k 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 ...
50
votes
2answers
3k 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 ...
10
votes
3answers
2k views

Algorithm for determining random events

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 ...
7
votes
2answers
1k 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 ...
16
votes
5answers
6k 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 ...
17
votes
4answers
5k 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: ...
12
votes
2answers
4k views

How to implement an experience system?

I'm currently writing a small game that is based on earning experiences when killing enemies. As usual, each level requires more experience gain than the level before, and on higher levels killing ...
6
votes
1answer
1k 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 ...
58
votes
4answers
4k 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 ...
26
votes
9answers
16k 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.
20
votes
7answers
9k views

Algorithm for generating a 2d maze

What algorithm have you used in the past to generate a simple 2d maze?
23
votes
1answer
1k 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, ...
15
votes
5answers
3k views

Quick 2D sight area calculation algorithm?

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 ...
14
votes
9answers
5k 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
730 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 ...
9
votes
3answers
1k 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 ...
21
votes
5answers
1k 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 ...
11
votes
3answers
852 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 ...
7
votes
2answers
477 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 tiles, So sort of a tile based RPG ...
4
votes
1answer
418 views

Help understanding Simplex Noise

Introduction This is less of a "how to" on using 2D simplex noise and more of a quest to understand what is happening both in the math and visually. I would rather not copy and paste the code I've ...
1
vote
1answer
549 views

What algorithms can I use for bullet movement toward the enemy?

I'm developing 2D strategy game. There are weapons that shoot at enemies. From what I've read in this, this, this and this post I think that I need linear algebra, but I don't really understand what ...
8
votes
2answers
239 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, ...
8
votes
2answers
3k 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 ...
6
votes
3answers
3k 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?
3
votes
4answers
2k views

3-in-a-row or more logic

This is a bit more difficult than it seems and the one other post on here isn't sufficient. You have a row of n items, and each item could be any one of 5 colors. You need to find if there are any ...
38
votes
3answers
13k 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 ...
30
votes
7answers
2k 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 ...
37
votes
11answers
11k views

What path finding algorithms are there? [closed]

I'd like to read up on path finding algorithms. Is there a primer available or any material or tutorials on the Internet that would be a good start for me?
11
votes
5answers
1k 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 ...
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 ...
6
votes
5answers
14k views

Match-three puzzle games algorithm

I am trying to write a match-three puzzle game like 'call of Atlantis' myself. The most important algorithm is to find out all possible match-three possibilities. Is there any open source projects ...
24
votes
2answers
2k views

Random/Procedural vs. Previously Made Level Generation

What the advantages/disadvantages of using random/procedural generation vs. pre-made levels? There seems to be few that I can think of, other than the fact that items may be a problem to distribute ...
6
votes
4answers
2k views

Is there a way to increase the collision check efficiency of a system of n objects?

I'm making a game that consists of many onscreen objects, one of which is the player. I need to know which objects are colliding every iteration. I made something like this: for (o in objects) { ...
6
votes
3answers
1k views

top down game - checking, drawing enemy's line of sight area with obstacles

Examples of what i'm going to need: I'm using cocos2d to draw a CCTMXTiledMap, on those tiles i'll have to draw the LOS cone. How would i test if the player is within that cone, taking obstacles ...
12
votes
2answers
1k views

How to implement an intelligent enemy in a shoot-em-up?

Imagine a very simple shoot-em-up, something we all know: You're the player (green). Your movement is restricted to the X axis. Our enemy (or enemies) is at the top of the screen, his movement is ...
11
votes
4answers
14k views

Logic behind a bejeweled-like game

In a prototype I am doing, there is a minigame similar to bejeweled. Using a grid that is a 2d array (int[,]) how can I go about know when the user formed a match? I only care about horizontally and ...
10
votes
2answers
438 views

Showing range on hexagonal grid

Here is the situation. I have hexagonal board,and a unit on it,with speed or move value 4.Diffrent terrain has a diffrent cost.When i click on the unit,game should show me a move range. My solution ...
6
votes
3answers
5k views

Efficient Tile-based collision detection for a lot of squares?

currently I am working on my own take of a tile-based game (think Terraria, but less fantastical (I think that's a word? Sorry if it isn't)). Anyway, I currently have collision detection working ...
4
votes
2answers
648 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 ...