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

6
votes
2answers
504 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 ...
5
votes
1answer
1k 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. ...
12
votes
2answers
4k 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
158 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 ...
14
votes
3answers
867 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 ...
3
votes
3answers
7k 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
425 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. ...
10
votes
1answer
1k 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
667 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
646 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
2k 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
1k 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
1k 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
383 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
2k 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 ...
4
votes
2answers
695 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 ...
4
votes
2answers
2k views

Bitmap font rendering, UV generation and vertex placement [closed]

I am generating a bitmap, however, I am not sure on how to render the UV's and placement. I had a thread like this once before, but it was too loosely worded as to what I was looking to do. What I am ...
4
votes
2answers
2k views

Control diamond square algorithm to generate islands/pangea

I generated a height map with the diamond square algorithm. The thing is i do not manage to create islands, this is, restrict the height other than water level range to a certain value in the center ...
5
votes
1answer
1k views

Algorithm to make groups of units

In Age of Mythology and some other strategy games, when you select multiple units and order them to move to some place, they make a "group" when they reach the desired location: I have a Vector ...
3
votes
2answers
263 views

Algo for narrowing cavern

I'm in a bit of crunch time and I find myself spending way too much time tinkering with an algo, so I would like some help. In the game I am working on, there are some old-style, pixelated minigames. ...
8
votes
2answers
2k views

Creating A Board Game AI

I want to code a board game that name is Okey and mostly popular in Turkey. http://en.wikipedia.org/wiki/Okey But i have got some problems about AI. Firslty let me explain the game.. The game is ...
6
votes
4answers
569 views

Creating non-rectangular hotspots and detecting clicks

Say for a game with irregular hotspots (say Risk, or a strategy game like Paradox's Hearts of Iron or Crusader Kings), how do you Define a non-rectangular hotspot of irregular shape (much like a ...
16
votes
1answer
8k 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 ...
10
votes
3answers
2k views

Algorithm for determining random events

I'm struggling with coming up with an elegant solution to generating random events in the game that I'm working on. Say there are 4 classes of events that can happen, with varying events in those ...
7
votes
2answers
545 views

Making a symbol appear on any colour

I'm developing an RPG/roguelike-style game. Instead of having maps like: ......... ......... ....@.... ...h..... Oh look, a dwarf. I was having solid background tiles, So sort of a tile based RPG ...
10
votes
3answers
1k views

Reduce the number of edges of a graph, keeping it connected

I'm designing a game with random generated dungeons. I'd like to view this as a connected, undirected graph in which nodes are rooms and edges are doors or corridors. Then I choose a "side" node as ...
6
votes
6answers
686 views

Are there important cases when one needs to know how to program sort algorithms in game programming?

Well I already read a little about sorting algorithms on wikipedia, the subject seems vast, especially when dealing with some cases where some algos are faster than others. That might need some quick ...
23
votes
6answers
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 ...
7
votes
2answers
270 views

Draw land for motocross game

I would like to draw a land for a motocross game. I've been thinking of Bezier Curves but I am not sure whether this is the best approach. Can you give me some advice? I want to do it in JavaScript, ...
3
votes
1answer
278 views

Correct Blitting 2 surface problem

this is a graphics/math problem. Consider this 2 sprite / surface As you can see they are a tank and his gun turret. Now, i manage the turret rotation, and it works, and, also, the rotation of ...
7
votes
3answers
2k views

Predicting enemy position in order to have an object lead its target

In my 2D game I have AI turrets that should assist the player by automatically firing towards enemies. I would like to make them fire intelligently and lead their target instead of just targeting an ...
16
votes
5answers
7k 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 ...
10
votes
2answers
502 views

How to avoid self-intersection when applying stroke to a curve?

I have several Spline2D objects in my code, each of which has a Position, Velocity, and Acceleration method that returns a vector of the specified quantity at a particular time. I've been using these ...
4
votes
2answers
405 views

Is there an efficient, available online, algorithm for converting a matrix of squares into a triangle strip?

Imagine having a 4x4 square, with 16 smaller squares inside of it, with associated data on what the squares should look like (ie., opacity, colour, etc...). Is there an existing, efficient, ...
5
votes
3answers
2k views

Car (or other “object”) acceleration and braking: how to?

I'm not good in math so I'm here to ask you how to manage, in a simple 2d game, the car acceleration and braking. I'm trying to develop it (as a hobby) in c# and sdl.net.
8
votes
1answer
2k views

Realistic slow-falling snow algorithm?

Is there a good algorithm that simulates falling snow? I'm particularly interested in snow that falls slowly, so it doesn't quite fall in a straight line but deviates a bit. Maybe even including ...
5
votes
5answers
975 views

Algo for given an amount of XP, find a character's level

In a RPG context, what are the ways to quickly find a character's level, given his XP? There are two cases which I am looking at: For when a formula is defined, like in the case of D&D, which is ...
24
votes
1answer
3k 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 ...
16
votes
14answers
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 ...
15
votes
3answers
605 views

Solids as high viscocity Liquids

A friend of mine and I were discussing different idea for allow materials in a world to be destroyed in a very piecemeal fashion and he proposed the idea of representing solids as very viscious ...
32
votes
7answers
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 ...
1
vote
4answers
336 views

Mahjong solitaire - navigating between open tiles

I am looking for an algorithm to help me navigate between 'open' tiles in a Mahjong solitaire game. The game is to be played on a limited device with only left-right-up-down buttons and I want to ...
8
votes
3answers
791 views

How does one separate the acceleration due to gravity from other motion in accelerometer input?

How does one separate the acceleration due to gravity from other motion in accelerometer input?
28
votes
9answers
18k 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.
4
votes
1answer
183 views

Are there any clever methods of regulating bandwidth usage for voice chat payload packets?

For example, suppose my code can determine that upstream bandwidth is unusually limited. And suppose I'm using a fully-connected mesh topology combined with a UDP-like protocol for voice chat. Is ...
7
votes
5answers
17k views

Match-three puzzle games algorithm

I am trying to write a match-three puzzle game like 'call of Atlantis' myself. The most important algorithm is to find out all possible match-three possibilities. Is there any open source projects ...
6
votes
3answers
2k views

How would one determine the position of a participant in a racing game?

Now, for the record, I'm currently not implementing any racing game whatsoever, but this problem just popped into my mind and now I'm curious. So how would one go about finding out which participant ...
14
votes
5answers
4k views

boolean operations on meshes

given a set of vertices and triangles for each mesh. Does anyone know of an algorithm, or a place to start looking( I tried google first but haven't found a good place to get started) to perform ...
41
votes
3answers
17k 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 ...