Tagged Questions

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.

10k views

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 ...
7k views

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.
4k views

How can I get textures on edge of walls like in Super Metroid and Aquaria?

Games like Super Metroid and Aquaria present the terrain with the other facing parts having rocks and stuff while deeper behind them (i.e. underground) there's different detail or just black. I ...
25k views

How to generate random level from a seed? [closed]

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 ...
20k views

What path finding algorithms are there? [closed]

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?
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 ...
24k views

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.
5k views

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 ...
2k views

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 ...
7k views

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 ...
4k views

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 ...
4k views

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 ...
3k views

Is there an algorithm to detect the “mainland” on a 2D map?

On this map, the "mainland" is all the land that can be connected to the center of the map in the four cardinal directions (north, south, east, west -- not diagonally). I would like to detect the ...
19k views

Understanding Perlin Noise

I'm toying with Perlin Noise after some work with Diamond Square. I followed the implementation by Hugo Elias that basically, makes a series of functions with x,y as input to throw each coordinate ...
20k views

How does Navigation Mesh path-finding work?

I want to understand how navmeshes work, how to implement them and why it is better than other types of pathing systems.
3k views

What are your favourite game-specific coding gems? [closed]

I'll start off with John Carmack's the Fast Inverse Square Root in Quake III: float Q_rsqrt(float number) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = ...
17k views

Algorithm for generating a 2d maze

What algorithm have you used in the past to generate a simple 2d maze?
16k views

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 ...
2k views

How do I avoid “too” lucky / unlucky streaks in random number generation?

I'm currently dealing with a multiplayer combat system where the damage dealt by the players is always multiplied by a random factor between 0.8 and 1.2. In theory, a truly random RNG may eventually ...
1k views

How do I produce “enjoyably” random, as opposed to pseudo-random?

I'm making a game which presents a number of different kinds of puzzles in sequence. I choose each puzzle with a pseudorandom number. For each puzzle, there are a number of variations. I choose the ...
4k views

Methods for generating a map

I'm looking to create a simple, "randomly" generated map for a small game. The game consists of a top-down view of a world, with land-mass and ocean areas. Think of a simple outline map of the world ...
2k views

Determine position of a rotated element in Tetris

Tetris-Tiles are stored as a 4x4 boolean matrix. Each rotation step has it's own matrix, the representation of the T-Block would look like this: [ 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, ...
3k views

Optimizing gravity calculations

I've got a bunch of objects of varying size and velocity which gravitate towards each other. On every update, I have to go over every object and add up the forces due to gravity of every other object. ...
4k views

Algorithm to modify a color to make it less similar than background

I'm creating a demo of 20 balls bouncing each other, with a background filled with a solid color. Color for each ball is chosen randomly with randint(0, 255) for each R, G, B tuple component. Problem ...
1k views

Spell casting - How to optimize damage per second

Imagine we have a wizard that knows a few spells. Each spell has 3 attributes: Damage, cool down time, and a cast time. Pretty standard RPG stuff. Cooldown time: the amount of time (t) it takes ...
1k views

Algorithm for spreading labels in a visually appealing and intuitive way

Short version Is there a design pattern for distributing vehicle labels in a non-overlapping fashion, placing them as close as possible to the vehicle they refer to? If not, is any of the method I ...
6k views

Quick 2D sight area calculation algorithm?

