title: How to promote my free javascript game?

text:
# Question
Title: How to promote my free javascript game?
> **Possible Duplicate:**
> Effective marketing strategies for independent game projects

I created a javascript game for browsers.
Do you know easy ways to promote it?

# Answer
Google has an excellent advertising network that reaches many very large audiences. You can do some advertising with it for very low cost that you are in complete control of, and there's no limit to the number of keywords/phrases you can specify that will trigger your ads to appear.

Google AdWords
http://adwords.google.com/

I suggest starting off with a minimal amount with them, such as $100.00 (or whatever you think seems reasonable), and try to stretch it out over the course of 1-3 months (you can specify the maximum per day with their system).

I've had a few clients experiment with this, and for some it worked out really well, yet for others it resulted in no new traffic or sales. I've found the staff at Google to be very helpful too.
> 0 votes

---
Tags: marketing
---


# Question
Title: Are game programmers aware of all the physics derivatives?
I am trying to study XNA for game programming. XNA has many methods that can simplify developer's life, such as reflecting the vector when it hits a solid plane.

I know these are good and developers almost always work at an abstracted level, which is also the basic fundamental of OOP. I am not comfortable with physics, nor have I studied physics anytime during my schooling and so it gets difficult for me to understand how these abstracted methods work.

Do developers need to be physics gurus in order to make good, not necessarily excellent, games? Are all professional game developers good at physics? Put simply, are they all Einstein types? Or is it just fine even we are not aware of what goes under the hood in abstracted XNA methods?

# Answer
Developers don't need to be physics experts to make good games. If you're developing a physics based game like Gish for example, at a minimum you need to understand how to properly use your physics library.

There are tons of great physics libraries out there and IMO it's more important that you understand how use a library and iterate on your implementation to make something fun than understand the math at a deep level. Of course understanding the math helps too :)

I made my own soft body physics game for XBLIG a couple years ago and my physics code was mostly based around implementing the math for springs and pressure bodies.
> 10 votes

# Answer
You can't get much better than the answers to this question :-)
What math should all game programmers know?

Also, just to be clear, XNA itself doesn't provide any physics functionality. For that, you will need to look to an engine like Velcro Physics (formerly Farseer Physics) which is based on Box2D.
> 7 votes

# Answer
Lets step back a bit - as much as it might seem challenging to implement physics in games (or not, depending on your experience), this is really basic physics we are talking about here - usually nothing much more complicated than equations of motions + gravity or thermodynamics equations.

Einstein developed general relativity (with a heavy dosage of tensor math) and quantum mechanics, which are orders of magnitude more difficult to understand and calculate compared to those classical and usually simplified topics covered in games. In fact, most of the physics covered in computer games can be learned at the high-school level (at least, where I went to it was being taught).

