title: Path finding algorithms?

text:
# Question
Title: Path finding algorithms?
I posted this question on stack overflow first, but I guess no one is very interested in video games there...

What are some path finding algorithms used in games of all types? (Of all types where characters move, anyway) Is Dijkstra's used a whole lot? I would think not, as it doesn't actually trace out the steps to take to get somewhere, right? If I'm understanding it right, it only determines which object is the closest. I'm not really looking to code anything; just doing some research, though if you paste pseudocode or something, that would be fine (I can understand Java and C++). I'm basically looking for a quick overview of path finding in general.

I know A\* is like THE algorithm to use in 2D games. That's great and all, but what about 2D games that are not grid-based? Things like Age of Empires, or Link's Awakening. There aren't distinct square spaces to navigate to, so what do they do?

What do 3D games do? I've read this thingy http://www.ai-blog.net/archives/000152.html, which I hear is a great authority on the subject, but it doesn't really explain HOW, once the meshes are set, the path finding is done. IF A\* is what they use, then how is something like that done in a 3D environment? And how exactly do the splines work for rounding corners?

# Answer
> 66 votes
Too many questions at once, so it's hard to give a concrete answer but to discuss a few of these topics. I'll divide the answer in two and try to address it as best as I can. I don't claim any of these lists to be *complete*, but they're some of the different methods I could remember.

---

# Part 1 - Pathfinding Algorithms

For starters, there are *many* ways to implement pathfinding, but not all of them return the shortest path, or are efficient or even reliable. For instance:

* Primitive methods that don't "look ahead" and take one step at a time:

+ **Random backstepping** \- Take one step at a time in the direction of the goal. If an obstacle is encountered try to work around it by backstepping a bit in a random direction and then trying again. Not reliable at all and will get stuck in a multitude of situations.
    + **Obstacle tracing** \- Other approach, similar to random backstepping but instead of moving back randomly, start tracing around the object once a collision is found, as if you had the right hand stuck to the wall and had to move touching it. Once there's no collision continue moving in the goal's direction. Once again can get stuck in many situations.
* Methods that look ahead to find the entire path at once:

+ **Breadth First Search** \- Simple graph traversal by visiting each layer of children at a time, stop when path is found. If the graph is *unweighted* (i.e. the distance between each adjacent node is always the same) it finds the shortest path although not too efficiently. For weighted graphs it might not return the shortest path, but will always find one if it exists.
    + **Depth First Search** \- Another way to traverse a graph, but instead of taking it layer by layer, the algorithm tries to search deep into the graph first. This method can have problems if the depth of the search is not limited, especially when using a recursive implementation, which may lead to a stack overflow, so it is usually safer to implement it iteratively using a stack.
    + **Best First Search** \- Similar to Breadth First Search but uses an heuristic that chooses the most promising neighbor first. The path returned may not be the shortest, but it's faster to run than breadth first search. A\* is a type of Best First Search.
    + **Dijkstra's Method** \- Keeps track of the total cost from the start to every node that is visited, and uses it to determine the best order to traverse the graph. Works with weighted graphs and returns the shortest path, but might involve a lot of searching.
    + **A\*** \- Similar to Dijkstra but also uses an heuristic to estimate how likely each node is close to the goal, in order to make the best decision. Because of this heuristic, A\* finds the shortest path in a weighted graph in a much more timely manner.
* Then there are variations of A\* (or pathfinding optimizations in general) that make it faster or more adapted to certain circunstances, such as (see related answer and a comprehensive list on cstheory.SE):

+ **LPA\*** \- Similar to A\* but can more quickly recalculate the best path when a small change to the graph is made
    + **D\* Lite** \- Based on LPA\*, it does the same thing, but assumes the "start point" is a unit moving towards the finish while graph changes are being made
    + **HPA\* (Hierarchical)** \- Uses several layers at different abstraction levels to speed up the search. For instance, an higher level layer may simply connect rooms, while a lower level layer takes care of avoiding obstacles.
    + **IDA\* (Iterative Deepening)** \- Reduces memory usage in comparison with regular A\* by using iterative deepening.
    + **SMA\* (Simplified Memory-Bounded)** \- Only makes use of available memory to carry out the search.
    + **Jump Point Search** \- Credits to Eric in the comments for mentioning it! Speeds up pathfinding on uniform-cost grid maps (link).

---

# Part 2 - Search Space Representation

And finally to address this question:

> I know A\* is like THE algorithm to use in 2D games. That's great and all, but what about 2D games that are not grid-based?

Two big misconceptions here! In fact:

1. A\* doesn't care if the game is 2D or 3D, and is equally appropriate for both cases.
2. A\* works under *any* graph representation, so it doesn't care whether the world is a grid or not.

So if the world doesn't need to be a grid, in what other ways can you represent it? Here's a brief overview of ways to partition the world space for pathfinding, and most of these work both for 2D and 3D alike:

* **Rectangular grid** \- Partition world into regular grid of squares with each cell in the grid being one node in the graph, and the connection between two unobstructed nodes is an edge.
* **Quadtree** \- Another way to partition the space, but instead of partitioning into a grid of regular sized cells, partition in four, then recursively divide each of these in four again. Adding a third dimension makes it an **octree**.
* **Convex polygons** \- Partitioning the walkable area into a mesh of interconnected convex polygons. Each polygon becomes a node, and shared edges are the edges of the graph. These can be triangles for instance, and sometimes even be a mesh created by an artist when creating the level assets. Often referred to as a **navigation mesh**. See this link. Here's a very popular navigation mesh construction toolset: Recast.
* **Points of visibility** \- The most common way is to place a node just outside each of the obstacle's convex vertices, and then connect each pair of nodes that can *see* each other. Check this link. The nodes don't have to be the vertices though, and can be placed manually by the designer in the map. In that case, the system is frequently referred to as a **waypoint graph**.

---
Tags: path-finding
---


# Question
Title: How to accurately score moving averages (indepenent of sampling window)
I'm developing a puzzle game, and coming up with a little trouble how to accurately create the 'score' for a particular player's solution.

In this game a player creates a machine which generates 'events'. The 'score' should be the number of events per second that a particular machine performs.

I.E. if my machine performs 6 events per second, and yours produces 8 per second, your score should be higher than mine.

I initially thought to use a moving average for this, but I've discovered it's trivially easy to manipulate this mechanic, such that solutions with an equal long-term performace don't generate the same score.

So in this case if my machine generates 1 event per second, and yours generates 3 every third second, they should have the same score. But if I use a running average to calculate the score, then the latter solution is likely to generate either a higher or lower score depending on the sampling window.

Case A:

```
   time    | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
solution A | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1  |   = 10 / 10 = 1 event per second
solution B | 3 | 0 | 0 | 3 | 0 | 0 | 3 | 0 | 0 | 3  |   = 12 / 10 = 1.2 events per second

```

Case B:

```
   time    | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
solution A | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1  |   = 10 / 10 = 1 event per second
solution B | 0 | 0 | 3 | 0 | 0 | 3 | 0 | 0 | 3 | 0  |   = 9 / 10 = 0.9 events per second

```

I'm wondering if theres some other metric possible to use other than 'average' that wouldn't be subject to this kind of inconsistency? The only way to make this works would seem to run the simulation for infinite time, at which point the two solutions would converge on 1 score / second, but that's not possible to do.

I'm somewhat doubtful that there's any solution to this problem, but just wanted to throw it out to see if there are any ideas.

# Answer
> 2 votes
What is it you're really looking for, a breakdown of how consistently the machine outputs events during each block of one second or how many total?

Try a running total designed to **capture consistent output** and downplay bursty results; you can do this by using the variability between blocks and not the total numbers.

Starting with a dummy block of 0, for each new block recorded if the new output is less than the previous block then accumulate a -1, otherwise accumulate a +1. You could also use a +- based on how big the difference is.

Using your "solution A" and "solution B" data this measure of consistency will make A look very attractive with a score of 10 while B lags behind with a score of 4.

To **capture total output** you really are at the mercy of your sampling window, someone will almost always be ahead or behind temporarily based on how bursty their output is and the granularity of your window compared to the total number of samples.

One defense against this behavior is to provide a **margin of error** to the accumulated score **to counter bias caused by your window** size. Using your example of 10 samples let's say that your margin of error will be 1/5. In both cases the results would be equal within the margin of error but let more significant differences prevail.

---
Tags: game-design, mathematics, game-mechanics
---


title: Word list for use in commercial game

text:
# Question
Title: Word list for use in commercial game
I need a word list to use in a commercial game (even though the game will be free to download)

Something like this

http://www.puzzlers.org/pub/wordlists/ospd.txt

Would be perfect (needs to be formatted .txt file) but obviously allowed to be used in a commercial game. I'm happy to pay if it's not too much.

Thanks for any advice.

*UPDATE*

After some more research (google), I came across this passage. Thought this might be useful for other people, although it still seems in contradiction to what the replies are saying on stack overflow here

"The nearest thing to a licence text for ENABLE, of which ABLE forms a part, is as follows.

The ENABLE master word list, WORD.LST, is herewith formally released into the Public Domain. Anyone is free to use it or distribute it in any manner they see fit. No fee or registration is required for its use nor are "contributions" solicited (if you feel you absolutely must contribute something for your own peace of mind, the authors of the ENABLE list ask that you make a donation on their behalf to your favorite charity). This word list is our gift to the Scrabble community, as an alternate to "official" word lists. Game designers may feel free to incorporate the WORD.LST into their games. Please mention the source and credit us as originators of the list. Note that if you, as a game designer, use the WORD.LST in your product, you may still copyright and protect your product, but you may *not* legally copyright or in any way restrict redistribution of the WORD.LST portion of your product. This *may* under law restrict your rights to restrict your users' rights, but that is only fair.

M Cooper and Alan Beale "

From this site http://www.quinapalus.com/dicts.html

Obviously I have no way of knowing if that's legit or not, so I was wondering what other peoples advice still is.

# Answer
According to the site you linked your list from:

> The official Scrabble player's dictionary, known as OSPD, is widely available on the internet. There is also a list targetted at Scrabble players known as the Enable list. This has been explicitly placed in the public domain.

In addition, the page the link resides on contains numerous other lists of words that are free to use.

**EDIT**

You found in your update, what I'd already said in my answer. Additionally, the SE link you've posted has plenty of alternative answers. For example: The English Open Word List, has more words that the OSPD and it's restriction free. Beyond that, the Enable list, as I said in my answer, seems to be a very good choice and is in the public domain.
> 9 votes

# Answer
I generally don't think you have to "pay" to use a word list.

