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

940 questions
170 views

### Redistributing sprites in procedural generation according to player movement

I am making space arcade with procedurally generated background consisted of nebulas and stars sprites, which spawn on Awake() in certain borders around player. Mobile phones have limited capacity ...
83 views

### How can I generate random levels like in “Square it!” game?

In this game, you have a 2d field with some free squares and two colored squares which you can move but only together (they'll move only if the spot is still "free"). And you have to fill whole free ...
94 views

### Wall collision and sweep and prune algorithm

I am documenting myself on collision detection algorithms. If I understand well, "sweep and prune" algorithm using frame coherence is powerful to detect object vs object collisions (almost as 0(n)). ...
57 views

### Generate random number biased to an input value

I've got enemies with a difficulty rating from 0 to 1. I want to generate a random reward that tends to increase as the difficulty rating rises, but still be possible to have a value anywhere in the ...
220 views

### Has there been any research done on ideal values for loot drop tables?

I doubt many people want to grind for an item that has a 0.00001% chance to drop from a boss that takes 30 minutes to kill. I'd imagine there are certain factors that play into how rare an item should ...
44 views

### dcitonary memory efficiency - unity

I'm trying to implement a word validator in unity for a word game, but every implementation I've tried so far has used too much memory. The least expensive attempt so far with adequate performance was ...
93 views

### Dynamic Tilemap size changer

I have started coding this project using the library SFML a few months ago. I have implemented a random map generation everytime I load the game thanks to Biome and the Perlin noise Algorithm. I ...
204 views

### Algorithm for fitting geometrical 2d shapes like in the android game Six! (or Tetris)?

In the game Six!, there's a perfectly rectangular tower of geometrical 2d shapes, that you destroy on tap to reach the ground with your player. The easy way would be to design the levels by hand. ...
87 views

### Voronoi graph - traversing from vertex to vertex

I'm working on a Unity Project in C# I've built a 3D Voronoi Diagram using the csDelaunay library from PouletFrit and using the X and Y values from a 2D diagram to instead setup some Vector3's with ...
244 views

### Scan for water in 2D procedural terrain locale

In my 2D-sideview game, I have certain biomes, each one having a unique sea level, or water height, (depending on the humidity of the biome). The terrain is composed of stacks of blocks, each being a ...
51 views

### How to split a group of tiles in a grid into separate groups if a break occurs between tiles?

I have a grid where objects can be placed down by the player. Each object that gets placed down is added to a dictionary where the key is the grid position. Each object that gets placed down either ...
345 views

### How to make a noise gradient?

Introduction: I am working on a heat map made by Perlin Noise with the next result: (Figure 1) ...
45 views

### Given N objects in my 3d world, how to set camera zoom to have all framed?

I have N objects and I've done a routine to get the overall objects : min_x, max_x min_y, max_y min_z, max_z and, i have an ...
260 views

### How to check if a pipe placed on a fixed grid size is connected correctly to a neighbor pipe?

Am looking for a solution (algorithm) to check if an object in a neighbor tile can be connected (i.e transfer power). Best example I could come up with to make this more clear, is pipes. I am using ...
315 views

### How to “place” object in a 3d world without overlapping them ?

I would like to place object in a 3d world "like minecraft player can do". What I'm trying to do is to allow the user to place objects, without overlapping them (like in minecraft you can do). So ...
84 views

### How to calculate a moving bonus limit

I'm trying to set a realistic limit on the number of bonus objects that randomly show up during a wave of enemies in my game. With each new wave I increase the number of enemies. During each wave I ...
89 views

### Some example of basic algorithms and frameworks used in game creation [closed]

I understand this sounds like a broad topic, I'm asked to have those skill from one of my applied job description. The thing is that i have been with Unity3d for 2~3 years, but I'm not really sure ...
80 views

### Algorithms on Random Level Generation with Predefined Objects and Constraints

Let's say I'm developing a game where a city is generated and buildings are placed in a random manner. Methods to generate the roads are easy to find, it is akin to creating a maze but I can't think ...
59 views

### Up / down powerbar computation at server side

I aplolgize if my question is unclear, because I don't know how to formulate the problem. I have a player that can do damage with a weapon. The weapon has a min and max damage. Holding the space bar ...
184 views

### How to calculate Camera “correct” position and distance to Frame all my Scene?

Consider I have N dynamic points on my Scene, I would like to "frame" all them, with my Camera. How can i calculate (at runtime) Vector3 Position to correctly frame all my scene ? This is my idea: ...
113 views

### How do I find out if this particular puzzle can still be solved?

A while ago, I made a simple game that involved swapping birds to combine them and release them to create points. The idea is that eventually, the birds would get stuck and your game is over, but I ...
129 views

### How do I detect a given sprite's bounds automatically using Java?

Background I have the following png file that contains the player sprite. As with any png file, the non-colored pixels are ...
449 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 ...
77 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: ...
104 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): ...
144 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 ...
326 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 ...
59 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. ...
250 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, ...
39 views

### Fixed time for game to model physics

I am a newbie game developer. I need to develop a simple 2D game, it is really simple. I have a Human model that should jump every n seconds. User sets different several options in settings. The ...
160 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 ...
246 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 ...
177 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 ...
657 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 ...
242 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 ...
72 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 ...
173 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, ...
581 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 ...
50 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 ...
534 views

...
284 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 ...
133 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 ...
282 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 ...
170 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? ...
26 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'...