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

9
votes
6answers
688 views

Solving maze without return ability

I need to write a program that will solve maze. Maze has graph structure, where each node - some room, and edges - exits to other rooms: Specification: We start from a random room. Maze has ...
23
votes
2answers
777 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 ...
8
votes
2answers
415 views

Manage a large number of independent actors in real-time

I am working on a large scale real-time strategy game - ideally with thousands of units active at once - but I am having trouble managing all of the units at once without it becoming astonishingly ...
3
votes
2answers
511 views

How does Half Life's covering work?

Enemies in this game take cover. AFAIK HL uses some logical decisions for enemy to start searching for cover and to abandon cover, and I am able so far to find them; but how does he find a cover ...
49
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 ...
2
votes
2answers
472 views

Best way to traverse triangles in a mesh

I'm implementing non-projective decals. As described in many places (ie: lengyel in the gpg2) I first need to detect all triangles that lie within some sort of frustum. Besides obvious brute-force ...
1
vote
2answers
2k views

AI for solving a Match 3 game

Is there a known good way to have a "computer" opponent play a Match 3 game? It doesn't have to be fancy, or even considered fair. If the AI always takes the best move on the board that would be OK ...
11
votes
4answers
11k 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 ...
8
votes
1answer
631 views

Are there well-known algorithms for fitting a polygon to an arbitrary shape?

I'm using the Chipmunk physics engine to make the levels for a 2D C game. I'd like to be able to fit a polygon to an arbitrary shape to serve as the collision mask. Given a black and white collision ...
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, ...
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 ...
11
votes
1answer
986 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 ...
8
votes
2answers
936 views

Render rivers in a grid

I have created a random height map and now i want to create rivers. I've made an algorithm based on a* to make rivers flow from peaks to sea and now i'm in the quest of figuring out an elegant ...
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 ...
1
vote
3answers
135 views

Regulating how much to draw based on how much was drawn last frame

[Edit: I found an answer - see below] I have a 3D game world on an iPhone (limited graphics speed), and I'm already regulating whether I draw each shape on the screen based on it's size and distance ...
13
votes
1answer
772 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 ...
8
votes
3answers
1k views

How to find 2D grid cells swept by a moving circle?

I'm making a game based on a 2D grid, with some cells passable and some not. Dynamic objects can move continuously, independent of the grid, but need to collide with impassable cells. I wrote an ...
2
votes
2answers
874 views

Path finding in grid for objects that occupy more than one tile

In a grid-based game I am working on, I want to add objects that occupy more than one tile of the grid. Are there any algorithms or techniques to find paths for this kind of objects?
10
votes
3answers
768 views

Drawing particles as a smooth blob

I'm new to game/graphics development and I'm playing around with particles (in 2D). I want to draw particles close to each other as a blob, just as liquid/water. I do not want to draw big circles ...
3
votes
1answer
150 views

Coordinate based travel through multi-line path over elapsed time

I have implemented A* Path finding to decide the course of a sprite through multiple waypoints. I have done this for point A to point B locations but am having trouble with multiple waypoints, because ...
3
votes
2answers
681 views

Infinite loop during A* algorithm

The A* algorithm is used by enemies to have a path to the goal. It's working but when sometimes I placed a tower in a grid (randomly) it produces a stack overflow error. The A* algorithm would iterate ...
4
votes
3answers
2k views

Which algorithm used in Advance Wars type turn based games

Has anyone tried to develop, or know of an algorithm such as used in a typical turn based game like Advance Wars, where the number of objects and the number of moves per object may be too large to ...
9
votes
3answers
7k views

Sorting array of points in clockwise order

Is there such an algorithm to sort an array of 2D points in clockwise order? I'm specifically dealing with right triangle in my case so only 3 points. However I'm interested in knowing if such an ...
-3
votes
2answers
397 views

Fifteen puzzle modifications algorithm

What would be a good algorithm for the Fifteen puzzle, if the puzzle is slightly modified in that you only have a small number of pieces that should be placed correctly and these correctly placed ...
4
votes
3answers
403 views

Finding closest coordinate of a pre-known set

Let's say I have a large number of conceptual objects of some kind, each of which occupies a pre-known set of points in a Cartesian 3-space. 1) What is the best combination of data structure (for ...
5
votes
3answers
333 views

Generating random values, keep trying till value within bounds are generated

Sorry for the strange topic name, couldn´t think of a good way to describe it. I´m basically trying to achieve the following: I'm placing items randomly on the screen, but these items shouldn't be ...
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, ...
12
votes
3answers
4k views

