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.
190
questions
4
votes
3
answers
4k
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
1
answer
1k
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
1
answer
1k
views
How to create a grid based on random shapes?
How to create a "grid" using actionscript like the image below?
Basically you have an area of 1100x615 which should be filled with shapes that could be rotated and scaled...
Collision detection ...
4
votes
3
answers
3k
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 ...
4
votes
3
answers
5k
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
1
answer
351
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 ...
3
votes
4
answers
2k
views
How do I apply different probability factors in an algorithm for a cricket simulation game?
I am trying to write the algorithm for a cricket simulation game which generates runs on each ball between 0 to 6. The run rate or runs generated changes when these factors come into play like skill ...
3
votes
3
answers
883
views
How to make obstacles spawn randomly but still leave a way for player to pass?
I'm trying to make a game like Crossy Road:
In this game, you control the character(the frog in this case) to go across the streets, and you have to prevent your character from being hit by a car.
...
3
votes
2
answers
124
views
Need the co-ordinates of innerPolygon
Let say I have this diagram,
Given that i have all the co-ordinates of outer polygon and the distance between inner and outer polygon is d is also given. How to calculate the inner polygon co-...
3
votes
3
answers
1k
views
How to read a sparse Octree sequentially, like a 3D array?
Is it possible to read a sparse Octree like a regular 3D grid:
for(z)
for(y)
for(x)
...and still benefit from skipping large empty areas?
I need this for a ...
3
votes
2
answers
3k
views
How does flocking algorithm work?
I read and understand the basic of flocking algorithm. Basically, we need to have 3 behaviors:
1. Cohesion
2. Separation
3. Alignment
From my understanding, it's like a state machine. Every time we ...
3
votes
1
answer
304
views
How to devise an algorithm for a person being on a walk?
The game is an isometric RPG. The map is tile based.
I'm creating a town for this game. And I want one of the characters to roam the town randomly, because she is on a walk with her children.
I ...
2
votes
1
answer
3k
views
Welzl Algorithm to find the Smallest Bounding Sphere
I'm implementing Welzl's Algorithm to find the Smallest Bounding Sphere.
In brief, the algorithm works by maintaining:
a set of points to contain in the sphere (inside its interior, or on its ...
2
votes
2
answers
3k
views
Data structure for bubble shooter game
I'm starting to make a bubble shooter game for a mobile OS. Assume this is just the basic "three or more same-color bubbles that touch pop" and all bubbles that are separated from their group fall/pop....
2
votes
2
answers
209
views
Decomposing a collision grid into a set of boxes
I'm looking for a decent algorithm to decompose a collision grid (e.g. bool[w,h])...
...into a non-overlapping set of boxes (e.g. ...
2
votes
0
answers
38
views
Finding a path to a circular zone in continuous space [duplicate]
I need to find the shortest path for an agent that wants to use a ranged attack against the specified target. This means that the path's ending point should be inside the range of the attack and have ...
2
votes
2
answers
2k
views
Best 2d AI movement system
I'm creating a top-down rpg (no tile-based) using libgdx. Now I need to make enemies move on map with obstacles. What is the best approach to realize that? A*(I think, if enemy see player, he should ...
2
votes
2
answers
6k
views
Fastest way to neutralize scale in the transform matrix?
Let's assume we have 4x4 3D transformation matrix, that is the result of scale, rotation, and translation transforms. How to set its scale to (1,1,1) in the fastest way? Assume also that the matrix is ...
2
votes
4
answers
1k
views
How do I approximate the result of battle between two armies with known strengths?
I need a simple algorithm to calculate the outcome of two differently sized armies battling.
Each army has 1-100 troops and every troop is the same value on the battlefield. The troops do not have ...
2
votes
1
answer
1k
views
Match-3 algorithm to fill empty space left from removing matches
I am currently creating a match 3 game.
I am at the point where I have objects dropping down in the column when only one item is removed. So if an item is removed, the above item moves into its old ...
1
vote
1
answer
182
views
Dividing amount of exp between rank A and B into a curve?
In my game I have a rank system. You start at rank A, and then you can level from level 1 to level 10. When you reach level 10, you get promoted to rank B, and you go from level 1 to 10 again, and ...
1
vote
2
answers
122
views
Deleting an item in the game world: detecting if an item supports other items
I'm writing a 3D construction module similar to the how you build houses in the Sims. Users are able to build walls and floors (which also act as ceilings) on multiple floors (layers). This question ...
1
vote
2
answers
991
views
How do I launch a ballistic projectile to hit a moving target, given: launch position & angle, target position & velocity?
This problem is in 3D space. My question is: How do you find the initial velocity of a projectile that flies under constant gravity, so that it hits a target moving with constant velocity, given the ...
1
vote
1
answer
137
views
Efficient algorithm for simultaneously updating game objects which need to be updated
I have a grid of objects like this:
1
+
F
1 is equal to the constant 1, ...
1
vote
1
answer
802
views
A* heuristic for use with Goal Oriented Action Planner
Many of the high-level descriptions I've found for GOAP and similar planners suggest using A* for their path-finding, but I'm struggling to implement it for my own planner. Specifically, I'm ...
1
vote
2
answers
2k
views
Surface creation algorithm using points cloud
I am looking for a realtime algorithm to create a 2D mesh using points. But I am quite confused. It seems that Delaunay triangulation can help me create mesh using point clouds, but Meta-balls seems ...
1
vote
1
answer
201
views
Implementation of finding an index in a 1D array for a triangular grid
Am using a while loop to find an index within a 1D array, is there an easier, less-time-consuming and/or mathmatical way to find the index?
Consider the next grid:
...
1
vote
4
answers
949
views
How to order points on a 3D grid such that we can connect them in a line loop correctly
I want to recreate an effect as close as possible to X-Com: Enemy Unkown's movement range feedback:
(source: gameinformer.com)
The blue line delimits the tiles which the soldier can reach using a ...
1
vote
1
answer
2k
views
Procedural terrain generation
Currently I have a procedurally generated planet using multiple octaves of perlin noise. The thing is, that I don't generate heightmap, but rather get the values of perlin function and apply them ...
1
vote
3
answers
3k
views
Why can't my A* implementation find a path out of an open room?
I tried to follow this article with the following example, but in my attempts it always ends up with a dead end.
If we take G being 10 in a straight line or 14 in a diagonal, and H the distance in ...
1
vote
1
answer
1k
views
What algorithms can I use for bullet movement toward the enemy?
I'm developing 2D strategy game. There are weapons that shoot at enemies.
From what I've read in this, this, this and this post I think that I need linear algebra, but I don't really understand what ...
1
vote
2
answers
6k
views
MiniMax not working properly(for checkers game)
I am creating a checkers game but My miniMax is not functioning properly,it is always switching between two positions for its move(index 20 and 17).Here is my code:
...
1
vote
1
answer
3k
views
What kind of shader is this?
Cube World uses a pretty good looking shader, I especially like the shading of the characters:
Is this soft shading? I'd like to achieve this effect in Unity 3D Free, but since the free version doesn'...
0
votes
3
answers
497
views
Simulating (Human) Needs? [closed]
How can I simulate the vegetation (of a human being)?
To simulate Hunger for example, I use some kind of saturation based system now. Means that every food-object saturates differently and the ...
0
votes
1
answer
200
views
Most efficient way to hide out of bounds object in tile based environment [duplicate]
I am working on a desktop game in C#, with Monogame framework. I am storing the tile instances in a 2D Array, for the sake of easy collision detection. But the levels are big (often 100x100 or bigger) ...
0
votes
2
answers
466
views
Weighted random events with conditions
I'm building a system for distributing ingame events for a strategy game. The game is heavily driven by the events and each country/player should receive one or more per time unit.
The algorithm is ...
0
votes
1
answer
495
views
Random equidistant points like a tree branch (JS)
I'm working on an algorithm to generate a "graph" like array of points in my game world. See Image Below:
Here is what i'm working on so far, which will generate the black line.. but this may not be ...
0
votes
1
answer
131
views
How to get a reflex edge on a non-convex mesh
I am trying to implement a convex decomposition and I need to find the convex vertex on a mesh. Is there a algorithm that I can use to find the convex vertex on a mesh.
0
votes
1
answer
916
views
Stepping from Point out on Archimedes Spiral for Length along Arc
I wasn’t sure whether to put this question in mathematics or programming?
My question has two parts with the second part dependent on the first.
I’m looking to use Archimedes spirals in some game ...
0
votes
1
answer
393
views
Algorithm for finding edge vertex points on a tilemap
I have a 2d tilemap array contains 1 or 0. 0 corresponds empty tile, 1 corresponds solid tile. If tile is 1 I draw a texture.
I have to find edge vertices and coordinates that 1's grouped.
I couldn't ...