If you finished a degree in CS (or even if you didn't), getting those equations down and understanding how they work shouldn't be a problem for a decent programmer.
> 5 votes

# Answer
You only need as much physics as your game needs. Some games don't have "physics" at all. At most you'll find games use at most your standard F=ma type algorithms. The hard part is not the physics itself, but how to make it so your simulations are fast, stable, and predictable.
> 4 votes

# Answer
When hiring programmers, we ensure they understand and can solve problems with basic 3D vector math: dot products, cross products, simulating simple trajectories, etc. Reflecting a vector is a perfect example of a question we might ask. A working knowledge of basic 3D math is crucial for developing 3D games.

That said, very few professional game developers have the knowledge to write a good physics engine. This is still a very specialized skill.

If you want to go pro, I strongly recommend that you learn to be comfortable with basic vector algebra. If you don't, you will eventually struggle to keep up, even in 2D games.
> 2 votes

---
Tags: xna, mathematics, physics
---


# Question
Title: How can I apply a shader to images in a map in XNA?
Basically, what I'm trying to do is apply a shader to my background image and only the background image. The problem is: the background is actually made up of tiles that are picked out of a list of images. The background code loads and draws the tiles according to a map (an int\[,\].) I've been reading up on using RenderTarget2d, but I haven't found anything that suggests I'd be able to use specific images (let alone images set up according to a map.) So here's my question: is there a way to render my backgrounds to a texture so I can apply a shader or is there another way for me to apply a shader that I might want to try?

# Answer
> 0 votes
You seem to have already figured out how to do this. Here's the process:

```
GraphicsDevice.SetRenderTarget(myRenderTarget);
RenderMyBackground();
GraphicsDevice.SetRenderTarget(null);
spriteBatch.Begin(SpriteSortMode.Deferred, null, null, null, null, myShaderEffect);
spriteBatch.Draw(myRenderTarget, Vector2.Zero, Color.White);
spriteBatch.End();
RenderEverythingElse();

```

You may want to have a look at the Bloom Postprocess sample. There's no reason you have to apply a post-process effect to your entire scene. You can apply it to just your background and then draw the rest of your scene over the top.

---
Tags: xna, tiles, maps, shaders
---


# Question
Title: What 3D level development tools are available to indie developers?
People who build in Unity or UDK have immediate access to a 3D level editor. People who build their games in XNA or from scratch have no such thing. I'm looking for 3D level development tools available to these people.

* It must be free, or affordable to an indie developer. I leave the term "affordable" open to interpretation.
* It must not be restricted to a specific game engine. I should be able to build my game from scratch and use this level editor to construct my levels.
* It should have a file format that comes with an interpreter, or sufficient documentation for me to be able to build my own interpreter.
* Open source and/or modifiable/customisable is a plus, but not a requirement.

I know beggars can't always be choosers, but I'm hoping there's something high quality out there.

If there isn't, maybe someone would like to jump on that opportunity and fill the void.

# Answer
You can use Blender 3D as level editor. In new version, it can export scene in COLLADA format which is very easy to parse. For special objects, just add tags, and then search for such tags in level loading script.

With similar workflow, you can use any ordinary 3D tool, just add tags to objects and then do something in your game about this tags.

I use this workflow in panda3D and it is very good!

In the case of using COLLADA files, there is a pre-existing C# library that parses the XML for you.
> 14 votes

# Answer
GtkRadiant, the primary editor for the Quake family of engines, is an open source level editor that may be something you want to look into.

* 100% free, licensed under GPL
* Not restricted to a specific engine
* Generates .map files which can be compiled using Q3map2 (also open source) into the Quake 3 BSP format. BSP loading code from the Q3 engine can be utilized in your own software.
> 8 votes

# Answer
A quick google gave me Getic \- you can browse the source, and I can't tell if it's free or something like $5 CAD per license.

A slightly out-of-the-box solution is to implement your own. There's a chapter on doing it in Game Coding Complete, and it really isn't too difficult. It's also guranteed to be free (except the book which earns that back via general usefulness) and does exactly what you want.
> 7 votes

# Answer
DeleD is a level editor for Windows. It saves to its own format and COLLADA so it's easy to read the levels to your own game.
> 4 votes

# Answer
After using some modeling tool to build the geometry, a great free tool for lighting your level is gile\[s\]

http://www.frecle.net/index.php?show=giles.about
> 2 votes

# Answer
Blender is probably the most advanced of free 3D editors, featuring modeling, IK, rendering, physics, etc.
**Update:** it is extensible with Python, and supports many output formats (see Import/Export page), including md5 (Doom 3), Neverwinter Nights and Crystal Space engine file formats.
> 1 votes

---
Tags: 3d, level-design, tools
---


# Question
Title: How to avoid collision detection to enter infinite loop in this case?
I am writing a collision detection system which uses the logic mentioned by Trevor here

But I have anticipated a problem which I have shown as a diagram

How do we handle this problem?

# Answer
Solution: You only detect and react to a collision on an object once per frame. This would move the second collision detection in step 3 to the next frame so that it will not enter an infinite loop and freeze.

Problems with the solution: If the two objects are not springs, but are instead solid objects you will see an age-old problem where it will look like the object shoots out at very high velocities from where it was. This may or may not be an issue either by the design of the game in question or simply because it would not matter if it does happen. Two common solutions when this happen, both of which require detection of the situation, is to remove the object either outright, or apply damage to it or the like or to alternately scan for the nearest 'open' area and move the object to that location.

Hope this helps
> 4 votes

# Answer
As James says, in many types of games, this sort of issue doesn't really matter much. But in others; particularly in games with fast-moving objects, it's critically important to get this right to handle complicated bounces in corners. So probably the smart thing to do is to ignore the problem unless it's actively causing problems for you. If it's causing problems, then here's how you handle it:

When your collision system is checking for collisions, instead of simply resolving collisions as you find them, you instead make a big list of all the collisions you find during the frame, and sort them according to the time-within-the-frame at which the collisions occurred. (your collision system will need to know about object velocities in order to calculate the time within the frame at which the collision occurred)

Once you have this sorted list, you resolve those collisions in order, from first to last. When performing the collision resolution, you need to use the "remaining frame time" as a parameter to the collision resolution function.

So here's a step-by-step version of this process, in the case of the situation shown in your diagram:

1. Find the collision between Obj and Spring2, which happened at (let's say) 3 milliseconds out of our 16 millisecond frame duration. No other collisions found.
2. No other collisions, so resolve that first collision, which results in Obj moving left from the collision point, with 13 milliseconds left of frame time remaining.
3. Since an object moved, we now need to check for collisions for the remaining 13 milliseconds of frame time. We find that now, Obj is colliding with Spring1, which happened at (let's say) 8 milliseconds out of our 16 millisecond frame duration.
4. No other collisions, so resolve the one collision we have, which results in Obj moving back to the right from the collision point, with 10 milliseconds of frame time remaining.
5. Repeat

Note that if implemented correctly, Obj should be moving a smaller and smaller distance with each bounce, because the collision resolution is covering a shorter period of time within the frame at each iteration, and so eventually, Obj will be bouncing a small enough distance to no longer collide with the opposite spring within the frame duration.

Also note that it's still possible to get into an infinite loop if Spring1 and Spring2 are immobile objects and are placed so closely together that Obj doesn't actually fit between them, so it's important to have some maximum number of times that your collision system will iterate per frame. The faster your objects can move, the more iterations you need to support, to handle common "complicated bounce" situations. But in general, four or five iterations is a reasonable maximum for most games.
> 3 votes

# Answer
The reason that this situation happens is because you didn't take away any kinetic energy from the object, which is unrealistic- you even added it and made it go further. When an object impacts a spring, it doesn't rebound further or even as far as it came from- it rebounds less. By simply returning the object with *less* velocity/force/energy than it came in with, you should be able to ensure that this case never happens.
> 2 votes

# Answer
If I were to solve this problem, I'd take these two steps.

**Step1: Infinite collision detection:** This scenario occurs when the Object repeats its collision with the same set of springs for unreasonable amount of time. So for every collision with a spring, I would check whether the last X no. of collisions(say 50 times), has occurred between the same set of springs. I'd just check between the current 2 collided springs with the last 2 collided springs and maintain a counter and when the counter reaches X, I'd call it as infinite loop.

**Step2: Preventing the infinite loop:** Once we identify the infinite loop, we can handle it however we want. Eg. Restarting the game or Stop the object from moving further or bringing the object to the starting position.

I'm new to game development. Feel free to correct me.
> 0 votes

---
Tags: collision-detection
---


title: Implementing Wall Jumping

text:
# Question
Title: Implementing Wall Jumping
I've read this wall jumping question but I'm having trouble implementing it. I've gotten as far as implementing a timer that controls when wall jumping is possible. Right now, if I go up against a wall, then jump, I'll have a timer that will later run out (and then I won't be able to wall jump in mid air).

However, I'm not sure how to implement it. I see two problems here - one is to determine the direction the player should go, and how to cancel out the effects of holding down a directional arrow key and counteracting the velocity I would apply when I jump off the wall. Also, I'm having troubles of determining when I hit *another* wall, so I can wall jump again.

# Answer
This is pretty dependent on how you're doing your collision detection. For example, for the "direction" question ... if you define your levels as polygons and do your collision detection that way, then it would be pretty trivial to determine the perpendicular vector to the line that you are colliding with ... that would be the direction that you would "jump" in.

For the effects of holding down the arrow key, ideally you would do nothing. Once you determine the direction of the jump, you would change the player's velocity in that direction to propel them. Once they are in the air after they've done the wall jump, why shouldn't the arrow keys affect their trajectory? I mean, of course that entirely matters on your game's control scheme since some games don't let you control the character in the air ... but even in that case, the default behavior *should* handle it because input would be disabled while in the air.

as to the question about how to determine when you hit another wall ... this shouldn't be a problem, and if it is it's indicative of an issue with the code's design. You should really put this logic inside of some sort of "Entity". Good object oriented design isn't a panacea, but it can go a long way to mitigating the complexities of a system like a game.
> 4 votes

---
Tags: xna, c#, game-mechanics
---


title: Half-Life 2 BSP Lightmaps

text:
# Question
Title: Half-Life 2 BSP Lightmaps
I'm writing a BSP viewer for a university project. So far I have the main geometry loaded properly, and the PVS working.

Now I'm trying to apply the lightmaps, but I can't seem to get the texture coordinates for the lightmaps calculated properly.

According to here: http://developer.valvesoftware.com/wiki/The\_Source\_Engine\_BSP\_File\_Format

```
struct texinfo_t
{
    float textureVecs[2][4];  // [s/t][xyz offset]
    float lightmapVecs[2][4]; // [s/t][xyz offset] - length is in units of texels/area
    int flags;                // miptex flags overrides
    int texdata;               // Pointer to texture name, size, etc.
}

```

> The first array of floats is in essence two vectors that represent how the texture is orientated and scaled when rendered on the world geometry. The two vectors, s and t, are the mapping of the left-to-right and down-to-up directions in the texture pixel coordinate space, onto the world. Each vector has an x, y, and z component, plus an offset which is the "shift" of the texture in that direction relative to the world. The length of the vectors represent the scaling of the texture in each direction.
>
> The 2D coordinates (u, v) of a texture pixel (or texel) are mapped to the world coordinates (x, y, z) of a point on a face by:
>
> u = tv0,0 * x + tv0,1 * y + tv0,2 * z \+ tv0,3
>
> v = tv1,0 * x + tv1,1 * y + tv1,2 * z \+ tv1,3
>
> (ie. The dot product of the vectors with the vertex plus the offset in that direction. Where tvA,B is textureVecs\[A\]\[B\].
>
> Furthermore, after calculating (u, v), to convert them to texture coordinates which you would send to your graphics card, divide u and v by the width and height of the texture respectively.

So I am doing the calculation as follows. Take the dot product of the vertex and the lightmap vector(lightmapVecs\[0\]\[0\], lightmapVecs, lightmapVecs\[0\]\[2\]) add the offset (lightmapVecs\[0\]\[3\]), subtract the mins, and divide the result by the width/height.

```
float s = Vector3f.dot(v, new Vector3f(lightmapVecs[0][0], lightmapVecs[0][1], lightmapVecs[0][2])) + lightmapVecs[0][3] - f.LightmapTextureMinsInLuxels[0];
float t = Vector3f.dot(v, new Vector3f(lightmapVecs[1][0], lightmapVecs[1][1], lightmapVecs[1][2])) + lightmapVecs[1][3] - f.LightmapTextureMinsInLuxels[1];
s /= (f.LightmapTextureSizeInLuxels[0] + 1);
t /= (f.LightmapTextureSizeInLuxels[1] + 1);

```

However it ends up looking like this:

Here's a sample calculation for the texture coord 't' for one vertex.

```
vertex = 352.0, -144.00027, -224.0
lightmap vector = -4, 0, 0
lightmap offset = 0
lightmap mins = 9
lightmap height = 14

```

So the dot product is -1408

```
(-1408 + 0 - 9) / 14

t = -101.21

```

This seems way off.

# Answer
I eventually figured out, I was reading the data in wrong. All the code above is correct.
> 1 votes

# Answer
You should normalize the vectors before calculating the dot product.
> 0 votes

---
Tags: textures, coordinates, binary-space-partitioning
---


# Question
Title: Java/Android pixel perfect hit detection
I am making a game for android which I need hit detection between two objects. The first bitmap I have is a flying superhero, and the second bitmap is anything that he collides with.

The superhero bitmap is created on the fly by rotating the original bitmap between -90 and 90 degrees. As a result of the rotation, the bounding box is much, much larger than the non-rotated version. I have code to detect if the bounding box of the player hits any object, but visually this creates a problem when the object comes in contact with the skewed bounding box.

I need a solution that computes pixel-perfect hit detection between the player and the object, not just the bounding boxes.

I have been searching for the past 5 days for examples, tutorials, code snippets, or anything that could help me, but I haven't found a solution. The solution I'm looking for would be simply one function call similar to public boolean(obstacle theobject), where the obstacle's bitmap. coordinates, width, and height are returned with obstacle.getbitmap, obstacle.getx, obstacle.gety, obstacle.getwidth, and obstacle.getheight. The bitmap of the player is named rotatedbm and has global variables playerx, playery, playerh, and playerw.

I do not wish to implement external game engines or libraries.

I have read much on using int arrays with Bitmap.getPixels, and then comparing the arrays, but I cannot grasp the math behind comparing the arrays nor sorting out alpha values. I cannot afford to stay stuck on this one problem much long for the sake of development.

Thank you

EDIT- This is my implementation of the pseudo code. In the log, 'hit true' is never thrown but 'hit trying' is. Its not working as intended...

```
public boolean gethit(obstacle second){

        int px,py,ph,pw;

        Bitmap sprite1 = rotatedbm;
        Bitmap sprite2 = second.getgfx();

        px = playerx;
        py = playery;
        ph = sprite1.getHeight();
        pw = sprite1.getWidth();

        int ox = second.obx;
        int oy = second.oby;
        int oh = second.obh;
        int ow = second.obw;

        int [] AABB1bl = {px, py+ph};
        int [] AABB1tr = {px+pw, py};
        int [] AABB2bl = {ox, oy+oh};
        int [] AABB2tr = {ox+ow, oy};

        AABB2bl[0] -= AABB1bl[0];
        AABB2bl[1] -= AABB1bl[1];

        AABB2tr[0] -= AABB1bl[0];
        AABB2tr[1] -= AABB1bl[1];

        AABB1tr[0] -= AABB1bl[0];
        AABB1tr[1] -= AABB1bl[1];

        AABB1bl[0] -= AABB1bl[0];
        AABB1bl[1] -= AABB1bl[1];

        int start_x = AABB2bl[0];
        int start_y = AABB2tr[1];
        int end_x = AABB1tr[0];
        int end_y = AABB1bl[1];

        int ALPHAMASK = 0xFF<<24; // assuming colors are represented as 0xAARRBBGG

        int alpha1;
        int alpha2;

        Log.i("hit", "trying");
        for(int x = start_x; x < end_x; x++)
            for(int y = start_y; y < end_y; y++) {
              alpha1 = sprite1.getPixel(x , y*sprite1.getWidth()) & ALPHAMASK;
              alpha2 = sprite2.getPixel(x + AABB2bl[0], (y+AABB2tr[1])*sprite2.getWidth()) & ALPHAMASK;
              if(alpha1 != 0 && alpha2 != 0) {
                Log.i("hit", "true");
                return true; // you'd probably wish to return after a colliding pixel has been found
              }
            }
        return false;
}

```

# Answer
1) Calculate the screen-space AABBs of the two potentially colliding objects. Note that this needs to be done after you've applied all rotations (there are very fast ways of obtaining AABBs from OBBs if you need to). You can represent AABBs in many different ways (e.g. vector2 and two floats - center and extents or two vector2s - bottom left, top right corner). I will assume the second representation - two vector2s for bottom left and top right corner.

```
struct AABB {
    Vector2 bottomLeft;
    Vector2 topRight;
}

```

2) Do a basic AABB intersection test for an early out.

3) Translate both AABBs to the coordinate space of the first one.

```
aabb2.bottomLeft -= aabb1.bottomLeft;
aabb2.topRight -= aabb1.bottomLeft;
aabb1.topRight -= aabb1.bottomLeft;
aabb1.bottomLeft -= aabb1.bottomLeft;

```

4) As the AABBs are in screen-space they (should) correspond directly to the bitmap representation of your objects on-screen. You get something like:

Now you have to iterate through the red pixels and compare the values from the two images you have. I am assuming you would wish to compare only the alpha values so you would need to mask them out from the ints you get from getPixels(). An example in pseudo C:

```
int start_x = aabb2.bottomLeft.x;
int start_y = aabb2.topRight.y;
int end_x = aabb1.topRight.x;
int end_y = aabb1.bottomLeft.y;

int ALPHAMASK = 0xFF<<24; // assuming colors are represented as 0xAARRBBGG
Bitmap sprite1;
Bitmap sprite2;

for(int x = start_x; x < end_x; x++)
for(int y = start_y; y < end_y; y++) {
  alpha1 = sprite1.pixels[x+y*sprite1.width] & ALPHAMASK;
  alpha2 = sprite2.pixels[(x+aabb2.bottomLeft.x)+((y+aabb2.topRight.y)*sprite2.width)] & ALPHAMASK;
  if(alpha1 != 0 && alpha 2 != 0) {
    // pixel is colliding
    return; // you'd probably wish to return after a colliding pixel has been found
  }
}

```
> 2 votes

---
Tags: java, collision-detection, android
---


# Question
Title: How should I structure my Android platform board game?
I'm new to developing Android games, but not new to developing mobile games (J2ME). I'm currently developing a board game, for a school project, with 2 things - a board and a spinning wheel (both are displayed at the same time). The user is able to zoom in/out and scroll around the board and spin the wheel. The wheel is also animated - resized during game. The board is build using tiles (2-4 different tiles on one image per board ) and the wheel is a image with numbers draw on it, using graphics.

My questions is what is the best practice to achive the best performance of the game (game has to run on every possible Android version)?

* Should i use Android canvas or open GL?
* Is there a mechanism for drawing tiles, animations or should i just implement it my self using drawImage()?
* Should i separate the wheel and the board into two different threads? Should i separate the wheel and the board in to 2 activities or put it in 1 activity and draw each part separatly?
* What would be the best way to resize the wheel during gameplay? Scale the wheel image (but the animation has to be smooth - opengl vs canvas)?
* What would be the best way to make the board zoomable - should i scale every image on the board when the zoom is detected or does android have some better way to do this?
* What would be the best way to make the board scrollable - should i implement a Camera that displays just a piece of the board or does android have some better way to do this?

# Answer
> 1 votes
* Should i use Android canvas or open GL?
OpenGL is faster, it makes use of GPU.
* Is there a mechanism for drawing tiles, animations or should i just implement it my self using drawImage()?
Take a look to this tutorial And check Android APIDemos graphics section. Also check LunarLander example.
* Should i separate the wheel and the board into two different threads?
Its not necesary, you should try to separate rendering from game logic, but one thread per object is not necesary because they will render at the same time.
* Should i separate the wheel and the board in to 2 activities or put it in 1 activity and draw each part separatly?
One Activity
* What would be the best way to resize the wheel during gameplay? Scale the wheel image (but the animation has to be smooth - opengl vs canvas)?
OpenGL, apply a matrix scale transformation.

---
Tags: opengl, android
---


# Question
Title: A little bit confused on how to set normals in this case
I'm learning how to use VBOs and I'm following up on the tutorial at the bottom of this page.

So I went ahead and created a structure Vertex to hold vertex data.(coordinates and normals).

```
struct Vertex  {
  GLfloat  x,  y,  z;
  GLfloat nx, ny, nz;
  GLfloat   r, g,  b;
  GLfloat padding[7];
};

```

For the moment I'm trying to draw a cube.So I created an array with 8 vertices. My question is how do I set the normals?

When I used immediate rendering, I would just do a `glNormal3f` and proceeded to draw the vertices for that face. Now that the normals are defined on a per-vertex basis, and a vertex practically belongs to 3 faces, I'm somewhat confused as what I should do here.

Have I taken a wrong approach on making that structure, or I am missing something else.

I would also like to note that I want to make something more generic, so I don't want it to be limited to just drawing cubes.

Thanks.

# Answer
> 2 votes
As you note, every vertex can only have one normal. That means that, depending on the lighting appearance you want, you may need to duplicate vertices. Specifically, if you want the edges of the cube to have a sharp boundary, then you will need to have separate vertices for each side. Make new vertices at the exact same position and use each duplicate for a different face.

If however you want to keep the vertices shared between multiple faces and have the lighting smoothed out over the edge, then you should set the normal of the vertex to the average of the normals of its faces.

# Answer
> 3 votes
The answer for your "cube" problem is probably that you're probably going to need more than 8 vertices. Make 4 for each face and set the normals for them to be the normal of the surface.

---
Tags: opengl, normals, normal-mapping
---


# Question
Title: Pub/Sub or message passing in multiplayer server backend?
For my masters thesis I'm going to develop a scalable multiplayer server for locationbased games. It's going to be a "service oriented architecture" e.g. one dedicated service for positions, one for the database, login etc. However 1..n frontend services for the clients to connect to. Scalability will be tested with simulated clients on some other machines. However, I'm still undecided on how my services will talk to each other.

On the one hand, there is publish/subscribe. And even there are different ways to implement it, using Multicast or let each subscriber subscribe directly with the publisher. The good thing with pub/sub is, that each message will be sent to every service that is interested, e.g. the Logger-Service receives a position update as well as the position service. I can also have some "shadow" services that keep in sync in case the major services crashes. Depending on the implementation pub/sub feels like flooding my internal network with messages. And flooding is never a good idea.

Then there is message passing. When the Frontend-Service receives a message, it finds out what type of message it is, finds the service that deals with this type and forwards the message to it. But there has to be a service discovery first, which requires some multicast or service directory.

There are pros and cons for each type. In an article on high scalability I read that Playfish uses the message passing method. But using pub/sub sound appealing too. Maybe someone can tell me which way is better.

**Edit:** I have to admit it isn't so clear what I'm asking. Imagine one frontend service receives a "position update" message from one of the clients. With a pub/sub system, I think about calling something like this: Network.publish(Topic,Message) or Network.publish(PositionUpdateType, Message). Using a message passing system I might call: Network.send(PositionManager, Message). I think pub/sub seems to be like "fire and forget", where the message passing is some kind of "direct" connection. My question is: Which one is better suited for the job or should I even use a combination of both?

# Answer
Pub/sub and message-based communication are not mutually exclusive. However, I think you're realizing that pub/sub abstracts the receiver, whereas message passing requires a recipient. They're both fire and forget unless structured otherwise (continuation-passing style comes to mind).

All in all, the two are not so different, we might argue that publishing a message is nothing more than sending a "publish" message to the "publisher" actor, which in turns delivers the message to any recipient that sent a "register" message to the publisher in the first place.

Anyway, to make it short: message-passing enables you to delay execution and share the load across workers. In our multicore age, this is handy, especially with task-stealing schedulers.

Which language are you targeting? I might give more details.

Edit: I just noticed the "Java" tag. I know nothing of Java :)

