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

5
votes
2answers
1k views

Algorithm for random flight of a fly

I'm new to game development. What is a good algorithm to model the random flight of a fly? I've been looking at path-finding algorithms, but they don't give any interesting random behaviour.
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. ...
5
votes
2answers
460 views

Matchmaking by user-supplied parameters

I'm looking for matchmaking algorithm for a 1 vs 1 online game. Players must not be matched by their skill level, but instead by some specific filters set by the players. Each player sends a request ...
5
votes
2answers
4k views

Generate islands/continents with simplex noise

Managed to get something like this using a simplexnoise port i made from the original javacode to php: Used some tips from other post: Understanding Perlin Noise basically, lowered the frequency ...
5
votes
3answers
202 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 ...
5
votes
4answers
837 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 ...
5
votes
3answers
172 views

Pathfinding Search for Path of Specific Length

I am creating a roguelike. This question applies to random map generation. First, I generate areas using a BSP algorithm, where I randomly divide the map into areas. Then, I generate a graph of the ...
5
votes
1answer
223 views

What makes a path finding heuristic Monotonic vs. Non-monotonic?

I am currently working on an algorithm that solves a path through the maze. So far I have implemented a Manhattan and Pythagorean Heuristic. I was wondering what makes a heuristic monotonic and how ...
5
votes
1answer
445 views

How do you parameterize turn based AI?

I would like to create/find an AI algorithm/process that can be parameterized such that a change in the parameters causes a change in the AI behavior. I am specifically looking to apply this to a turn ...
5
votes
1answer
648 views

How to generate portal zones?

I'm developing a portal-based scene manager. Basically all it does is to check the portals against the camera frustum, and render their associated portal zones accordingly. Is there any way my editor ...
5
votes
2answers
575 views

How to place rooms proceduraly (rule based) on in a game word

I am trying to design the algorithm for my level generation which is a rule driven system. I have created all the rules for the system. I have taken care to insure that all rooms make sense in a grid ...
5
votes
1answer
274 views

In the GJK algorithm, when is a point ever closer to the origin than a line?

The GJK algorithm depends upon a function in its loop that updates the simplex and search direction for the next iteration (which is often called something like DoSimplex() or ProcessSimplex()). In ...
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 ...
5
votes
1answer
231 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 ...
5
votes
1answer
313 views

Triangulating a partially triangulated mesh (2D)

Referring to the above exhibits, this is the scenario I am working with: starting with a planar graph (in my case, a 2D mesh) with a given triangulation, based on a certain criterion, the graph ...
5
votes
1answer
1k views

3D isometric depth sorting

How is it possible to depth sort tiles and objects in an isometric environments without any limitations? I've been researching this for a while now and there seems to be no publicly available answers ...
5
votes
2answers
273 views

Randomly generated track

I would like to create randomly generated track from one point to another with specified length of that track (it can be 2 more or less as a result of that function) in matrix. I have function called ...
5
votes
2answers
789 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 ...
5
votes
2answers
148 views

Determining a sensible gear-like hierarchy for a series of connected objects

I would like a series of objects to behave in similar manner to a series of connected gears. This means that each black object in the diagram below will rotate at a speed based on the ratio of their ...
5
votes
3answers
195 views

How can I ensure a grid can be filled with Tetris-like pieces?

I'm thinking of making a puzzle game where the objective is to fill a grid with shaped puzzle pieces (for example, the classic Tetris shapes). How can I go about generating a set of pieces that can ...
4
votes
2answers
3k views

How do I optimize searching for the nearest point?

For a little project of mine I'm trying to implement a space colonization algorithm in order to grow trees. The current implementation of this algorithm works fine. But I have to optimize the whole ...
4
votes
2answers
916 views

Repairing back-facing triangles without user input