Any word list you find can easily be reformatted using a bit of string manipulation / text output.

For a large group of word lists, just go here.
> -1 votes

---
Tags: game-mechanics
---


# Question
Title: How do I stop my game from Skipping Screens?
I used the code from this - http://www.xnadevelopment.com/tutorials/thestateofthings/thestateofthings.shtml (The second method using enumerations)

I modified it to add a 3rd screen for gameplay and it functioned like the previous screen. The issue is that since the Controller Detect Screen and Title Screen both use the A button to advance. Because of this, it advances through both at the same time, going straight to the gameplay screen. I changed the code (as seen below) so that the Title Screen uses a different button. However, I want to have it so it uses the same button, but not advance at the same time.

Hopefully I explained it correctly.

```
        private void UpdateControllerDetectScreen()
    {

        //Poll all the gamepads (and the keyboard) to check to see

        //which controller will be the player one controller

        for (int aPlayer = 0; aPlayer < 4; aPlayer++)
        {

            if (GamePad.GetState((PlayerIndex)aPlayer).Buttons.A == ButtonState.Pressed || Keyboard.GetState().IsKeyDown(Keys.A) == true)
            {

                mPlayerOne = (PlayerIndex)aPlayer;

                mCurrentScreen = ScreenState.Title;

                return;

            }

        }

    }

    private void UpdateTitleScreen()
    {

        //Move back to the Controller detect screen if the player moves

        //back (using B) from the Title screen (this is typical game behavior

        //and is used to switch to a new player one controller)

        if (GamePad.GetState(mPlayerOne).Buttons.B == ButtonState.Pressed || Keyboard.GetState().IsKeyDown(Keys.B) == true)
        {

            mCurrentScreen = ScreenState.ControllerDetect;

            return;

        }

        if (GamePad.GetState((PlayerIndex)mPlayerOne).Buttons.A == ButtonState.Pressed || Keyboard.GetState().IsKeyDown(Keys.C) == true)
        {

            mCurrentScreen = ScreenState.GamePlay;

            return;

        }

    }

    private void UpdateGamePlayScreen()
    {

        //Move back to the Controller detect screen if the player moves

        //back (using B) from the Title screen (this is typical game behavior

        //and is used to switch to a new player one controller)

        if (GamePad.GetState(mPlayerOne).Buttons.B == ButtonState.Pressed || Keyboard.GetState().IsKeyDown(Keys.B) == true)
        {

            mCurrentScreen = ScreenState.Title;

            return;

        }

    }

```

# Answer
You need to distinguish between a **single key press** (or button) from **the key being held down**.

This can be accomplished by adding an extra check to your if statement, so that besides checking if the button (or key) is *currently* down you also need to check if that same button (or key) *was* up on the previous frame.

If *both* are true, then we're dealing with with the first frame of a key press, and anything you put inside will only be triggered once. In order for it to be triggered again, you would need to *release* the button and press it again.

I've already written twice about this problem:

But transcribing the most essential bits, the technique can be summarized as this:

```
private KeyboardState _currentKeyboardState;
private KeyboardState _previousKeyboardState;

public void Update(GameTime elapsed)
{
    // Before handling input
    _currentKeyboardState = Keyboard.GetState();

    if(_currentKeyboardState.IsKeyDown(Keys.A) &&
       _previousKeyboardState.IsKeyUp(Keys.A))
    {
        // Change screen here
    }

    _previousKeyboardState = _currentKeyboardState;
}

```

Adapt this to your needs, i.e. store the gamepad state and check for it too, possibly encapsulate everything in a class (for example, the first question I linked above has an answer with an implementation that seems pretty complete, while the second question has a minimalistic implementation).
> 5 votes

---
Tags: xna, c#
---


title: XNA with WPF or Winforms

text:
# Question
Title: XNA with WPF or Winforms
If you compare integration between WPF with XNA vs Winforms with XNA, what is the most suitable framework to integrate XNA framework with.

# Answer
Both approaches are valid, but require a bit of thinkering. Using Winforms or WPF in XNA can work great and is great for level editors, but it's usually not that polished that you can ship it to customers, so only use it for your internal tools.

XNA in WPF

XNA in Winforms (official method, preferred)

XNA in Winforms (quick but hacky method **read the notes at the end!**)

Another method, that you can ship to customers is to use one of the many GUI libraries for XNA. I've looked around a bit and this seems the most complete, but there is also this one which I've seen used in actual games: NeoforceControls
> 3 votes

# Answer
Most people seem to prefer WinForms due to reduced hassle it takes to make XNA and WPF work together, which for the most part is fine. However, more and more people are doing their best to make WPF a good choice with the help of components and libraries that enable the ability to Render XNA inside an area or control portion of the screen. I helped develop the one I'm posting here and I think it's a fairly lightweight, simple solution for having XNA in WPF. However, just building a good UI system in XNA itself will make your product more shippable.

In either case, I'll leave this here: https://xnaml.codeplex.com/
> 2 votes

# Answer
This is a "which is better" question, and it depends entirely on your needs.

That being said I have done this previously using WinForms, I decided to use WinForms because the approach seemed to be simpler and require less setup. WinForms Graphics Sample is a link to an App Hub posting which includes the relevant source code to get started. Be warned though, mixing XNA calls and GDI calls causes severe flickering and is impractical. To overcome this limitation I drew basic shapes with another App Hub code sample: Primitive Batch.
> 0 votes

---
Tags: xna, wpf
---


title: XNA transparent objects?

text:
# Question
Title: XNA transparent objects?
I've working on a voxel like game like Minecraft, but I'm not sure how I should handle alpha. I've got the world split into chunks and I render each chunk, I have things like leaves which have alpha which is either on or off, but if you look through them you can only see other chunks which have already been rendered, here's a picture because I can't explain it.

https://i.stack.imgur.com/py0yz.png

It also works with leaves from the same chunk, for example if I'm looking through them from one direction to another then I can see the other leaves through the leaves, but if I'm looking the other way I get the same effect.

# Answer
In example you gave, you don't need any sort of alpha blending. (Pixel is either visible or not - and i suspect most of studd in minecraft like game will be like this)