Edit 2:

Sharing the workload across services is just the beginning. You have to find a way to max out these services, and when the services are maxed out, you also need strategies to spawn new services and share the workload again. If you're using one server to the max, you can't just spawn a new process, but you need another physical server, ready to crunch numbers until the next load peak. And even then, you have to be careful about the strategies you use to spawn new workers.

Intra-server:

1. A main server broadcasts a discovery message.
2. Server 1 replies, says it can deal with logging
3. Server 2 replies, says it can handle player movement etc.
4. Server 3 replies, says it can handle trades and chat.
5. The main server will acknowledge the servers and subscribe them to specific service-dependant topics.
6. However, also server 1, 2, 3 will have to keep a list of subscribers, unless it's fine to let the main server do all the publishing.
7. Every n milliseconds, servers will have to show they're still alive by sending a message to the main server.
8. Intra-server and foreign events (from clients) will be dispatched to the correct subscribers.
9. At some point, the volume of events will cap the processing power of one or more servers, requiring more workers.
10. This is where things become messy; existing services will have to yield responsibility of a part of their processing to services on a different machine. Also, workload sharing criteria may be dynamic (you thought having workers per world region was enough, but turns out 90% of players is in the same city, in the very same region, nullifying your strategy).

As for maxing out a service, you really want to divide your work in tasks and, while order matters, let a task-stealing scheduler process them as fast as they come.

It's a wall of text already. Questions? Comments?
> 3 votes

# Answer
These aren't opposing paradigms, just different aspects of the same thing. Publish/subscribe can send messages. And service directories may be filled only with services that have subscribed to that directory. And if your subscriptions are 'flooding' anything then presumably you aren't subscribing to something fine-grained enough. So it's not really clear what you're asking.
> 2 votes

# Answer
Consider using a job server such as Gearman. Your services are workers that pull jobs from the job server, do some work, and put a result back which is forwarded to the job submitter. If you find that some service has a high number of jobs per unit time, simply add more workers to handle the load.
> 0 votes

---
Tags: architecture, java, networking, mmo, server
---


title: Box2D networking

text:
# Question
Title: Box2D networking
I am trying to make a simple sync between two box2d rooms, where you can drag boxes using the mouse.

So every time player clicks (and holds the mousedown) a box, I try send joint parameters to server, and server sends them to other clients. When mouseup occurs, I send command to delete joint.

The problem is that sync breaks too often. Is my way radically wrong, or it just needs some tweaks?

http://www.youtube.com/watch?v=eTN2Gwj6\_Lc

Source code https://github.com/agentcooper/Box2d-networking

# Answer
> 4 votes
I think this is because of some parameters which differ in two computers, for example they are not computing your scene with same speed (their delta\_time values are not same), and simulation result is based on them. you either have to sync all these parameters in 2 computers or everyonce in a while send a snapshot of your whole scene, to sync results. the later is much more easier to implement ( at least I think so), be the former has much less network load. you can combine both ideas somehow and increase the time between sending snapshots to take benefit from both. for the diffrence in delta\_times I can suggest the following code :

```
void update(float delta_time)
{
    static float total_elapsed_time = 0;
    total_elapsed_time += delta_time;
    while (total_elapsed_time > 1.0/30)
    {
        total_elapsed_time -= 1.0/30;
        world.step(1.0/30,10,10);
        other_updates(1/30);
    }
}

```

in this code you are somehow syncing all the timers between two computers. of course you can change 1/30 or other parameters as you like but they should be same in both computers (and also they should be somthing logical not much less than actual processing power)

# Answer
> 1 votes
I think @Gajet is on the right track; the other thing I think you may be missing, is that the server should define the state. Events should be sent to the server, who does world calculations and then updates each client.

In other words, when a client clicks, it should send the data about that click to the server; the server then calculates where the box ends up, and sends that data to all clients. The client who actually performed the event can start "predicting" where the server is going to tell it to put the box.

Put a different way, each client should tell the server "the user just did X" at the moment it knows that X happened. Then, the server goes about figuring out what that means, and updates all of the clients. As soon as the client finishes telling the server about X, it starts moving the box and when it gets the update from the server, it adjusts the box from its own calculation to the calculation received from the server.

# Answer
> 0 votes
What I did for this same problem, javascript implementation Box2D networked system was to create a system in which the players send inputs to the server, and the server is the one running the simulation and sends world-updates to all players at discrete intervals.

Repository:
https://github.com/onedayitwillmake/RealtimeMultiplayerNodeJs

You can see the box2d demo of this here:
http://vimeo.com/24149718

---
Tags: networking, box2d
---


title: Vectors in game development

text:
# Question
Title: Vectors in game development
I'm new to programming and game programming. I've reading something about vectors and math, but I have a question - where do I use vectors in game programming? Maybe anyone can give a simple example where you are using vectors (in 2D)?

I've found examples but mostly they are in the console where they output numbers, and big examples which I don't understand.

# Answer
**What are vectors?**

Vectors are sets of coordinates of varying dimension. Each coordinate in a vector represents some absolute position in that direction of the space the vector is in.