I have a matrix of tiles, on some of that tiles there are objects. I want to calculate which tiles are visible to player, and which are not, and I need to do it quite efficiently (so it would compute ...
12k views

Simple noise generation

I'm looking to generate noise that looks like this: (images courtesy of Understanding Perlin Noise) I'm basically looking for noise with lots of small "ripples". The following is undesirable: ...
6k views

How to convert mouse coordinates to isometric indexes?

I draw isometric map with tile 64x32: const Offset = 160; int X, Y; for (int a=0; a < 6; a++) for (int b=0; b < 6; b++) { X = a * 32 - b * 32 + Offset; Y = a * 16 + b * 16; ...
724 views

Finding direction of travel in a world with wrapped edges

I need to find the shortest distance direction from one point in my 2D world to another point where the edges are wrapped (like asteroids etc). I know how to find the shortest distance but am ...
8k views

Procedural river or road generation for infinite terrain

I should say paths, not roads as I'm thinking more medieval-like. Also, not looking for realism. The answer I'm looking for will be to fit into the mold I describe rather than realism. I am looking ...
12k views

What is the simplest method to generate smooth terrain for a 2d game?

What is the simplest method to generate smooth terrain for a 2d game like "Moon Buggy" or "Route 960"? I got an answer at stackoverflow.com about generate an array of random heights and blur them ...
10k views

Quad tree vs Grid based collision detection

I'm making a 4 player co-op r-type game, and I'm about to implement the collision detection code. I've read a lot of articles and stuff about how to handle collision detection, but I'm having a hard ...
3k views

How can I generate floating land masses for a Minecraft-like engine?

I am creating a Minecraft-like engine in XNA. What I want to do is create floating islands similar to the one shown in this video: http://www.youtube.com/watch?v=gqHVOEPQK5g&feature=related ...
3k views

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 ...
643 views

How can I maintain a rectangular formation when units are added or removed?

I've got bots in a rectangular formation with rows and columns. A problem arises when a bot is added or removed from the formation. When this happens, the bots have to rearrange themselves so that the ...
27k views

How can I create a random “world” in a tile engine?

I am designing a game that is working on a classic tile engine, but whose world is generated randomly. Are there existing games or algorithms that do this? The procedural generation algorithms I have ...
2k views

Matching a chunk of procedurally generated world to a chunk of other world

Have you read The Chronicles of Amber by Roger Zelazny? Imagine yourself playing in 3rd person MMO game. You spawn in the world and start to wander around. After some time, when you think, that you'...
1k views

Why is my sky color calculation in Mathematica incorrect?

I'm trying to implement an algorithm to calculate sky color based on this paper (Perez' model). Before I start programming the shader I wanted to test the concept in Mathematica. There are already ...
2k views

Does Big O really matter?

In academia worst case Big O is taught over everything else. Compared to space complexity, normal case analysis, simplicity over complexity, etc. In particular to game programming and industry, what ...
8k views

When should vector/list be used?

I can understand when to use lists, but I don't understand when it is better to use vectors than using lists in video games: when it is better to have fast random access ? (And I understand why it's ...
642 views

How can I detect connected (but logically distinct) bodies of water in a 2D map?

I have a 2D hexagonal grid map. Each hex cell has a height value used to determine if it's water or ocean. I'm trying to think of a good way to determine and label bodies of water. Oceans and inland ...
189 views

Flowing GPU compute water

I have a civil engineering background and perform hydraulic and hydrologic analysis' regularly. They sell degrees for that sort of thing, but it's really not rocket science. I recently got it in my ...
18k views

How to implement A.I. for checkers/draughts?

I saw this checkers game and I wondered how the A.I. was implemented. How should I implement an A.I. for checkers (draughts, dama, dame)? Are there any known algorithms? Very thnaks full to all. I ...
6k views

Dynamic pathing algorithm for tower defense game

I'm making a Tower Defense and I need a good pathing algorithm for it. I have thought about Dijkstra but I need one that can be dynamic; it must be able to update itself when one edge is removed or ...
8k views

Real Time Dynamic Pathfinding?

I'm currently doing some pathfinding research and my simulation is the following: I have a 3d scene with a start and end point represented, I'm capable of creating navigational meshes, waypoints and ...
3k views

How do history generation algorithms work?

I heard of the game Dwarf Fortress, but only now one of the people I follow on Youtube made a commentary on it... I was more than surprised when I noticed how Dwarf Fortress actually generates a ...
11k views

Calculating velocity needed to hit target in parabolic arc

If I have a point which I want to hit at the end or during a parabolic arc, how would I calculate the needed x and y velocity?