You can just call discard in shader for pixels you want to be transparent (and they won't write to depth buffer)

(In XNA 3 it was possible to set RenderState.AlphaTestEnable which will do the same.)
> 1 votes

# Answer
You need to leave the rendering of objects with transparency to the end of your rendering cycle and, preferably, render them from the furthest away to the nearest (as this is generally more efficient. Inversely, non transparent objects are most efficiently rendered from the nearest to the furthest away).

To try this out initially, just put in a flag for each object to mark it if it has transparency then, in your normal render function, just run it twice, once where you only draw non transparent objects and then again for only transparent objects.
> 1 votes

# Answer
If i'm not utterly mistaken, it's to do with the depth information. If you first render the transparent material before solids are drawn, it will skip rendering the solids becouse of the z-index. Render transparent materials afterwards as extra step.
> 1 votes

# Answer
I quite agree to Toni and OriginalDaemon. It's true that handling transparent objects need care.

Especially for tree which has both transparent part, and opaque part. At least, we have to draw it twice for optimum of quality of result for look & feel.

If it's relevant at all, please take a look at this link (from Riemers). It explains how to handle this stuff.

For brief (as it requires 2 passes/steps to accomplish this)

**1**: Draw only the opaque part (with the power of alpha testing function, and alpha reference value set) with z-depth writable enabled. This way your depth buffer will be correctly written by the actual tree!

**2**: Draw transparent part of tree. This will give a correct and better look & feel of group of trees.

You're done.

Please note as from my own experiment, it's up to your tree whether it's billboarding or polygons forming into itself. For billboarding, it usually require 2 steps above to completely give a better look & feel. But for poly-tree (as for my case), I can ignore step 2 and save cost but still have a decent look without much different.
> 0 votes

---
Tags: xna, c#, 3d, minecraft-modding
---


# Question
Title: How do I move a body using the hardware accelerometer?
I want to move the ball as I move the device but I can not able to find how to use accelerometer in libGDX. I know that `Gdx.input.getAccelerometerX()` returns x coordinate but I don't know how to apply it to the body I have created.

# Answer
> 4 votes
LibGDX offers these three methods in the `com.badlogic.gdx.Input` interface:

* **float getAzimuth()**: The azimuth is the angle of the device's orientation around the z-axis. The positive z-axis points towards the earths center.
* **float getPitch()**: The pitch is the angle of the device's orientation around the x-axis. The positive x-axis roughly points to the west and is orthogonal to the z- and y-axis.
* **float getRoll()**: The roll is the angle of the device's orientation around the y-axis. The positive y-axis points to the magnetic north pole of the earth.

All three return a value in degrees. They tell you what angle the phone's being held at in the world, so you should also be able to construct a plane in your game which the ball would be sitting on, and thus determine how the ball should roll. Do note these only map perfectly to the screen if the phone is facing north, so you'd need to use the Azimuth value to find the direction of the game's local 'north' (which points towards the top or the side of the phone).

From there you just implement the physics of a ball rolling down a hill, which would mean applying acceleration to the ball depending on the direction and steepness of the ramp it's on.

# Answer
> 3 votes
I have found an answer of my question after hardworking towards it. The solution is

cfg.useAccelerometer = true;

For using accelerometer we have to enable it in the android file that this I was missing

---
Tags: libgdx
---


title: SQL Database using Adobe Air

text:
# Question
Title: SQL Database using Adobe Air
How do you create an SQL database (I believe it's tinySQL/SQLite) using Adobe Air? I have searched around, and all sites give code, and then explains to wrap it within an xml document, for example here.

So I have created this xml file, but no one seems to explain what to do from there. I am also VERY new to database creations and management. So any super n00b friendly help would be much appreciated.

Thanks.

# Answer
> 6 votes
Regarding that link you posted: The creation of a SQLite Database has nothing to do with XML, nor is XML needed. What you see there is a MXML document, a special XML flavor introduced by Macromedia/Adobe. But the majority of this document is just plain Actionscript 3 (wrapped in `<mx:Script>` tags).

So you're going to use Actionscript to create and access the Database. But since you're new to the whole database thing, I suggest you first take a step back and actually learn some SQL. This is going to be easiest by using a tool that allows you to create Databases and run queries. There's even a Firefox addon that allows you to manage SQLite databases from within your Browser.

Once you are comfortable with SQL (you can also look up the exact syntax for SQLite here), the step to using this in Actionscript is really small, because in Actionscript you do nothing else than sending SQL queries (so it's actually good practice to learn the query syntax before you integrate it into more complicated code).

The help documents over in the Adobe Flash help should contain enough information to show you how to use SQLite in Flash/Flex.

**Update**: Here's a short explanation of the most important SQL commands and when you're typically going to use it in your application.

* When your application starts up, you should check if the Database already exists. If not, you can create one using `CREATE TABLE`. With `CREATE TABLE` you specify all the database fields and their types. This can be quite complicated at first, but some of the tools linked above allow you to create the table using a GUI and then "export" the SQL create statements. Example:

```
CREATE TABLE myTable (
  id INTEGER PRIMARY KEY,
  name VARCHAR(127)
);

```
* To read data from one (or multiple) tables, use `SELECT`. Example:

```
SELECT * FROM myTable

```
* To write to a table, use `INSERT`. Example:

```
INSERT INTO myTable (id, name) VALUES (1, 'Foo')

```
* To update data, you use the `UPDATE` statement. Example:

```
UPDATE myTable SET name = 'Bar' WHERE id = 1

```
* To delete data, there's the `DELETE` statement. Example:

```
DELETE FROM myTable WHERE id = 1

```

---
Tags: databases, sql
---


# Question
Title: Why did an Android update disable  the textures in my game?
I recently updated my tablet to Android 4.0.3 and now the textures for my game do not show up. I'm using OpenGL-ES 2.0 for my engine. It worked fine when I was running android 3.0. Is there any reason as to why this is happening?

# Answer
> 3 votes
It's not terribly well documented, but there are some events which cause an OpenGL context loss on android. Make sure your textures are reloaded after every context loss.

---
Tags: android, textures, opengl-es2
---


# Question
Title: Web Card Game , MySQL vs SQLite performance wise
Been thinking of creating a js/PHP/MySQL game, with multiple players / games happening concurrently. Is there any chance SQLite might be faster for something like this than MySQL? Keep in mind that I'll propably test this on a shared hosting server...

# Answer
You probably don't care. I'd suggest that maybe it's not necessary to use a database at all, and a commercial gaming company almost certainly uses a custom server process (not a web server at all). However, you can do whatever you like.

In particular, you're very unlikely to have either enough data or players that you will actually notice. Gaming data are very, very small unless you start storing huge amounts of historical reporting data for previous games. And if you do decide to start doing that, you can host historical data on independent servers so they can't interfere with new games.
> 1 votes

# Answer
Writing every single action to the database, like you are suggesting you are doing, is usually a bad idea.

You would do much better writing a real server, and update the database only once a match ends.
> 2 votes

# Answer
My advice is to look at a PHP interface that is database agnostic, so you can switch it later.
> 0 votes

---
Tags: browser-based-games, php
---


# Question
Title: How to keep track of players nearby other players in an MMO
I'm confused how to handle the players in my MMO server (using Socket.IO but I think this should apply to any MMO).

Suppose there are 2 players in my server that are far away from eachother. I will call them A and B in this example.

The server launches. No clients are connected.

A joins and is added to the server's active playerlist.

Every second A gets a list from the server with the active players nearby to update their positions. Since there are none online currently, the list is empty.

B joins, far away from A. The server adds B to the active playerlist. Since A cannot see B yet, the list that A receives from the server is still empty.

B is moving towards A and comes within visual range.

**What to do now for A?** Send an event to A that B has come within range? How can the server know that A was informed of B being nearby? Does this mean I have to maintain a list on the server which player can see another?

Here's what I was doing before with my previous project: I never told the clients that a player was in range, instead the server just sent a list every second of players that are nearby and let the client do the rest. This way, the client keeps track which unit is added and which is not. Is this the best approach, or am I missing something?

# Answer
Nic explained this to me briefly yesterday. Check out the explanation on his blog.

http://nic-gamedev.blogspot.com/2011/11/mmo-architecture-creating-ghosting.html
> 6 votes

# Answer
It's quite an advanced topic, and as word of warning I'm hesitant to indulge too much in to this because I only know some theory and haven't actually produced an MMO.

In MMOs, optimization is perhaps the primary factor in decision making on the technical side. The more users you are able to host, the better. It's easy to accidentally use poorly scaling methods, and I recommend you find a good external resource on this.

The movement updates are a critical piece of any MMOs: They occur very often, and you will want to restrict these updates as efficiently as possible to others. Do consider carefully if you really require the visibility information to be part of server-side calculations. Most games only divide the world with some form of space partition in to many cells. The server then keeps track of which cell the player is at and informs that cells and nearby cells' users, when it comes to move-updates.

For efficiency, server will assume that clients keep track of the world accurately and will usually send out only when player has moved and output all new positions when moving from cell to another, or when player disconnects or connects etc. Usually absolute positions are used for movement updates. Client can keep its own state of the world and remove players in farther cells according to the same rules server uses.

Merely relying on these updates can sometimes lead to bugs and strange behavior though if the client's state strays from server's state, but for optimization's sake, we should rely on client to perform as intended. Client messing up only affects that one player usually, which is reasonable price to pay for being able to support more players on the server.

For other less-frequent actions, it's much cheaper to check the actual distance when you know the interacting players. For actions that target areas rather than other players, you would check against the cells first too. Space partitioning can be quite advanced topic, but probably what you want/need.
> 4 votes

# Answer
Take position of player A. Subtract position of player B. Get the length of the resulting vector. If it's under the sightrange, add the other player to a list that a player can see. This will help you with all updates, ie you don't need to send all movement/socials that a player that isn't visible is doing. You can do the initial check fairly seldom(say once every few seconds), and then check for removal from the list every second if you're worried that it might take alot of processing power.
> 2 votes

# Answer
> Does this mean I have to maintain a list on the server which player can see another?

Basically, yes. The way we did it on a previous project was that each character had 2 lists: one of IDs of the characters that it knew about, and one of IDs of characters that knew about it. (Obviously it's possible to derive the 2nd list from the 1st but it's quicker just to keep the 2 updated in parallel.) To decide what information is available to the character, you use the first list, and when deciding who to broadcast updates to, you use the second list.

How to manage the list(s) is basically a mix of a game design issue and an optimisation issue; ideally the list would always be "every other character in the world" but practically that doesn't tend to scale. So you may limit the lists by distance or by zone, or you might choose to update them only periodically, or you might sort by distance and cap the length of the lists, or some combination of the above.
> 2 votes

# Answer
One option is to make the server simulate what the client knows. You can then compare that to the real game state on the server and send update messages to the client when there's a difference.

The main benefit from that is you can use that information to minimize what you send to the client. Stationary objects only need sending once for example because after that the client and server will be in sync.

If you have limited bandwidth you can send only the updates for objects which are the worst synchronized to the client and leave ones which only have minor changes till later on.
> 0 votes

---
Tags: node.js, websocket
---


# Question
Title: What limits the level of graphic detail in a game?
This question popped into my head after seeing some preview images for Halo 4.

What limits a games' graphic level?

(If this is the wrong place for this question, I understand)

Game series' like Halo have multiple installments that come out on the same system ie. Halo-\>Halo 2 on the XBOX, Halo 3-\>Halo 4 on the Xbox 360, and the sequel invariably looks MUCH better than its predecessor. When I see behind-the-scenes-type development videos, the game creators will talk about, "Oh, this character model has x-times the amount of polygons as the old one..." which I assume is what makes it look better. My question is, if the game system could have handled that many... objects (to my layman understanding)... on screen at the same time, why couldn't the original game look that good?

1.Where is the limitation? What changes from game to game?

2.What improves from game to game?

# Answer
I think answer is pretty obvious. Given hardware is a constant, the only variable is software (i.e. the game).

1. Game changes :-).
2. Game engine is improved and optimized, assets quality is increased. Usually second version is improved version of the first. So not only developers don't need to do everything from the scratch, but also they know weak points which need to be improved, and have much more time to work on it. Game artists also have more time to improve graphics, etc.
> 4 votes

# Answer
> Halo-\>Halo 2 on the XBOX, Halo 3-\>Halo 4 on the Xbox 360, and the sequel invariably looks MUCH better than its predecessor. When I see behind-the-scenes-type development videos, the game creators will talk about, "Oh, this character model has x-times the amount of polygons as the old one..." which I assume is what makes it look better.

Actually Halo 2 used fewer polygons for characters than Halo\* which makes it an instructive example. A lot of people assume more polygons equals better graphics because it's an easy number to directly point to, but it's not hard to think of an example where no, more polygons isn't better:

Imagine a sphere comprised of a couple hundred polygons, and another sphere comprised of a couple thousand polygons. They're both just spheres.

Now imagine the first sphere is rendered with a specular map for shiny highlights and a normal map for subtle texture on its surface, while the second sphere is rendered with basic Garoud shading. So now which sphere looks better, the one with more polygons?

I'm not saying that polygon count doesn't matter at all, but rather it's just one of a whole complex set of factors that determines the look of your graphics. Textures matter a ton, lighting matters a ton, etc. The reason sequels on the same hardware look better is simply that the artists are getting more practiced at creating graphics for that hardware.

\*A couple years before Halo came out I had a conversation where I argued that we needed better lighting rather than more polygons, and everyone else piled on to crucify me for criticizing their polycount dogma. After Halo 2 came out I wished I had a time machine to go back and say "I told you so!"
> 3 votes

# Answer
As Petr said, ditto. Well, it would be a long lecture to teach all that is involved. Performance of hardware and optimization/qualities of the engine used, play part of what is possible to render in given framerate.

But mere polygon cruching and processing power is not really enough to make what we will perceive as pleasant graphics. To clarify... Here's a good video on graphics vs aesthetics
> 0 votes

---
Tags: graphics
---


# Question
Title: Translation from one coordinate system to another having Z-offset issues
I'm using ARToolkit to do an augmented reality application, but my problem is really with the 3D coordinates.

In this application, I use my webcam to generate the scene. I have two markers (printed - they have a thick black border with a letter inside to signify which object is to be drawn), and when the ARtoolkit framework recognizes the object, it will draw a specific OpenGL object on top of the marker in real time.

So onto the actual problem.

The first marker I consider to be my world coordinates, and the second to be a floating object that I will move around the scene.

The overall problem is that when I translate my secondary object to my world coordinate system, the Z-value is typically way off from what it should be, and I'm not sure how to rectify this (this is really my first foray into 3D programming).

As a note, I get the OpenGL 1x16 matrix in from the ARToolkit, using the recognized marker as (0,0,0).

First, I take the world coordinate system marker, store it into a 4x4 matrix, and then create a variable to hold its affine inverse (I am using a framework to do this part, so I don't think it is anything I'm doing here).

Next, I take the secondary marker and store that into a 4x4 matrix.

Finally, to move the secondary marker into the world coordinate system, I multiply them in-order, together, as such:

```
new_coords = world_coords_affine * secondary_coords

```

For my understanding, this should take the secondary object and move it to the world coordinates, so that I can simply draw it based on the new x, y and z values.

As I mentioned however, the Z coordinate is far greater than it should be. I am drawing my scene typically at about (0, 0, 50) to hide the markers in the scene, and the secondary object tends to have Z-coordinates in the thousands when it is debugged. For reference, I am actually putting the two markers directly next to each other, so really there should only be an X-offset (which I am seeing at least).

# Answer
Are your values normalized? It would cause that kind of problem.
> 2 votes

---
Tags: opengl, 3d, matrix, coordinates, artoolkit
---


# Question
Title: Examples of RESTful Web Services for Browser Games
Can anyone point me towards examples of Browser Games / Browser Game Sites that use RESTful web services?

I have been convinced time and again that building web sites using RESTful principles is a good idea. And I agree. But I just can't wrap my head around what RESTful means when the service you're providing is just a single (or a few) games.

Any ideas or thoughts would be nice, but I'd also love to see some solid examples.

# Answer
I think the network protocol is really irrelevant, each game uses its own protocol, REST or any other standard is only important if you need to interoperate with third party software - which game servers mostly do not.

For example, if you published the API, using REST might be a good idea. But otherwise, I don't see any reason to do so.
> 3 votes

# Answer
You would have REST services for all the moves one could make, or for the game information requests.

Something like:

```
POST /game/45093/move?x=3&y=2

POST /game/45093/surrender

GET /game/45093/status

GET /games

```

etc...
> 1 votes

---
Tags: browser-based-games
---


# Question
Title: How do I create selectable menu options in C#/XNA?
Ok, I have my game's menu system set up. There are 3 screens (Controller Detect Screen, Title Screen, and GamePlay Screen). I wish to improve on this by having the ability for the player to select options on the screen, but I do not know how.

I don't know how to make menu choices that can be highlighted or making transitions from screen to screen rather than having it warp the way it presently does.

# Answer
Take a look at the Game State Management sample that Microsoft provides. Not only does it contain screen transitions, but it shows how to "select" menu items. I included some pseudo code in each section below. Hopefully it will help you grasp what I am talking about.

## Screen Transition

In a nutshell, you have a ScreenManager. Its job is to contain a list of the active screens and call the update/draw methods on them. When it is time to do a transition, an alpha blend is used to make the old screen fade out to black, and the new one to fade in. You can do any effect. Instead of fading maybe you make the slide away.

```
//In the GameScreen
// If the game is transitioning on or off, fade it out to black.
if (TransitionPosition > 0 || pauseAlpha > 0)
{
    float alpha = MathHelper.Lerp(1f - TransitionAlpha, 1f, pauseAlpha / 2);

    ScreenManager.FadeBackBufferToBlack(alpha);
}

//The ScreenManager lays over the alpha
public void FadeBackBufferToBlack(float alpha)
{
    Viewport viewport = GraphicsDevice.Viewport;

    spriteBatch.Begin();

    spriteBatch.Draw(blankTexture,
                        new Rectangle(0, 0, viewport.Width, viewport.Height),
                        Color.Black * alpha);

    spriteBatch.End();
}

```

## Menu Items

This is a bit more simple then you may think. You have a list of menu items (let's pretend it is an array), and a pointer saying which item in the array is active - default it to zero for now. `int ativeItem=0`. Anytime the user presses up/down on the controller you increment/decrement the pointer. The MenuScreen can use this two determine what menu item to highlight. In the case of the sample linked above, I believe they also have it pulsate.

The MenuScreen is also the component that listens for the "activate" button. I will Assume it is the **A** button for now. When the **A** button is pressed, it checks to see which item in the list the `activeItem` pointer is on. It then does whatever is appropriate.

```
if(input.IsUpPressed)
{
    activeItem--;
    if(activeItem <0)
        activeItem = menuEntries.Count - 1; //if he was at the top and pressed "UP", loop the pointer to the end
}

if(input.IsDownPressed)
{
    activeItem++;
    if(activeItem > menuEntries.Count - 1)
        activeItem = 0; //if he was at the bottom and pressed "DOWN", loop the pointer to the start
}

if(input.IsAPressed)
{
    SelectMenuItem(activeItem);
}

```

## Putting it together

Now, I explained this very quickly in a short post. It would behoove you to look at the example. Start with the Game.cs file to see how they create a ScreenManager.

Once you understand that (it is only a few lines of code) look at the `GameScreen` class next. It is a base class you each of your screen will need to override. The reason I am having you look at this first is because you will need to know how the `ScreenManager` is interacting with it.

Now that you get what properties & methods are in `GameScreen` look at `ScreenManager`. Take your time. There is a decent amount going on here. When you are finished look at the individual screens the have. There is a `MenuScreen` (you will like this one) and a `GamePlayScreen` where they have their logic for the current level in the game.

If you get stuck, just put a breakpoint in the code somewhere, run the game, and step through it line-by-line. If you get really stuck ask away here. There are plenty of us that would love to help.
> 11 votes

# Answer
Since you are a student you will be able to get a free version of ScaleForm which may help you out here. Scale Form FAQ \- see question 2
> 0 votes

---
Tags: xna, c#
---


# Question
Title: OpenGL gradient banding on Samsung Galaxy S2 Android phone
I've got a live wallpaper out on the market which uses OpenGL to render some basic shapes and a flat plane. The simple lighting creates a gradient effect across the plane, which looks fine on most devices. The Samsung Galaxy S2 series seems to have some trouble rendering the gradient, though, as you can see in this screen shot:

The color banding looks awful, especially compared to this screen shot from an Incredible:

I'm using a 565 EGL config in both cases, so I believe this is just a display issue with the GS2 devices. Can anyone confirm this suspicion?

Is there any solution to the banding?

# Answer
> 1 votes
Looks like it really is the GS2's display, or more accurately, its dithering algorithm. I tried upping my requested config to RGB888, and this is what I get (from my test user's phone):

So it really seems like the GS2 just does a horrible job of dithering when trying to map colors in an 888 space to a 565 config.

Now I'm not sure if I want to up the config to 888 across all devices (better quality but a performance hit), or only on devices which I know to dither poorly. Hmmm.

# Answer
> 4 votes
You're getting the banding because of a bad setting for colour bit depth on your surface. Romain Guy and Chet Haase (both Google employees who work on graphics in Android gave a presentation that covers these issues at the San Francisco Android User Group in 2010. The video is available on YouTube here and I've actually made some notes on the stuff they cover (shameless plug) here. Specifically the section that you want starts at about 25 minutes in and lasts for 10 minutes.

Relevant section from my notes:

> Supported Bitmap formats are ALPHA\_8 (for alpha masks), ARGB\_4444 (this isn’t recommended, uses 4 bits for each component and therefore doesn’t look very good), ARGB\_8888 (recommended, 32 bit images, allows for transparency), and RGB\_565 (doesn’t contain alpha channel, limited precision for colours, faster to draw, uses dithering). JPEG images do not contain transparency and pre-Gingerbread were loaded automatically with RGB\_565. **This meant that jpg images automatically lost some quality pre-gingerbread.** Post Gingerbread all images are loaded by default as ARGB\_8888 (and application memory usage limits are increased to compensate). **When loading a Bitmap, make sure to specify the format that you want, otherwise it will be loaded as its default and every time the Bitmap is drawn it will need to be converted.** For instance, pre-Gingerbread the default bit depth for a Surface is 16 bits, so a 32 bit image will need to be converted before rendering which can be slow. **You can control quality of this rendering by enabling/disabling dithering on the Paint object and the Drawable object that the Bitmap’s being used by.** Blending should be avoided with the alpha channel. If Android detects an image is completely opaque it can perform a faster rendering pass.

(emphasis mine)

There's both performance and precision loss when loading an image with the wrong bit depths and he gives an example at about 30:00 showing how artefacts and banding can occur and the different options you have to cope with it, as well as the differences in rendering speed for each option.

This is relevant even in OpenGL if you're loading an image with BitmapFactory before putting it into a buffer, you can specify the config you want with BitmapFactory.decodeStream().

# Answer
> 2 votes
I solved color banding in two phases:

1) When we use the BitmapFactory to decode resources it decodes the resource in `RGB565`which shows color banding, instead of using `ARGB_8888`, so I used `BitmapFactory.Options` for setting the decode options to `ARGB_8888`

Second problem was whenever I scaled the bitmap it was banded again.

2) This was the tough part and took a lot of searching and finally worked. The method `Bitmap.createScaledBitmap` for scaling bitmaps also reduced the images to `RGB565` format after scaling I got banded images (the old method for solving this was using at least one transparent pixel in a PNG but no other format like JPG or BMP worked) so here I created a method `CreateScaledBitmap` to scale the bitmap with the original bitmap's configurations in the resulting scale bitmap (actually I copied the method from a post by logicnet.dk and translated in Java)