* A 1-D vector would be **{1}** . This could be, for example, a position at X = 1. Or a time t = 1.
* A 2-D vector would be **{-4,3}**. This could be, for example, a position at -4 on the X-axis, and 3 on the Y-axis. It could also be the temperature (3 degrees) at a position (-4 meters) back on the X-axis.
* A 3-D vector would be **{1,2,3}**. This could be a position in space 1 along the X-axis, 2 back on the Y-axis, and 3 up on the Z-axis. Or it could be 1 red, 2 green, and 3 blue in a color. Or, it could be an XY position (**{1,2}**) at some time T (**{3}**).

Note that in all cases, we've assigned meaning to the vectors for our problem. While you will commonly find vectors being used for geometry in games, there is no reason you can't do something else with them.

**Why do I use vectors?**

First, you never *have* to use vectors. As long as you are keeping track of x and y, or whatever coordinates you care about, in some way you are fine.

However, the advantage to using vectors is that they neatly represent things such as direction and position, and also have several mathematical operations defined on them that make your life easier.

For a simple example of these, consider the *dot product*.

Suppose you have a radar system in a top-down style game. Every enemy that appears in the sector of the radar (some pie-shaped wedge in 2D) should get a little red dot in your screen. So, you need to figure out what enemies are in your radar section.

You could test if the enemies are inside a triangle. You could also test if the enemies are contained in the intersection of the two half-spaces of the planes/lines defining the two side of the radar sector.

Or, you could just use a dot product to do the check. Here's how:

1. Create a vector going from the center of the radar out towards the "front of the radar". Normalize it.
2. Create a vector going from the center of the radar out towards the object we want to check the radar visibility of. Normalize it.
3. Take the dot product of the two normalized vectors.
4. Take the arccosine of that product, and check if it is less than half the angle of the width of the radar. If it is, draw a blip.

This is very handy, and also now lets you easily have radars that point in different directions (just change the forward vector) and have different widths (just change the radar width angle)--and you can reuse the same code for those cases too!

**Why else do I use vectors?**

If you are in 2D, perhaps the best way of achieving complex effects and motions (spinning, scaling, etc.) is to use a scene graph. A planet has an orbiting ship, the ship has an orbiting drone. The calculation for this without using vector math is really, really ugly.

With vector math, we represent each as having a point and a 3x3 transform matrix. The planet uses its transform, the ship uses its transform and the planet's transform, and the drone uses its transform and the ship's transform and the planet's transform.

When the planet moves, you change its transform, and the ship and drone automatically get positioned "for free". Much cleaner code.

**Still not convinced.** Vectors are also the native representation for position, geometry, and motion used by nearly all graphics libraries--and certainly OpenGL and DirectX. You aren't likely to get away without having to use them.

**Conclusion** Vectors are a powerful tool for writing clear code that solves geometrical problems cleanly and elegantly.
> 31 votes

# Answer
A 2D example are screen coordinates, it identifies a pixel on the screen and has an x- and an y-component \[x, y\] i.e. Left upper screen position \[0, 0\]

Another example: Imagine a text scrolling from right screen border to the left screen border. Now you need to define the velocity of the scrolling text in pixel per second, i.e. \[-20, 0\] which means the text scrolls 20 pixels to the left per second and never changes the height.

Another more advanced example: Imagine a 2D game that is supposed to run on different screen resolutions 800x600, 1024x768 etc. This can easily be done by internally using a screen width from 0.0 to 1.0 and a height from 0.0 to 1.0 to decouple the game logic from the actual screen resolution. Now when you draw to the screen you just multiply the internal vector with the resolution vector:

```
screen_pos = internal_pos * screen_ressolution

```

note, all 3 variables are 2D vectors here, they have an x- and an y-component, i.e. for this internal\_pos \[0.5, 0.25\]:

```
[400, 150] = [0.5, 0.25] * [800, 600]

```

So internal position \[0.5, 0.25\] is transformed to actual screen position \[400, 150\]

This was the basic stuff. The real advantage of vectors is the application in Linear Algebra where you can use matrices to transform your vertices (rotate, scale, mirror etc), i.e. to easily rotate all your internal position by 90 degrees, or you have to swap the screen-y position 0 from top to the bottom of the screen, because i.e. a third party library that you use, uses this convention.
> 14 votes

# Answer
Here's a great explanation of vectors in game development on Wolfire Games blog:

http://blog.wolfire.com/2009/07/linear-algebra-for-game-developers-part-1/
> 6 votes

# Answer
Anywhere where you have a number for each dimension to represent something, the collection of these numbers can be considered a vector. Position, velocity and acceleration are the prime examples of vectors. It can in some cases also be practical to represent direction of facing as a vector.

For basic stuff it doesn't really matter whether or not you consider these numbers to be vectors, but if you want to do any kind of physics you ought to look into vector maths.
> 1 votes

# Answer
A vector is an entity that has both a value and a direction. Examples of vectors in the real world and physics based games include velocity and momentum. Properties that have only values but no direction are called scalars and include location, mass, density and so forth.

Vectors are needed for games that emulate physical properties that are vector like (as mentioned - speed, acceleration and so forth). The mathematics that are used for vector calculations are called linear algebra.
> 1 votes

# Answer
Very simply, anything with a position, or a direction, which is everywhere in a game they use vectors. A vector is like a point

```
struct Point2
{
float x, y;
};

struct Vector2
{
float x, y;
};

```

However the difference really comes down to this. A point is just a dot, while a vector is an Arrow.

if you have

```
Point2.x = 5;

Point2.y = 10;

```

your saying that I mean at this location x 5 and y 10.

however when you declare a vector...

```
Vector2.x = 5;

Vector2.y = 10;

```

Your really saying im declaring an arrow from 0,0 to x 5 , y 10;

you can even have the point from which your vector is pointing from be a point in space from anywhere, for example lets use a point and a vector to move our object we'll use a Point2 to store its location and a vector2 to move it.

```
point2.x = 10;

point2.y = 15;

```

now you can use a vector to move this point, lets say we want to move this point up the x axis 10 units so you have

```
vector2.x = 10;

vector2.y = 0;

point2 += vector2;

```

now point has moved where your vector arrow told it to.

point now is

```
point2.x = 20;

point2.y = 15;

```

One last thing to note is sometimes a vector is used like a point and vice versa just because they hold the same type of data.
> 0 votes

---
Tags: vector
---


# Question
Title: Which axis-aligned line does an AABB collide with first?
I am making the collision resolution system for my 2d top-down game, and I managed to find a solution where I query which surfaces of other AABBs the current entity can collide with in the next frame.

To resolve the new location of the player however, I need to find which surface the entity collides with first.

I have a list of lines, which is `LinkedList<int[4]> collidedLines`. a line is `{x1,y1,x2,y1}`, however in this case, they are axis-aligned, so either x1==x2 or y1==y2.

I also have the entity, which has the following properties:

```
int posX
int posY
int speedX  // The amount to move in the
int speedY  // next step of the game.
int size  // The halfwidth of the square AABB.

```

How can I find the first line the entity collides with? Thanks for your help!

# Answer
You can also achieve this with the following steps:

* 1/ Find the intersection points between the infinite lines passing though the four sides of the AABB and the infinite line passing through the entity position (pre-collision) which use the entity speed vector as slop. (You can either find a collision point or an undefined number, which corresponds to parallels or overlapping lines)
* 2/ Once you know the intersection points (if they exist) you can search for those that are into the segment bounds.
* 3/ Finally, if there is still multiple points on the list (the velocity vector can pass through multiple sides), you can search for the closest point from the entity origin using the magnitudes of the vector from the intersection to the entity origin.

---

More details:

* 1/ Find intersections

+ a / Determine the implicit lines ( Ax + Bx = D ) using their parametric forms ( P(t) = Po + tD ).

    > Point origin: Po = \[posX, posY\]
    > Direction vector: D = \[speedX, speedY\]
    > **A** = D.y = **speedY**
    > **B** = -D.x = **-speedX**
    > **D** = (Po.x * D.y) - (Po.y * D.x) = **(posX\*speedY) - (posY\*speedX)**
    > Ax + By = D \<====\> (speedY\*x) + (-speedX\*y) = (posX\*speedY) - (posY\*speedX)

    **I used the entity point values to illustrate the method, but this is exactly the same method to determine the 4 side implicit lines** (Use Po = \[x1,y1\] and D = \[ x2-x1 ; y2-y1 \] instead).
    + b / Next, to find the intersection of two implicit lines we can solve the following system:

    > A1x + B1x = D1 \<== Line passing through the entity point with the speed vector as slop.
    > A2x + B2x = D2 \<== One of the lines passing through the AABB sides.

    which yields the following coordinates for the interception:

    > Interception **x** = ((**B**2\***D**1) - (**B**1\***D**2)) / ((**A**1\***B**2) - (**A**2\***B**1))
    > Interception **y** = ((**A**1\***D**2) - (**A**2\***D**1)) / ((**A**1\***B**2) - (**A**2\***B**1))

    If the denominator ((A1\*B2) - (A2\*B1)) equals zero, then the both lines are parallels or overlapping, otherwise you should find an intersection.
* 2/ Test for the segment bounds. As this is straightforward to verify, there is no needs for more details.
* 3/ Search for the closest point. If there is still multiple points on the list, we can find which side is the closest to the entity origin point.

+ a / Determine the vector going from the intersection point to the entity origin point

    > V = Po - Int = \[Po.x - Int.x ; Po.y - Int.y \]
    + b / Compute the vector magnitude

    > ||V|| = sqrt( V.x² + V.y² )
    + c / find the smallest one.

---

Note: this is probably not the most efficient way to do it, but as it still can helps some people i think it worth to be added.
> 1 votes

# Answer
Since all the collision objects in your universe are axis-aligned, it might be easier to have separate lists of vertical lines and horizontal lines. And keep both lists sorted. Then it's relatively straightforward to figure out the first horizontal line that the actor actually hits; similarly for the first vertical line, and then all you have to worry about is which one of these two is actually first.
> 1 votes

---
Tags: 2d, collision-detection
---


title: DX9 sprite / font draw depth order

text:
# Question
Title: DX9 sprite / font draw depth order
I need the ability to order the drawing of sprites and fonts. Some sprites need to be drawn behind and some in front of text. My problem is that my sprites and fonts use separate Begin() End() calls so I can't simply order the draw calls.

How is sorting generally done in DX9?

# Answer
You say that you can't order your sprite drawing because they use separate begin/end calls.

The solution is to separate them into as many begin/end blocks as you need in order to get the sprites into the sorted order that you need.

If this is performance critical and you're trying to reduce state changes, then you can use the same shader to draw your fonts and sprites (fonts are also really just sprites). However, I'm guessing that this is premature optimization.
> 2 votes

---
Tags: sprites, directx9, fonts
---


title: Vary speed of enemy smoothly

