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

1
vote
0answers
68 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 ...
1
vote
1answer
38 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 ...
1
vote
2answers
68 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 ...
0
votes
0answers
37 views

How do I efficiently generate all valid configuration spaces of a Tetronimo in Tetris?

This question is relevant to How can I do optimal pathfinding for a tetris piece, which assumes we already have a start and end state. How we can efficiently generate all those valid configuration ...
1
vote
3answers
73 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 ...
0
votes
0answers
26 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 ...
0
votes
1answer
40 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 ...
2
votes
1answer
35 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 ...
2
votes
3answers
147 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 ...
-2
votes
1answer
59 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) ...
2
votes
1answer
58 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 ...
6
votes
2answers
149 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 ...
3
votes
2answers
143 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 ...
-2
votes
1answer
68 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 ...
2
votes
3answers
72 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 ...
0
votes
1answer
87 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 ...
1
vote
2answers
201 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 ...
7
votes
2answers
181 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'] ...
14
votes
3answers
2k 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 ...
0
votes
1answer
39 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)?
3
votes
3answers
314 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 ...
3
votes
1answer
76 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 ...
-1
votes
1answer
47 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 <= ...
0
votes
2answers
260 views

Map Generation Algorithm [BOMBERMAN]

I'm looking for some wise tips concerning a specific game development : Bomberman-like. I am currently implementing a "random map" generation for the game, but I feel like I'm not doing in the best ...
1
vote
2answers
33 views

MiniMax strategy - What is the context of the numbers?

I've watched a new videos about the MiniMax concept and invariably the lecturer will say that the computer has 2 parties, Min and Max; Min always takes lower number and Max takes higher number. The ...
0
votes
2answers
129 views

finding a path from one point to another with obstacles help

Im building a tile based game and im implementing my path finding algorithm. Currently, it can find a path from point A to point B with no problems. However, if there are obstacles between point A and ...
3
votes
3answers
190 views

Getting one-point-collision object to conform to uneven terrain while keeping constant distance covered

This is probably best described by image: I have a character. For floor collision, it uses a single point (the red X). When the character moves, it conforms to the terrain; note how the blue line ...
3
votes
2answers
401 views

Pathfinding in 3d voxel: waypoints?

I have an application where I have a 3d collision voxel space (passable or non-passable at each point) and I want to plot a short unobstructed path between two points. There are no gravity ...
1
vote
1answer
80 views

Best way to calculate city influence maps similar to civilisation?

As the title says, imagine you want to generate the influence mask for a city, given that the map is a 2D grid rather than hex. An extra bit is that different points on the map might have different ...
1
vote
0answers
38 views

Integrating specular, diffuse reflection and refraction

I am implementing an MLT bidirectional path tracer. I have a problem integrating diffuse, specular reflection and refraction. 1) The first problem is diffuse and specular reflection. Diffuse ...
-1
votes
1answer
88 views

How can i fix my Ground detection code?

My ground detection works by checking if the player's x position is between the range of a sprite xpos+16 and xpos-16 if it is,then it uses a separate axis theorem on the y axis to see if the player ...
0
votes
2answers
71 views

Is there any easy way to understand the Alpha Beta for Othello?

I'm stuck with coding the Alpha Beta algorithm for a console-based game I'm developping at the moment. I tried to understand how it works for a week but still no idea how to get started with it. Here ...
2
votes
1answer
243 views

Pathfinding in a 2D “sidescrolling” strategy game

I've been thinking up a real-time strategy game that plays on a platformer type of map. The collidable portion of these maps will be made up of square tiles. I've done A* pathfinding in top down tile ...
32
votes
9answers
6k views

How can I quantify a drawn line's straightness?

I'm working on a game which requires players to draw a line from a point A(x1,y1) to the other point B(x2,y2) on the screen of an Android device. I want to find how well that drawing fits to a ...
0
votes
1answer
36 views

Texture to Painted Vertex Algorithm