My 3D application works with user-imported 3D models. Frequently, those models have a few vertices facing into the wrong direction. (For example, there is a 3D roof and a few triangles of that roof ...
4
votes
1answer
385 views

Help me please to choose proper path-finding algorithm

I am new to game development and just want to ask for advice. I need to know which path-finding algoritm will be suitable for my scenario: Units - any shape. But in most cases rectangles of ...
4
votes
3answers
1k views

Simple speed deceleration with variable time step?

When you use a fixed time step you can call speed=speed*0.95 to emulate speed deceleration in a simple way. I want to do the same thing with variable time step. I wish to have a simple function ...
4
votes
2answers
518 views

Generate random starting points at same distance between them

Is there an algorithm to generate random 2D points that are at the same distance between each other? Useful for starting points. Check map: Don't be picky, I know in the image points are not at the ...
4
votes
1answer
799 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
495 views

Can I use an AI engine written in C++ in my Unity game? If yes, how can I do this?

I am studying some chess and others AI algorithms and the majority of these implementations are made in C and C++, my question is, if I make a chess board and all the graphic thing in Unity, can I ...
4
votes
3answers
699 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 ...
4
votes
2answers
636 views

How simulate the return effect of the wheel of fortune needle

I am trying to create a spinning wheel which slows down after a specific time. I managed to simulate the slowdown of the wheel but I need also to put a needle which go up and down with an angle of ...
4
votes
5answers
646 views

Goalkeeper Jumping Algorithm?

This may be a "best way to" question, so may be susceptible to opinion-based answers (which is ok for me). But I would also like if there are any tutorials , research papers , etc. I'm trying to make ...
4
votes
1answer
398 views

Path finding in games

I am writing my term paper about Path finding algorithms in games, and i've got a couple of questions, hopefully you people could help me out with those ;) So, i've done a little bit of searching ...
4
votes
2answers
675 views

Factors to consider when building an algorithm for gun recoil

What would be a good algorithm for calculating the recoil of a shooting guns cross-hairs? What I've got now, is something like this: Define min/max recoil based on weapon size Generate random ...
4
votes
2answers
167 views

What is the best way to store temporary selected characters and their insertion order?

I'm developing word game similar to word mole. I'm having a hard time determining how to store temporary selected character (and in turn will changed into word). Here's the situations. Say, I have ...
4
votes
2answers
391 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 ...
4
votes
2answers
417 views

How can I adapt “random walk” generation to very large maps?

The random (or drunkard's) walk is a great, simple algorithm that can generate very organic-looking maps, such as this: Unfortunately it seems to have poor scalability, making it unsuitable for ...
4
votes
3answers
576 views

Creating the nodes for path finding during run time - more like path making and more

I'm making my 1st game. I'm using javascript as I currently want to learn to make games without needing to learn another language but this is more of a general game dev question. It's a 2d turn-based ...
4
votes
3answers
130 views

How can I check if a player-drawn line follows a path?

I want to draw an invisible path that the user must follow. I've stored that path as points. When a player draws a line, how can I test if it follows the path I've stored? Here's an example for ...
4
votes
2answers
760 views

Building triangle adjacency data

Given a list of triangle indices, how exactly does one go about converting that to a list of indices with adjacency for a geometry shader? Note that we're strictly talking about indices here - ...
4
votes
1answer
482 views

Help understanding Simplex Noise

Introduction This is less of a "how to" on using 2D simplex noise and more of a quest to understand what is happening both in the math and visually. I would rather not copy and paste the code I've ...
4
votes
3answers
2k views

Bubble shooter falling algorithm

To complete this question about the same color search algorithm, I would like to know if someone knows which is the best implementation for making other bubbles fall when they are no longer attached. ...
4
votes
2answers
393 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, ...
4
votes
2answers
191 views

Exists a dedicated non-O(n²) Algorithm for avoiding to have overlapping elements?

I am generating positions in a random fashion. In the game world, instantiated elements have a radius, and shouldn't overlap. The problem is that they will overlap because I use a usual random ...
4
votes
3answers
393 views

What techniques make next gen look so realistic [closed]

I have watch several gameplays from upcoming titles for ps4 and xbox one and I must admit that they are breath taking. Of course with new hardware, models will have more polygons and higher texture ...
4
votes
1answer
101 views

Finding line of best fit demarcating national borders

Per title, what algorithms are available for defining borders for states (or other entities) based on certain nodes in the world (eg. cities or armies) with varying weights? For example, there are ...
4
votes
1answer
247 views

Create shape from points / lines in editor and mathematically calculate nearest points within shape

If I want an editor that accepts "points" of a minimum of three (a triangle) and I just add some points first, like this: how can I mathematically connect these corners (points) into an object of ...
4
votes
3answers
166 views

Determine inventory item position shape

Not a great title but couldnt think of a shorter way to describe it. I am trying to think of the best way to determine the shape of items placed in the players inventory. I guess the best examples ...
4
votes
1answer
111 views

Best approach to get clicked objects from a display list (2D)

I'm implementing a display list to manage my visuals on screen. I want to know which object is clicked. My objects already have z-order variable. With my current knowledge (almost nothing) the only ...
4
votes
1answer
852 views

Find sub-graphs in a graph

The initial problem I'm trying to solve is for pac-man, but of course there must be thousands of other situations with the same problem. I consider the pac-man grid to be a graph (two ways of doing ...
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 ...
4
votes
3answers
418 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 ...