text:
# Question
Title: Vary speed of enemy smoothly
Hey. I'm trying to create an enemy that travels at a speed `s` on screen but I'm having trouble with trying to make the speed vary in a smooth motion. Basically, I can get the enemy to move at a constant rate but at random intervals, I'd like it to speed up then slow back down to it's original speed, or slow down then speed up to it's original speed. I imagine I'd have to use a graph function of sorts, but I'm not great at maths so are there any suggestions on how this can be achieved? Feel free to let me know if my question is unclear.Thanks!

# Answer
> 6 votes
What you're talking about here is commonly called a "lerp", short for interpolation. You can find a lot of different implementations and specifics about this sort of operation on Google by searching for "lerp", but here's a very basic one:

```
T Interpolate(float fraction, T startingValue, T endingValue)
{
  T delta = endingValue - startingValue;
  return startingValue + (delta * fraction);
}

```

In this, "fraction" should be a value between zero and one (inclusive), and the type T is anything that supports +, -, and * operators (So floats, vectors, etc). In your case, you'd use one with 'float' instead of T, but this same approach works for interpolating lots of other mathematical types, so this will almost certainly be useful to you again in other situations in the future.

The simplest way to get your speed to increase smoothly will be to simply interpolate from the object's current speed toward its target speed each frame, using a low *fraction* value for the interpolation. For example, like this:

```
float speedFraction = 0.1f;
object->SetSpeed( Interpolate( speedFraction, object->GetCurrentSpeed(), object->GetDesiredSpeed() );

```

This will give what is referred to as a "slam in, ease out" curve; the object will get a sudden burst of acceleration when it changes its desired speed, but that acceleration will taper off as it approaches that destination speed. If you make *speedFraction* higher, the object will approach its final speed faster. Lower, and it will reach that speed slower.

This is almost certainly all that you'll need to have your character change speeds smoothly enough for you. But be aware that this will produce different behaviours if it's being done 30 times per second than if it's being done 60 times per second.

Advanced: If you do want the object to accelerate even more smoothly than this (that is, to start accelerating slowly, instead of quickly), or if it's important that the object actually reaches that final speed (rather than approaching that speed asymptotically), or if you want to make sure that the acceleration works the same no matter what frame rate you're running at, then you can use that same interpolation function differently.

If you keep track of when the object began to accelerate, and know how long you want the acceleration to take, then you can calculate:

```
if ( object->IsSpeedingUp() )
{
  float fraction = (timeNow - object->GetAccelerationStartTime() ) / object->GetFullAccelerationDuration();
  float easeInEaseOutFraction = 3*fraction*fraction - 2*fraction*fraction*fraction;
  object->SetSpeed( Interpolate( easeInEaseOutFraction, object->GetSlowSpeed(), object->GetFastSpeed() );
}

```

In this, *easeInEaseOutFraction* is using a hermite interpolator on the value "fraction", to convert it from a linear transition from zero to one, into a very smooth curve over that same range. And since it still varies only between zero and one, that means that we can pass it into the same Interpolation function we've already been using, to make the interpolation extremely smooth.

You may find that you prefer this smoother behaviour over the simpler approach that I gave earlier. Or you may find that it makes no difference in your case. My advice is to do the simpler version first, and stick with it if it's good enough for your purposes.

If you do go with the more advanced variation, just be aware that it's critical that the "fraction" value remains between zero and one. If you're using interpolation in this way (by passing in a variable "fraction" value that changes over time), then you must stop interpolating once the object has actually reached its target speed, or else you'll get unexpected behaviour as "fraction" exceeds 1.

# Answer
> 5 votes
You want the speed to increase smoothly from an initial value, let's call it `s1` and reach a final value, let's say that's `s2`.

That sounds like a Logisic Function to me! A simple logistic function -- a smooth transition from 0 to 1 is `P(t) = 1 / (1 + e^(-t))`. It looks scary! Don't be afraid! Math is your friend! Drawing it might make it clearer -- you should get an S-shape with asymptotes (values of `P(x)` that the curve tends towards) of 0 and 1.

Set up an increment for some variable, let's say `t`, from a small value (say -10; this will cause `P(x)` to approximate 0) to a large value (say 10; this will make `P(x)` approximate 1) and every step of the game, run something like

```
s = s1 + P(t) * (s2 - s1);

```

until `t == 10` or whatever you chose the large value to be. At this point, you should also set `s = s2` since `s` will only be an *approximation* -- remember that the graph only *tends toward* 1, never quite reaching it.

This is all based on the fact that when `t` reaches 1, `P(t)` will be roughly 1 and the the expression on the right of the assignment will evaluate to roughly `s2`.

The same code works if you want to reduce speed.

**EDIT:** I'd made a logical error with what to choose for `t`. Fixed.

# Answer
> 2 votes
You might consider attributing an acceleration value with an enemy. So for each enemy you might associate a velocity(v) and acceleration(a) variable. This would handle the case of the enemy smoothly increasing speed from an initial velocity of zero. Of course you would then need to also associate a maximum speed for the enemy. As for slowing down, there are many ways one could handle this. Simply use the negative of the acceleration, or create your own deceleration variable.

# Answer
> 0 votes
Here is a function from our engine that I've used over the years. Maybe it can help. It will take aValue up to aMax by aAmount. If you then pass aAmount=0, it will then take it down to zero by aDrag amount... all smoothly. If you view the AstroBlaster video/demo on our site, it uses this routine to control the ship speed. Works great for us. It's Object Pascal but you should be able to adopt it easily to the language you use.

```
procedure TSvMath.SmoothMove(var aValue: Single; aAmount, aMax, aDrag: Single);
var
  Amt: Single;
begin

  Amt := aAmount;

  if Amt > 0 then
  begin
    aValue := aValue + Amt;
    if aValue > aMax then
      aValue := aMax;
  end else if Amt < 0 then
  begin
    aValue := aValue + Amt;
    if aValue < -aMax then
      aValue := -aMax;
  end else
  begin
    if aValue > 0 then
    begin
      aValue := aValue - aDrag;
      if aValue < 0 then
        aValue := 0;
    end else if aValue < 0 then
    begin
      aValue := aValue + aDrag;
      if aValue > 0 then
        aValue := 0;
    end;
  end;
end;

```

---
Tags: c#, mathematics, animation, graphs, easing
---


title: MySQL - Storing Character Inventory

text:
# Question
Title: MySQL - Storing Character Inventory
What is the best way of storing the character's inventory (consisting of each item having a value for type and quantity). The only methods I can think of is to use the "text" type of field then parse the value from that whenever the inventory is loaded. Is there a better method or data structure?

# Answer
> 6 votes
Read up on standard database design. Specifically normalized forms. An approach would be to have 3 tables:

character having a character\_id and other data

items having an item\_id and other data (names, weight etc...)

inventory having character\_id, item\_id, quantity.

A player's inventory could be expressed as "SELECT items.name FROM items, inventory WHERE inventory.character\_id = 'THECHARSID'" Of course based on your other questions I'd much more likely suggest using an ORM that handles this for you. Look at Relationships, and backrefs in something like SQLAlchemy.

If you need the concept of inventory 'slots' then that's another column in the inventory table. (IE: Character 32423 has an item of type 832 in slot 0 (The head slot)) If each item has unique stats (Durability/upgrades) Then you can do something like the item table contains the item specific data, and has a link to an item\_base column that defines the base stats that all items of that type have in common.

---
Tags: character, storage, databases, sql
---


# Question
Title: Meaning of knots when drawing a NURBS curve?
I'm using `gluNurbsCurve` to draw some curves with some control points. I've got the basic setup as described in the red book working correctly and I'm trying to expand on it.
This sample looks like this:

```
float knots[8] = {0,0,0,0,1,1,1,1};
float pnts[4][3] = { {...},{...},{...},{...} };
GLUnurbsObj *m = gluNewNurbsRenderer();
gluBeginCurve(n);
gluNurbsCurve(n, 8, knots, 3, pnts, 4, GL_MAP1_VERTEX_3)
gluEndCurve(n);

```

One thing I was wondering about is the meaning of the knots data. How does it affect the result? What other options can I experiment there?
For some reason I could not find any tutorial which properly explains this.

# Answer
This page has good explanations.

> The knots are a list of degree+N-1 numbers, where N is the number of control points. Sometimes this list of numbers is called the knot vector. In this term, the word vector does not mean 3‑D direction.
>
> This list of knot numbers must satisfy several technical conditions. The standard way to ensure that the technical conditions are satisfied is to require the numbers to stay the same or get larger as you go down the list and to limit the number of duplicate values to no more than the degree. For example, for a degree 3 NURBS curve with 11 control points, the list of numbers 0,0,0,1,2,2,2,3,7,7,9,9,9 is a satisfactory list of knots. The list 0,0,0,1,2,2,2,2,7,7,9,9,9 is unacceptable because there are four 2s and four is larger than the degree.
>
> The number of times a knot value is duplicated is called the knot’s multiplicity. In the preceding example of a satisfactory list of knots, the knot value 0 has multiplicity three, the knot value 1 has multiplicity one, the knot value 2 has multiplicity three, the knot value 3 has multiplicity one, the knot value 7 has multiplicity two, and the knot value 9 has multiplicity three. A knot value is said to be a full-multiplicity knot if it is duplicated degree many times. In the example, the knot values 0, 2, and 9 have full multiplicity. A knot value that appears only once is called a simple knot. In the example, the knot values 1 and 3 are simple knots.
>
> If a list of knots starts with a full multiplicity knot, is followed by simple knots, terminates with a full multiplicity knot, and the values are equally spaced, then the knots are called uniform. For example, if a degree 3 NURBS curve with 7 control points has knots 0,0,0,1,2,3,4,4,4, then the curve has uniform knots. The knots 0,0,0,1,2,5,6,6,6 are not uniform. Knots that are not uniform are called non‑uniform. The N and U in NURBS stand for non‑uniform and indicate that the knots in a NURBS curve are permitted to be non-uniform.
>
> Duplicate knot values in the middle of the knot list make a NURBS curve less smooth. At the extreme, a full multiplicity knot in the middle of the knot list means there is a place on the NURBS curve that can be bent into a sharp kink. For this reason, some designers like to add and remove knots and then adjust control points to make curves have smoother or kinkier shapes. Since the number of knots is equal to (N+degree‑1), where N is the number of control points, adding knots also adds control points and removing knots removes control points. Knots can be added without changing the shape of a NURBS curve. In general, removing knots will change the shape of a curve.
> 1 votes

---
Tags: opengl, 3d, graphics
---


# Question
Title: Best way to create a 2D right-triangle grid
I would like to create a 2D right triangle grid for a game I am working on. Currently I am creating creating a 2D square grid, and each square contains 2 triangles.

I am wondering, is there a way to create and manage a right-triangle grid without having to contain 2 triangles in each square?

# Answer
> 4 votes
At first I thought you wanted to switch to equilateral triangles like below

