Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

6
votes
1answer
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 ...
4
votes
2answers
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. ...
9
votes
1answer
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 ...
7
votes
4answers
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 ...
24
votes
2answers
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 ...
13
votes
3answers
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 ...
7
votes
2answers
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
votes
3answers
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 ...
7
votes
6answers
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 ...
23
votes
6answers
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 ...
7
votes
2answers
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, ...
3
votes
1answer
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 ...
11
votes
3answers
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 ...
17
votes
5answers
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 ...
11
votes
2answers
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 ...
5
votes
2answers
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,...
6
votes
3answers
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.
10
votes
1answer
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 ...
5
votes
5answers
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 ...
27
votes
1answer
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 ...
17
votes
14answers
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 ...
15
votes
3answers
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....
33
votes
7answers
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 ...
1
vote
4answers
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 ...
8
votes
3answers
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?
50
votes
9answers
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.
4
votes
1answer
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 ...
7
votes
5answers
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 ...
8
votes
3answers
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 ...
15
votes
5answers
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 ...
46
votes
3answers
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 ...
8
votes
4answers
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 '...
5
votes
6answers
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 ...
9
votes
5answers
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 ...
5
votes
4answers
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 ...
1
vote
2answers
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 ...
10
votes
1answer
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 ...
14
votes
5answers
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 ...
27
votes
3answers
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.
3
votes
2answers
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 ...
24
votes
11answers
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: ...
16
votes
9answers
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 ...
27
votes
6answers
25k views

Algorithm for generating a 2d maze

What algorithm have you used in the past to generate a simple 2d maze?
3
votes
6answers
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 ...
67
votes
7answers
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.
12
votes
4answers
740 views

Gesture Recognition Strategies

Working with the Wii I often find it necessary to recognize simple gestures, so far I've been able to mainly look at magnitude of acceleration in order to recognize the gestures called out for in our ...
48
votes
11answers
42k 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?