# 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.

961 questions
597 views

### Best data structure to store large amount of data

I am making a minecraft kind of game. In which I have 100s of objects and their crafting recipe. Now I want to store them inside the program, ie I cannot load external files. Everything must be ...
78 views

### Split a grid into shapes that can be moved back from 4 directions

Basically I have 4 grids Left, Right, Top, Bottom. Player can choose each of them and move all the blocks on that grid to the Middle grid to fulfill it, like tetris from 4 directions: ...
153 views

### Chunked QuadTree creation & handling

I am new to LOD-based techniques so please be lenient with your comments about my naive questions. Preface: My aim is a simple terrain renderer (preferred C++ and OGL) that is to load a height-map (...
3k views

### How to compute the area of an irregular shape?

I have a room object defined by a collection of looping line segments that I need to calculate the area for. The classes can be described as follows (in pseudo-code): ...
185 views

### Procedural sidescroller world gen algorithm by seed

I'm trying to recreate a procedural side-scroller world gen algorithm by using a seed and I find my self stuck trying to solve a particular problem. Seed generation applies very well with voxel-like ...
419 views

### Multiple Object Collision SDL

I figured this is would be the correct place to ask the following ... 1) How would I go about making multiple object collision detection (Bullets For Example)? 2) How would I make it efficient ...
69 views

### What could I use to search tiles in a game [duplicate]

I'm creating a tile based game similar to Minesweeper. When a user clicks on a tile and its not a mine or a number space I need to search and expose the adjacent tiles that are empty and stop when it ...
3k views

### Is A* efficient even when the obstacles are moving?

I'm just starting to learn about path-finding and have been looking into the A* algorithm and my main concern is that it all of the examples I have seen show static obstacles that it computes around. ...
325 views

### Generating Arrow Maze puzzles

I have picked this puzzle shown here as training in programming games. In these mazes you follow the arrows. From each arrow you can move to any of the arrows it's pointing to, in the same row, ...
196 views

### How to implement D&D 4e's line of sight algorithm?

D&D 4th Edition (the tabletop game) has combat on a 2D map with square tiles. A creature occupies an entire single tile. The attacker has clear sight on the defender if lines can be drawn from ...
303 views

### Split a grid into random paths

I need an algorithm to split a grid into randomly generated paths where: A path is a list of cells connected at most to two adjacent cells. Paths have a minimum and maximum length. All cells in the ...
184 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 ...
826 views

### Procedurally generating dungeons using predefined rooms

Most attempts at procedurally generating dungeons I have stumbled upon do space out areas that will be rooms and connect them will corridors and hallways but what about instances where you have a ...
299 views

### Managing game progress - states, stages, or flags

I am creating an rpg. So far I've used a global game stage as well as individual npc stages (increased when completing a quest for example) to control the "stage" the game is in. I.e if I have a log ...
93 views

### How to simulate camera turbulence for in-game cinematics [closed]

Are there any good algorithms for generating a convincing turbulence effect that can be applied to an in-game camera. For example, in use cases such as the viewpoint of a plane flying low and fast ...
182 views

### Tile-based board game collision mechanism algorithm

I am looking to see ideas for an algorithm which will handle collisions for some battle-ship tile-based board game. A little about the game The game is pretty simple. Basically there is a board, ...
832 views

### Space nebula cloud generation?

I found a cool kickstarter project called "Skywanders". It's an minecraft like space game with a lego like building system and pretty cool graphics. One thing I noticed are the "nebula clouds". They ...
64 views

### Good item distribution for 2d scroller game

I have made a scroller game where player moves to the right of the screen. I add a new uniform ground block about every 5 seconds. I was wondering how often should I put bonus items. Currently I put ...
886 views

...
355 views

### Triangulating a 3D mesh from a set of data points

I'm trying to implement the Bowyer-Watson point insertion version of the Delaunay triangulation algorithm, but in 3D. I previously implemented the 2D version without problems, but when transitioning ...
154 views

So I'm creating a Unity project that has a bunch of buttons (like hundreds) that each do a different thing when pressed. This is a 3D project and these buttons are also 3D. I already know how to ...
300 views

### What algorithm should I use to laid out pre-made rooms into a level?

I want to have a semi-procedural level, where rooms are pre-made but the way they're connected are proc-gen. The connections need to really exist - you can walk between rooms in hallways - not just ...
2k views

### How to detect matches in match-3 game?

