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.
18
votes
4answers
2k views
Find Nearest Object
I have a fairly sizable game engine created, and I'm adding some needed features, such as this, how do I find the nearest object from a list of points?
In this case, I could simply use the ...
10
votes
5answers
834 views
How could you parallelise a 2D boids simulation
How could you program a 2D boids simulation in such a way that it could use processing power from different sources (clusters, gpu).
In the above example, the non-coloured particles move around ...
11
votes
1answer
851 views
How to gain accurate results with Painter's algorithm?
A while ago I asked how to determine when a face is overlapping another. The advice was to use a Z-buffer.
However, I cannot use a Z-buffer in my current project and hence I would like to use the ...
8
votes
2answers
823 views
Render rivers in a grid
I have created a random height map and now i want to create rivers. I've made an algorithm based on a* to make rivers flow from peaks to sea and now i'm in the quest of figuring out an elegant ...
7
votes
1answer
949 views
Finding out which tile a mouse click landed in
I am working on an isometric grid based game and im having an issue trying to link a mouse click from the user to a tile. I have been able to split the problem into 2 parts :
Finding a rectangle ...
1
vote
3answers
132 views
Regulating how much to draw based on how much was drawn last frame
[Edit: I found an answer - see below]
I have a 3D game world on an iPhone (limited graphics speed), and I'm already regulating whether I draw each shape on the screen based on it's size and distance ...
13
votes
1answer
685 views
What are pros and cons of Voronoi shatter?
I have seen some Voronoi shatter videos on Youtube.
What is your experience with it?
What are the pros and cons in time complexity, resource complexity, implementation difficulty...?
Does it ...
8
votes
3answers
887 views
How to find 2D grid cells swept by a moving circle?
I'm making a game based on a 2D grid, with some cells passable and some not. Dynamic objects can move continuously, independent of the grid, but need to collide with impassable cells.
I wrote an ...
2
votes
2answers
617 views
Path finding in grid for objects that occupy more than one tile
In a grid-based game I am working on, I want to add objects that occupy more than one tile of the grid. Are there any algorithms or techniques to find paths for this kind of objects?
10
votes
3answers
639 views
Drawing particles as a smooth blob
I'm new to game/graphics development and I'm playing around with particles (in 2D). I want to draw particles close to each other as a blob, just as liquid/water. I do not want to draw big circles ...
3
votes
1answer
136 views
Coordinate based travel through multi-line path over elapsed time
I have implemented A* Path finding to decide the course of a sprite through multiple waypoints. I have done this for point A to point B locations but am having trouble with multiple waypoints, because ...
3
votes
2answers
553 views
Infinite loop during A* algorithm
The A* algorithm is used by enemies to have a path to the goal. It's working but when sometimes I placed a tower in a grid (randomly) it produces a stack overflow error. The A* algorithm would iterate ...
3
votes
3answers
1k views
Which algorithm used in Advance Wars type turn based games
Has anyone tried to develop, or know of an algorithm such as used in a typical turn based game like Advance Wars, where the number of objects and the number of moves per object may be too large to ...
7
votes
3answers
4k views
Sorting array of points in clockwise order
Is there such an algorithm to sort an array of 2D points in clockwise order?
I'm specifically dealing with right triangle in my case so only 3 points.
However I'm interested in knowing if such an ...
-3
votes
2answers
359 views
Fifteen puzzle modifications algorithm
What would be a good algorithm for the Fifteen puzzle, if the puzzle is slightly modified in that you only have a small number of pieces that should be placed correctly and these correctly placed ...
4
votes
3answers
374 views
Finding closest coordinate of a pre-known set
Let's say I have a large number of conceptual objects of some kind, each of which occupies a pre-known set of points in a Cartesian 3-space.
1) What is the best combination of data structure (for ...
5
votes
3answers
292 views
Generating random values, keep trying till value within bounds are generated
Sorry for the strange topic name, couldn´t think of a good way to describe it.
I´m basically trying to achieve the following:
I'm placing items randomly on the screen, but these items shouldn't be ...
21
votes
1answer
827 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,
...
10
votes
3answers
2k 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 ...
5
votes
2answers
962 views
top down game - checking, drawing enemy's line of sight area with obstacles
Examples of what i'm going to need:
I'm using cocos2d to draw a CCTMXTiledMap, on those tiles i'll have to draw the LOS cone.
How would i test if the player is within that cone, taking obstacles ...
5
votes
1answer
209 views
Splitting an object into two
I'm using Farseer physics engine.
I have a simple rectangle body and would like it to split into two pieces given a starting coordinate (where the bullet enters the object) and ending coordinate ...
7
votes
3answers
494 views
The best algorithm enhancing alpha-beta?
I'm studying AI. My teacher gave us source code of a chess-like game and asked us to enhance it. My exercise is to improve the alpha/beta algorithm implementing in that game. The programmer already ...
2
votes
5answers
451 views
How to model irregular boundary of a 2D map in Game?
I am creating a map in a game, the map contains different countries, my question:
Q. How to model the irregular boundary of each countries? How to do quick country searching if I click on the map ...
17
votes
5answers
860 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 ...
5
votes
3answers
197 views
Preventing ties
I'm working on a simple game to rate a users' preference among several styles. There are C classes, and the game consists of R rounds of comparison. At each round, the user is presented a ...
6
votes
3answers
887 views
Pathfinding with multiple random paths in a Tower Defense game
I thought about random pathfinding for my Tower Defense game. A* would not work for my puposes, because I specifically need random pathfinding.
Imagine a map with routes, a starting point and a ...
2
votes
1answer
823 views
Which is faster: raycasting or shadowcasting?
I'm looking to create an FoV implementation and I was wondering which algorithm is faster - raycasting or shadowcasting?
17
votes
6answers
5k 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 ...
3
votes
3answers
577 views
Algorithm for making sets in a Rummikub game
I'm developing an Okey game (a Turkish version of Rummikub/Rummy). In it, each players has a bunch of tiles. Tiles have a colour and a number, like playing cards. Now, the player needs to make sets of ...
2
votes
1answer
1k views
C# Pathing algorithm for moving a object from point(X, Y) to point(X, Y)
Given a object which may move forward, backward, left and right at a given X,Y point. How to efficiently direct the object to a X,Y point using the given movement mechanics in the most efficient and ...
3
votes
1answer
825 views
(real) 3d map rendering in wpf without an engine - how to handle the map data?
I'm just doing some research before embarking on rendering a 3D map inside a wpf app. I've never delved into 3D before, and hence the question..
I have map data (in several formats, and many files) ...
11
votes
3answers
3k views
Beat detection and FFT
I am working on a platformer game which includes music with beat detection. I am currently detecting beats by checking for when the current amplitude exceeds a historical sample. This doesn't work ...
3
votes
2answers
1k views
polygon triangulation algorithm
I need to triangulated a polygon for rendering in opengl es on android ( no glu triangulation available)
Is there an already known algorithm for this? The polygon can be convex or concave (with no ...
6
votes
2answers
458 views
Calculating and detecting curves
How can I detect the 'steepness' of a curve? For example, if the user swipes their finger across the screen in a curve, what's the best way of detecting whether the curve is almost a semi-circle, or ...
3
votes
1answer
921 views
Significance of Bresenhams Line of Sight algorithm
What is the significance of Bresenhams Line of Sight algorithm in chasing and evading in games?
As far as i know and implemented this algorithm calulates the straight line between two given points. ...
10
votes
2answers
2k views
How to implement an experience system?
I'm currently writing a small game that is based on earning experiences when killing enemies. As usual, each level requires more experience gain than the level before, and on higher levels killing ...
2
votes
2answers
147 views
Resources on expected behaviour when manipulating 3D objects with the mouse
In my animation editor, I have a 3D gizmo that sits on the origin of a bone; the user drags the mesh around to rotate the bone.
I've found that translating the 2D movements of the mouse into sensible ...
13
votes
2answers
569 views
AI to move custom-shaped spaceships (shape affecting movement behaviour)
I'm designing a networked turn based 3D-6DOF space fleet combat strategy game which relies heavily on ship customization. Let me explain the game a bit, since you need to know a bit about it to set ...
2
votes
3answers
4k views
best way to compute vertex normals from a Triangle's list
hi
i'm a complete newbie in computergraphics so sorry if it's a stupid answer.
i'm trying to make a simple 3d engine from scratch, more for educational purpose than for real use.
for now i compute ...
1
vote
3answers
356 views
Given a start and end point, how can I constrain the end point so the resulting line segment is horizontal, vertical, or 45 degrees?
I have a grid of letters. The player clicks on a letter and drags out a selection. Using Bresenham's Algorithm I can create a line of highlighted letters representing the player's selection.
...
8
votes
1answer
780 views
Triangulation A* (TA*) pathfinding algorithm
I need help understanding the Triangle A* (TA*) algorithm that is described by Demyen in his paper Efficient Triangulation-Based Pathfinding, on pages 76-81.
He describes how to adapt the regular A* ...
1
vote
2answers
486 views
XNA: How to make the Vaus Spacecraft move left and right on directional keys pressed?
I'm currently learning XNA per suggestion from this question's accepted answer:
Where to start writing games, any tutorials or the like?
I have then installed everything to get ready to work with XNA ...
3
votes
1answer
530 views
Breakout clone, how to handle/design for collision detection/physics between objects?
I'm working on a breakout clone, and I wish to create some realistic physics effects for collision - angles on the paddle should allow the ball to bounce, as well as doing curve balls etc. I could use ...
3
votes
3answers
1k views
Collision detection of convex shapes on voxel terrain
I have some standard convex shapes (cubes, capsules) on a voxel terrain. It is very easy to detect single vertex collisions. However, it becomes computationally expensive when many vertices are ...
0
votes
1answer
1k views
Ruby: implementing alpha-beta pruning for tic-tac-toe
So, alpha-beta pruning seems to be the most efficient algorithm out there aside from hard coding (for tic tac toe). However, I'm having problems converting the algorithm from the C++ example given in ...
6
votes
3answers
984 views
How can I get a velocity vector for an object moving in a circle?
I am simply trying to make an object move in a circle around a point. Let's say I have an object with a position vector going from that point to the object, and also the angle of the object with the x ...
8
votes
5answers
921 views
Why is Reinforcement Learning so rarely used in pathfinding?
The venerable shortest-path graph theoretic algorithm A* and subsequent improvements (e.g., Hierarchical Annotated A*) is clearly the technique of choice for pathfinding in game development.
...
6
votes
1answer
355 views
Building 2D Assets for a Game Targeting Multiple Framerates
To make a real-world example, lets assume I want to build an animated sprite for an explosion. The duration of the animation should last ~1 second, and we'll say exactly one second to make the math a ...
3
votes
1answer
1k views
How Can I Improve This Card-Game AI?
Let me get this out there before anything else: this is a learning exercise for me. I am not a game developer by trade or hobby (at least, not seriously) and am purely delving into some AI- and ...
3
votes
2answers
533 views
Factors to consider when building an algorithm for gun recoil
What would be a good algorithm for calculating the recoil of a shooting guns cross-hairs?
What I've got now, is something like this:
Define min/max recoil based on weapon size
Generate random ...