Real Time Dynamic Pathfinding?

I'm currently doing some pathfinding research and my simulation is the following: I have a 3d scene with a start and end point represented, I'm capable of creating navigational meshes, waypoints and ...
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 ...
5
votes
1answer
224 views

Splitting an object into two

I'm using Farseer physics engine. I have a simple rectangle body and would like it to split into two pieces given a starting coordinate (where the bullet enters the object) and ending coordinate ...
7
votes
3answers
562 views

The best algorithm enhancing alpha-beta?

I'm studying AI. My teacher gave us source code of a chess-like game and asked us to enhance it. My exercise is to improve the alpha/beta algorithm implementing in that game. The programmer already ...
2
votes
5answers
515 views

How to model irregular boundary of a 2D map in Game?

I am creating a map in a game, the map contains different countries, my question: Q. How to model the irregular boundary of each countries? How to do quick country searching if I click on the map ...
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 ...
5
votes
3answers
200 views

Preventing ties

I'm working on a simple game to rate a users' preference among several styles. There are C classes, and the game consists of R rounds of comparison. At each round, the user is presented a ...
7
votes
3answers
1k views

Pathfinding with multiple random paths in a Tower Defense game

I thought about random pathfinding for my Tower Defense game. A* would not work for my puposes, because I specifically need random pathfinding. Imagine a map with routes, a starting point and a ...
2
votes
1answer
1k views

Which is faster: raycasting or shadowcasting?

I'm looking to create an FoV implementation and I was wondering which algorithm is faster - raycasting or shadowcasting?
18
votes
6answers
7k 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 ...
3
votes
3answers
805 views

Algorithm for making sets in a Rummikub game

I'm developing an Okey game (a Turkish version of Rummikub/Rummy). In it, each players has a bunch of tiles. Tiles have a colour and a number, like playing cards. Now, the player needs to make sets of ...
2
votes
1answer
2k views

C# Pathing algorithm for moving a object from point(X, Y) to point(X, Y)

Given a object which may move forward, backward, left and right at a given X,Y point. How to efficiently direct the object to a X,Y point using the given movement mechanics in the most efficient and ...
3
votes
1answer
1k views

(real) 3d map rendering in wpf without an engine - how to handle the map data?

I'm just doing some research before embarking on rendering a 3D map inside a wpf app. I've never delved into 3D before, and hence the question.. I have map data (in several formats, and many files) ...
13
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 ...
6
votes
2answers
485 views

Calculating and detecting curves

How can I detect the 'steepness' of a curve? For example, if the user swipes their finger across the screen in a curve, what's the best way of detecting whether the curve is almost a semi-circle, or ...
4
votes
1answer
1k views

Significance of Bresenhams Line of Sight algorithm

What is the significance of Bresenhams Line of Sight algorithm in chasing and evading in games? As far as i know and implemented this algorithm calulates the straight line between two given points. ...
11
votes
2answers
3k 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 ...
2
votes
2answers
154 views

Resources on expected behaviour when manipulating 3D objects with the mouse

In my animation editor, I have a 3D gizmo that sits on the origin of a bone; the user drags the mesh around to rotate the bone. I've found that translating the 2D movements of the mouse into sensible ...
14
votes
3answers
690 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 ...
2
votes
3answers
5k views

best way to compute vertex normals from a Triangle's list

hi i'm a complete newbie in computergraphics so sorry if it's a stupid answer. i'm trying to make a simple 3d engine from scratch, more for educational purpose than for real use. for now i compute ...
1
vote
3answers
380 views

Given a start and end point, how can I constrain the end point so the resulting line segment is horizontal, vertical, or 45 degrees?

I have a grid of letters. The player clicks on a letter and drags out a selection. Using Bresenham's Algorithm I can create a line of highlighted letters representing the player's selection. ...
9
votes
1answer
1k views

Triangulation A* (TA*) pathfinding algorithm

I need help understanding the Triangle A* (TA*) algorithm that is described by Demyen in his paper Efficient Triangulation-Based Pathfinding, on pages 76-81. He describes how to adapt the regular A* ...
1
vote
2answers
592 views

XNA: How to make the Vaus Spacecraft move left and right on directional keys pressed?

I'm currently learning XNA per suggestion from this question's accepted answer: Where to start writing games, any tutorials or the like? I have then installed everything to get ready to work with XNA ...