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

11
votes
4answers
17k 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
1answer
917 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 ...
26
votes
5answers
5k views

In 2D, how do I efficiently find the nearest object to a point?

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 each distance and choose the minimum one, but that ...
13
votes
5answers
2k 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 ...
14
votes
1answer
1k 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
1k 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 ...
7
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
137 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 ...
14
votes
1answer
885 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
1k 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
873 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
157 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
1k 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
3k 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 ...
13
votes
3answers
12k 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
421 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
427 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
383 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 ...
24
votes
1answer
2k 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
3answers
6k 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
2k 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
233 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 ...
8
votes
3answers
719 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
574 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 ...
22
votes
4answers
2k 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
203 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 ...
8
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
10k 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
1k 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
5k 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
510 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 ...
5
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. ...
12
votes
2answers
5k 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
161 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
921 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 ...
3
votes
3answers
8k 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
455 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. ...
10
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
691 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 ...
3
votes
1answer
664 views

Breakout clone, how to handle/design for collision detection/physics between objects?

I'm working on a breakout clone, and I wish to create some realistic physics effects for collision - angles on the paddle should allow the ball to bounce, as well as doing curve balls etc. I could use ...
3
votes
3answers
2k views

Collision detection of convex shapes on voxel terrain

I have some standard convex shapes (cubes, capsules) on a voxel terrain. It is very easy to detect single vertex collisions. However, it becomes computationally expensive when many vertices are ...
0
votes
1answer
1k views

Ruby: implementing alpha-beta pruning for tic-tac-toe

So, alpha-beta pruning seems to be the most efficient algorithm out there aside from hard coding (for tic tac toe). However, I'm having problems converting the algorithm from the C++ example given in ...
6
votes
3answers
1k views

How can I get a velocity vector for an object moving in a circle?

I am simply trying to make an object move in a circle around a point. Let's say I have an object with a position vector going from that point to the object, and also the angle of the object with the x ...
8
votes
5answers
1k views

Why is Reinforcement Learning so rarely used in pathfinding?

The venerable shortest-path graph theoretic algorithm A* and subsequent improvements (e.g., Hierarchical Annotated A*) is clearly the technique of choice for pathfinding in game development. ...
6
votes
1answer
383 views

Building 2D Assets for a Game Targeting Multiple Framerates

To make a real-world example, lets assume I want to build an animated sprite for an explosion. The duration of the animation should last ~1 second, and we'll say exactly one second to make the math a ...
3
votes
1answer
2k views

How Can I Improve This Card-Game AI?

Let me get this out there before anything else: this is a learning exercise for me. I am not a game developer by trade or hobby (at least, not seriously) and am purely delving into some AI- and ...