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.

1171 questions
82
votes
5 answers

Procedural... house with rooms generator

I've been looking at some algorithms and articles about procedurally generating a dungeon. The problem is, I'm trying to generate a house with rooms, and they don't seem to fit my requirements. For one, dungeons have corridors, where houses have…
pek
  • 2,827
  • 1
  • 27
  • 31
69
votes
7 answers

How does A* pathfinding work?

I would like to understand on a fundamental level the way in which A* pathfinding works. Any code or psuedo-code implementations as well as visualizations would be helpful.
Daniel X Moore
  • 1,785
  • 1
  • 20
  • 24
63
votes
9 answers

Texture packing algorithm

What is a good texture packing algorithm? Technically, bin packing is NP-hard , so a heuristic is what I'm really after.
deft_code
  • 7,652
  • 5
  • 40
  • 55
56
votes
1 answer

How do Raymarch shaders work?

I have been looking at shaders found here shadertoy.com and most of the cool ones have noise and raymarch in common. I do not understand the source code at all but I really want to. How do these shaders work and how does the raymarch algorithm work?…
jmasterx
  • 2,099
  • 3
  • 26
  • 44
52
votes
11 answers

What path finding algorithms are there?

I'd like to read up on path finding algorithms. Is there a primer available or any material or tutorials on the Internet that would be a good start for me?
Spoike
  • 1,461
  • 2
  • 15
  • 21
49
votes
3 answers

How to generate random level from a seed?

How would I go about using a random seed to generate a game level? The same seed should always generate the exact same level. For this example it would be a Worms style level. So each level would have a theme (grasslands, snow etc), base terrain,…
Adam Harte
  • 2,454
  • 3
  • 24
  • 32
49
votes
3 answers

How can I generate Worms-style terrain?

I'm working on a Worms-styled game and want to generate some terrain procedurally. I've previously done a lot of terrain generation using perlin noise, and this is what I started out using for this game. The only problem with it is that it's too…
Xeon06
  • 1,152
  • 2
  • 12
  • 13
40
votes
9 answers

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 straight line. For instance, a result of 90% would mean…
user3637362
  • 549
  • 1
  • 5
  • 8
39
votes
5 answers

In 2D, how do I efficiently find the nearest object to a point?

I have a sizable game engine and I'd like a feature for finding the nearest of a list of points. I could simply use the Pythagorean theorem to find each distance and choose the minimum one, but that requires iterating through all of them. I also…
ultifinitus
  • 1,922
  • 1
  • 16
  • 19
37
votes
5 answers

How to generate caves that resemble those of Minecraft?

I've been working on a 3D procedural world for a while now and am wanting to start adding cave systems. I'm currently using 2D/3D Perlin Noise for the terrain generation in combination with Marching Cubes for smoother terrain. I'm just getting…
Mythics
  • 1,486
  • 2
  • 21
  • 32
34
votes
12 answers

How can I make A* finish faster when the destination is impassable?

I am making a simple tile-based 2D game, which uses the A* ("A star") pathfinding algorithm. I've got all working right, but I have a performance problem with the search. Simply put, when I click an impassable tile, the algorithm apparently goes…
user2499946
  • 559
  • 2
  • 5
  • 9
33
votes
2 answers

How can I generate a lightning bolt effect?

Is there an algorithm to generate a lightning bolt? I would like an algorithm that generates a list of segment or point objects specifying where the bolt will land. The method would need a start point parameter, along with an endpoint. The bolt…
Geoffroi
  • 495
  • 1
  • 5
  • 8
33
votes
7 answers

Elegant way to simulate large amounts of entities within a game world

Assume you have a game in which there are many (many many) entities serving some functions, not all of which are constantly needed or need to be considered in every frame. The concrete problem I am working on in which this issue is present is a…
Marc Müller
  • 1,007
  • 11
  • 17
32
votes
2 answers

Random/Procedural vs. Previously Made Level Generation

What the advantages/disadvantages of using random/procedural generation vs. pre-made levels? There seems to be few that I can think of, other than the fact that items may be a problem to distribute in randomly generated terrain, and that the…
Pip
  • 1,454
  • 1
  • 16
  • 32
32
votes
5 answers

How can I generate Sudoku puzzles?

I'm trying to make a Sudoku puzzle generator. It's a lot harder than I expected and the more I get into it, the harder it gets! My current approach is to split the problem into 2 steps: Generate a complete (solved) Sudoku puzzle. Remove numbers…
user223150
  • 421
  • 1
  • 5
  • 3
1
2 3
…
78 79