```
    BitmapFactory.Options myOptions = new BitmapFactory.Options();
    myOptions.inDither = true;
    myOptions.inScaled = false;
    myOptions.inPreferredConfig = Bitmap.Config.ARGB_8888;//important
    //myOptions.inDither = false;
    myOptions.inPurgeable = true;
    Bitmap tempImage =
    BitmapFactory.decodeResource(getResources(),R.drawable.defaultart, myOptions);//important

    //this is important part new scale method created by someone else
    tempImage = CreateScaledBitmap(tempImage,300,300,false);

    ImageView v = (ImageView)findViewById(R.id.imageView1);
    v.setImageBitmap(tempImage);

```

// the function

```
public static Bitmap CreateScaledBitmap(Bitmap src, int dstWidth, int dstHeight, boolean filter)
{
    Matrix m = new Matrix();
    m.setScale(dstWidth  / (float)src.getWidth(), dstHeight / (float)src.getHeight());
    Bitmap result = Bitmap.createBitmap(dstWidth, dstHeight, src.getConfig());
    Canvas canvas = new Canvas(result);

        Paint paint = new Paint();
        paint.setFilterBitmap(filter);
        canvas.drawBitmap(src, m, paint);

    return result;

}

```

Please correct me if I am wrong. Also comment if it worked for you. I am so happy I solved it, hope it works for you too.

# Answer
> 1 votes
I've noticed the same thing with a background image in a game I've worked on. On my Samsung Vibrant, it looks as expected, but on my wife's Evo, it has the same banding effect. Both are using 565 and OpenGL ES. Unfortunately, this isn't something I've solved yet (though I haven't spent much time with it).