I am working on a match 3 game where the number of matched cells matters (if you match 3 then they just get removed, if you match exactly 4 then something happens, and if you match more than 4 ...
192 views

### How do people implement pathfinding movement?

I understand how A* works, but I don't understand how movement is implemented, e.g. creating a list of directions and then going through that list until every direction is empty. How does that work? ...
29 views

### Algorithm for clipping convex quadrilaterals

I'm dealing with hardware that uses quads as its polygonal primitive. Not triangles. A triangle can be expressed by setting 2 of the 4 equal to each other for a degenerate quad. For the 3D engine, I'...
1k views

### Ray tracing and Z buffering in graphics

I am a high school student taking computer science as a subject, and someone who is very interested in the game development industry. I am currently writing an essay on Raytracing and Z-buffering by ...
74 views

### What is the simplest way to calculate energy earned based on time?

A player has 0 energy, and gains 5 every 15 minutes, but has a maximum of 100 energy. How would I be able to both store this in a database, and then recall the data later, to figure out how much ...
1k views

### Merging box colliders for optimization

Look at the picture. The figure on the left shows the individual box colliders in green. The yellow boxes on the right are the results of the optimization of the original box colliders. What is the ...
199 views

### Limiting number of user clicks to reduce micro: best method of implementation?

I'm making a client-server game where the user can select armies and move them from one place to another. In a bid to reduce the advantage of "being able to click faster" I've decided to implement ...
30 views

### Creating Smooth Corners when Converting 2D Polylines to 3D Models

Part of my game takes SVG polylines (which are just basically a set of x,y coordinates that define a multi-segment line) and converts them into 3D 'paths' (ie. a line created as a set of faces all ...
296 views

### Using a vector to measure an angle relative to the screen / camera

My game is supposed to have an object that changes it sprite depending on which way the mouse faces. programming this has become a challenge, because I want to calculate the angle relative to the ...
3k views

### How to optimize pathfinding on a very large dynamic 2d grid?

I have a large 2d tilemap, ranging anywhere from hundreds to thousands in size. The map is formed by 8x8 chunks. I am currently using A* but it isn't quite efficient because I may have as many as a ...
791 views

### How does D* pathfinding work?

I would like to understand on a fundamental level the way in which D* pathfinding works. Any code or psuedo-code implementations as well as visualizations would be helpful.
295 views

### Is this a suitable “pathfinding” algorithm for a tower defense game?

Note: I put "pathfinding" in quotes because I'm not sure if it's the proper term for this. My goal is to create a 2D tower defense game with HTML5/JavaScript. It's mostly for learning purposes, so I'...
168 views

### What algorithm can I use to distribute energy between connected nodes?

I'm creating a game where every user has a network of connected nodes that each have a specific amount of energy. The nodes will try to distribute energy evenly amongst themselves. If a node has more ...
1k views

### How can I fill the interior of a closed loop on a tile map?

In my game the player can dynamically modify terrain. The map is stored within a 2D array of prefabricated 3D objects. This is working well for now. The player modifies terrain by selecting what ...
88 views

### Is there an algorithm to move vertices along a planar mesh to give an area more vertex without destroying the shape too much?

Currently, I am playing around with a terrain technique called Vector-Field terrain as created and used for the game Halo Wars. I have successfully recreated the technique. However, I'm having ...
70 views

### Find points inside a closed area

I have a 2D rectangular grid (100x100) with 3 types of cell (Empty, Base and Outline). I need to find cells inside the territory formed by Base and Outline cells. For example, in this scheme: I need ...
83 views

### Numerical differentiation to calculate size of circular buffer

I'm using Allegro 5 to create a software-generated "motion blur" effect for my 2D sprites. I basically just have a boost::circular_buffer of some length which holds "snapshots" of the sprite going ...
642 views

### How to convert a premade mesh into voxels so I can use algorithms such as marching cubes

I have a mesh that was created in a 3D program which is the terrain the player will walk on. I want to allow the terrain to be deformable by the player, but for it to be smooth (not like Minecraft). ...
207 views

### How to calculate a projection of 360° equirectangular slides?

My goal is to have a light source inside of a transparent sphere that has an equirectangular texture to act as a 360°-slide. I want to get the projection on arbitrary objects as a texture image on ...
231 views

### Letting an Pathfinding Algorithm generate movement paths for all possible Connections in a Starsystem-based Universe

First of all I want you to forgive me when I make mistakes in my writing, english isn't my first language, and also: If this is the wrong place to ask, please direct me to the right place then. So, ...
551 views

### Train-like movement in a 2D game

I am developing a 2D game using Cocos2d-X in C++ language. In my game, I need to implement train movement. Here is the image about the output I want to achieve: I tried to do the above moment using ...
3k views

### How do modern game engines handle many shadow casting lights?

This is a very general question, and not aimed at any particular language or graphics API; I am more interested in the theories & algorithms behind the solutions. I'm reasonably familiar with the ...
78 views

### Generating vertices for group of hexagons

I'm working on the map editor of a game, where you can create a grid of hexagons to paint. An example of a grid of radius 6: What I want Once map creation is done, I would like to generate a mesh ...
428 views

### Creating a Simple Puzzle resolution Algorithm

I develop a (really) simple puzzle game that asks you to join a point A to a B (enter/exit) using a ball and mechanisms that you can rotate to give the correct direction to the ball in order to join ...
2k views

### How does transvoxel algorithm work and how can I implement It?

After wasting over three days of researching on DuckDuckGo/Google, trying to understand transvoxel paper and existing implementation, I come here to clarify the subject for me and made it easier for ...
311 views

I've been running into walls for the past week or so on my toy project in UE4. My goal is to draw procedural roads on a procedural landscape (eventually getting to intersections and buildings). The ...