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

14
votes
3answers
13k 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 ...
22
votes
2answers
10k 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 ...
3
votes
3answers
840 views

tic tac toe computer opponent

I am just starting to do some very very very basic game dev(in java), i'm trying to create a game of tic tac toe but i am having some trouble implementing an a computer opponent.I just wanted to know ...
-1
votes
2answers
645 views

Why is my Diamond-Square implementation producing blocky, banded results?

Do you know why my diamond square algorithm is giving me this such "ragged" results? I used to render it in a way that concealed the roughness (basically asigning color ranges instead of fractional ...
10
votes
5answers
618 views

How would one determine the length of a path?

I have a game that requires each player to move along one specified path. I draw the path using Bézier curves. How can I determine the total real (not linear) length of the path and the distance that ...
4
votes
3answers
609 views

Implementing recoil in a realistic and balanced way?

To clarify, I've seen this post already I really like the idea that the chosen answer suggests, yet when I go to implement it the recoil still doesn't "feel" right. The problem is mainly the fact ...
7
votes
2answers
224 views

Determining if player-created structure matches a template in a 3D block-based game

Disclaimer: this is one of those dreaded Minecraft-style questions, but I feel it's more a data structures and algorithms question I'm really new to 3D data structures and am wondering what the best ...
7
votes
7answers
580 views

Random looking item placement that's deterministic?

I'm working on a sidescrolling game and I want to generate a forest for the background. I want the background to be the same for every one to make sure the quality is the same. I don't have access ...
6
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
565 views

Linking nodes algoritm for Visual Design

I'm developing an editor for my game, and now it's time to make a visual scripting system to let designer modify behaviours. This video shows what i have done and the problem to resolve the link ...
2
votes
1answer
395 views

All Pairs Shortest Paths in Weighted Undirected Graph

I'm currently working on path-finding for my game and need help with finding an efficient algorithm to calculating the all-pairs shortest paths in a weighted undirected graph (each vertex in the graph ...
4
votes
2answers
756 views

How can I implement shader lookups for my material system?

I have been working on a material system and for the most part everything works just fine, however, I hard code the shader that will be used. Obviously this causes a problem when I want to have the ...
2
votes
2answers
268 views

How can I animate a recursive algorithm?

Say I have a recursive algorithm, for example one that generates a random tree: // Pseudocode, just a simple algorithm: it isn't perfect. function generate_branch(angle, length, current_depth, ...
4
votes
2answers
446 views

Enemy mathematical behavior

I'm really trying to up my game in game mathematics and now I'm working on enemy movement and a bit of AI. I have an enemy with two modes attack and avoid, based on an integer avoid variable that's ...
2
votes
1answer
2k views

How do I generate a torus mesh?

I'm trying to programmatically generate vertices and indices for a torus. I found this piece of code somewhere, and it looks like it works, but I'm not certain it is correct. With my little knowledge ...
10
votes
1answer
659 views

Algorithm for a tool to theorycraft stats based on a game(league of legends)

I would like to create a simulator(basically for testing purposes) for a game(League of legends). The basics of the game: you have a hero which has some stats: Health Point Attack Damage Attack ...
-2
votes
1answer
550 views

Dungeon map generator not working in javascript

I am trying to convert this dungeon algorithm from java into javascript, however, my script works 70% of the time. When it works, the rooms are missing a wall on one side, and when it does not work, ...
9
votes
3answers
2k views

Networking in real-time strategy games

What is the current state-of-the-art to network real-time strategy games? I seem to recall that a few years ago, some AAA titles only transmitted the player inputs (Starcraft 1, Age of Empires). ...
0
votes
1answer
559 views

What is the difference between the marching cubes algorithm and metaballs?

After doing some research, I found out about the marching cubes algorithm and "metaballs". How exactly do they differ?
6
votes
2answers
432 views

Is it possible to have concurrent collision detection where every entity acts at exactly the same time?

There are many algorithms that can be used for collision detection. In many cases we check for an overlap in coordinates of an entity. If we make a triangle a,b and c. We have 2 entities at a and b ...
11
votes
3answers
8k views

How to implement A.I. for checkers/draughts?

I saw this checkers game and I wondered how the A.I. was implemented. How should I implement an A.I. for checkers (draughts, dama, dame)? Are there any known algorithms? Very thnaks full to all. I ...
1
vote
2answers
676 views

Why isn't my player movement code working properly?

I'm making a text-based RPG. One thing I've been trying to implement for a long time now is the ability for the player to move North, South, East, or West. I have my code placed in a MoveBehavior ...
12
votes
1answer
319 views

Detecting a sequence of nodes in a grid

Given the image below, I need to detect the most optimal sequence on the board (the green line). The blue/red lines represent possible, but not the best moves. Here are the rules: You can move to ...
4
votes
1answer
704 views

Issue with implemented Minesweeper algorithm

So I'm attempting to learn Python by way of Minesweeper. I've got experience with SDL, so I figured playing around with PyGame sounded like a fun way to learn the syntax of the language. Anywho, I'm ...
4
votes
2answers
339 views

How do I find the contour points of a png?

In my game, I need a way to produce convex polygons from pngs of objects. For example, a maple leaf would result like this: Essentially right now, the way my algorithm works is by putting all ...
5
votes
3answers
2k views

How can I generate a terrain heightmap from the perlin algorithm?

How can I generate a terrain heightmap from the perlin algorithm? I am trying to make a terrain generator (like World Machine). This is the source code I have for the perlin. The only thing that I ...
9
votes
6answers
714 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
816 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
418 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
523 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
490 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
13k 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
705 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
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
967 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
794 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
944 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
797 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
152 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
722 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
8k 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
405 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 ...