I've pulled the same image up in the embedded web browser and it looks fine, so I can confirm that it's not merely a display limitation.

Have you tried increasing the precision of variables related to color that you use in your shader(s)?

---
Tags: opengl, android, color
---


# Question
Title: How do I fairly distribute resources among factories when resources are near exhausted?
The main resource in my game is *mass*, stored as a floating point number that changes over time. Resource nodes increase mass and factories drain it. For example, if I have a resource node yielding 5 mass per second, I'll gain `5 * deltaT` mass each game step. Mass is displayed rounded to the nearest integer, and gain/loss indicators are displayed by tenths.

**How should I handle mass hitting zero?** This creates a race condition if multiple factories are trying to build at once: Factories first in the queue or which drain less resource get priority once some more resource comes in and so build faster than the others.

How can I deal with this? Should I skip the step entirely?

# Answer
I agree with Petr: There is no set way to do it. How you want to do it is a matter of how you want to design your game.

In this circumstance, however, I think it's immediately obvious the sort of mechanic you're trying to get at: you just want things to produce as fast as possible, within the amount of mass you have available.

### Producing within capacity

I'm going to take a leaf out of Supreme Commander's book, since you're doing a system very much like theirs: If you're producing above capacity, the neatest way to deal with it is have production slow down across the board. Lowering production capacity is actually pretty simple.

### A production speed mechanic

Each update step, your factories don't just produce a set amount: they operate by a **production speed**, which determines how much progress they make in each step and how much mass they use up. When you're producing at 75% capacity, your factories make 75% as much progress each step and use up 75% the mass compared to 100% capacity.

To calculate the production speed, before building anything at all, you should query your factories to determine the total resources that would be used this step at full capacity. Then you perform a simple calculation:

```
production speed = (total mass capacity / mass required this step)
if (production speed > 1.0) production speed = 1.0

```

Let's say you need 125 mass this step to produce at full capacity, but only have 100 mass this step. This equation provides you with a production speed of 0.8 (the decimal representation of 80%). When you tell your factories to *actually perform their building*, you hand them this value to tell them what speed they're building at: and now your production is slowed down across the board.

### Alternatives

You could also begin shutting down factories temporarily until production capacity frees up, and it could be very interesting to see that happening to factories farther away from generators when at extremely low capacity.

### Multiple resources?

Up to you how you handle this; there are a lot of options. The simplest one is probably to calculate a production capacity for each resource and then pick *the lowest one*, such that your weakest resource becomes a bottleneck for all the rest.
> 9 votes

# Answer
Although I like Jonathan Hobbs' answer I think a queue system is even simpler:

```
Queue<Factory> queue = ...;
int numFactories = ...;

Update()
{
    int resources = GetAllResourcesForThisStep();
    for(int i = 0; i < numFactories; i++)
    {
        if(queue.Peak().RequiredResources <= resources)
        {
            Factory f = queue.Pop();
            resources -= f.RequiredResources;
            queue.Push(f);
        }
        else
        {
            break;
        }
    }
}

```

This will probably work on average in the same way as Jonathan's implementation. However Jonathan's solution might give problems if the workspeed is set very low and my implementation could have a factory with a very high resourcerequest for this frame have it block other factories for several frames.
> 6 votes

# Answer
I am developing a similar supply system in my own game, so I have also been thinking about how to resolve the supply-lock issue, and favoritism. To illustrate the problem, I'll create a simple example:

If you have a list: \[producer1, consumer1, consumer2, consumer3\] and you update in order, starting at supply = 0, you'll get this:

```
producer1 produces 5 mass. You now have 5 mass
consumer1 wants 3 mass. Success, you now have 2 mass
consumer2 wants 3 mass. Fail
consumer3 wants 3 mass. Fail
[next tick]
producer1 produces 5 mass. You now have 7 mass
consumer1 wants 3 mass. Success, you now have 4 mass
consumer2 wants 3 mass. Success, you now have 1 mass
consumer3 wants 3 mass. Fail
etc...

```

consumer1 gets all the fun, while consumers 2 and 3 starve until consumer 1 has been satisfied. Depending on your game, this may not be desirable. I know in my game, it's not. When I get around to it, I'm going to create a queue where consumers that have been fed in one tick will move to the back of the queue for the next tick, which I believe is what Roy T. is getting at. The example above would look like this:

```
producer1 produces 5 mass. You now have 5 mass
consumer1 wants 3 mass. Success, you now have 2 mass. <-- Move to end of queue
consumer2 wants 3 mass. Fail
consumer3 wants 3 mass. Fail
[next tick]
producer1 produces 5 mass. You now have 7 mass
consumer2 wants 3 mass. Success, you now have 4 mass  <-- Note the order change
consumer3 wants 3 mass. Success, you now have 1 mass
consumer1 wants 3 mass. Fail
etc...

```

This way, everyone will get their fair share of the resources.

I also plan to implement an additional queue to be used as a priority queue so that the user can select certain structures to have resource priority. The priority queue will always be served before the standard queue. Make sure that all producers are updated first, then consume all resources second, otherwise the queue will break down when you produce resources part way through a tick and some consumers have already been starved.

So to recap: Update the producers, then the priority queue, moving fed consumers to the end of the priority queue, then update the standard queue, moving fed consumers to the end of the standard queue.
> 4 votes

# Answer
Well, i'll expand on John's idea, since we discussed this a bit in chat.

edit: This solution is actually only preferable if the consumableAmount is relevant to how often the factory should get a batch of resources. If it's all the same, then you can indeed just use a queue.

My solution: all factories listed in a priority queue. Priority is increased as a factory is suffering from starvation. Starvation, priority, set to zero when factory has consumed resources. Top priority is always going to get the next batch of resources.

On determining which factory gets what resources, in some kind of pseudo code:

```
iterator i = factoryqueue.start()
bool starvation = false
while(i.next())
  if(i.ready)
    if (!starvation)
      if (i.consumeAmount < resource.count) starvation = true
      else
        i.consume(resource)
        i.priority = 0
    if (starvation)
      i.priority += 1

```

This way your factories will make 1 product each in turn, if you want to adjust by taking in to account the consumeAmount so that cheaper products are made more frequently, you could increase priority by 1/consumeAmount for example.
> 3 votes

# Answer
Strange question.

> My problem is that if the resource hits 0 I don't know what to do. Should I make a queue of some sort? Should I skip an object's step. What?

What you need to do, depends on a game logic *you* create. You can do a queue, you can skip. Depends on how you think your game should behave. Correct me, if I wrong on your question.
> 2 votes

# Answer
You can keep a number of the total resource demand per tick for all constructions. If one resource storage hits less than this required amount, then all construction would stop completely until the storage has gathered enough to support at least 1 tick of production. Then production can resume.

So instead of storing production rate as a float, it is binary - either your factory produces at full speed or it doesn't.

That being said, this approach is essentially the same as Jonathan's answer, for the production rate special cases 0.0 and 1.0 - an arbitrary float f with 0.0 \<= f \<= 1.0 is probably more elegant as you don't get jerky storage amount movements, but the logic should be a bit simpler.
> 1 votes

---
Tags: game-mechanics, rts
---


title: iPhone 3D Game Development using Maya?

text:
# Question
Title: iPhone 3D Game Development using Maya?
I'm reading up on 3D game development for the iPhone. I'm looking into programs like Unity for 3D development. My question is are these the best ways to go for 3D development for the iPhone-Unity or say Shiva? Is it common to use other 3D programs like Maya? What would be the disadvantages of using Maya or 3DsMax-or is this not even a possibility for iPhone development?

# Answer
> 5 votes
Maybe it's just a language barrier but there seems to be some misunderstanding here.

Maya and Max are 3D model authoring tools. Either one of these are going to spit out models that pretty much whatever 3D engine you want can use. It doesn't matter what platform it's going to be on. How else would you author 3D models for your 3D engine?

As far as "which one", well, http://blog.stackoverflow.com/2011/08/gorilla-vs-shark/

# Answer
> 1 votes
If you're going to be doing 3D Game Dev on the iPhone I would suggest:

http://iphonedevelopment.blogspot.com/2009/05/opengl-es-from-ground-up-table-of.html
He has code samples that imports models from blender.

Discussion of 3D Game Engines for iOS: http://iphonedevelopment.blogspot.com/2011/05/3d-game-and-graphics-engines.html

# Answer
> -3 votes
I'd say both are great packages.. Maya is a bit more geared towards Fikm as Max is to GAming.. but this line is pretty well blurred these days since Alias is now AutoDesk. Just grab whichever package people around you are using.. this way you have someone to talk to locally and swap ideas etc... and keep it simple.

---
Tags: 3d, ios, maya
---


# Question
Title: An odd performance problem rendering a simple scene (less than 14k vertices) in OpenGL using two vbos with LWJGL
**Problem**

I have been having a strange degrading performance issue rendering a simple scene containing two "chunks" of 4x4x4 cubes each.

**Video of problem**

This is a screen capture showing my console output, look specifically at the FPS dropping (which is the issue).

http://assets.cognitive.io/bugconsole.swf

**Details about problem**

My machine (a mid-2009 mbp 15") is on average using something like 10% cpu, but the machine is getting very hot to touch so I believe the graphics card is working very hard.

Someone else tested this code on another machine and experienced 100% cpu usage on a quad-core AMD cpu (on one core) and the same kind of performance problem.

I can't quite figure out what's going on, multiple people have looked at this and we are not getting any smarter.

Currently there is no frustum culling or any other sort of culling. I do not think that is the problem, I should be able to render a much much higher number of vertices without experiencing problems.

I have a list of chunks (ArrayList) that is created on start, not within the render loop, that generates a vbo and all that.

In my renderer I loop through the list of chunks and for each one I bind the vbo, setup some uniform variables and such before calling glDrawArrays().

I have a version of this where I only have one vbo (but then also only one cube per vbo/glDrawArrays call, very inefficient) where everything is working fine.

**Thoughts and ideas**

I believe the problem is something related to either VRAM filling up or me doing something incredibly wrong.

I've tried looking at my project with OSX's OpenGL profiler application, which has given me two different results:

First I was just using glBufferData each frame to pass the data, which resulted in 90% of the gl time spent being spent on CGLFlushDrawable().

After some advice from someone on #opengl on Freenode, it was suggested I should setup the vbo once with glBufferData, and then call glMapBuffer to pass the data after that.

This results in the same performance problem but 99% of the gl time being spent on glMapBuffer().

I was hoping someone had some advice for me, I would really like to just be able to continue learning opengl instead of being stuck debugging this performance issue for weeks.

**Code on GitHub**

The code is available at https://github.com/flexd/Game/tree/chunkrenderer (specifically the chunkrenderer branch!, you can see that the lighting2 branch works without the same performance issue).

The main game class is Game.java which contains the main method and it's also where I setup OpenGL.

Chunk.java, Cube.java, Renderable.java and ChunkRenderer.java are also of interest. Shader.java is where the shader class lives, but I doubt that has anything to do with the issues, it's basically the same shader as before.

Thanks in advance, I hope to be able to find the issue soon :)

