# Tagged Questions

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.

370 views

### Find two points in a point cloud with the maximum distance?

What is the least computationally complex way to find two points such that the distance between them is greater or equal to any other pair. Remember hearing something about how you could find such a ...
123 views

### Why is my delta time constantly under 1 millisecond?

I have a game loop that looks like this: while (Sync()) { DoStuff(); } The sync function computes my delta time like this: bool Sync() { EndTime = GetTime(); DeltaTime = (EndTime - ...
479 views

### How should a circuit or power system (like redstone in Minecraft) be implemented

I want to implement a power-system like the redstone system in minecraft. I have n power sources and m cables. If I disconnect the power source or a cable the circuit should turn off. How do I ...
102 views

### Most efficient way for nested loop to not repeat a value of parent loop in pair-wise structure (C# or Javascript) [closed]

It's hard to choose the correct title for this question, so let's see if I am able to better convey here what I am in search for. If the title is too far away, suggestions are welcome and I can edit ...
396 views

### How to implement view bobbing?

I'm developing a First-Person shooter game. Everything is just fine but I've a little problem with my camera moving. My FPS camera is moving smoothly! But the camera should move like a human is ...
65 views

### Marching cubes and greedy meshing

Currently i am trying to implement the marching cubes algorithm into my voxel engine to get smoother terrain. My voxel engine also uses the greedy meshing algorithm to optimize the engines meshing. My ...
2k views

### Matching a chunk of procedurally generated world to a chunk of other world

Have you read The Chronicles of Amber by Roger Zelazny? Imagine yourself playing in 3rd person MMO game. You spawn in the world and start to wander around. After some time, when you think, that you'...
185 views

### Are hard coded “rooms” better than dynamically generated on a smart phone, from performance point of view

This question pertains to a type of platform/maze game (made with Unity 5) for typical smartphones (iOS/Android). This game has following characteristics: 1. an upper limit (about 100) on the amount ...
180 views

### Improve (adding randomness) minmax algorithm for Connect Four

I have implemented the minmax algorithm for the Connect Four game. It works well (almost...), but if the player does the same moves, the computer will do the same moves as well, for each match. There ...
63 views

### What is a viable way of finding the minimum swaps to sort numbers in pyramid?

I have made a game that consists of a pyramid of hexagons with numbers from 00 to 99 randomly positioned in groups of 6, 10 or 15 elements. Now, I'm working to create an auto-solver but for the last 2 ...
138 views

### Funnel algorithm

I'm implementing the funnel algorithm for pathfinding. After searching many resources I found those : https://skatgame.net/mburo/ps/thesis_demyen_2006.pdf http://digestingduck.blogspot.com.by/2010/03/...
266 views

### Good algorithm to generate pixels for thick line?

I am not really making some drawing as of picture manipulation but I use line function to calculate "claimed" pixels in my line race game (demo here): The actual rendering is apart from the game ...
236 views

### City-region generation

I am currently making a procedural generated map and wanted to add regions to the cities indicating their reach, the way I am achieving it currently is by expanding outwards from the city center until ...
306 views

### RTS: Unit sight in fog of war

I am making an RTS game, and like most RTSs, you can see what's going on in a part of a map only if you have a unit over there. I have few ideas how to accomplish this, but there are problems with ...
454 views

### Match 3 game - Check for matches

I'm out of ideas and need help. So far I generate a board nicely using a flood fill algorithm and a 2d-array, I can also move tiles around the board. Each Tile knows its own row, column and ID (...
21 views

### How can I dynamically change the bone structure to reach a point?

Say I have a skeletal animation about a whip hit a target. When I create this animation, the root of the whip is at (0, 0, 0) and the target is at (10, 20, 10). Now in the real game, the target is not ...
119 views

### How do I make hit damage a Gaussian distribution centered around a value?

I'd like my character's attacks to on average 10 damage, but to vary anywhere from 0 to 20. Instead of a linear spread, I would like a normal distribution, so most of their hits are between 10-15, ...
103 views

### How can I calculate an octree node's depth from its location code?

The article Advanced Octrees 2: node representations states: The AABB (axis-aligned bounding box) of the node can be stored explicitly as before, or it can be computed from the node’s tree depth ...
340 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 ...
40 views

### How to get a difference of angles in one mathematical expression? [duplicate]

I need to do this for AI and also range calculation over a curved surface. I have two angles, a1 and a2, which can be in the range from 0 to 359. I need to calculate the difference between them, and ...
99 views

### A* Pathfinding math for 2D, oblique style game

I'm making a 2D, oblique-styled RPG game and am implementing A* pathfinding for NPCs. The game is on canvas, using melonJS engine and sprites not confined to a 'grid'. I'm having a hard time ...
118 views

### A Star pathfinding on oblique map

I'm making an RPG and want to make npc ai to navigate the city. I am using polylines for collision detection, and my map is 2D, but oblique styled. I am considering using the A* algorithm to help them ...
172 views

### Special Pathfinding Algorithm

I need help with following pathfinding Task: I have a grid (7x7 squares) and the starting square is always on the far left side (column 0) and its target is to reach the far right side (column 6). ...
41 views

### traversing the area

i want to move point along spiral like hexagon for example i want to traverse the whole area and my player (point) is standing where i have placed it manually. now i want to start from this point and ...
151 views

### Pathing for 2D, sprite-based game

I'm making a 2D, oblique-styled sprite based RPG. My game does not live in a 2D matrix (like Tetris), rather it's sprites animating over a tilemap. I am trying to set pathing rules for NPCs. I've ...
50 views

### Calculating the illumination level of an object

In my (UE4) scene I have an object and several (point) light sources. The object can move around, getting closer and away from all those light sources. Now I need to calculate for each light source ...
431 views

### What are the disadvantages of R-Trees in collision detection?

I was poking around in SQLite and discovered R-trees. A little digging revealed that R-trees are really just fancy AABB-trees. Then I realize that the state of the art in collision detection (often ...
85 views

### Efficient dynamic character shadows [SW Rasterizer]

I am working on a SW rasterizer for a quarter-century old console (think sub-100 MHz RISC CPU, no dedicated 3D HW, couple megs of RAM) and am approaching a stage where I will be adding dynamic ...
141 views

### How can check a collision between 2 non-axis aligned boxes?

I'm making a simple and easy game and I need to detect the collision between 2 boxes. It only needs to return trueor false, no physics involved. I started working and couldn't find an algorithm that ...
97 views

### Best collision algorithm for Axis Aligned Bouding Boxes [duplicate]

I have a number of quads (suppose like 20-40) and i want to quickly check the collisions between any of them. I would like to know if there's a quick algorithm to do that 60 times per second without ...
78 views

### Grid board fill with special cells - predicting movement

I have to create an algorithm which will fill a board, which is made of square cells, with elements. Board can have different sizes and it doesn't have to be a square. Elements fall from top to bottom....
125 views

### Algorithm to fill a shape defined by 4 pixel points?

I'm developing an application in Unity3D where a user can define 4 pixel points on screen, and what I would like to do is fill this shape with pixels using Unity's SetPixel. While I can do this ...
50 views

### How does hidden surface removal work?

Lately, I've been learning some OpenGL for fun, and I've been thinking about hidden surface removal. Say you have a high poly count static scene, with nothing that moves, no bones, physics, etc. Just ...
172 views

### How do game engines mitigate CPU cost for many trigger zones & entities? [closed]

It's a rather simple question, but a somewhat fundamental in computing in general. Let's say we have a player controlled character in an open world. The world is large. In this game-world we have a ...
74 views

### Optimal trajectory of area exploration

I've got next problem. There is three objects: first one, with next characteristics: circular area of view, speed, drag coefficient; wind (or water current, doesn't matter; some sort of resistance) ...
65 views

### Short distances from reference point

I would like to compute short distance from reference point in 2d grid. To expose: 0, 0: not penetrable 0, 1: not penetrable ... 1, 1: penetrable ... I search an algorithm who return: 1, 1: 1 ...
255 views

### Pathfinding with inertia

I'm currently working for pathfinding for a game where units are moving, but they have inertia. Most typical pathfinding algorithms (A*, Djikastra, etc.) are simply designed to minimize the length of ...
251 views

### Algorithm for a smooth weather transitions in game weather system

I've been slowly learning c++ and building up a codebase intending to create a simple first person role playing game. I've coded a time management tool to track time elapsed in game, an inventory and ...
136 views

### Libgdx array of Vector2 closest point

I have an array of objects. Their position is a Vector2 (x, y). I want to select the closest object, given a (x, y) coordinate (that represents an user touch on screen). Searching on web I found a few ...
113 views

### Get algorithm (Chance-to-Hit) from Input and Output

I am currently working on a chance-to-hit formula for an rpg. It consists of the following parts: AttackSkill: The used Attribute of the Attacker (Range: 1-10) AttackBonus: A Modifier from ...
133 views

### Pathfinding Algorithms [closed]

I am new to game programming I currently am using unity's 2D power to remake an 2D game for sake of practice. So I am just little confuse about one thing, so far every enemy in my game was dumb(they ...
613 views

### What makes Minecraft so CPU intensive, and what could be done to improve it? [closed]

Recently I've been searching for VPSes that allow Minecraft servers to be hosted, and surprisingly very few do. Most allow for games - but Minecraft in specific is disallowed by many. Now it's fairly ...
290 views

### How to create a map from graph

I want to draw a 2d polygon map based on data provided by another source to ease analysing actions on the map. The data has the following format: 1 ['2', '4', '5', '7', '17', '10'] 2 ['1', '3', '4'] ...
3k views

### How to render infinite universe?

I'm curious what are the best practices in game development industry to render 3d universe? To be more specific: The data points are given and static. Each point has position, color and size; The ...
63 views

### How to calculate normal vector of a curve?

How I can calculate the normal vector for tow dimension curve (I have the points of the curve in plane x y)?
543 views

### Algorithm for dividing a 2D grid into organic looking plates

the title pretty much says it all: How could one go about segmenting a 2D grid into smaller parts? My goal here is to create tectonic plates for further procedural world generation Details to ...
93 views

### Placing an AABB close to a point so that it doesn't intersect any other AABBs

Give a 2D space with a bunch of non-intersecting AABBs, and a point in this space (that may or may not be inside an AABB), how can I find the closest place where I can place a new AABB of a given size?...
54 views

### Java libgdx get clicked square without iter

I would like to detect which square is clicked without iterating over all elements! i don't want to do this anymore for all elements. if( x >= this.getAnchorX()-HalfWidth && x <= ...