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.

learn more… | top users | synonyms

2
votes
1answer
998 views

What is an efficient packing algorithm for packing rectangles into a polygon?

I need to put as many rectangle of same size as possible inside a polygon. The algorithm can put rectangles in different orientation(angle). But they cannot overlap. This is image is an example of the ...
4
votes
2answers
812 views

Repairing back-facing triangles without user input

My 3D application works with user-imported 3D models. Frequently, those models have a few vertices facing into the wrong direction. (For example, there is a 3D roof and a few triangles of that roof ...
1
vote
2answers
2k views

How does flocking algorithm work?

I read and understand the basic of flocking algorithm. Basically, we need to have 3 behaviors: 1. Cohesion 2. Separation 3. Alignment From my understanding, it's like a state machine. Every time we ...
2
votes
1answer
248 views

Constrained/penalized distance function

Assume a character is located on a n by n grid and has to reach a certain entry on that grid. Its current position is (x1,y1). Also on the same grid is an enemy with coordinates (x2,y2). Each step ...
11
votes
4answers
3k views

Calculate random points (pixel) within a circle (image)

I have an image that contains a circles at a specific location, and of a specific diameter. What I need to do is to be able to calculate random points within the circle, and then manipulate the pixels ...
6
votes
3answers
3k views

How do I shuffle cards for a card game?

I am trying to develop an card game for Android Can anyone suggest me how to write code for effectively shuffling the playing cards?
6
votes
4answers
2k views

Smoothing found path on grid

I implemented several approaches such as A* and Potential fields for my tower defense game. But I want smooth paths, first I tried to find path on very small grid ( 5x5 pixels per tile) but it is ...
1
vote
3answers
1k views

How do you blend multiple colors in HSV (polar) color-space?

In RGB color space, you can do a weighted multiple-color blend by just doing: Start with R = G = B = 0. Then we perform a blend at index i using a set of colors C, and a set of normalized weights w ...
1
vote
2answers
251 views

How to track and find entities within radius in realtime game?

What is best approach to implement tracking in real time for, say, 1000 npcs? Every frame update simple a square grid (remove or insert into linked list) and every time check in square radius? I tried ...
6
votes
1answer
278 views

How to highlight non-rectangular hotspots?

So my question is highly related to Creating non-rectangular hotspots and detecting clicks. Yet again, I've irregular hot-spots (think the game Risk). So basically, we can detect clicks on these ...
12
votes
4answers
2k views

How do I determine the draw order in an isometric view flash game?

This is for a flash game, with isometric view. I need to know how to sort object so that there is no need for z-buffer checking when drawing. This might seem easy but there is another restriction, a ...
4
votes
1answer
107 views

Best approach to get clicked objects from a display list (2D)

I'm implementing a display list to manage my visuals on screen. I want to know which object is clicked. My objects already have z-order variable. With my current knowledge (almost nothing) the only ...
4
votes
3answers
533 views

Creating the nodes for path finding during run time - more like path making and more

I'm making my 1st game. I'm using javascript as I currently want to learn to make games without needing to learn another language but this is more of a general game dev question. It's a 2d turn-based ...
1
vote
1answer
230 views

A* and Space partitioning

I'm planning on implementing A* in my game for pathfinding, I understand the basics of how the algorithm works but I was wondering, other than finding the start and end nodes Are there any benefits to ...
8
votes
2answers
1k views

Physics engine that can handle multiple attractors?

I'm putting together a game that will be played mostly with three dimensional gravity. By that I mean multiple planets/stars/moons behaving realistically, and path plotting and path prediction in the ...
6
votes
2answers
2k views

Bounding boxes in octrees

I've seen that octrees are often used for things like frustum culling and collision detection in 3D. But I'm just not sure how the algorithm works at all. Surely the whole principle of the octree ...
2
votes
3answers
759 views

basic Theory that we need to know before start learning game programming [closed]

Came from Java (and fairly C++) and I am very confident in my programming skill Now I'm about to move to something more interesting, game programming The thing is as I am new to this, I need to know ...
11
votes
1answer
3k views

Giving a Bomberman AI intelligent bomb placement

I'm trying to implement an AI algorithm for Bomberman. Currently I have a working but not very smart rudimentary implementation (the current AI is overzealous in placing bombs). This is the first AI ...
2
votes
3answers
842 views

Stuck in an infinite recursion in Minesweeper

I am trying to build a simple minesweeper game. The game gets stuck in an infinite recursion whenever a user clicks on a tile which is not a mine... I have used the following function code for the ...
1
vote
0answers
119 views

Fixed time step with Akihabara

How could I implement fixed time step with Akihabara framework? I would like my avatar to move by fixed distances of one block as in Supaplex.
9
votes
5answers
643 views

Increasing the probability for similar tiles to generate next to each other

I'm working on a tile map system, which insofar looks like this (green is grass, air is white, stone is grey, and blue is water): It uses a simple random number generator so that there's a 45% ...
3
votes
2answers
1k views

Why would someone chose midpoint displacement over perlin noise for 3D terrain generation?

I myself am creating a terrain generation algorithm and would be interested in knowing why others have chosen midpoint displacement over perlin noise. Minecraft is an example where midpoint ...
3
votes
2answers
2k views

Find a line that connects the outer most points in a set of points

Does anyone know an efficient algorithm to find the edge of a point cloud? Hopefully the picture in the link can illustrate what I mean. It's a plus if the algorithm can handle point clouds that are ...
1
vote
1answer
2k views

How does Terrain following work on height map?

I'm writing a 3D world game which consists of a terrain map (generated by brownian motion algorithm) and a simple avatar. My goal is to make the avatar move smoothly between points of different ...
6
votes
4answers
2k views

Is there a way to increase the collision check efficiency of a system of n objects?

I'm making a game that consists of many onscreen objects, one of which is the player. I need to know which objects are colliding every iteration. I made something like this: for (o in objects) { ...
5
votes
1answer
262 views

In the GJK algorithm, when is a point ever closer to the origin than a line?

The GJK algorithm depends upon a function in its loop that updates the simplex and search direction for the next iteration (which is often called something like DoSimplex() or ProcessSimplex()). In ...
5
votes
2answers
1k views

Algorithm for random flight of a fly

I'm new to game development. What is a good algorithm to model the random flight of a fly? I've been looking at path-finding algorithms, but they don't give any interesting random behaviour.
5
votes
3answers
225 views

A* : Partial recalculation when one node *changes*

I have implemented an A* library. Its most interesting feature is that it is "interruptible"; for example, you can stop the calculation loop on a game frame, and resume it later on the following ...
3
votes
2answers
441 views

Programmatically drawing a “pencil” line or curve

If you look closely (scan it on a computer and zoon in) at a carbon pencil line you can see that there are differing shades of gray. I tried looking on the Internet for any kind of algorithm or ...
0
votes
1answer
424 views

throw a 2D ball facing the target to simulate a 3D like effect

How would you update the state of a 2D object that is thrown forward(with an arc) facing a target to simulate a 3D(depth) like effect? var ball; //2D ball from a sprite sheet ball.x = 0; ball.y = 0; ...
0
votes
2answers
305 views

Partial recalculation of visibility on a 2D uniform grid

Problem Imagine that we have a 2D uniform grid of dimensions N x N. For this grid we have also pre-computed a visibility look-up table, e.g. with DDA, which answers the boolean query is cell X visible ...
1
vote
2answers
7k views

How can i use A star pathfinding algorithm

How would i implement an A star algorithm for a game that i'm making on the android in java? i'm looking for a pre-made A star API in java with classes and methods to call. i don't want to have to ...
6
votes
1answer
387 views

How do I calculate market share in an economic simulation?

I want to make a game in which the players create different products (supply), and I give them a certain finite number of customers (demand). Players can choose the price and quality of their products ...
4
votes
2answers
204 views

Load state / continue game based on user input

I'm working on a rather simple 2D game, with a pretty small set of values that will need to be preserved for a user to pick up where they left off last time they played. Rather than saving/loading ...
0
votes
1answer
287 views

Resizing a dynamically resizable widget with a fixed aspect ratio?

I've been trying to figure this out for hours. It is a bit tricky to explain but I'll try to explain it. I'm making a game where I have a Window with 3 panels in it. The 3 panels must always be ...
2
votes
2answers
1k views

Sparse Voxel Octrees which parts on GPU or CPU?

I'm currently doing research into building my own voxel engine and found a lot of articles mentioning SVOs as the best mechanism. I just wanted to know that I understood the algorithm correctly, ...
3
votes
3answers
312 views

Algorithm for generating levels for shooting game

I have a shooting game made in Java. It's based on time, i.e you have to shoot the objects before the time runs out. Everything is working fine, except that I'm trying to implement an algorithm to ...
0
votes
1answer
838 views

Large Blob of landmass in Minecraft Terrain Engine in XNA

I am creating a Minecraft Terrain engine in XNA, and want to create a large blob/cluster of blocks, in a random sort of blob thing, shaped somewhat like the stuff under the Volume Rendering heading on ...
0
votes
1answer
442 views

Best Algorithm for attacking in the Risk Game

I apologize in advance for my English.I'll try to explain my problem. I am working on new version of the Risk game. I want to change the attacking algorithm to make it more similar to real life war. ...
7
votes
3answers
1k views

Generating random Pools or lakes

I have implemented functions that can draw any polygonal shape, however I have been unable to generate a smooth shape that mimics the rounded edges of a lake. I tried generating two circles and ...
10
votes
1answer
973 views

2D helicopter game, how to create corridor walls?

I'm looking into adapting the classic "helicopter" game (i.e. http://www.addictinggames.com/helicopter.html), but I haven't yet figured out how to create the walls-generation engine. Any pointers ...
27
votes
4answers
2k 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 ...
8
votes
4answers
988 views

What kind of hardware would be required to render an Earth sized minecraft like map?

I have been thinking about this problem. Is it possible with current technology to create a 1:1 replica of the earth in voxel based game? What's the best data structure to store this giant map? Which ...
8
votes
2answers
725 views

Function for sun movement?

So, given a sun sprite set at the horizon (x = 0, y = worldheight/2) I'm trying to devise a function to make the sun rise, then fall. The best way to do this would be the sin function, but I have no ...
16
votes
5answers
4k 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 ...
2
votes
2answers
766 views

Is there a known most efficient version of A* search algorithm?

Is there a known 'most efficient' version of the A* search algorithm? I know some people write papers on the most efficient way to compute common operations, has this been done for A*?
6
votes
3answers
5k views

Efficient Tile-based collision detection for a lot of squares?

currently I am working on my own take of a tile-based game (think Terraria, but less fantastical (I think that's a word? Sorry if it isn't)). Anyway, I currently have collision detection working ...
5
votes
1answer
989 views

Documentation on 2D space partitioning

I am looking for documentation that explains the different kinds of (well the major ones anyway) 2D space partitioning algorithms & data structures. Any pointers besides 'Google it and sift ...
3
votes
1answer
797 views

How does double dispatch help collision detection?

There are a few specific techniques to test if one object has hit another object in a game. One of them is called "double dispatch." Can someone explain what double dispatch is, and how it can be used ...
16
votes
3answers
2k 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 ...