Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
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 ...
1
vote
1answer
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: ...
1
vote
0answers
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 (...
17
votes
3answers
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): ...
0
votes
2answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
30
votes
2answers
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. ...
1
vote
2answers
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, ...
2
votes
1answer
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 ...
4
votes
2answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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, ...
4
votes
3answers
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 ...
1
vote
1answer
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 ...
0
votes
2answers
886 views
1
vote
0answers
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 ...
2
votes
2answers
154 views

Add action to GameObject

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 ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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? ...
1
vote
0answers
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'...
5
votes
3answers
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
6
votes
2answers
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 ...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
7
votes
3answers
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 ...
2
votes
1answer
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.
1
vote
1answer
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'...
3
votes
2answers
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 ...
5
votes
2answers
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 ...
7
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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). ...
1
vote
1answer
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 ...
1
vote
0answers
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, ...
6
votes
1answer
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 ...
4
votes
3answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
3
votes
2answers
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 ...
3
votes
3answers
311 views

Drawing roads on heightmaps

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 ...
4
votes
1answer
157 views

Convert 2d generated level to graph or analyze

Do you have any idea how to extract graph data from this type of procedurally generated level? Well, actually we need to analyze only top level (gray). Background (black) does not matter. What I am ...
0
votes
1answer
141 views

A* Implementation broken?

I tried implementing Wikipedia's version of the A* pathfinding algorithm, but when I run it in Unity the object which the script is applied to does nothing and Unity ends up taking 15% of my CPU. I ...