Then you can index into this grid in the exact same way as a rectangular grid.

The top left triangle will be (0,0), and the one to the right of it will be (1,0) then to the right of that will be (2,0), etc.

The row below is (1, j).

---

However, I see now that you question is about right triangles.

That is just as easy, because two right triangles form a rectangle. So your coordinates will clearly still be rectangular, the same as above.

If you have a 2D array storing your grid of triangles, you can just index directly into any triangle using a rectangular coordinate system (i.e., pretend that you just have a grid of squares).

So you'll have a 2D array that stores one triangle each. `array[0,0]` stores nothing, to make the coordinate system simpler.

There are multiple ways to index into these triangles, so I've just chosen the coordinate system that I think is easiest.

This corresponds to a rectangular coordinate system that you're used to pretty closely. If it's still not clear, just ask me to elaborate.

---
Tags: 2d, grid
---


# Question
Title: How to use a multi-thread OpenGL application to update VBOs and use them at the same time?
I have a simple application. It has two threads, each with its own rendering context, but they share one VBO (this is working, I tested it).

Now what I want: One thread is rendering some data from the first half of the VBO and the second thread is updating the second part of the VBO.

When I don't update the VBO, it's working fine.

But I have some weird issues when updating. When I use `glMapBuffer` to update the VBO (in the second thread), in the first thread, most of the time, it renders nothing—the whole screen is clear (after a `glClear` call). It looks like it can't touch data from the VBO (this is understandable, because the whole buffer is mapped and so it can be locked somehow).

I tried to use `glMapBufferRange`, which uses `GL_MAP_UNSYNCHRONIZED_BIT`. This should mean, "don't wait and use the VBO as you want, I (the program) will synchronize it by myself". Also, when I map a range of VBOs and render data from another part, it shouldn't be waiting, but I'm experiencing the same issues as I am with `glMapBuffer`.

Can anybody help me fix this or explain why it happens?

# Answer
If someone is interested in this problem, you can find solution on OpenGL forum. Basically, buffers can't be accessed by two threads or contexts simultaneously, neither for reading nor writing. Therefore, a locking mechanism like `std::mutex` is needed.
> 6 votes

---
Tags: opengl, multithreading, vbo
---


# Question
Title: Dual paraboloid point light shadows in deferred lighting setup
I've been playing around with this tutorial/sample code that demonstrates a simple implementation of light-pre-pass, which is a type of deferred lighting setup.

I'm in the process of implementing point light shadows, using dual-paraboloid shadow maps. I'm following this description of DPM: http://gamedevelop.eu/en/tutorials/dual-paraboloid-shadow-mapping.htm

I am able to create the shadow maps, and they seem to look fine.

I believe that the current problem I'm having is in my pixel shader that looks up a depth value in the shadow map when rendering point lights.

Here is my point light shader code: http://olhovsky.com/shadow\_mapping/PointLight.fx

The pixel shader function of interest is `PointLightMeshShadowPS`.

Does anyone see a glaring error in that function?

Hopefully someone has tackled this problem before :)

As you can see in the images above, the post's shadows do not match up with the positions of the posts, so some transformation is wrong somewhere...

This is what it looks like when the point light is very close to the ground (almost touching the ground).

As the point light moves closer to the ground, the shadows come together and touch along the line where the two shadow maps meet (that is, along the plane where the light camera was flipped to capture the two shadow maps).

---

Edit:

Further information:

When I move the point light away from the origin, there is a line parallel to the light camera's "right" vector that clips the shadow. The above image shows the result of moving the point light to the left. If I move the point light to the right, there is an equivalent clipping line on the right instead. So I think this indicates that I'm transforming something incorrectly in the pixel shader, like I thought.

---

Edit: To make this question more clear, here are a few pieces of code.

Here is the code that I currently use to draw a shadowed **spot light**. This works, and uses shadow mapping as you'd expect.

```
VertexShaderOutputMeshBased SpotLightMeshVS(VertexShaderInput input)
{
    VertexShaderOutputMeshBased output = (VertexShaderOutputMeshBased)0;
    output.Position = mul(input.Position, WorldViewProjection);

    //we will compute our texture coords based on pixel position further
    output.TexCoordScreenSpace = output.Position;
    return output;
}

//////////////////////////////////////////////////////
// Pixel shader to compute spot lights with shadows
//////////////////////////////////////////////////////
float4 SpotLightMeshShadowPS(VertexShaderOutputMeshBased input) : COLOR0
{
    //as we are using a sphere mesh, we need to recompute each pixel position into texture space coords
    float2 screenPos = PostProjectionSpaceToScreenSpace(input.TexCoordScreenSpace) + GBufferPixelSize;
    //read the depth value
    float depthValue = tex2D(depthSampler, screenPos).r;

    //if depth value == 1, we can assume its a background value, so skip it
    //we need this only if we are using back-face culling on our light volumes. Otherwise, our z-buffer
    //will reject this pixel anyway

    //if depth value == 1, we can assume its a background value, so skip it
    clip(-depthValue + 0.9999f);

    // Reconstruct position from the depth value, the FOV, aspect and pixel position
    depthValue*=FarClip;

    //convert screenPos to [-1..1] range
    float3 pos = float3(TanAspect*(screenPos*2 - 1)*depthValue, -depthValue);

    //light direction from current pixel to current light
    float3 lDir = LightPosition - pos;

    //compute attenuation, 1 - saturate(d2/r2)
    float atten = ComputeAttenuation(lDir);

    // Convert normal back with the decoding function
    float4 normalMap = tex2D(normalSampler, screenPos);
    float3 normal = DecodeNormal(normalMap);

    lDir = normalize(lDir);

    // N dot L lighting term, attenuated
    float nl = saturate(dot(normal, lDir))*atten;

    //spot light cone
    half spotAtten = min(1,max(0,dot(lDir,LightDir) - SpotAngle)*SpotExponent);
    nl *= spotAtten;

    //reject pixels outside our radius or that are not facing the light
    clip(nl -0.00001f);

    //compute shadow attenuation

    float4 lightPosition = mul(mul(float4(pos,1),CameraTransform), MatLightViewProjSpot);

    // Find the position in the shadow map for this pixel
    float2 shadowTexCoord = 0.5 * lightPosition.xy /
                            lightPosition.w + float2( 0.5, 0.5 );
    shadowTexCoord.y = 1.0f - shadowTexCoord.y;
    //offset by the texel size
    shadowTexCoord += ShadowMapPixelSize;

    // Calculate the current pixel depth
    // The bias is used to prevent floating point errors
    float ourdepth = (lightPosition.z / lightPosition.w) - DepthBias;

    nl = ComputeShadowPCF7Linear(nl, shadowTexCoord, ourdepth);

    float4 finalColor;

    //As our position is relative to camera position, we dont need to use (ViewPosition - pos) here
    float3 camDir = normalize(pos);

    // Calculate specular term
    float3 h = normalize(reflect(lDir, normal));
    float spec = nl*pow(saturate(dot(camDir, h)), normalMap.b*50);
    finalColor = float4(LightColor * nl, spec);

    //output light
    return finalColor * LightBufferScale;
}

```

Now here is the **point light** code that I'm using, which has some sort of bug in the transformation into light space when using the shadow maps:

```
VertexShaderOutputMeshBased PointLightMeshVS(VertexShaderInput input)
{
    VertexShaderOutputMeshBased output = (VertexShaderOutputMeshBased)0;
    output.Position = mul(input.Position, WorldViewProjection);

    //we will compute our texture coords based on pixel position further
    output.TexCoordScreenSpace = output.Position;
    return output;
}

float4 PointLightMeshShadowPS(VertexShaderOutputMeshBased input) : COLOR0
{
    // as we are using a sphere mesh, we need to recompute each pixel position
    // into texture space coords
    float2 screenPos =
        PostProjectionSpaceToScreenSpace(input.TexCoordScreenSpace) + GBufferPixelSize;

    // read the depth value
    float depthValue = tex2D(depthSampler, screenPos).r;

    // if depth value == 1, we can assume its a background value, so skip it
    // we need this only if we are using back-face culling on our light volumes.
    // Otherwise, our z-buffer will reject this pixel anyway
    clip(-depthValue + 0.9999f);

    // Reconstruct position from the depth value, the FOV, aspect and pixel position
    depthValue *= FarClip;

    // convert screenPos to [-1..1] range
    float3 pos = float3(TanAspect*(screenPos*2 - 1)*depthValue, -depthValue);

    // light direction from current pixel to current light
    float3 lDir = LightPosition - pos;

    // compute attenuation, 1 - saturate(d2/r2)
    float atten = ComputeAttenuation(lDir);

    // Convert normal back with the decoding function
    float4 normalMap = tex2D(normalSampler, screenPos);
    float3 normal = DecodeNormal(normalMap);

    lDir = normalize(lDir);

    // N dot L lighting term, attenuated
    float nl = saturate(dot(normal, lDir))*atten;

    /* shadow stuff */

    float4 lightPosition = mul(mul(float4(pos,1),CameraTransform), LightViewProj);

    //float4 lightPosition = mul(float4(pos,1), LightViewProj);
    float posLength = length(lightPosition);
    lightPosition /= posLength;

    float ourdepth = (posLength - NearClip) / (FarClip - NearClip) - DepthBias;
    //float ourdepth = (lightPosition.z / lightPosition.w) - DepthBias;

    if(lightPosition.z > 0.0f)
    {
        float2 vTexFront;
        vTexFront.x =  (lightPosition.x /  (1.0f + lightPosition.z)) * 0.5f + 0.5f;
        vTexFront.y =  1.0f - ((lightPosition.y /  (1.0f + lightPosition.z)) * 0.5f + 0.5f);

        nl = ComputeShadow(FrontShadowMapSampler, nl, vTexFront, ourdepth);
    }
    else
    {
        // for the back the z has to be inverted
        float2 vTexBack;
        vTexBack.x =  (lightPosition.x /  (1.0f - lightPosition.z)) * 0.5f + 0.5f;
        vTexBack.y =  1.0f - ((lightPosition.y /  (1.0f - lightPosition.z)) * 0.5f + 0.5f);

        nl = ComputeShadow(BackShadowMapSampler, nl, vTexBack, ourdepth);
    }

    /* shadow stuff */

    // reject pixels outside our radius or that are not facing the light
    clip(nl - 0.00001f);

    float4 finalColor;
    //As our position is relative to camera position, we dont need to use (ViewPosition - pos) here
    float3 camDir = normalize(pos);

    // Calculate specular term
    float3 h = normalize(reflect(lDir, normal));
    float spec = nl*pow(saturate(dot(camDir, h)), normalMap.b*100);
    finalColor = float4(LightColor * nl, spec);

    return finalColor * LightBufferScale;
}

```

# Answer
> 3 votes
With PIX you can debug pixels isolated, maybe you find the error in this way. FOV or a projection error is a hot hint. Or have you forgot the world transformation?!

