# 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.

947 questions
2k views

### Algorithm to make groups of units

In Age of Mythology and some other strategy games, when you select multiple units and order them to move to some place, they make a "group" when they reach the desired location: I have a Vector with ...
272 views

### Algo for narrowing cavern

I'm in a bit of crunch time and I find myself spending way too much time tinkering with an algo, so I would like some help. In the game I am working on, there are some old-style, pixelated minigames. ...
3k views

### Creating A Board Game AI

I want to code a board game that name is Okey and mostly popular in Turkey. http://en.wikipedia.org/wiki/Okey But i have got some problems about AI. Firslty let me explain the game.. The game is ...
794 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

### 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 ...
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 ...
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 ...
3k 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 ...
818 views

### Are there important cases when one needs to know how to program sort algorithms in game programming? [closed]

Well I already read a little about sorting algorithms on wikipedia, the subject seems vast, especially when dealing with some cases where some algos are faster than others. That might need some quick ...
1k 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 ...
286 views

### Draw land for motocross game

I would like to draw a land for a motocross game. I've been thinking of Bezier Curves but I am not sure whether this is the best approach. Can you give me some advice? I want to do it in JavaScript, ...
311 views

### Correct Blitting 2 surface problem

this is a graphics/math problem. Consider this 2 sprite / surface As you can see they are a tank and his gun turret. Now, i manage the turret rotation, and it works, and, also, the rotation of the ...
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 ...
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 ...
576 views

### How to avoid self-intersection when applying stroke to a curve?

I have several Spline2D objects in my code, each of which has a Position, Velocity, and Acceleration method that returns a vector of the specified quantity at a particular time. I've been using these ...
562 views

### Is there an efficient, available online, algorithm for converting a matrix of squares into a triangle strip?

Imagine having a 4x4 square, with 16 smaller squares inside of it, with associated data on what the squares should look like (ie., opacity, colour, etc...). Is there an existing, efficient, algorithm,...
5k views

### Car (or other “object”) acceleration and braking: how to?

I'm not good in math so I'm here to ask you how to manage, in a simple 2d game, the car acceleration and braking. I'm trying to develop it (as a hobby) in c# and sdl.net.
2k views

### Realistic slow-falling snow algorithm?

Is there a good algorithm that simulates falling snow? I'm particularly interested in snow that falls slowly, so it doesn't quite fall in a straight line but deviates a bit. Maybe even including ...
1k views

### Algo for given an amount of XP, find a character's level

In a RPG context, what are the ways to quickly find a character's level, given his XP? There are two cases which I am looking at: For when a formula is defined, like in the case of D&D, which is ...
7k 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 ...
2k 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 ...
686 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 fluids....
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 ...
418 views

### Mahjong solitaire - navigating between open tiles

I am looking for an algorithm to help me navigate between 'open' tiles in a Mahjong solitaire game. The game is to be played on a limited device with only left-right-up-down buttons and I want to ...
1k views

### How does one separate the acceleration due to gravity from other motion in accelerometer input?

How does one separate the acceleration due to gravity from other motion in accelerometer input?
36k 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.
232 views

### Are there any clever methods of regulating bandwidth usage for voice chat payload packets?

For example, suppose my code can determine that upstream bandwidth is unusually limited. And suppose I'm using a fully-connected mesh topology combined with a UDP-like protocol for voice chat. Is ...
27k 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 ...
5k views

### How would one determine the position of a participant in a racing game?

Now, for the record, I'm currently not implementing any racing game whatsoever, but this problem just popped into my mind and now I'm curious. So how would one go about finding out which participant ...
10k 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 ...
38k 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 ...
1k views

### SoA Vectors on SPU

I've read a lot about the benefits of organizing data into 'Structs of Arrays' (SoA) instead of the typical 'Array of Structs' (AoS) to get better throughput when using SIMD instructions. While the '...
3k views

### Algorithm for drawing asteroids from, er… Asteroids game?

What would the algorithm be for generating/drawing the asteroid shapes from the original Asteroids game? Is it even an algorithm? Or would they be hard coded shapes? Here is a screenshot to jog your ...
994 views

### Slow performance on an A* implementation in a tower defense game

I'm making a Tower Defense game in Flash with no predefined path. Although my grid is 40x40 (small?), A* is struggling when recalculating every time. So I made my own modification to ease the ...
1k views

### Dynamic Dijkstra

I need dynamic dijkstra algorithm that can update itself when edge's cost is changed without a full recalculation. Full recalculation is not an option. I've tryed to "brew" my own implemantion with no ...
403 views

### How to allow character to keep moving after it hits a wall

I am developing an iPhone game. There is a fountain that the user should not be able to walk through. Now, this question is about checking circle-point collision or anything like that. I am checking ...
571 views

### Locate the shortest path through obstacles when all normal paths are blocked

I'm making a Tower Defense and I have basic pathfinding working, but I got a problem. I want to make the path blockable, and when a block occurs the runners will attack the blocking towers. So what ...
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 ...
28k 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.
633 views

### How to use transposition tables with MTD(f)

I'm writing an AI for a card game and after some testing I've discovered that using MTD(f) on my alpha beta algorithm - a series of zero-window searches - is faster than just using alpha-beta by ...
3k 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: ...
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 ...
25k views

### Algorithm for generating a 2d maze

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

### In what instances would you want to use path-finding algorithms other than A*?

I am familiar with how the common ones technically work (BFS, DFS, Dijkstra, A*) but as far as their realistic benefits I don't quite see the need for them. Considering that, given the right ...
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.