I want to generate some game textures into coloured vertex arrays. Is there a known algorithm to transform texture/bitmap data into an optimised vertex array. Much like how the Homeworld skyboxes ...
1
vote
0answers
121 views

Recursive backtracking sometimes missing a tile?

I have a basic recursive backtracking alghorithm for a maze. It pretty much works but ocasionally leaves some tiles in the corners untouched. This is the recursive function: void ...
-2
votes
2answers
105 views

Minesweeper number placement [closed]

My professor gave us a project: make a minesweeper clone. However, he said that he will give bonus points for the 3 fastest algorithms for board generation. I'm currently doing the algorithm that ...
0
votes
1answer
75 views

A* pathfinding not finding shortest path with weird behavior [closed]

NOTE I have read through this thread and have tried the implemented answer The A* pathfinding algorithm works fine most of the time but in some specific cases, it seems to not use the shortest path. ...
-1
votes
1answer
128 views

Tile map optimization algorithm

I've read this artical on tilemap optimization https://www.scirra.com/blog/ashley/3/tech-blog-tilemap-tidbits and wondering what algorithm is used to achieve something like this. I'm wondering ...
0
votes
2answers
120 views

Fast Ray Sphere collision code

I am looking at here and while it's well organized a lot of links are broken: http://www.realtimerendering.com/intersections.html I am trying to find fast code that will give me the hit point and the ...
0
votes
2answers
186 views

Space invader barrier implementation algorithm

I've been struggling with implementing the space invader bullet to barriers. I wanted right now to blast a circle around, when the bullet hits the barrier and modifies the circle. As shown in the ...
0
votes
2answers
84 views

In a grid based system, where users can build their own walls to create buildings, how do you determine which parts are indoors? [duplicate]

I've looked around for an algorithm to solve this problem, but I can't seem to find anything. In a game I am working on, data is held in a grid. Certain squares within that grid can be set as walls, ...
0
votes
1answer
74 views

How to invert a damage formula?

I have created simple damage formula based on source percent, which return fixed percent of damage. DAMAGE_PERCENT = Exp(Log(100) * (1 - (100 - SOURCE_PERCENT) / 150) Here is the result: ...
0
votes
1answer
108 views

Collision Detection algorithm using Line Detection

For a 2D physics sandbox I am working on, I need a way of detecting detecting a collision using lines. This sandbox uses a class called Particle, which has a x and a y (stored as a struct called ...
0
votes
0answers
88 views

Isometric staggered multi tile buildings

I'm writing a isometric staggered rpg engine and i am at loss to how to make the buildings placement diamond show up. What I mean is i have tile2screen and screen2tile functions and it works ok. I ...
1
vote
1answer
68 views

Paint game level algorithm

I have a game, and I have a level editor where you can build your level from blocks. Blocks positioned in cells. So blocks can have no neighbours or have one or few neighbours. My problem is that I ...
1
vote
2answers
131 views

Bubble shooter clone, structure for storing/adding of bubbles

Im having a few issues trying to figure out what the best data structure to use for storing bubbles on the grid, and how to connect new bubbles to the grid when a moving ball collides with a ball on ...
0
votes
1answer
102 views

How to calculate a score algorithm based on elapsed time?

I'm trying to calculate an alogirthm based on elapsed time to calculate score based on a music beat. I have the music beat divided into 4 because that's the time measure of that beat. So If the user ...
0
votes
0answers
18 views

Smoothly scaling positions of GraphicsItems on a 2D GraphicsScene

I layout a bunch of nodes on a QGraphicsScene(A 2D Canvas). The nodes are basic ellipses. It works reasonably well. However I would like to know how to better size the ellipses. Currently I have a ...
1
vote
1answer
78 views

Planar scene graph

Suppose there are many line segments on a plane (2D scene) and I would like to redraw only small portion ("window") of the whole scene. The scene is dynamic, meaning one can add/remove/transform ...