# Answer
> 2 votes
Hey Olhovsky, nice challenging question. I know your pain, I implemented Deferred Shading, Inferred Lighting and shadows in my last job. It was really great fun, but lots of pain too when it didn't work as expected.

I think the advice with PIX is actually a good one. You don't have to mess with the assembler instructions of the shader, but you can look at the shadow maps and other render targets, select a pixel and call its pixel shader and step through it and also its vertex-shader.

General debug tricks for this kind of situations include simplification of the scene.

One that comes to my mind is: put the camera at the same position as the light source with the same fovy and other attributes as in the lighting pass. Now you can easily compare the values in the pixel-shader. The pixel-xy in the normal render-pass for your current object should be the same as the calculated pixel-xy for the lookup in the shadowmap, as long as it has the same resolution.

Another one is switch to orthographic projection, render something easy, predictable and checkable. The simpler the better you can check each calculation step.

Other than that, can you show how you create the matrix that calculates the position in the shadow-map for the current pixel, that is the transformation from screen-space to light-space?

---
Tags: shadow-mapping, deferred-rendering
---


# Question
Title: How to calculate the enemy to arrive in the middle of cell?
The game is 2d, and the genre of this game is tower defense.

I managed to get it moving to the cell and arrived in the cell. But it never arrives at the middle of a cell.

Here's what I did...

```
public Enemy plotPath(Cell start, Enemy enemy, float deltaTime) {

    //Direction
    int directionx = 0;
    int directiony = 0;
    if(enemy.position.x < start.position.x) {
        directionx = GraphConstants.X_DIRECTION_RIGHT;
    }
    else if(enemy.position.x > position.x){
        directionx = GraphConstants.X_DIRECTION_LEFT;
    }
    else {
        directionx = GraphConstants.X_DIRECTION_NA;
    }

    if(enemy.position.y < start.position.y) {
        directiony = GraphConstants.Y_DIRECTION_DOWN;
    }
    else if(enemy.position.y > start.position.y){
        directiony = GraphConstants.Y_DIRECTION_UP;
    }
    else {
        directiony = GraphConstants.Y_DIRECTION_NA;
    }
    enemy.position.add(velocity.x * deltaTime * directionx, velocity.y * deltaTime * directiony);

    return enemy;
}

```

Then, the game would calculate the distance between the enemy and a point. If it is zero, then remove the cell from the enemy's list of cells (A\*star algorithm). The enemy position would be calculated by vector addition. It looks like the enemy's position wouldn't never arrive at the point.

Vector addition

```
public Vector2 add(float x, float y) {
        this.x += x;
        this.y += y;
        return this;
    }

```

I have the enemy positioned in (-0.1f, 3.5f). The velocity of the enemy is 2f. The cell is based 1f x 1f. The middle of a cell is (0.5f, 3.5f);

I logged the calculations, here's the calculations -

```
-0.1    3.5
0.03482666  3.5
0.04385986  3.5
0.054541014 3.5
0.072546385 3.5
0.106665045 3.5
0.14072266  3.5
0.17520753  3.5
0.21030274  3.5
0.24313965  3.5
0.27927247  3.5
0.31210938  3.5
0.3467163   3.5
0.3805298   3.5
0.41867676  3.5
0.44882813  3.5
0.486792    3.5
0.5188354   3.5

```

I used distance between the enemy and the middle of a cell -

```
if(position.dist(start.position) == 0) {
                path.remove(0);
 }

```

I'm thinking the velocity * deltaTime * direction isn't correct. I tried to google around but couldn't find the solution. Any ideas?

# Answer
Can you show the code where you check if it has arrived? Do you make a floating point comparison using `==` ? That would not work, check for `>=` or `<=`

Edit: You are right, `velocity * deltaTime * direction` isn't correct, because the velocity should already be the direction, assuming that the velocity has been set properly. It should only be `velocity * deltaTime`, but I dont think thats the problem, since it actually arrived as your logging shows.

Edit: Instead of:

```
if(position.dist(start.position) == 0)

```

use something like:

```
if(position.dist(start.position) < 0.3)

```
> 2 votes

# Answer
if you are going with a\* algorithm there is no need for enemy to reach to exactly center of the cell, just check if it is near the center remove that cell from it's list. you can easily check that : `sqrt(sqr(enemy.x - cell.center.x) + sqr(enemy.y - cell.center.y)) < closevalue`. you can also change velocity at every frame to move directly toward the center and if you are realy close, just set velocity to `distance / dt` or jump your character directly to the center. and as maik said having another variable as direction is wrong, since velocity already contains direction (it can be negetive or positive).
> 0 votes

---
Tags: tower-defense
---


# Question
Title: Looking for a good technique for character movement in hack&slash game
I'm making hack&slash game and I want my characters move like for example in Torchlight, Diablo, etc. Currently I generate set of nodes for all walkable areas of a floor. When I click somewhere player goes there through interpolated path of nodes. This doesn't look very natural. Player moves like a robot. Enemies also use this node system for movement and share the same issue but I have one more problem with them. When enemies detect player they go to him by a shortest path. Sometimes they use the same path and line up to the player instead of surrounding him. I don't know how to make enemies choose different paths and surround the player. Do you know how can I solve this problems? Maybe I should use different approach for character movement?

---

My current technique:

---

Torchlight screenshot:

---UPDATE---

## I want to know how to deal with these situations:

Situation 1, I have dynamic/static obstalces on my way

##

Situation 2, Enemies have the sam path to player ( get into queue to fight with us )

# Answer
> 24 votes
***Steering Behaviours*** in combination with a ***navigation data structure***.

There are a number of ways to do this, but that's the basic concept. It might be easier to use a navigation mesh so that you can apply pathfinding within each convex section.

If you're adamant about keeping a graph, you can use a Seek behaviour to each node in the path, rather than rigidly following a path from node to node.

Another method you could employ is Path Smoothing but bear in mind that this is fairly computationally expensive.

Hope that helps.

EDIT:

To help with your obstacle avoidance issues, use some sort of Obstacle Avoidance.

# Answer
> 3 votes
If you'd rather stick with a nodegraph rather than switch to a nav mesh as others have suggested, then you can solve the "line up to the player instead of surrounding him" problem by assigning each enemy to attack from a particular direction.

There are many ways to accomplish this, but I usually use a 'token' system to assign unique directions to monsters, where the player object possesses one token for each direction (north, northeast, east, etc). When an enemy wants to path to the player, it must first acquire a token from him. The direction specified by the token tells the monster which side of the player it is allowed to pathfind to. Since the player only has one token for each direction, and monsters need a token before they can attack, multiple monsters won't all try to path to the same side of the player, which should break up their paths a bit.

Additionally you might also want to apply a small penalty to nodes during the process of finding paths, to encourage monsters to approach from a direction that matches the token they have. (That is, if a monster has the token which allows it to attack from the east, then for the purpose of determining the "shortest path" for that monster, treat any path nodes which are north/west/south of the player as if they are several nodes, instead of just one). This will make monsters separate faster and try to flank the player, instead of marching up to the player in single-file and only spreading at the last step.