Looking forward to being able to learn more of this.

PS: Let me know if I am posting this in the wrong place, I don't know if there's a opengl category that's better suited for this.

# Answer
I believe I've just fixed it myself!

I added a `boolean dirty = true;` to the Chunk class, with the default value of `true`, because I set the position initially.

I wrapped the entire code that generated the vertexData ByteBuffer in a `if (dirty) {}`

So that it only regenerates the vertexData buffer when the chunk has changed.

It's now rendering at 150+ fps.
> 1 votes

# Answer
When I was tracking down graphics performance issues early in the development of my game, I utilized a program called dDEBugger. From their site:

> gDEBugger is an advanced OpenGL and OpenCL Debugger, Profiler and Memory Analyzer. gDEBugger does what no other tool can - lets you trace application activity on top of the OpenGL and OpenCL APIs and see what is happening within the system implementation.

Not only is this a great tool, but it's free! Additionally, you can utilize CPU side profilers to asses memory usage and which calls are taking the most time. The built in for NetBeans is OK and there are some good ones for Eclipse too.

Beyond that I suspect your issue is with memory usage. I only looked at your code briefly, but I did notice things like generating a few new `FloatBuffers` per chunk per frame. Also, in `Chunk.java` after the initialization you're filling up `VertexData`, mapping `driverSideBuffer` then clearing `VertexData` then filling `driverSideBuffer` with an empty `VertexData`:

```
driverSideBuffer = glMapBuffer(GL_ARRAY_BUFFER, GL15.GL_WRITE_ONLY, driverSideBuffer);
vertexData.clear();
driverSideBuffer.clear();
driverSideBuffer.put(vertexData);
glUnmapBuffer(GL_ARRAY_BUFFER);

```

Now, since your drawing seems to be working, that's likely not a big issue, but it shows me that there are likely more subtle issues if this one has been missed.
> 3 votes

---
Tags: opengl, java, performance, lwjgl
---


# Question
Title: What are the disadvantages of using multiple inheritance to implement components?
I've been doing research on component-based game engines and would like to use that model for future game projects. From what I gather, objects in a component-based system are just collections of attributes and behaviors. The examples I've seen have a high-level interface such as `Attribute<T> *Entity::getAttribute<T>(int id)` but discussions about those systems often talk about performance problems. It seems like this could be implemented with greater efficiency in C++ using multiple virtual inheritance since the compiler could inline attribute accesses and behavior method calls:

```
// Layer 1: Base
struct Entity {
  virtual ~Entity() {}
  virtual void draw() {}
  virtual void update(float seconds) {}
};

// Layer 2: Attributes each extend from Entity
struct Position : virtual Entity { Vector3 pos; };
struct Velocity : virtual Entity { Vector3 vel; };
struct Health : virtual Entity { int health; };
struct Target : virtual Entity { Position *target; };

// Layer 3: Behaviors extend from the attributes they need
struct Renders : virtual Position {
  Model model;
  void draw() { model.draw(); }
};
struct Moves : virtual Position, virtual Velocity {
  void update(float seconds) { pos += vel * seconds; }
};
struct Seeks : virtual Moves, virtual Target {
  void update(float seconds) {
    if (target) vel = (target->pos - pos).unit();
    Moves::update(seconds);
  }
};

// Layer 4: Definitions extend from the behaviors they need
struct Rocket : virtual Health, virtual Renders, virtual Seeks {};

```

However, many component-based engine resources discount multiple inheritance without really saying why. I'm sure I'm missing something, but what are the disadvantages of using multiple inheritance like this over lists of components? I know calls to base classes when using multiple inheritance incur an additional constant offset, but that seems better than going through a run-time map for each attribute access. The only disadvantage that I can think of is not being able to swap out components at run-time.

Resources:

# Answer
Well, you pointed out The Big Disadvantage yourself:

> The only disadvantage that I can think of is not being able to swap out components at run-time.

Its direct consequence makes it a no-go... One of the most interesting feature of a component-based system is that it can be data-driven. By using inheritance, **creating a new entity kind means a recompile**. Compiling can be, very, very long. And worse, you're limiting that to *programmers* only.

Gajet gave some other valid points too, but to me that's the #1 problem with the approach you expose.

A detail: I've hardly ever seen virtual inheritance used in a game engine. It might be plain ignorance/laziness, or maybe there's never a good reason to use it, but I also suspect poor compiler support on consoles.
> 5 votes

# Answer
I can think of one or two reasons but I don't think they are not solid proof:

1. Using multiple inheritance as extensive at what you explained could easily get out of control. I know at first it seems it may help you along the way, but with a simple mistake you might end up with a bunch of code that generates a run-time error; Which you can't track down.
2. The whole multiple inheritance thing is based on too many memory jumps before calling each function. the same goes for each data lookup. So later when you need a high performance structure to do everything neat and fast you might end up with bunch of slow codes not allowing you to add any features.
3. Keeping the code simple is always the best strategy against large code bases. And games (specially in engine part) always end up having a large amount of code.
4. Though this might be the stupidest thing you've ever heard but working with an structure will lead somehow to being used to that structure. for example a person who works with C# almost always have a hard time switching to Java, though their syntax is very likely. I'm not saying he can't but he'll keep nagging about how good C# was and how bad Java is. multiple inheritance is something just a few languages implemented, so by using it you might later have a hard time switching to other languages.
5. With the exact same reason other languages doesn't support multiple inheritance yo might later get into trouble when porting your game to other languages. If you use common tools, you'll only need to change syntax while converting. But using multiple inheritance you need to convert the whole implantation method which takes as much time as writing a new code from scratch.

All that said I also think it would be nice if someone try that once and tell if he had a good experience with that kind of design. But you know existing mostly used structures are proved through the ages that can do any thing you want them to, so why do you want to change these well-proved mechanisms?
> 4 votes

---
Tags: c++, architecture, component-based
---


# Question
Title: 2D isometric: screen to tile coordinates
I'm writing an isometric 2D game and I'm having difficulty figuring precisely on which tile the cursor is. Here's a drawing:

where xs and ys are screen coordinates (pixels), xt and yt are tile coordinates, W and H are tile width and tile height in pixels, respectively. My notation for coordinates is (y, x) which may be confusing, sorry about that.

The best I could figure out so far is this:

```
int xtemp = xs / (W / 2);
int ytemp = ys / (H / 2);
int xt = (xs - ys) / 2;
int yt = ytemp + xt;

```

This seems almost correct but is giving me a very imprecise result, making it hard to select certain tiles, or sometimes it selects a tile next to the one I'm trying to click on. I don't understand why and I'd like if someone could help me understand the logic behind this.

Thanks!

# Answer
For accurate measure, we could consider following:

Lets first consider how to transform coordinates from isometric space, determined by i and j vectors (as in isometricMap\[i,j\]) or as the yt and xt on the screen, to screen space, determined by x and y of the screen. Lets assume your screen space is aligned at origin with isometric space for simplicity's sake.

One way to do the transform is to do a rotation first, then scale the y or x-axis. To get the necessary values to match your yt and xt I can't quite come up with on the spot here. You may create a matrix to do this or not and then use reverse matrix, but the reverse operation is basically what you want.

Scale the value in reverse and then rotate backwards to get the values and round downwards.

There are other ways to this I guess, but this seems most proper to me right now.
> 2 votes

# Answer
I had this same problem for a game that I was writing. I imagine that this problem will differ based on how exactly you implemented you isometric system, but I'll explain how I solved the problem.