# Answer
> 2 votes
Basically for enemies what you want to do is do pathfinding on a macro level (think about generating convex areas and pathing to the area the player is in), and do some boid-style steering behaviors on the micro level (once you're close to the player).

Here's an example of boid behavior: http://www.red3d.com/cwr/boids/

For the player I think torchlight does pathfinding on a nav mesh for where you click/drag, and that works pretty well. It may feel a bit more disconnected than direct control, but it does lead to better results for the player.

# Answer
> 1 votes
there is an algorithm named rrt which is used for realworld pathfinding problem. the surface your hero (or enemies) can walk on is an input along with the suface that objects can move, and using some optimization algorithm it finds a path to your destination. as much as I know this algorithm is greatly used in robocup leagues. it's fast, finds the shortest path and avoids collision and sharp turns. you can use this powerpoint show to get a grasp on how it generates path.

# Answer
> 0 votes
To make pathfinding routes look more "realistic", I suggest you check out the article about natural-looking A\* in Game Programming Gems Vol.1

---
Tags: ai, rpg, movement
---


# Question
Title: Having a hard time finding a graphic engine programmer
I'm looking for a graphic engine programmer that knows both OpenGL and software rendering code to hire for a very short period (2 days). It's urgent and I'm willing to pay a very high amount of money. Any ideas where I could find one keeping in mind the points mentioned below?

**Clarifications**

1. I am not specifically looking for significant expertise, even intermediate knowledge in OpenGL and software rendering engine code will do.
2. I do not represent a company therefore I can't use gamasutra jobs, stackoverflow careers, etc.

# Answer
> 2 votes
I'm not sure what kind of project that requires significant expertise you can actually do in 2 days, but your best bet is to probably look at the resumes posted on the gamasutra jobs board.

http://www.gamasutra.com/jobs/

# Answer
> 0 votes
try http://careers.stackoverflow.com/

# Answer
> 0 votes
You can try: OpenGL Job Classifieds

---
Tags: opengl, c++, graphics-programming, hiring
---


# Question
Title: Showing Unicode in XNA on Windows Phone 7
I am creating an application which downloads names from server. These names can be any unicode language text which I need to render in XNA on WP7. The biggest problem I see here is WP7 xna system can't render unicode (especially complex script) well. I tried few asian scripts and it looks ridiculous. Some aisan scripts render a character differently depending on neighbor character (generally vowels). Spritefont just renders them one after another without giving any consideration to vowels.

I think I need something like freetype library to render vector fonts on runtime. I wish to know if there are any alternatives to overcome this issue.

# Answer
Recently Microsoft announced using silverlight to render unicode texts in XNA with its mango update for WP7. I think this might solve this issue. I think one just needs to render TextBlock control into XNA, which can handle unicode well.
> 1 votes

# Answer
I don't know if it supports all the fonts you're interested in, and it's rather old so there will certainly be some translation effort if you want to use it. But I figured I may as well post it in case it's useful:

http://blogs.msdn.com/b/manders/archive/2007/01/12/stroke-based-text-rendering-in-xna.aspx
> 1 votes

---
Tags: xna, windows-phone-7, fonts
---


title: Why is my velocity decaying?

text:
# Question
Title: Why is my velocity decaying?
Programming in Java. Tinkering around with physics. My entities all have position and velocity. In the main loop, all I'm doing is applying gravity and bouncing off the edges, like so:

```
    //  add gravity vector
    o.velocity.add(GRAVITY.cpy().mul(dt));

    //  bounce off walls
    if ((o.position.x<0 && o.velocity.x<0) || (o.position.x>WORLD_SIZE_X && o.velocity.x>0))
        o.velocity.x*=-1;

    //  bounce off of ground
    if (o.position.y<=0.0f) {
        o.position.y=0.0f;
        if (o.velocity.y<0)
            o.velocity.y *= -1;
    }

```

The x and y values of my vectors are just floats.

For the first second it looks like it's working fine, but the vertical velocities slowly decay. Any idea why?

# Answer
> 9 votes
As long as you only apply **constant acceleration** (i.e. from constant gravity) **Eulers Method is accurate** and the ball must bounce forever, reaching its initial position again after each bounce phase. If not, then there is something wrong with the implementation of Euler's Method. Here is how it should look like:

```
void update(float dt)
{
    position += velocity * dt + acceleration * 0.5 * dt * dt;
    velocity += acceleration * dt;
    // handling only the simple ground collision case here
    if(position.x < radius)
    {
        velocity = -velocity;
    }
}

```

Note the acceleration is constant here, its simply the gravity.

**EDIT:**

It seems both, the article on gaffergames and the code in the question use a simpler form of Euler's Method, namely:

```
     position += velocity * dt;
     velocity += acceleration * dt;

```

whereas this one as also shown in this paper:

```
     position += velocity * dt + acceleration * 0.5 * dt * dt;
     velocity += acceleration * dt;

```

is still capable of correctly integratiing constant accelerations.

Note: This answer is not supposed to mean that the Euler Method is a good choice for complex physics and non-constant accelerations, nor that you should stick to it once you want to add more physics dynamics to your scene. However, if the application will only use constant acceleration, then this method perfectly fits your needs.

# Answer
> 5 votes
Your objects are bouncing with subsequently smaller bounces because you are applying basic newtonian physics rules to your objects, so they mimic behavior of such objects as you'd expect them to in real life.

You are constantly applying gravity to the velocity of the objects.

When you flip the direction of velocity, the object is now moving up, with an upward velocity, but you are removing some of this velocity with a downward gravity velocity application. With perfect elasticity, and zero friction, you'd expect the object to reach the previous height, but...

You are using Euler integration to approximate the integration of force. This approximation underestimates the effect of the force application.

So when your object hits the ground and velocity is flipped, it can't reach as high as it was before, because the application of gravity is not perfectly accurately integrated (it would be if you had an infintesimally small timestep).

Read "Why Euler's is never good enough": http://gafferongames.com/game-physics/integration-basics/

I think that Euler's actually **is** often good enough, but that's another matter...

# Answer
> 2 votes
Olhovsky explains the problem, but he left out the simple fix. Apply gravity twice.

Basically you are doing three things over and over.

Gravity
Collision
Movement

Swap the order of any two and you'd actually get the opposite problem. Do a halfway swap and you are even. In practice that means do half the gravity before collision checks, and half the gravity after.

½ Gravity
Collision
½ Gravity
Movement

---
Tags: java, physics, euler-method
---


# Question
Title: How to generate a rotation matrix or a quaternion (properly rotated in regards to texture coordinates) for each triangle of a mesh?
I'm trying to build a uniform grid made of 3D points over the surface of an arbitrary mesh (we have texture-coordinates for each vertex...)

Or to reformulate: imagine a mesh textured with a texture featuring equally spaced dots: I want to obtain the 3D coordinates of these dots.

So far, I'm able to generate a normal for each triangle of the mesh but it is not enough.

If I had the right matrix, or quaternion or even orthonormal-basis for each triangle, I guess that I could transform any 2D coordinates (on the triangle's plane) to 3D coordinates (in object space...)

The problem is how to rotate properly in regards to texture coordinates?

To be more specific: for each triangle, I can define a normal. It could serve as the x,y,z part of a quaternion. But how could I generate the w part?

# Answer
> 0 votes
I found this answer by user S1CA in the gamedev.net forum:

A, B, C are the vertices of a particular triangle.
Auv, Buv, Cuv are the UV coordinates at the vertices.
Axyz, Bxyz, Cxyz are the positions of the vertices.
Puv are the UV coordinates of the point.
Pabc are the barycentric coordinates of the point \[for that triangle\]
Pxyz is the object space position of the point

aa = (Bu-Au) * (Cv-Av) - (Cu-Au) * (Bv-Av)
Pa = ((Bu-Pu) * (Cv-Pv) - (Cu-Pu) * (Bv-Pv)) / aa
Pb = ((Cu-Pu) * (Av-Pv) - (Au-Pu) * (Cv-Pv)) / aa
Pc = ((Au-Pu) * (Bv-Pv) - (Bu-Pu) * (Av-Pv)) / aa

The above are just a bunch of 2D cross products. The 2D cross product happens to give you the area of a triangle. If you look at the Wolfram reference posted above, it notes that the areas of the sub triangles ABP ACP and BCP are proportional to the barycentric coordinates.

The division of each sub triangle by the area of the main triangle is so we can get the useful property of areal coordinates that for any point which is *inside* the triangle, Pa+Pb+Pc=1

Once you have barycentric coordinates, you can use those to convert between texture units and object units by doing:

Pxyz = Axyz\*Pa + Bxyz\*Pb + Cxyz\*Pc

# Answer
> 0 votes
**Edit new answer:**

Ok this shows you how to calculate the rotation-matrix that rotates the triangle from its local space into world-space.

Given `normalLocal` (the normal of the triangle in object-space) and `normalWorld` (the normal of the triangle in world-space)

1. Find the rotation-axis by taking the cross-product of the 2 normals

`axis = normalLocal cross normalWorld`
2. Find the rotation angle by taking arccosine of the dot-product of both normals

`angle = acos(normalLocal dot normalWorld)`
3. Now create a rotation-matrix from those values .

---

**Old obsolete answer:**

You can just use the texture-coordinates to define the triangle points. Just put them into x and y of the point and leave z at zero.

**Example:**

`texUV {u, v}` are the 3 texture-coordinates for 1 trangle

`p` are the 3 associated euclidean points of the triangle

```
texUV0 = {0.0, 0.0}
texUV1 = {0.5, 0.5}
texUV2 = {0.5, 0.0}

p0 = {texUV0.u, texUV0.v, 0.0}
p1 = {texUV1.u, texUV1.v, 0.0}
p2 = {texUV2.u, texUV2.v, 0.0}

p0 = {0.0, 0.0, 0.0}
p1 = {0.5, 0.5, 0.0}
p2 = {0.5, 0.0, 0.0}

```

The normal for this triangle is `{0.0, 0.0, 1.0}` or `{0.0, 0.0, -1.0}` depending on your definition of a front face, clockwise or counterclockwise.

---
Tags: opengl, mathematics, geometry
---


title: Multiplayer HTML5, Node.js, Socket.IO

text:
# Question
Title: Multiplayer HTML5, Node.js, Socket.IO
I trying create simple Multi-player with HTML5 Canvas, JavaScript(too using John Resig simple Inheritance library) and Node.js with Socket.IO. My client code:

```
var canvas  = document.getElementById('game');
var context = canvas.getContext('2d');
var socket  = new io.Socket('127.0.0.1', {port: 8080});

var player = null;

var UP    = 'UP',
    LEFT  = 'LEFT',
    DOWN  = 'DOWN',
    RIGHT = 'RIGHT';

socket.connect();

socket.on('connect', function() {socket.send();
    console.log('Connected!');
    player = new Player(50, 50);
});

socket.on('message', function(msg) {
    if(msg == 'UP') {
        player.moveUP();
    } else if(msg == 'LEFT') {
        player.moveLEFT();
    } else if(msg == 'DOWN') {
        player.moveDOWN();
    } else if(msg == 'RIGHT') {
        player.moveRIGHT();
    } else {

    }
});

socket.on('disconnect', function() {
    console.log('Disconnected!');
});

var Player = Class.extend({
    init : function(x, y) {
        this.x = x;
        this.y = y;
    },
    setX : function(x){
        this.x = x;
    },
    getX : function(){
        return this.x;
    },
    setY : function(y){
        this.y = y;
    },
    getY : function(){
        return this.y;
    },
    draw : function(){
        context.clearRect(0, 0, 350, 150);
        context.fillRect(this.x, this.y, 15, 15);
    },
    move : function() {
        this.x += 1;
        this.y += 1;
    },
    moveUP : function() {
        this.y--;
    },
    moveLEFT : function() {
        this.x--;
    },
    moveDOWN : function() {
        this.y++;
    },
    moveRIGHT : function() {
        this.x++;
    }
});

function checkKeyCode(event) {
    var keyCode;
    if(event == null) {
        keyCode = window.event.keyCode;
    } else {
        keyCode = event.keyCode;
    }

    switch(keyCode) {
        case 38: // UP
            player.moveUP();
            socket.send(UP);
        break;
        case 37: // LEFT
            player.moveLEFT();
            socket.send(LEFT);
        break;
        case 40: //DOWN
            player.moveDOWN();
            socket.send(DOWN);
        break;
        case 39: // RIGHT
            player.moveRIGHT();
            socket.send(RIGHT);
        break;
        default:
        break;

    }

}

function update() {
    player.draw();
}

var FPS = 30;
setInterval(function() {
    update();
    player.draw();
}, 1000/FPS);

function init() {
    document.onkeydown = checkKeyCode;
}

init();
```

And server code:

```
var http = require('http'),
    io = require('socket.io'),
    buffer = new Array(),

server = http.createServer(function(req, res){
    res.writeHead(200, {'Content-Type': 'text/html'});
    res.end('

# Hello world

');
});
server.listen(8080);

var socket = io.listen(server);

socket.on('connection', function(client){

    client.on('message', function(message){
        console.log(message);
        client.broadcast(message);
    })
    client.on('disconnect', function(){

    })

});
```

And when I run two client's I with first client can move second client Rect and with second client move first client rect and something like with third client can move first and second client rect's.

I have question how to create real Multi-Player? something like: Open three client's and first client get rect1, second rect2 and last rect3. First client only can move rect1, client third can move only rect3.

Maybe anyone have idea? I search in Google but don't find answer.

Sorry for my English language, Thanks.

# Answer
I have created a framework specifically for creating HTML5 realtime multiplayer games, based on the Client/Server model. In this model, players send only input to the server (keys being pressed) - and the game occurs on the server.

The server sends timed world-snapshots to all clients, and clients render themselves say 75 ms back in time from the current time, by finding two known world updates their rendertime falls between.

Repository (contains 3 demos)
https://github.com/onedayitwillmake/RealtimeMultiplayerNodeJs

Video Box2D demo in action:
http://vimeo.com/24149718

Slides from JSConf 2011:
http://www.slideshare.net/MarioGonzalez15/realtime-html5-multiplayergameswithnodejs-7868336

It's based on Quakeworld and Valve's Source engine whitepapers:
http://fabiensanglard.net/quakeSource/index.php http://developer.valvesoftware.com/wiki/Source\_Multiplayer\_Networking
> 15 votes

---
Tags: multiplayer, html5, html-canvas, websocket, node.js
---