I first started with my tile\_to\_screen function. (I assume that's how you are placing the tiles in the right location in the first place.) This function has an equation to calculate screen\_x and screen\_y. Mine looked like this (python):

```
def map_to_screen(self, point):
    x = (SCREEN_WIDTH + (point.y - point.x) * TILE_WIDTH) / 2
    y = (SCREEN_HEIGHT + (point.y + point.x) * TILE_HEIGHT) / 2
    return (x, y)

```

I took those two equations and made them into a system of linear equations. Solve this system of equations in any method you choose. (I used a rref method. Also, some graphing calculators can solve this problem.)

The final equations looked like this:

```
# constants for quick calculating (only process once)
DOUBLED_TILE_AREA = 2 * TILE_HEIGHT * TILE_WIDTH
S2M_CONST_X = -SCREEN_HEIGHT * TILE_WIDTH + SCREEN_WIDTH * TILE_HEIGHT
S2M_CONST_Y = -SCREEN_HEIGHT * TILE_WIDTH - SCREEN_WIDTH * TILE_HEIGHT

def screen_to_map(self, point):
    # the "+ TILE_HEIGHT/2" adjusts for the render offset since I
    # anchor my sprites from the center of the tile
    point = (point.x * TILE_HEIGHT, (point.y + TILE_HEIGHT/2) * TILE_WIDTH)
    x = (2 * (point.y - point.x) + self.S2M_CONST_X) / self.DOUBLED_TILE_AREA
    y = (2 * (point.x + point.y) + self.S2M_CONST_Y) / self.DOUBLED_TILE_AREA
    return (x, y)

```

As you can see, it's not simple like the initial equation. But it does work nicely for the game I created. Thank goodness for linear algebra!

*Update*

After writing a simple Point class with various operators, I simplified this answer to the following:

```
# constants for quickly calculating screen_to_iso
TILE_AREA = TILE_HEIGHT * TILE_WIDTH
S2I_CONST_X = -SCREEN_CENTER.y * TILE_WIDTH + SCREEN_CENTER.x * TILE_HEIGHT
S2I_CONST_Y = -SCREEN_CENTER.y * TILE_WIDTH - SCREEN_CENTER.x * TILE_HEIGHT

def screen_to_iso(p):
    ''' Converts a screen point (px) into a level point (tile) '''
    # the "y + TILE_HEIGHT/2" is because we anchor tiles by center, not bottom
    p = Point(p.x * TILE_HEIGHT, (p.y + TILE_HEIGHT/2) * TILE_WIDTH)
    return Point(int((p.y - p.x + S2I_CONST_X) / TILE_AREA),
                 int((p.y + p.x + S2I_CONST_Y) / TILE_AREA))

def iso_to_screen(p):
    ''' Converts a level point (tile) into a screen point (px) '''
    return SCREEN_CENTER + Point((p.y - p.x) * TILE_WIDTH / 2,
                                 (p.y + p.x) * TILE_HEIGHT / 2)

```
> 4 votes

# Answer
You're using a good coordinate system. Things get much trickier if you use staggered columns.

One way to think about this problem is that you have a function to turn (xt, yt) into (xs, ys). I'll follow Thane's answer and call it `map_to_screen`.

You want the *inverse* of this function. We can call it `screen_to_map`. Function inverses have these properties:

```
map_to_screen(screen_to_map(xs, ys)) == (xs, ys)
screen_to_map(map_to_screen(xt, yt)) == (xt, yt)

```

Those two are good things to unit test once you have both functions written. How do you write the inverse? Not all functions have inverses but in this case:

1. If you wrote it as a rotation followed by a translation, then the inverse is the inverse translation (negative dx,dy) followed by the inverse rotation (negative angle).
2. If you wrote it as a matrix multiply, then the inverse is the matrix inverse multiply.
3. If you wrote it as algebraic equations defining (xs, ys) in terms of (xt, yt), then the inverse is found by solving those equations for (xt, yt) given (xs, ys).

Be sure to test that the inverse + original function give back the answer you started with. Thane's passes both tests, if you take out the `+ TILE_HEIGHT/2` render offset. When I solved the algebra, I came up with:

```
x = (2*xs - SCREEN_WIDTH) / TILE_WIDTH
y = (2*ys - SCREEN_HEIGHT) / TILE_HEIGHT
yt =  (y + x) / 2
xt =  (y - x) / 2

```

which I believe is the same as Thane's `screen_to_map`.

The function will turn the mouse coordinates into floats; use `floor` to convert them into integer tile coordinates.
> 2 votes

---
Tags: geometry, isometric, coordinates
---


# Question
Title: What are the advantages of having a real time based physics?
> **Possible Duplicate:**
> Fixed time step vs Variable time step

Now just let me clarify what I mean by "real time based physics", which I will call RTBP from now on. Well, basically, it implies taking, you guessed it, actual time into calculations.

For example:

```
timePassed = time - lastTime

positionx += vx*timePassed
positiony += vy*timePassed

lastTime = time

```

This would be a simple RTBP model. What's the alternative? I call it "step based physics" (SBP from now on), which would just be this:

```
positionx += vx //v in SBP is obviously smaller than in RTBP
positiony += vy

```

I currently use SBP, but I see that many people actually include time in their calculations. Why is that? I of course limit the update time to 1000/60ms.

Once the update interval is limited, both models would behave the same. The only difference is when the FPS drops. I believe that here is where PBS excels over RTBP. In PBS the game would, yes, run slower, but would always produce the same results! In RTBP, the position might increase so much that an object actually passes through a wall!

Anyway, there must be something that I'm missing.

# Answer
> 2 votes
RTBP (as you've written it) can't detect collisions if the time step is too big - objects may jump so much they simply don't ever overlap to cause a collision. Of course the same is true of SBP if the step is too big. It's true for both if the movement is very fast and/or objects are small enough to just skip over each other.

Unless there was a compelling reason to write my own, I'd go with one of the existing physics engines myself - they've solved a lot of these problems before.

---
Tags: physics
---


title: Averaging Camera Position

text:
# Question
Title: Averaging Camera Position
I'm making a camera which tracks the player. I am using a basic algorithm to calculate a position for the camera relative to the player. Then I am taking an average of this over the last x number of frames. This creates a nice chase camera which always slightly lags and evens out the players movements.

Where I am running into trouble is with delta Time. How can I weight each entry in my list of previous positions so that delta time is taken into account. Currently I'm having an issue where, when the frame rate is particularly slow, the camera lags really far behind the player.

I should also mention that currently I am adding each entry ElapsedTimeInSeconds/0.01f times to give the weight. So the average is effectively over fewer frames if the frame rate is slow. I also tried entering values as Value * DeltaTime, then keeping an average of delta time to divide the values by when I get them back out of my average tracking class but that didn't work.

What I think I really want is an average over the last n seconds rather than the last n frames.

# Answer
Because your historical positions are recorded with delta time "baked in" applying any corrections on top of that seems excessive if not counterproductive. You don't want to change their values, but you do want to change how much the history affects the current target position.

This might work for you:

Pick an ideal framerate, say 1/30, and use that as a baseline to represent 100%. This 100% applies to how much the history affects the current camera target so at any framerate of your ideal 1/30 or faster your tracking acts as normal.

When your framerate slows down below 1/30 you want that 100% to drop so that the historical positions affect less and less of the camera's current target which will ease the camera closer to your target the slower the game is running.
> 1 votes

---
Tags: game-design, mathematics, camera
---


# Question
Title: 2D sprites not drawing at correct depths?
I've been having some problems with getting my sprites to draw in the correct order.

Right now there are 2 types of objects: nodes and paths. I always want the nodes to draw over the paths so I have set the depths of the nodes to 0 and the depth of the paths to 1. They're being drawn in the same SpriteBatch call and I'm using SpriteSortMode.Deferred yet the paths are still being drawn on top of the nodes.

I've tried swapping the depths of these and they still draw in the wrong order. I've also tried switching the sort mode to BackToFront and FrontToBack but both of those mess up the graphics for the rest of the game so it's not really worth switching to either one of those.

Is there something obvious that I'm doing wrong? Is changing the draw order (paths are always drawn after nodes) the only way to get the nodes drawing on top of the paths?

Thanks!

# Answer
From the SpriteSortMode documentation you can see that sorting by depth only happens in `BackToFront` or `FrontToBack` modes, while `Texture` sorts by texture, and the other two don't sort at all.

Since you wrote that these modes bring you problems elsewhere, my recommendation is to divide the draw call into two layers, and stop relying on the `depth` parameter.

The easiest way is to keep two separate lists, one for paths and one for nodes, and render them in that order using the default `SpriteBatch` mode which is `Deferred`:

```
var _paths = new List<Sprite>();
var _nodes = new List<Sprite>();

_spriteBatch.Begin();
_paths.ForEach(s => s.Draw(_spritebatch));
_nodes.ForEach(s => s.Draw(_spritebatch));
_spriteBatch.End();

```
> 3 votes

# Answer
Deferred and Immediate both draw in the same order as your SpriteBatch.Draw calls, the depth value is ignored. Use either FrontToBack or BackToFront (In your case FrontToBack sounds best).
> 0 votes

---
Tags: xna, 2d, spritebatch
---


# Question
Title: C# OpenTK - Getting world coordinates of points that are altered by matrices
I have written a skeletal animation system for a game I am working on. To draw lines that represent a skeleton, I use the GL matrix, and multiply it by each bone a long the body. For example before drawing the left hand, GL.multMatrix has been called for the lower back, upper back, left shoulder, left upper arm and left lower arm.

Currently I am now trying to deal with hitboxes. After this series of matrix transformations have been made, I am drawing a box with the local coordinates of -2,-2,-2 to 2,2,2. This works fine, the animated skeleton has a box around the hand.

However I've reached the stage of actually needing to use the hitbox, to check if it collides with another hitbox. I've worked out the algorithms I shall use for checking if there is a collision, but I first need to change those coordinates from their local to the hand coordinates, into coordinates I can use against other things in the world.

For example the left hand hitbox has the same local coordinates as the right hand hitbox, but how could I change that all back to global coordinates so I can get their proper world coordinates?

# Answer
OpenGL stores its model matrix and view matrix together. As far as i know, you can't separate them once they are together.

To solve this, i simply ended up storing my own model matrix, which i then used GL.MultMatrix() to combine with the view matrix when it came time to draw. To access coordinates all i had to do then was to get M41, M42 and M43 (x, y and z) from the model matrix, and to get offset coordinates for a box, creating a translation of the offset of each vertex gave me the new coordinates of each respective vertex.
> 1 votes

---
Tags: c#, opengl, collision-detection, opentk
---


# Question
Title: Present fails randomly on mixed C++ Direct3D9 app
I have a mixed .NET application (managed and unmanaged code bridged by C++/CLI wrappers) which uses unmanaged Direct3D9 9.0c to do rendering inside a control which is wrapped inside a C++/CLI class which extends System.WIndows.Forns.UserControl.

Everything has been working fine for years now, but I recently put another instance of this Direct3D9 control inside a new Windows Form. That is, I have two concurrent instances of the control. I had done that before and it worked, but now I have issues. Perhaps the problem was always there, but because it's related to a race condition, it started happening now...

Ok, the details: When I try to render an image over a texture on the new instance of the control, sometimes it works, sometimes it doesn't. And when it doesn't, nothing is rendered, and from that point onwards, all Present calls fail (I log those failures). If I close the form and open it again, it might work or not. Nasty.

If I use DXGetErrorString and DXGetErrorDescription, all I get is something like:

> EFAILED Undetermined error

Not really helpful... To make matters worse, I can't reproduce the issue in my development environment; I only see it in a production box.

As far as I know, the main reason Present fails like this is a Lost Device. But I implemented the usual scheme to handle that (I can post the code if necessary), and it seems like the device is not being lost... What else can I try?

# Answer
You will likely get your answer by viewing debug output.

Really, it's like a whole set of documentation there, embedded right in the debug spew. Run in debug mode and view the output in Visual Studio, or use a program like DebugView to see the messages. Be sure to enable the D3D9 debug runtime as the diagrams show in the linked answer above.
> 1 votes

---
Tags: c++, windows, directx9, windows-forms, c++cli
---


title: Rotating a vector by a quaternion

text:
# Question
Title: Rotating a vector by a quaternion
I am trying to rotate a direction vector (0,0,1,0) by a rotation quaternion in DirectX.

From what understanding, to rotate the vector you must do

```
NewVector = rotQuaternion * Vector * inverse(rotQuaternion)

```

In directX11, I am testing out the algorithm above using an identity quaternion.

```
XMVECTOR qIdentity = XMQuaternionIdentity();
XMVECTOR inverse = XMQuaternionInverse(qIdentity);
XMVECTOR test = qIdentity * XMVectorSet(0.0f,0.0f,1.0f,0.0f) * inverse;

```

My new test vector should just be (0,0,1,0), however it is completely zeroed out, and I am not exactly sure why or if I multiplied it correctly.

# Answer
Quaternions do not multiply component-wise like vectors, thus the `*` operator must not be used here.

```
XMVECTOR qIdentity = XMQuaternionIdentity();
XMVECTOR inverse = XMQuaternionInverse(qIdentity);

XMVECTOR test = XMQuaternionMultiply(qIdentity,
                                     XMVectorSet(0.0f,0.0f,1.0f,0.0f));
test = XMQuaternionMultiply(test, inverse);

```
> 2 votes

---
Tags: xna, directx, vector, quaternion
---


title: Render 3D torus shape entirely in GLSL

text:
# Question
Title: Render 3D torus shape entirely in GLSL
I was wondering, is it possible to render a (3D) torus shape entirely in GLSL, i.e. without using vertex/index arrays? Suggestions are welcome, thanks.

# Answer
You can use distance functions described in here: http://iquilezles.org/www/articles/distfunctions/distfunctions.htm
> 5 votes

# Answer
One can use different approaches, but the best way to my mind is to code your own renderer in the fragment shader. Some ray-tracer or ray-marcher. In both cases you will need function that builds ray for current pixel on the screen. Next you can analytically find intersection of ray with torus (ray-tracer), or iteratively step along your ray until you encounter torus (ray-marching). In the latter case distance field is the best solution. See *artificialidiot's* answer.

Some links:

1. Raytracing Topics & Techniques by Jacco Bikker
2. A raytracer in C++
3. introduction to raytracing
4. simple gpu raytracing
5. terrain marching

For advanced studying of ray-tracing see this book.

Ray-tracing example:

Ray-marching example:
> 2 votes

# Answer
Not really an answer, but I can't post comments yet..

In Directx you can make Draw(x, 0) calls, x being the number of vertices to draw, and should no vertex buffer be bound it will auto-generate x vertices with no attributes except a unique ID. If something similar is possible in openGL...

You could then pass these vertices with just an ID through to a geometry shader, and use the ID\*4 to determine the position on the torus, and generate a quad for each ID. Think of the torus' surface flattened out as a simple plane of rows by colums. For example, (int)((ID\*4) / number\_of\_minor\_segments) would give you the row offset along the length of the torus' surface, and ((ID\*4) % number\_of\_minor\_segments) would give you the column offset in the current row, minor segments beingt the number of segments you want around the minor radius.

You can calculate the offsets of the next 3 vertices by doing the same for (ID\*4)+1, +2, and +3.

Map the offsets from "torus coordinates" to object then to world space, then send two triangles (from vertices 0, 1, 2; 2, 3, 0) to the rasterizer.

Of course the geometry would be re-generated every frame. Why do you want to avoid vertex buffers in the first place?
> 1 votes

# Answer
If you're using a wrapper for OpenGL, like GLUT, there are often built in methods to render basic shapes. For example there is glutTorus() in the OpenGL wrapper GLUT to draw a torus without having to set anything up.

As for the comment about impostors by Nicol Bolas, I'm not sure if it's helpful in this case. All I could find with a quick search was True Impostors in which case you indeed don't have to set up vertex and index arrays but I think this method might be more advanced than you need.

Anyway, if you can explain us better why you don't want to set-up a vertex and index buffer we can come up with better solutions.
> 0 votes

---
Tags: opengl, shaders, glsl
---


title: Best practices, extending classes

text:
# Question
Title: Best practices, extending classes
I'm developing a game in XNA(C#) and I wonder what are the best practices for having different types of pads. For example I have 2 types of pads:

* Pad that just moves left (decreasing X coordinate)
* Pad moves left and moves up and down (cos function on Y coordinate)

Later I would like to implement more pads. I know I could check type in `Update` method and do a proper method for updating but I think it could be done better. I have the Pads class:

```
class Pads
    static list of pads;
    public void draw();
    public static void drawAll(); //Iterate through list and draw each item
    public void update();
    public static void updateAll(); //Iterate through list and update each item

```

Should I create another class for example cosPad which would extend Pads?

I really don't have idea how to make everything logical.

# Answer
> 6 votes
If the pads are only different in their movement/behavior I would create a separate class to control this and use composition to get the desired effect.

```
public class Pad : GameObject{
    Vector2 Position;
    Behavior B;

    Update(GameTime t){
        B.Update(this, t);
    }
}

public class Slide : Behavior{
    Update(GameObject o, GameTime t){
        o.Position.X = sin(t);
    }
}

public class Circle : Behavior{
    Update(GameObject o, GameTime t){
        o.Position.X = sin(t);
        o.Position.Y = cos(t);
    }
}

```

# Answer
> 0 votes
You could create an abstract class `Pad` that represents a moveable pad, then your `Pads` class would have a list of these `Pad`s.

The `Pad` class could have an implemented draw method if that was common to both, and an abstract `Update(GameTime)` method.

You'd derive your 2 concrete classes `PadMoveLeft` and `PadCosine` from `Pad` which would implement `Update`.

---
Tags: xna, c#, architecture
---


title: Reflect angle on pong clone

text:
# Question
Title: Reflect angle on pong clone
I'm working on collision detection for a pong clone. I've calculated the angle of incidence but I can't find any information on how to specular reflect the angle I found.

The code for calculating the angle of incidence is below

```
 if (ballPosition.Y >= height - 6)
  {
    Vector2 bottomNormal = new Vector2(400, 460) - new Vector2(400, 480);
    Vector2 ballNormal = ballPosition - new Vector2(400, 480);
    ballNormal.Normalize();
    bottomNormal.Normalize();

    float angle = Vector2.Dot(bottomNormal, ballNormal);
 }

```

# Answer
Well done knowing the terminology to describe your problem. The specular reflection angle can be found with the following formula (in pseudo code):

```
reflectionAngle = 2*(dot(normalVec,incidenceVec))*(normalVec-incidenceVec);

```

Essentially you want to find the vector that is the same degrees of rotation from the `bottomNormal` as your angle of incidence. In the image below, the angle of incidence you're finding would be `θi` and the normal is your `bottomNormal`, making `P` your angle of incidence and `Q` the vector you want to find. Note that `θi` and `θr` are equal.

Source: Wikipedia
> 1 votes

# Answer
For the specific instance of a Pong clone you can cheat with this problem and flip the sign of your velocity vector component in the axis normal to the collision surface. Since in pong all surfaces have normals that match the coordinate system you can just flip the sign for the component on a per surface basis.

In code:

```
if (x_ball_position >= x_upper_limit || x_ball_position <= x_lower_limit)
{
    x_velocity = -x_velocity;
}
if (y_ball_position >= y_upper_limit || y_ball_position <= y_lower_limit)
{
    y_velocity = -y_velocity;
}

```
> 3 votes

---
Tags: xna, collision-detection
---


title: How to get file paths in XNA 4.0?

text:
# Question
Title: How to get file paths in XNA 4.0?
Is it possible to use OpenFileDialog in XNA 4.0 to get the file path? If not, what is the alternative? I'm using XNA 4.0 to create a graphic display (not a game) and I have a file that contains informations on how and what to draw on screen. The only problem is that I hard-coded the path because I don't know how to dynamically get that path? Do you know a solution for that?

# Answer
Just put the Attribute \[STAThread\] above the Main method in the class Program and add the System.Windows.Forms in the References of the project.

After that you'll be able to instantiate and invoke the dialog boxes.
> 6 votes

---
Tags: xna-4.0
---


# Question
Title: How do I find the angle between two vectors?
I have 3 points on my screen:

```
a = a point which is (c.x, 0) makes a line pointing straight up
b = a user input touch, can be anywhere on the screen
c = a moving object

       a
_______.________
|      |       |
|      |       |
|   b  |       |
|  .   |       |
|   \  |       |
|    \ |       |
|     \|       |
|      | c     |
|______._______|

```

I have drawn some lines so that you can see the vectors.

I want to be able to get the angle between a and b. I have tried this, but it doesn't work, does anyone know what I'm doing wrong?:

```
//v1 moving object
float boxX = this.mScene.getLastChild().getX();
float boxY = this.mScene.getLastChild().getY();

//v2 user touch
float touchX = pSceneTouchEvent.getX();
float touchY = pSceneTouchEvent.getY();

//v3 top of screen
float topX = boxX;
final float topY = 0;

float dotProd = (touchX * topX) + (touchY * topY);

float sqrtBox = (touchX * touchX) + (touchY * touchY);
float sqrtTouch = (topX * topX) + (topY * topY);

double totalSqrt = sqrtBox * sqrtTouch;
double theta = Math.acos(dotProd / Math.sqrt(totalSqrt));

```

The answer I usually get is between 0 and 1. How do I fix this so that I get the angle in degrees?

# Answer
> 16 votes
You are looking for the wondrous atan2.

```
// v1 moving object
float boxX = this.mScene.getLastChild().getX();
float boxY = this.mScene.getLastChild().getY();

// v2 user touch
float touchX = pSceneTouchEvent.getX();
float touchY = pSceneTouchEvent.getY();

double theta = 180.0 / Math.PI * Math.atan2(boxX - touchX, touchY - boxY);

```

Normally it is used as `atan2(y,x)` but since you are looking for the angle with the vertical line, you need to use `atan2(-x,y)` instead.

# Answer
> 2 votes
I see you use dot product, try invcos(value) it might do the thing (but not sure).

Otherwise just do it the 'regular' way with atan2(dy/dx):

```
b=b-c:
angle=atan2(b.y, b.x);

```

---
Tags: java, android, vector, andengine
---


title: Free voxel editor?

text:
# Question
Title: Free voxel editor?
Does anyone know of a good free voxel editor and/or voxel-to-mesh converter?

# Answer
> 12 votes
Thermite3D is a voxel-based game engine. It isn't an editor per se. It does, however, have a list of voxel editors on its wiki here: Thermite-Recommended Voxel Editors.

Of those, Sproxel, Voxel, and QBlock are all free. Paint3d and Everygraph (Voxel3d) have trial versions, and one not on the list, Qubicle Constructor, has a crippled trial as well.

# Answer
> 5 votes
I wrote one for my Voxel Roguelike. You can get it here: link

If you need some info on the file format, just post a question on the blog and I can help you out.

# Answer
> 4 votes
There's also Thermite3D. I've looked at it a little but haven't actually used it. The forum community is very friendly and helpful, however.

# Answer
> 4 votes
You can try this (highly experimental)

http://popelka.misto.cz/cubes/cubes.htm

# Answer
> 2 votes
You could try this one http://dmytry.pandromeda.com/voxelworld/, though I think it's not being maintained anymore (still, it's open-source, should you want to mess with the code).

# Answer
> 0 votes
This is the one I use, by Eric Haines: http://www.cs.princeton.edu/~min/binvox/

---
Tags: tools, models, editors, voxels
---