# Question
Title: What would most games benefit from having?
I think I've seen "questions" like this on stackoverflow but sorry if I'm overstepping any bounds.

Inspired by my recent question and all the nice answers (Checklist for finished game?) I think every gamedev out there has something he/she thinks that almost every game should have. That knowledge is welcome here!

So this is probably going to be an inspirational subjective list of some sorts and the point is that anyone reading this question will see a point or two that they've overlooked in their own development and might benefit from adding.

I think a good example might be: "some sort of manual or help section. Of course it should be proportional to how advanced the game is. Some users won't need it and won't go looking for it but the other ones that do will become very frustrated if they can't remember how to do something specific that should be in the manual".

A bad example might be "good gameplay". Of course every game benefits from this but the answer is not very helpful.

# Answer
Most games would benefit from having some character.

Good games have a core of solid gameplay. **Great games combine solid gameplay with character.** Here's the checklist we use:

**1. Iterate until the high concept is remarkable.**

The process here is straightforward -- wrap the damned game description up into a single sentence. Speak it to a bunch of people. If they smile and say "yeah, that sounds cool," scrap it, and think about what really makes your game unique. After a while, you'll sum things up right, and they'll laugh, or they'll yell, "Holy crap, I have to play it!"

Our last game's high concept was "BASE jump off of a perfectly good building, create your own stunts, and flip people off for points." It's simple, but it worked really well for us at conventions/conferences.

**2. Make unexpected tidbits remarkable.**

When you repeatedly clicked on your Starcraft pieces, they started saying some crazy shit. Players didn't expect this, yet that tiny thing (how long did that take to write and record?) is something people still talk about today. This is really low-hanging fruit; go through your design, piece by piece and add the quirky bits.

We added a guided meditation to our most recent game. It gave something for reviewers to talk about. People kept commenting on how they sat through it, waiting for it to start screaming at them.

**3. Make boring things interesting.**

Game installers are typically boring. Setup menus are typically boring. Sit down for a half hour, poke at all these boring places, and see what comes out.

Playground slides are typically boring, but they don't have to be (http://www.foundshit.com/elephant-playground-slide).
> 28 votes

# Answer
Pausable and skippable cutscenes. In my opinion both should be in the TRCs for the major consoles.
> 17 votes

# Answer
Can't believe no-one has added the ability to rebind keys!
> 14 votes

# Answer
People always like achievement/trophies, and they're really easy to make.
> 8 votes

# Answer
Personally I think nearly every game should have some way for you to challenge other gamers, whether it be directly in multiplayer or in some sort of highscore boards. Recently I have noticed a lot of (mainly mobile) games with great potential ignore this which brings down replayablity.

also -***cough***\- dedicated servers -***cough***\- ¬\_¬
> 8 votes

# Answer
If your buttons are mostly just graphics, not labeled by words of what they do, there should be a way to find out exactly what that button does **without** clicking it. An effective way to do this is with tool-tips.
> 7 votes

# Answer
Leaderboards, lots of them. Not arcade-style top-10 lists because those get dominated by a handful of people quickly. Fastest time to completion, high score, most damage dealt, whatever, for all-time and the past week. Ideally every player should feel like they could get to the top of at least one if they tried.
> 7 votes

# Answer
NO CHECKPOINTS. Let me save anytime I want. I paid for the game and I have a life I need to get back to quickly sometimes.
> 7 votes

# Answer
A release.

Many games that have great potential on the indie side of things never get this.
> 7 votes

# Answer
Not a lot of people will play a game if they have to read 10 minutes worth of instructions first. I think it's important to have the user actually participating in the tutorial, and have the tutorial advance based on the user's pace (f.e allow them to skip certain parts that they might already know how to do (because they've played other similar games)).
> 6 votes

# Answer
If you have multiplayer, you should do your best to offer some kind of local multiplayer (co-op is usually easier to do than local versus). This seems to be a dying art, especially among console titles.
> 6 votes

# Answer
Autosave. I hate playing through the first chapters of a game just to realize that I have to do the beginning tutorial all over again when I die.
> 6 votes

# Answer
**Sixty Frames Per Second!**

If a game contains any form of action, it would benefit greatly from running at 60fps\*, vsynced, without tearing.

This can be the difference between an OK game and an awesome game.

I expect that several uninformed newbies will now respond 'but the human eye can only see 25-ish'. That's nonsense. (Someone needs to write a nice little test program to demonstrate the difference, maybe split-screen 30 and 60fps)

As developers we've got very sloppy about performance recently, in the push to add 'more stuff' and 'bigger stuff' to games. It's not uncommon for games to drop to 20fps or less, which is really quite poor.

Back in the early-mid 90's, maybe even before, 60 frames per seconds was the very definition of 'Arcade Quality'. All those lovely smooth 16bit platformers and shooters. And remember games like Daytona and Ridge Racer? Early, groundbreaking 3D titles - that made the (correct) decision to run at 60fps, rather than add more visual detail.

These days everyone's competing on screenshot quality, and making games 'bigger'. Gameplay has really suffered, particularly in certain genres, such as racing games, where 30fps or less feels terrible to play once you've had a taste of 60fps

(\*Ok, there's nothing magic about 60 as a number, but to look good, a game should by synchronised with the refresh of the screen, at a constant framerate of 50 or more. And use of lower framerates for cutscenes, for a 'cinematic' look is perfectly acceptable)
> 6 votes

# Answer
The ability to suspend play at any time. A pause menu option that quits the game but takes you back to the main menu. You can resume the game from that point but only once. This restriction stops you turning it into a quicksave system, but still allows you to exit whenever life demands it. It would probably be in addition to some checkpointing system.

A fair number of games already do this, but I can't think of any examples off the top of my head!
> 5 votes

# Answer
Replayability.
Some games you play once through, and then that's the end of it. Something like Portal; there's no replayability in it.
On the other hand, a lot of the non-linear RPGs - Fallout 3 and Oblivion, for example - have huge amounts of replayability.
Not just from going 'I might play this kind of character next time' or 'I will be friendly to these people', but also to 'I haven't been to place X, I wonder what's there'.
Second point is more of plenty to do, but still adds replayability.
> 3 votes

# Answer
IMHO every game should allow for a certain number of play styles. (I.e. Deus Ex and Way of the Samurai for RPG like games and Card games like Yu-gi-OH or Magic the gathering, Scribblenauts as well did this very very well with multiple ways to solve a puzzle the way you want to.)
> 2 votes

# Answer
A clock. Really, if your game starts in fullscreen by default (which far too many games do, but thats another show) it needs to have a wall-time clock (as opposed to game time).
> 2 votes

# Answer
**Easy to learn controls.**

This means I don't want to spend the first 3 hours of 'gameplay' doing frustratingly dull tutorial levels. I want to play (even a very easy level) of the game now.

FPS games are by far the worst offenders here.. 'go hit this moving target', 'run over here', etc. Very boring. If I want to learn the basic controls then I'll check the controls screen on the menu. Or the manual.

If I absolutely must learn one or two things to be able to play the level I'm on, then as long as they are introduced the first time I need them that's OK, but it shouldn't feel like a chore to learn to play the game!
> 1 votes

# Answer
My wish list contains:

* **Dynamically adjusting difficulty**. In most genres it's the easiest thing to implement. And nothing is more depressing, than paying 60 bucks for a new game and not getting past level 4, because meanwhile you got a life and have become a casual gamer ;) Also, it's depressing to have to select "very super dummy easy" ;) However, this should always be an (defaulted) addition to standard difficulties, because in first-person shooters it kills off comparability to others.
* **COOP**, It's awesome to dive into a overwhelming, exciting fantasy-RPG world, but what's with being king of the hill, if no-one knows about it? ;) Oblivion and Two Worlds are good bad examples of this. Same goes for first-person shooters. Remember Counterstrike clan wars? Well guess what, that was a crippled self-made COOP variant of the game. IMHO, COOP should be in every 21st century game. Why do you guess the Wii boomed so much, apart from the controller? Certainly not because of good graphics or physics.
* Remotely referencing Wight's post: **Non-linear gameplay**. Admittedly, if done very very well, a linear story can work. I guess Mafia II roughly did okay, because they had a dense story. But still: We should be way past the days where "COMBINE glue WITH stick" wouldn't work while "COMBINE stick WITH glue" did. I don't demand complete diversity like Fahrenheit/Indigo Prophecy stood out with (mainly because it's hard to continue the story with a follow-up, and it vastly challenges the ratio of gameplay length to game design effort (and thus financial spendings). Still: Every alternative makes the game more vivid and less "gamey" ^^
> 1 votes

---
Tags: game-design
---


# Question
Title: Physics in my game confused after restructuring the Game loop
I'm on my way with making a game in Java. Now I have some trouble with an interpolation based game loop in my calculations.

Before I used that system the calculation of a falling object was like this:

* **Delta based system**

```
private static final float SPEED_OF_GRAVITY = 500.0f;

@Override
 public void update(float timeDeltaSeconds, Object parentObject) {

parentObject.y = parentObject.y +
          (parentObject.yVelocity * timeDeltaSeconds);

parentObject.yVelocity -= SPEED_OF_GRAVITY  * timeDeltaSeconds;
    ......

```

What you see here is that I used that delta value from previous frame to the current frame to calculate the physics. Now I switched and implement a interpolation based system and I actually left the current system where I used delta to calculate my physics.

However, with the interpolation system the delta time is removed - but now are my calculations screwed up and I've tried the whole day to solve this:

* **Interpolation based system**

```
private static final float SPEED_OF_GRAVITY = 500.0f;

@Override
public void update(Object parentObject) {

parentObject.y = parentObject.y +
        (parentObject.yVelocity);

parentObject.yVelocity -= SPEED_OF_GRAVITY;
    ......

```

I'm totally clueless - how should this be solved? The rendering part is solved with a simple prediction method. With the delta system I could see my object be smoothly rendered to the screen, but with this interpolation/prediction method the object just appear sticky for one second and then it's gone.

The core of this game loop is actually from here deWiTTERS Game Loop, where I trying to implement the last solution he describes.

**Shortly - my physics are in a mess and this need to be solved.**

Any ideas? Thanks in advance!

# Answer
> 5 votes
Shortly put, your gravity speed is very, very different in the two systems.

In the first, your delta time is probably around a few milliseconds (let's say 0.15 seconds for simplicity's sake).

You are adding 500 * 0.15 to the y position which is 75.

In the second, you're adding 500. Always. And increasing the velocity by 500 in each update is going to cause MASSIVE problems! So for the second reduce your gravity speed drastically, and see what happens.

Hope that helps :)

# Answer
> 2 votes
As pointed out by Ray, you need to adjust the gravity. I'd like to add that your life will be easier if you adapt metric units to your game. That means:

* In the coordinate system 1.0 should equal one meter
* For time 1.0 should equal one second
* For mass 1.0 should equal one kilogram

If you follow these rules, you can intuitively relate values from the game physics to real world units. What also follows is that you can use 9.81 for the gravity constant to get natural gravity.

---
Tags: physics, java, game-loop
---


# Question
Title: Obtaining a world point from a screen point with an orthographic projection
I assumed this was a straightforward problem but it has been plaguing me for days.

I am creating a 2D game with an orthographic camera. I am using a 3D camera rather than just hacking it because I want to support rotating, panning, and zooming. Unfortunately the math overwhelms me when I'm trying to figure out how to determine if a clicked point intersects a bounds (let's say rectangular) in the game.

I was under the impression that I could simply transform the screen point (the clicked point) by the inverse of the camera's View * Projection matrix to obtain the world coordinates of the clicked point. Unfortunately this is not the case at all; I get some point that seems to be in some completely different coordinate system.

So then as a sanity check I tried taking an arbitrary world point and transforming it by the camera's View\*Projection matrices. Surely this should get me the corresponding screen point, but even *that* didn't work, and it is quickly shattering any illusion I had that I understood 3D coordinate systems and the math involved.

So, if I could form this into a question: How would I use my camera's state information (view and projection matrices, for instance) to transform a world point to a screen point, and vice versa? I hope the problem will be simpler since I'm using an orthographic camera and can make several assumptions from that.

I very much appreciate any help. If it makes a difference, I'm using XNA Game Studio.

# Answer
> 2 votes
Is you screenPoint between values (-1 ; 1)? If you are using ( 0 ; screenResolution ) it will not work.

```
//conversion from pixel values to unit cube (result of projection)
vec4 screenPoint = ( (clickedX / screenWidth)*2.0 - 1.0, (clickedY / screenHeight)*2.0 - 1.0, 0.5, 1.0);

```

`screenPoint.Z` defines distance from camera 0.0 = znear, 1.0 = zfar. As you are making 2D game, you dont care about it propably.

`screenPoint.W` have to be 1.0

---
Tags: xna, 2d, 3d, camera, coordinates
---


title: Online architecture guide

text:
# Question
Title: Online architecture guide
I am a newbie in gamedev, and I don't know about programmer's problems that can appear during development.

So can you advice me some best practice for starting build new online multi-player game backend?

I just saw reddraft server, and I think Spring library can also do some of its features. What is big difference? Do I need learn more spring or I have to use servers like reddraft or write these tools myself?

I know that I need to learn hard and many - and the question is - what I should to learn now at the beginning?

Thanks.

# Answer
I know this is disheartening, but I'd recommend getting a bit of single-player development experience before coding a multiplayer game. Multiplayer development has all of the issues of single-player, plus a hundred more. Doing a single-player game will let you learn some of the programming problems that can appear. When you no longer consider yourself a gamedev newbie, go for multiplayer.
> 6 votes

---
Tags: architecture, java, tools, server, online
---


# Question
Title: Control diamond square algorithm to generate islands/pangea
I generated a height map with the diamond square algorithm. The thing is i do not manage to create islands, this is, restrict the height other than water level range to a certain value in the center of the map.

I manualy seeded a circle in the middle of the map but the rest of the map still receives heights over the water level.

I dont fully understand the Perlin noise algorithm so i'd like to work with my current implementation of the diamond square algorithm which took me 3 days to interpret and code in PHP. :P

UPDATE:

I'm trying to get a gradient and its working (it's late and have to refine it, i'll try tomorrow). I tried to work with gradients but silly me, I had been clamping the affected values to a radius, giving me a circle when generating the map.

The seeding option is NOT working. I may get some bigger landmass, but may be located in any sector in the map, not even close to the center.

Please have in mind that the DSA generates the middle value averaging it's corners, so its not possible to seed the middle of a square.

```
a     b
   f
c     d

f = (a+b+c+d) / 4 + random(-value,value)

```

Perhaps that's why seeding it's not working.

# Answer
> 2 votes
From your question I infer that you're trying to seed the border/shore of the island. You might want to do that if it's important that the island's shape is fairly circular, otherwise there's no need.

But what you do have to do is seed a point (the highest) inside the island and few points (the lowest) outside the island. The rest will arrange itself.

To simplify, assuming sea-level is 0, highest point 1, this should be enough a seed:

```
 -1,0                    -1,0

              1,0

 -1,0                    -1,0

```

Ignoring randomization, first iteration (square) gives:

```
 -1,0       [-0,3]       -1,0

[-0,3]        1,0       [-0,3]

 -1,0       [-0,3]       -1,0

```

Second (diamond):

```
 -1,0        -0,3        -1,0
      [-0,2]      [-0,2]
 -0,3         1,0        -0,3
      [-0,2]      [-0,2]
 -1,0        -0,3        -1,0

```

Third (square):

```
 -1,0 [-0,4] -0,3 [-0,4] -1,0
[-0,4] -0,2  [0,1] -0,2 [-0,4]
 -0,3  [0,1]  1,0  [0,1] -0,3
[-0,4] -0,2  [0,1] -0,2 [-0,4]
 -1,0 [-0,4] -0,3 [-0,4] -1,0

```

A bit of clutter, but you might see the beginning of an island in the middle of the map.

# Answer
> 0 votes
There are multiple ways to generate islands, if you want a single island you could try to simply add a gradient (multiplying the result by 0 (edges of the map) to 1 (perfect center)) would usually create a single island.

Its also possible to pre-seed certain values, initialize part of the height map with some values and on choosing a new value check before hand if it hasn't been pre-seeded yet, this could create multiple islands (choose a few random places and put large values in them) or a single island (put a large value in the center of the map).

---
Tags: algorithm, maps, php, heightmap
---


title: Very slow direct3D texture sampling

text:
# Question
Title: Very slow direct3D texture sampling
So I'm writing a small game using Direct3D 9 and I'm using multitexturing for the terrain. All I'm doing is sampling 3 textures and a blend map and getting the overall color from the three textures based on the color channels from the blend map. Anyway, I am getting a massive frame rate drop when I sample more than 1 texture, I'm going from 120+ fps to just under 50.

This is the HLSL code responsible for the slow down:

```
float3 ground = tex2D(GroundTex, multiTex).rgb;
float3 stone  = tex2D(StoneTex, multiTex).rgb;
float3 grass  = tex2D(GrassTex, multiTex).rgb;
float3 blend  = tex2D(BlendMapTex, blendMap).rgb;

```

Am I doing it wrong ? If anyone has any info or tips about texture sampling or anything, that would be nice.

Thanks.

# Answer
If you want to speed things up you can use something called a texture atlas.

> **Wikipedia** — A texture atlas is a large image, or "atlas" which contains many smaller sub-images, each of which is a texture for some part of a 3D object. The sub-textures can be rendered by modifying the texture coordinates of the object's uvmap on the atlas, essentially telling it which part of the image its texture is in. In an application where many small textures are used frequently, it is often more efficient to store the textures in a texture atlas which is treated as a unit by the graphics hardware.

It is more efficient for a GPU to sample a single large texture 4 times versus 4 images sampled once each. Here is an example of a terrain texture atlas.
> 9 votes

# Answer
Another thing to consider is the texture format. Is it a raw 32bpp texture? If so, consider using a compressed DXT1 texture, which is 4 bits/pixel (taking 1/8th of the space), or DXT5 if you need the alpha channel, at 8 bits/pixel.

Reducing the size of the texture data should result in reduced texture memory bandwidth requirements, and improved texture cache performance.

Also, check that you've not setting maximum quality anisotropic filtering - that can add a fair bit of cost.
> 4 votes

# Answer
Do your textures have mipmaps?

Without mipmapping, texture sampling can be particularly expensive (loads of cache misses)
> 3 votes

---
Tags: textures, directx, shaders, hlsl
---


# Question
Title: Are there benefits to stage selections where only the appearance changes (i.e. Street fighter, King of fighters etc.)?
I'm not really sure if it's a good value add seeing as it would entail asset generation.

The only value I see in it would be for variance but even that would wear thin really quickly.

Clarification: i.e. Backgrounds that don't add game play related features, just appearance changes.

# Answer
> 5 votes
This post about de Blob is cited in the first chapter of *Game Feel*:

> When the ball bounces or moves very fast, it slightly deforms, and while rolling it slightly sags. On screenshots this is quite a subtle effect, but when seen in action, it really looks fun. An interesting detail about this, is that it changes the feel of the gameplay entirely. Without the squash-shader, the game feels like playing with a ball made of stone. Then with no changes to the physics at all, the squash-shader makes it feel much more like a ball of paint.

In other words, *yes*. Appearance alone can significantly affect *perception* of the game mechanics, which in turn affects *how players play*. Swink calls this "interactions emphasized by polish", and it's the earliest working definition of "game feel" provided in the book.

# Answer
> 11 votes
Playing against the same background repeatedly would get boring quick. Also in single player the stage selection generally meant who you fought against.

I remember always wanting to play on the air force base level in street fighter 2, and a friend always wanted to play Ryu's level, so there is some preference.

So yes it is entirely cosmetic, as with so much in games the visual element provides a great deal. However fighting games don't have much in the way of assets anyway, so variation in backgrounds isn't so much to ask.

# Answer
> 4 votes
Not only fighting games do this. It's a technique used in most games & genres. To name a few: Mario, Sonic, Zelda, Contra, R-type, Ghost-n-goblins, Out-run, Starcraft 2.

All those have several "tilesets" and "backgrounds".

The first reason, as PhilCK has mentioned, is that players get bored really when they get presented with the same art again and again.

The other reason is that art (even on non-interactive elements, such as backgrounds) adds another layer of meaning to the levels it is used in.

Take Super Mario's Ghost House, for example. The shadowy black tiles & closed windows in the background (and that music!) really do transmit something completely different from the ones in Yoshi's Island.

# Answer
> 2 votes
Keep in mind that not all fighting games have gameplay-identical backgrounds. I've played a few games where the stages had different environmental hazards, or secrets that allowed for special fatality-like moves when performed in specific locations, etc.

So if it really bugs you to produce extra assets with no gameplay value, you could always add some gameplay to the equation...

---
Tags: game-design
---


# Question
Title: How do I plot individual pixels using the XNA APIs?
If I wanted to fill my game screen with individually coloured pixels, how would I do this?

For example, if I wanted to write a 'game of life'-type game where each pixel was a cell, how would I achieve this using XNA?

I've tried just calling `SetData()` on a `Texture2D` object using a screen-sized array of `Color` values, but it complains with:

```
You may not call SetData on a resource while
it is actively set on the GraphicsDevice.
Unset it from the device before calling SetData.

```

How do I do as it asks? Or better still... is there an alternative, better, efficient way to fill a screen with arbitrary pixels?

# Answer
It sounds like the texture is still selected into the GraphicsDevice (or at the very least in use still as the GPU is allowed to lag behind the CPU to achieve the best performance). I've not really used XNA so I can't really speak to the exact nature of that error.

However, if you do this with a single texture and managed to fix the above problem you would most likely incur a costly peformance bottleneck which requires the CPU to sit around waiting for the GPU to finish using that texture before it can lock it again (the CPU would be blocked from continuing until it could lock the texture knowing it was safe to do so). A better solution would be to create two textures and double-buffer their usage, so you write to Texture 1, then render with it, the next frame write to Texture 2 instead, render with it, switch back to Texture 1 again, etc. That way you can ensure the GPU won't be using the texture still and should also solve the problem you have now.
> 5 votes

# Answer
For drawing lines and such I've just used a 1x1 white texture and scaled/rotated it. Not sure if that will be any faster, but it is an option

```
pixel = new Texture2D(graphicsDevice, 1, 1);
pixel.SetData<Color>(new Color[1] { Color.White });

```
> 0 votes

---
Tags: xna, graphics, directx
---


# Question
Title: How does Blizzard manage to support Mac OS and Windows in their games?
I've always thought that using Direct X for Windows was the most powerful, easy and modern method to create games with modern graphics, nowadays. Knowing that it's only Windows, I thinks it's pretty difficult to make something similar on other platforms; Mac OS, to be exact. However, Blizzard somehow managed to deliver Starcraft 2 for Mac OS, and Diablo 3 will be available for Mac, too.

So what I'm interested in is information about:

* what technologies are they using for their game engines?
* are they using one engine for both games (Starcraft 2 and Diablo 3), or do they develop custom engines for each game?
* what are they paying, in terms of time and money, for Mac OS support?

# Answer
Blizzard is very custom-tech driven. I don't have links to the articles, but I remember seeing that they develop thousands of custom shaders per game for both multiplatform compatibility and backwards compatibility.

Multiplatform support isn't something new. Plenty of software supports Linux, Mac OS, and Windows. As was mentioned above, the important part is abstracting away from platform specifics.

Any contemporary game engine handles multiplatform and many can switch between OpenGL and DirectX depending on the platform.

Blizzard is a C++ house, like most professional large scale developers. But, as was mentioned by S.gfx, if you're looking for an easy solution, there are plenty of non-C++ solutions -- including jMonkeyEngine or LWJGL.

From the C++ side, you can utilize Glut and Glu to easily handle different operating systems while using OpenGL, or write your own abstraction for specific OS calls.

To more specifically answer your bullets:

**what technologies are they using for their game engines?** Blizzard probably wouldn't say; but, you can be sure the engine is written in C++ and utilizes OpenGL or OpenGL and DirectX. Remember, OpenGL runs on Windows.

**are they using one engine for both games (Starcraft 2 and Diablo 3)? Or develop custom for each game?** Blizzard has been known to maintain multiple engines. Diablo 3, from the onset, was a fork of WoW's code, I believe. But, you can be sure it will be nothing like WoW once they've finished the project. Blizzard isn't a company afraid of writing plenty of code per project.

**what are they paying in terms of time and money for Mac OS support?** If done correctly, Mac OS support shouldn't be "too" significant of a cost. Anyone can guess. Blizzard, as I said, has a tendency to write custom shaders so everything looks "just right"; so, it could be more than other houses pay.
> 17 votes

# Answer
There are graphic engines out there (take Ogre3D as an example) that provide an abstract layer on top of DirectX and OpenGL. So as a developer you just use the Framework and don't have to care much about the underlying GPU-API. Some special things like shaders may have to be written in HLSL *and* GLSL but there are also higher level shader languages that can run/compile to both APIs.

My assumption would be that the engine Blizzard uses (they wrote their own) also provides an abstraction layer that makes it easy to swap the underlying graphics API, so that they don't have to rewrite all their graphics code for a Mac port.
> 9 votes

# Answer
I am not sure on what they actually use (each one would have a powerful solution, surely) . Probably already proven and used game engines succesfully releasing games on that platform, or rolling their own custom solution. But to me that it'd be opengl, shaders, etc, mostly. If you are an indy developer, or even plan on doing commercial games (just no AAA) jMonkeyEngine 3 is quite a nice free solution. It's java based, so probably you could deploy trusting on OSX's included JRE (probably cutting features if not using a very modern jre) , or embed/wrap a binary (we made a test doing so for Windows) using any of the available free or commercial solutions. There are a bunch of other engines compiling to OSX and other platforms, but not totally 'AAA', which output for OSX and other platforms: Unity, C4 Engine, etc. Or if using other open source or commercial multiplatform engine, you might need using a cross platform installer like InstallBuilder.
> 2 votes

---
Tags: windows, macos
---


# Question
Title: Can Achievement systems be implemented later in development?
I'm undecided if I want to implement this feature in my game at the time or not. I don't want the project to get to far out of control so I'm focusing on core mechanics first.

Is this a feature that is easy to implement later assuming I data drive everything and store everything?

# Answer
Are you asking from the perspective of technicalities of implementing or the ramifications of the design? Either way, the answer to your question is "yes".

From the technical side of things, generally speaking you just find the hooks in your code that are responding to your achievement events and put in your stat tracking code there. You might have to add some new things if you're tracking things that aren't exactly discrete events that are already happening in the game (for example: X amount of hours played).

From the design side of things, well, achievements are extrinsic motivators and adding them doesn't really play too much into the core gameplay loop, except for people who want to seek them out. So they're pretty safe regardless.
> 19 votes

# Answer
Provided that your game engine is designed well and uses some kind of observable event system (where events are generated and listened for by interested parties), it should be quite easy to "plug-in" an achievement system at a later point (by adding appropriate listeners). This kind of design is very flexible.
> 5 votes

# Answer
As already the existing people have added good answers, let me answer uncovered situations.

If at all you are in a position where you have completed coding your game and now starting to code achievements and find it very complex to maintain too many variables and counts and clearing them off at certain events and things like that.

You can always create one class (preferably singleton) to receive all events. Now list all your achievements. Then list all game events needed to be tracked. For e.g. my current list looks like this

KILL ENEMY - walking, bullets PLAYER DEATH - falling\_off, health ENTER\_ROOM, EXIT\_ROOM etc.

Those extra details like walking, bullets can be parameters. Now have one function called fireEvent in that Achievement tracking class. Search all places in code where you need to fireEvents and call that function. Now do the rest of dirty work in the Achievements class. this is the safest way to not disturb existing code and code Achievements. It worked out pretty fast for me.
> 2 votes

---
Tags: game-design, achievements
---


# Question
Title: How Do I Do Alpha Transparency Properly In XNA 4.0?
Okay, I've read several articles, tutorials, and questions regarding this. Most point to the same technique which doesn't solve my problem. I need the ability to create semi-transparent sprites (texture2D's really) and have them overlay another sprite.

I can achieve that somewhat with the code samples I've found but I'm not satisfied with the results and I know there is a way to do this. In mobile programming (BREW) we did it old school and actually checked each pixel for transparency before rendering.

In this case it seems to render the sprite below it blended with the alpha above it. This may be an artifact of how I'm rendering the texture but, as I said before, all examples point to this one technique. Before I go any further I'll go ahead and paste my example code.

```
    public void Draw(SpriteBatch batch, Camera camera, float alpha)
    {
        int tileMapWidth = Width;
        int tileMapHeight = Height;

        batch.Begin(SpriteSortMode.Texture,
            BlendState.AlphaBlend,
            SamplerState.PointWrap,
            DepthStencilState.Default,
            RasterizerState.CullNone,
            null, camera.TransformMatrix);

        for (int x = 0; x < tileMapWidth; x++)
        {
            for (int y = 0; y < tileMapHeight; y++)
            {
                int tileIndex = _map[y, x];

                if (tileIndex != -1)
                {
                    Texture2D texture = _tileTextures[tileIndex];

                    batch.Draw(
                        texture,
                        new Rectangle(
                            (x * Engine.TileWidth),
                            (y * Engine.TileHeight),
                            Engine.TileWidth,
                            Engine.TileHeight),
                        new Color(new Vector4(1f, 1f, 1f, alpha )));
                }
            }
        }

        batch.End();

    }

```

As you can see, in this code I'm using the overloaded SpriteBatch.Begin method which takes, among other things, a blend state. I'm almost positive that's my problem. I don't want to BLEND the sprites, I want them to be transparent when alpha is 0. In this example I can set alpha to 0 but it still renders both tiles, with the lower z ordered sprite showing through, discolored because of the blending. This is not a desired effect, I want the higher z-ordered sprite to fade out and not effect the color beneath it in such a manner.

I might be way off here as I'm fairly new to XNA development so feel free to steer me in the correct direction in the event I'm going down the wrong rabbit hole.

TIA

# Answer
> 18 votes
If I follow the issue correctly try calling Begin with BlendState.NonPremultiplied. This article may also help shed some light on how alpha blending works in XNA.

# Answer
> 6 votes
Fully agree with Alex's response, though if you stick with premultiplied alpha I believe you could also do it this way

```
new Color(new Vector4(alpha, alpha, alpha, alpha ))

```

Shawn also did a post explaining the difference between premultiplied and non-multiplied alpha - Link

---
Tags: xna, 2d, c#, rendering, transparency
---


# Question
Title: Is it a good idea to simplify a character-driven game engine to the point where it's unnecessary to learn scripting/programming?
I remember, and I still think, that one cannot even make a prototyped 3D game to test just simple behaviors without using gigantic tools like unity or knowing extensive C++ programming, design patterns, a decent or basic 3D engine, etc.

Now I'm wondering, since I know programming, whether I'm even more lucky than the ones who need to learn programming before knowing how to make something. Even scripted engines such as Unity are not for kids, and to my sense they tend to dictate their ways of doing things. This is not the case with engine like Ogre or Irrlicht.

Now I'm thinking that character-driven games occupy a big part of the game market. Do you think it is a good idea to make a character-control oriented game engine which only allows building AI to the exclusion of anything else?

When I say prototype, I also mean "generic" in the sense that one can quickly choose from a set of gameplay parameters such as the scene manager, the camera POV of the player, the controls, some very basic collisions/physics, and integration of basic steering (OpenSteer for example). The main idea is to make an AI sandbox but in 3D, so it can be demonstrated without the 2D constraints (and also make it more fit to prototype in 3D for a 3D project instead of 2D).

# Answer
> 6 votes
I really like the under-appreciated game engine in Blender. (http://www.blender.org) The sensor-controller-actuator model is really easy to follow even for non-programmers, and it's possible to make a reasonably complete game (move an animated character, fire a weapon, destroy targets, show score, keep track of health, reset level or move to a new one) without any programming at all.

Of course, some things do require programming (especially getting mouse input for an FPS.) However, blender already incorporates Python, and Python scripting is tied very nicely into the model so you never need to replace sensor-actuators with Python. Instead, you just switch from a very simple 'pass-through' controller to a complete Python script that can read all the sensors in the scene and pass control to all actuators.

It is quite feasible to create a game prototype in a few days in Blender (I did it for a project at a local children's museum last year.)

Of course, nothing replaces good-old programming know-how, and eventually, a developer does need to understand programming.

# Answer
> 4 votes
Regardless of the input mechanism, at the end of the day you still need to set up some kind of way of telling the game what the logic is. "Scripting" is a good colloquial term for this. So basically I disagree with the assertion that you can simplify something to the point where you don't need to know "scripting".

That being said, not all scripting needs to be done with a text-based programming language. There has been some work (but not a lot) towards making a visual scripting system. Unreal's level scripting tool, Kismet, is a pretty good example of one. Source engine has a similar mechanic, but it uses entities in the world instead of on a flat plane.

Basically you have boxes that you drag around in some kind of environment that have inputs and outputs. If you need some kind of branching output you have some box that have one input and multiple outputs. Those outputs can go to actions that have data tied to them (i.e. "move to this point", "say this line", "ask this question", etc.). It's usually a significantly lower barrier to entry to get something up and running in a visual language since you don't have to know keywords or syntax, you just have a limited set of boxes to pick from which all have defined behaviors, and you just connect them together.

However it's my opinion that visual scripting engines aren't really worth the trouble. You need to be able to think structured and logically in order to successfully tell the engine what you want to do. If you can think like that, making the jump from boxes with inputs/outputs to basic branching statements and function calls in a scripting language isn't that big of a deal. In fact, after a while the visual part of it is probably a hindrance. Plus, it's a lot more work on the engine side of things. You have to do things like implement undo, copy/paste, maybe have some higher level features for organizing your scripts. With a text-based language you can leave all that to the IDE.

# Answer
> 1 votes
It will in general be a trade off. If you truly want to remove the need to do any sort of scripting you are generally going to be talking about making some sort of an interface that will piece the scripts together in the background (or just connect logic objects or what not). There are entire games where that is the entire point to them, a well defined environment where you drag and drop functionality to see how it interacts with it.

At the end of the day however, it will always be a trade off.. The more simple you attempt to make the interface the more simplistic the things created through that interface.

---
Tags: 3d, architecture
---


title: gpgpu vs. physX for physics simulation

text:
# Question
Title: gpgpu vs. physX for physics simulation
First theoretical question. What is better (faster)? Develop your own gpgpu techniques for physics simulation (cloth, fluids, colisions...) or to use PhysX?
(If i say develop i mean implement existing algorithms like navier-strokes...)

I don't care about what will take more time to develop. What will be faster for end user? As i understand that physx are accelerated through PPU units in gpu, does it mean that physical simulation can run in paralel with rastarization? Are PPUs different units than unified shader units used as vertex/geometry/pixel/gpgpu shader units?

And little non-theoretical question: Is physx able to do sofisticated simulation equal to lets say Autodesk's Maya fluid solver?

Are there any c++ gpu accelerated physics frameworks to try? (I am interested in both physx and gpgpu, commercial engines are ok too).

Edit: Simulation does not have to be realtime i'm thinking just about acceleration.

# Answer
> 2 votes
If you have a "special case" where you know exactly what you want, then in theory you should be able to at least match, if not beat for your scenario, one of the generic physics engines that run on the GPU. Will you write something that beats the off-the-shelf solution in a short amount of time, no. They've got a lot of smart people doing nothing but that for a long time (plus the GPU manufacturers helping them out to optimise).

The physics simulation will not run in parallel with rasterisation on the same graphics card (it's the same hardware used for vertex/pixel processing). If you have 2 cards then I think that's the ideal scenario for doing both physics and rendering via the GPU (unless you have very basic visuals that leaves a lot of spare time on your fast GPU).

I've not used any of the GPU physics systems myself, however I'd expect PhysX to be designed for performing real-time simulation work, where Maya's fluid solver doesn't have to work in real-time and can therefore run a much more sophisticated simulation, however the only thing stopping PhysX being able to match it would be how long it takes to do the simulation.

---
Tags: c++, physics, physics-engine, gpgpu
---


# Question
Title: Texture2D.GetData fails to return pixel colour data
Because I'm using sprite sheets instead of an individual texture per sprite, I need to pass in a `Rectangle` when calling `Texture2D.GetData()` in my collision detection for per-pixel tests. Unfortunately, without fail I get an `ArgumentException` percolated down from an internal method inside the `Texture` (not `Texture2D`) class.

My code for getting the texture data looks like this:

```
    public override Color[] GetPixelData()
    {
        Color[] data = new Color[(int)size.Product()];
        Rectangle rect = new Rectangle(hframe * (int)size.X, vframe * (int)size.Y, (int)size.X, (int)size.Y);

#if DEBUG
        if (sprite.Bounds.Contains(rect) && sprite.Format == SurfaceFormat.Color)
#endif
            sprite.GetData(0, rect, data, 0, 1);

        return data;
    }

```

Even with the check to ensure I'm grabbing a valid rectangle and that the texture format matches what I'm trying to get, I still get that exception, claiming "The size of the data passed in is too large or too small for this resource." Unfortunately, the debugger won't let me check the locals within the `Texture.ValidateTotalSize()` method where the exception originates.

Has anyone else had this problem and knows how to fix it? I'm relying on AABB testing only for now, but that doesn't really work for some of my game's entities due to odd shapes, rotation and scaling.

# Answer
You can use Reflector to look inside `Texture.ValidateTotalSize()` to get an idea of what might be happening to throw the exception.

But in this case I think it's simply that:

```
sprite.GetData(0, rect, data, 0, 1);

```

should be:

```
sprite.GetData(0, rect, data, 0, data.Length());

```
> 6 votes

# Answer
The code you've posted isn't necessarily enough to figure out what's going wrong. XNA's Texture2D.GetData() method takes a Type, for instance, so you must be using some custom class. I have a guess though.

From the looks of it, the type you're using for size uses floats (or doubles; same thing for purposes of this). It's eminently possible that the problem comes from that: casting a float to an int truncates the result. Assuming size.Product() multiplies the floats together and returns the result, you could easily be getting something like:

size.X = 10.3 size.Y = 20.4

(int)size.X * (int)size.Y = 200 (int)(size.X * size.Y) = 210

Try:

`Color[] data = new Color[(int)size.X * (int)size.Y];`

and see what happens.
> 0 votes

---
Tags: xna, textures, xna-4.0
---


# Question
Title: What causes player box/world geometry glitches in old games?
I'm looking to understand and find the terminology for what causes - or allows - players to interfere with geometry in old games. Famously, ID's Quake3 gave birth to a whole community of people breaking the physics by jumping, sliding, getting stuck and launching themselves off points in geometry.

Some months ago (though I'd be darned if I can find it again!) I saw a conference held by Bungie's Vic DeLeon and a colleague in which Vic briefly discussed the issues he ran into while attempting to wrap 'collision' objects (please correct my terminology) around environment objects so that players could appear as though they were walking on organic surfaces, while not clipping through them or appear to be walking on air at certain points, due to complexities in the modeling.

My aim is to compose a case study essay for University in which I can tackle this issue in games, drawing on early exploits and how techniques have changed to address such exploits and to aid in the gameplay itself. I have 3 current day example of where exploits still exist, however specifically targeting ID Software clearly shows they've massively improved their techniques between Q3 and Q4.

So in summary, with your help please, I'd like to gain a slightly better understanding of this issue as a whole (its terminology mainly) so I can use terms and ask the right questions within the right contexts. In practical application, I know what it is, I know how to do it, but I don't have the benefit of level design knowledge yet and its technical widgety knick-knack terms =)

# Answer
If I understand correctly what you are talking about, then its dealing with framerates and the short cuts taken to get physics, and collision in general, to run in a reasonable manner in video games.

Basically you would do the movement, collision and reaction calculations over the time step of each frame. What if the time step of the frame with the current forces were enough to push you Into an object.. A wall or narrow passage say, that you normally would not be able to enter? Well the system has to 'eject' you from the object.. Depending on how this ejection was done it could result in a very large force applied over a very small time that may Not get you all the way out of the object.. The force could build up over 2-3 frames and pretty much just send you flying.

I am not 100% sure this is the actual case as mentioned in Quake 3, but I know in learning to develop games this is the type of example they would use to explain why the strangest things happen some times when you do not take into consideration all the time within a time step.. most physics engines I have worked with will use some sort of a set time step to do its calculations (This includes the people that nVidia bought :)). If a frame rendered to fast, the physics do not get calculated that frame, if the next time step is over that set value then enough to make a complete step is taken, physics is calculated, and that bit of time is used as the new point to add each next frame's time to before the next step.

Hope this helps give you some ideas of what to look for.
> 2 votes

# Answer
Regarding Quake 3: I remember websites with quite in-depth analysis of strafe-jumping and their relation to current framerate, including some mathematical formulas behind it. Quick google search turned out this site: http://www.funender.com/quake/articles/strafing\_theory.html looks preaty good, but I'm almost sure it's not the one I saw before.
> 0 votes

# Answer
I can think of a couple of potential reasons.

First is that the geometry in these games is rarely "airtight". While working on a 3d game project we talked with a PVS technology provider, who processed some of our levels through their system and showed that perfect PVS data is impossible due to the holes in the geometry. These holes are not visible; I'm talking about t-intersections and floating pointy inaccuracies etc.

Sometimes physics just manages to blow up because the players hit the geometry "just right"; geometry that, while visually perfect, isn't mathematically so.

The second reason that I can think of, to quote Tim Sweeney - making realistic game physics is *difficult*. Floating point calculations are surprisingly inaccurate. There's plenty of articles about this on the net (for instance, http://docs.sun.com/source/806-3568/ncg\_goldberg.html is a pretty good one). Add to that the fact that we're talking about online games with all their interpolations, predictions and such, and you get a rather unstable system, which still somehow manages to work.
> 0 votes

---
Tags: collision-detection
---


# Question
Title: Best strategy (tried and tested) for using Box2D in a real-time multiplayer game?
I am currently tackling real-time multiplayer physics updates for a game engine I am writing. My question is how best to use Box2D for networked physics. If I run the simulation on the server, should I send position, velocity etc to every client on every tick? Should I send it every few ticks? Maybe there is another way that I am missing?

How has this problem been solved using Box2D before? Anyone with some ideas would be greatly appreciated!

# Answer
> 8 votes
You might see this question which deals with the same challenge...

Lag compensation with networked 2D games

Though not specifically about 2D physics, the same issues apply.

# Answer
> 5 votes
Something else to think about, is a clear separation of 'gameplay physics' which needs careful synchronization, and 'special effects physics' which doesn't.

Physics used for effects only, such as explosion debris, does not usually need keeping in sync, and can run independently on each client. It doesn't matter if it looks a bit different on each.

# Answer
> 2 votes
One of the most important things in game networking is to only send information *when* it's needed.

So the answer is neither of your suggestions. You run the simulation on both client and server (or just clients if peer2peer). If you press the up arrow, you send a packet that you now have initiated an upward motion, and until you stop moving in that direction there is no need to send any more packets, as both the clients and servers can run their physical simulation based on the information in that packet.

It's called Client-side prediction.

# Answer
> 1 votes
What kind of game is it?

Is it possible to keep the 2 simulations entirely in sync?

If you start the 2 instances of the simulation in exactly the same state, and update with a fixed timestep, then they should remain synchronized.

But when you do anything to a physics object, you send a message to all clients telling them what to do and on which frame.

So if you were making something like 'Worms' or 'Angry Birds', and the player launched a projectile on frame 1000, you'd send a message saying 'on frame 1000+N' we're going to spawn a physics object with these parameters.

Of course, this will add input lag. And you need some way to ensure that no player will get too far ahead to respond to messages on the correct frame. Maybe a 5-10Hz 'clock' message, telling all clients 'you may advance your simulation to frame N, but no further'.

(I believe that this is how online RTS games work, where it would not be practical to send the positions and states of several hundred units every update, and where a fraction of a second's lag between giving an order and the unit executing it is acceptable)

---
Tags: networking, multiplayer, box2d, game-mechanics
---


# Question
Title: Determining relative velocities on impact?
I'm trying to figure out a way to determine the relative velocity of a body colliding with another in a 2D environment.

For example if one body is moving at (1,0) and another traveling behind it collides with it from behind at (2,0) the velocity of the impact relative to the first body was (1,0).

I need a method which takes in two velocities, one velocity belonging to the body the velocity is being measured against, and the other for the impacting body and return the relative velocity.

# Answer
> 10 votes
This is a simple operation of vector difference. In XNA you don't even need to create a specific method for it - vectors already support subtraction.

If you want the velocity of Body B from the perspective of Body A, you subtract Body A's velocity from Body B.

So in C# with XNA, using your example:

```
Vector2 MovingBody = new Vector2(1, 0);
Vector2 Impact = new Vector2(2, 0);
Vector2 PerceivedImpact = Impact - MovingBody;
// PerceivedImpact equals (1, 0) in this scenario

```

---
Tags: xna, physics, vector
---


# Question
Title: Using idle time in turn-based (RPG) games for updating
If you take any turn based RPG game there will be large periods of time when nothing is happening because the game is looping over 'wait\_for\_player\_input'. Naturally it seems sensible to use this time to update things.

However, this immediately seems to suggest that it would need to be threaded. Is this sort of design possible in a single thread?

```
loop:
if not check_something_pressed:
    update_a_very_small_amount
else
  keep going

```

But if we says 'a\_very\_small\_amount' is only updating a single object each loop, it's going to be very slow at updating.

How would you go about this, preferably in a single thread?

EDIT: I've tagged this language-agnostic as that seems the sensible thing, though anything more specific to Python would be great. ;-)

Second edit: This game is not planning on having any animated components; that is, I'm currently running it as a wait-for-player-input then update everything and draw. So rather than X FPS it depends on the user's speed.

# Answer
> 7 votes
Yes, its possible to do in a single thread. Generally speaking though, you'll want to be updating the objects every frame and not just when there are spare cycles. Your animations and movement will be disconnected from the frame rate and look rather choppy if you don't. If you're talking more about AI updates or something else that does not need to be real-time, I would put a timer on it. You should know what your target frame rate is and the idle time will be whatever is remaining after everything else has been completed.

Let's say you're targeting 60 FPS for your game. That leaves you with 16.667 ms to perform all of the work you need to do each frame. At the beginning of the game, get the current time using the highest resolution timer available, add 16.667 ms to it and store it somewhere. I think the function in python is time() though it has been a while since I worked in the language. After your processing is complete, enter a loop that checks the current time against the time you've recorded. If the current time is less than the frame end time, update\_a\_very\_small\_amount. I wouldn't worry much about the processing going past the end of the frame since your small update should be quick to process. It would only be a slight delay to the start of the next frame and you appear to have enough idle time to handle it.

After the frame has finished processing, add 16.667 ms to the time that was stored for the end of the last frame to find out where the end of the next frame should be. If you use the current time + 16.667 ms and the processing goes over, the end of the next frame will be pushed out by however much time the last frame ran over.

**Re: Second Edit**

To clarify, I use the term frame-rate here to indicate one iteration through the main loop. If it's based off of the user's input speed, I imagine that your goal is to simply make the game feel responsive. Otherwise you could just check for input and update everything each time through the loop even if it takes 10 seconds to do so. To make it feel responsive though, you'll probably want to check for input around 20 times per second which gives an effective frame rate of 20 FPS, even if you're not actually drawing these frames. This would give you 50 ms to update things before you need to check for input again.

# Answer
> 2 votes
For **Python** specifically you can try and use **Coroutines** to do calculations over multiple update calls.

> ... coroutines are program components that generalize subroutines to allow multiple entry points for suspending and resuming execution at certain locations...

**PEP-0342** details coroutine implementation in Python.

You can create your own scheduler and tasks which can simulate multithreading on a single thread. This is the same way that Javascript frameworks allow for multithreaded like processing even though Javascript is run on a single process.

# Answer
> 1 votes
Yes this is possible. Your game will have some kind of main game loop. Something like this:

```
while(gameRunning)
{
  checkUserInput()
  updateGame()
  renderGame()
}

```

In updateGame you can iterate over your game objects and update them "a little". If you are doing any heavy calculation in this method the game will simply hang. So you need a way to split up these calculations to run over several iterations of the game loop.

How to split them up, depends on the kind of game you are building. Suppose you are have a path finder routine which uses A\* to calculate a path through a labyrinth. You would need to stop the algorithm after a certain amount of time or after a fixed amount of iterations, keep the calculated path so far and return control back to the game loop. The path finding will continue next time updateGame is called. You can even move the character along the partial path while it is still being calculated.

Most times you don't need to worry about the updateGame call taking too long.

"Premature optimization is the root of all evil!"
If you do hit a performance bottleneck in your update routine, that's the time to investigate and optimize. Since you cannot know in advance what parts of your game will take the most time to compute and might waste time optimizing the wrong stuff.

# Answer
> 1 votes
The way I understand your question is that basically you're asking about cooperative multitasking.

Basic infrastructure would be a list of function pointers, all called in a round-robin manner (unless a more sophisticated prioritization is required), and all these functions would do "a little bit of work", small enough not to cause the game to become sluggish. I've done this in DOS before threads were hot, and also on mobile devices that didn't support threading.

A better question, in my opinion, is what to do while waiting for the player to move. What kinds of things would be so processor-intensive that they can't be performed on the fly anyway, while, at the same time, being so optional that if the player just hammers some move key fast enough, the game doesn't have time to process these. Thus, stuff like calculating A\* for a couple thousand AIs is out.

Better solution, in my opinion, is to simply yield/sleep, and let the computer's power management do its job. Laptop users will like you better for it.

---
Tags: architecture, game-loop, rpg, turn-based
---


# Question
Title: Entity system in Lua, communication with C++ and level editor. Need advice
I have a 2D basic editor written in Qt, and I'm in the process of adding entities. I want the editor to be able to receive RTTI information from entities to change properties, create some logic being able to link published events to published actions (for example, A level activate event throws a door open action), etc... Because of this I guess my entity system should be written in a scripting language, in my case Lua.

On the other hand I want to use a component based design for my entities, and here starts my questions:

1) Should I define my componentes in C++? If I do this in C++ won't I lose all the RTTI information I want for my editor? On the other hand, I use box2d for physics, if I define all my components in script won't it be a lot of work to expose third party libs to lua?

2) Where should I place the messaging system for my game engine? Lua? C++?

I'm tempted to just have C++ object to behave as servers, offering services to lua business logic. Things like physics system, rendering system, input system, World class, etc... And for all the other things, lua. Creation/Composition of entities based on components, game logic, etc...

Could anyone give any insight on how to accomplish this? And which approach is better?

---

Sorry for the late response James, I did go to sleep. I have prefered to create a new response becaue I'm going to write a somehow long text.

I think you were not wrong and you did get the idea exactly as I wanted. Let me explain my ideas right now and key points after some sleep to clarify everything:

1) Components: At first I wanted to write them in lua. Now I have clear I'm going to write them in C++ and expose everything needed. Ussually only interfaces are exposed to lua, so I have come across that to export properties to be published in the editor we could get all "getXXXXX" methods (that have been exported to lua) and show them in the editor as XXXXX. Other things like data type, etc... should be thought.

2) Entities: They will be defined in lua through composition of C++ components (entity templates). They could be hardcoded too in the C++ side and have a factory for components and another for entities and let the lua side instantiate them.

All this, is what I can think of now. I know my editor can still be using game objects even if it is external, but the game am I into is for iphone using cocos2d and the editor is writtien in QT, so, I can't have the game running in a qt canvas and make qt\<-\>game talk.

# Answer
1) Yes. While you want to expose the functionality via Lua for scripting you will in general want all the objects defined in C++. This will likely require either using the built in (and usually crappy) RTTI or writing your own system (If you look into it, for the basics, its really not that hard to do so dont let this deter you).

By keeping all of the objects within C++ then your game knows how to deal with them, and you can use the scripting to define them or give them small little action sets via the script and the like. And as you said, this keeps them available for other third party libs if need be.

2) C++ again. This will just be another thing that you want to expose through Lua so that other things can trigger or script logic to react to the messages and the like. This will also let the objects defined in C++ use the system as well with out having to go through Lua to do it.

In general I would say Always design your engine in the language its going to be running in. Hardware these days is very powerful compared to even a few years ago, but that doesnt mean you will not reach the ends of that power with your projects. A Scripting language will never run as fast as a compiled language.

Secondly this allows you to develop the entities/objects as completely as you want with out having to expose everything to the scripting interface. This is potentially another handy layer of abstraction that you can utilize to rework and upgrade or the like, parts of the system as you work on it with out necessarily having to redo every part at the same time.

Plus, Kudos on the Component system... Most people go straight tree hierarchy from the get go and then get overwhelmed with its upkeep and lack of extensibility.
> 3 votes

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


title: Trouble with touch events on iPhone

text:
# Question
Title: Trouble with touch events on iPhone
I'm making a simple 2D game for iPhone. Think of the game as a ball on the screen that goes up while the user is touching the screen and falls down when the user stops touching the screen.

The ball starts moving up in touchesBegan:withEvent and starts moving down in touchesEnded:withEvent. This works fine almost all the time. However on occasion the ball will keep moving up after the user stops touching... or the ball will keep moving down while the user is touching. Why is this happening?

Just fyi the ball is drawn on a UIWindow. The taps are handled by a UIImageview subclass that's clearColor and takes up the entire screen. This "touchLayer" is also moved to the front of the window in the game loop.

Any idea why this control scheme occasionally fails? Perhaps the touch events just aren't firing? Or they're fired out of order?

Cheers!

# Answer
Occasionally touch events get dropped, so you may also need to implement the same logic in touchesCancelled:withEvent.

See http://discussions.apple.com/thread.jspa?messageID=8397178
> 3 votes

---
Tags: iphone, touch
---


title: How do I tackle top down RPG movement?

text:
# Question
Title: How do I tackle top down RPG movement?
I have a game that I am writing in Java. It is a top down RPG and I am trying to handle movement in the world. The world is largely procedural and I am having a difficult time tackling how to handle character movement around the world and render the changes to the screen. I have the world loaded in blocks which contains all the tiles.

How do I tackle the character movement?

I am stumped and can't figure out where I should go with it.

**EDIT**: Well I was abstract with the issue at hand.

Right now I can only think of rigidly sticking everything into a 2D array and saving the block ID and the player offset in the Block or I could just "float" everything and move about between tiles so to speak.

# Answer
> 11 votes
### Use World Coordinates

(Or as you put it, float everything.)

World coordinates are what you generally work with, and there's plenty of reasons for that. They're the most simple and intuitive way of representing your position in the world, and the only way of really comparing the positions of any two entities in the same world.

You gain nothing but work by having him be tracked within individual blocks. Well, one advantage is you get to determine which block he's in, but you can already calculate that with world coordinates.

---

**The rest of this answer** will be an explanation of how to calculate the world block a player is in based on his world coordinates.

I'll write the code snippet as if you have a 2D vector class named `Vector2` \- the kind of vector you find in geometry, not the `Vector` list type offered by `java.util`. If you don't have any geometric Vector classes, you should find some online or write some yourself (anyone know any quality geometry libraries for Java?)

The Vector2 class will have an `X` field and a `Y` field, which are public numbers (doesn't matter which numeric type here).

```
// Current player X,Y position in the world
Player.Position.X, Player.Position.Y

// An array of map blocks with consistent width and height
Block[x][y] blocks = World.GetBlocks();

// We'll wing it with an example global width/height for all blocks
Block.GetWidth() == 100;
Block.GetHeight() == 100;

// To ensure we're on the same page:
// blocks[0][0] should be at position (0,0) in the world.
// blocks[2][5] should be at position (200,500) due to the width/height of a block.

// Also:
// Assuming (0,0) is in the top-left of the game world, the origin of a block
// is its top-left point. That means the point (200,500) is at the top-left of
// blocks[2][5] (as oppose to, say, its center).

public Vector2 GetPlayersBlockPosition() {
    Vector2 blockPosition = new Vector2();
    blockPosition.X = (int)(Player.Position.X / Block.GetWidth());
    blockPosition.Y = (int)(Player.Position.Y / Block.GetHeight());

    return blockPosition;
}

public Block GetPlayersBlock() {
    Vector2 bp = GetPlayersBlockPosition();
    return blocks[bp.X, bp.Y];
}

Block block = GetPlayersBlock();

```

2 functions \> all the mess of within-block tracking and inter-block transferring

# Answer
> 0 votes
Your question is a bit abstract but perhaps you're looking for a path finding algorithm, I suggest A\* (http://en.wikipedia.org/wiki/A\*\_search\_algorithm). This will help you move your character tile to tile if the tile is not blocked terrain.

---
Tags: java, tiles, rpg, movement
---


title: RPG Item processing

text:
# Question
Title: RPG Item processing
I started working on an item system for my (first) game, and I'm having a problem conceptualizing how it should work. Since Items can produce a bunch of potentially non-standard actions (revive a character vs increasing some stat) or have use restrictions (can only revive if a character is dead). For obvious reasons, I don't want to create a new Item class for every item type. What is the best way to handle this?

Should I make a handful of item types (field modifiers, status modifiers, )?

Is it normal to script item usage? Could (should?) this be combined with the above mentioned solution (have a couple of different sub item types, make special case items usage scripted)?

# Answer
> 3 votes
I'd store everything about items as pure data, and then traverse the data to determine how the item behaves.

For example, suppose item properties vary per item type (instead of per item instance), and there can be multiple properties per item type. This could be set up as a set of lookup tables on the item type. Example in JSON format:

```
restrictions = {
  'ghost_amulet': ['must_be_dead'],
  'magic_sword': ['in_combat'],
  …
};

actions = {
  'ghost_amulet': [('revive', 0)],  # note: int parameter not used for revive
  'magic_sword': [('fire_damage', +3), ('ice_damage', -1)],
  'wooden_shield': [('armor_modifier', +5), ('block_modifier', +3)],
  …
}

```

Each action and restriction would map to a piece of code that implements it. Note that instead of restricting items to have only one type of modifier, I'd start out with having any item have any action or restriction. It's simpler and more flexible to put all of this into a data file than to use a class hierarchy that has to be recompiled when you change something. If there are space/speed issues you can add restrictions to streamline the data format.

There are lots of variants of this. There might be properties that vary per item instance. There might be more parameters for some actions. The action names might correspond to method names in the code instead of fields to modify. Actions and restrictions might be ints instead of strings. If only one restriction/action is needed you wouldn't need a list. Modifiers might be put into their own lookup table (for example you could make a fire\_damage lookup table that maps to numbers). All of these details will vary by game.

# Answer
> 1 votes
You can use a very similar strategy as described here: How to design the attack class in an RPG game?

Just imagine that you're dealing with Items instead of Attacks.

---
Tags: architecture, rpg
---


title: OpenGL vs DirectX?

text:
# Question
Title: OpenGL vs DirectX?
I saw the articles that were going on about OpenGL being better than DirectX and that Microsoft are really just trying to get everyone to use DirectX even though it's inferior so that gaming is almost exclusively for Windows and XBox, but since the article was written in 2006 is it still relevant today?

Also I know plenty of games are written in DirectX but does anyone have any examples of popular games written in OpenGL?

Thanks

# Answer
"Better", in this case, is a relative term. The two (assuming, as mentioned, D3D) are very similar in what they do and how they do it; but there is a pivotal point in here:

While D3D has more tools available (jury is still out on "better"), and perhaps better support on the Windows platform, on other platforms support is pretty much non-existent.

In computers, both Mac OS X and Linux both support OpenGL, and in terms of consoles, at least the Wii has interfaces that are highly reminiscent of OpenGL. I can't speak to the PSP or handhelds, but if they don't have proprietary interfaces, they probably have OpenGL (which is pretty much true everywhere).

It all boils down to portability: If you are supporting one platform, and one platform only, for all of eternity; use whatever makes your job the easiest on that platform.

If you plan on ever possibly supporting other platforms, the OpenGL path is probably one of the more attractive ones open to you. The other option is doing a lot of abstraction, or an engine that can interface with several different GPU interfaces.
> 7 votes

# Answer
Assuming you mean Direct3D:

The difference is in interface mostly. They both talk to the same underlying hardware, and there might be minor differences in what they expose, but most skills you get in one can be used in the other.

That said, tool support is a lot better for D3D than for GL.
> 2 votes

# Answer
First off, the only time this question is applicable is for Windows-based PCs. Console, smartphones, and mac platforms all have a singular API (or a singular API and a "closer to the hardware" API), so your question doesn't apply to them.

"Better" is a terrible term anyway. Better for what? As far as I'm concerned, DirectX is better for Windows since OpenGL drivers are generally terrible. Or at least that's what the Unity guys discovered with their cross-platform engine. I really wish I had a link for that.

Maybe at some point in time API X has feature Y which is really attractive (and therefore might seem "better")... but you can't use it because nobody would have a video card to support that feature. And if you made a game that really needed that feature it would be much harder to port it to another platform that didn't use that API.
> 2 votes

# Answer
The situation about those two API is greatly dependent of the PC game market which is completely dominated by microsoft.

You also have to understand that as the graphic technologies has been very much influenced by the progress made in computer speed, and since graphic acceleration involves **all** aspects of a computer (the electronic architecture aspect, the OS aspect, the CPU aspect, the API compatibility aspect), it involves a very tight and dense engineering work, so you can easily understand that it requires enormous resources so those technologies can not only be released, but evolve and be "easy" enough to work with for game and/or 3D engines developers.

Microsoft has been tightly working with nVidia, and they are more able to throw money to be sure their technology is more advanced on such special hardware, something which can't be possible with an open source model, since there are much less developers ready to work for an open model which doesn't rewards them money directly.

Open standards are been efficient for a long time but as this quote says: "Walking on water and developing software from a specification are easy if both are frozen." Edward V Berard

The reason why it favors direct x is because shiny stuff sells more, and shiny stuff requires recent software AND hardware.

But you can still learn OpenGL, do something sufficient with it, and let the engines do the hard work, because graphic programming evolves a lot, and don't remember Direct X is not the only proprietary: Sony, Nintendo, and other Arcade or other systems, use proprietary APIs.

So my advice is this: learn OpenGL, because for the shiny stuff, you won't stay on OpenGL. You can also learn Direct X, but if you plan to work on consoles, you will have to learn again.

All that chit chat is not very interesting: just pick an engine like Ogre or Irrlicht or Panda3D and start coding.

And one thing: if you plan to learn either Direct X or OpenGL, be sure to learn everything you can about Matrix algebra, and some more which are specific to graphic programming.

The read will be long.
> 2 votes

# Answer
Popular games that use OpenGL: Quake 1, 2, 3 and 4 (maybe 4), Doom 3
> 1 votes

---
Tags: opengl, directx
---


title: AAA Games and OpenGL?

text:
# Question
Title: AAA Games and OpenGL?
What modern AAA games on the top of the market used OpenGL? If applicable, what engine did they use?

# Answer
Any 3D game that runs at least on a platform different from microsoft, nintendo and sony uses OpenGL.

This includes any game that runs on Linux, Android, Mac Os X, iPhone/iPad, Symbian and probably more.

AAA games usually have got an engine written ad-hoc for the game (or for a little set of games). The ones I know the better are ID Tech engines (from 2 up to 5) and Unreal Engine (from 1 up to 4).
> 9 votes

# Answer
Not complete, but very long list at Wikipedia.

http://en.wikipedia.org/wiki/List\_of\_OpenGL\_programs
> 6 votes

# Answer
All Id Software engines uses OpenGl for graphics rendering since Quake 1.

Ogre3D can use Direct3D or OpenGl (although is not an engine used in AAA titles AFAIK)
> 3 votes

# Answer
I don't know about the exact ratio but I think about 50% (or even more) of all AAA titles run on OpenGL. Just the console games (without X-Box) make up for a *lot* of games.

Or take Blizzard as an example (Starcraft2, WoW, Diablo3). All of their games run on both PC and Mac and therefore use OpenGL too. AFAIK Blizzard uses custom developed engines for their games.
> 1 votes

# Answer
Nintendo and Sony provide Opengl like libraries but AAA titles tend to not use it and go for the platform's lower level libraries. Id tends to use opengl. Though they have said their system is abstract enough that to switch between the two is trivial. Valve licensed id's stuff for the original halflife but built their own stuff on DX for Source so either they ported to Opengl or they licensed transgaming's Cider(that is how EA does its duel relases) to tell you the truth I haven't heard either way. Really there is no way to tell who uses what without working there or big articles about it.
> 1 votes

# Answer
PC games by Starbreeze uses OpenGL. The Chronicles of Riddick and Enclave.
> 1 votes

---
Tags: opengl
---


# Question
Title: What elements make a simple game addictive?
> **Possible Duplicates:**
> What should a game have in order to keep humans playing it?
>
> How can I make my score-based game addictive
>
> What makes puzzle games addictive?

I am creating simple game for iPhone like "Bubble Explode". Generally, what elements of game make it addictive and exciting for similar simple games.

# Answer
Flow is one part of it, as notabene mentioned. However behind the effects is a whole host of psychological effects that combine to make games fun or addictive. MMORPGs, especially WoW, thrive off of such tools, to make themselves addictive at the very least.

Behavioural Game Design is a good, short introduction to the psychological toolset that tackles some key concepts. Psychology Is Fun is a good follow-up, as it goes into more depth, especially on generating a sense of Flow.

If you're after more, it's no understatement that the professionals who blog for Gamasutra seem to have turned it into a treasure trove for this sort of thing. They're how I found out about these concepts myself. Googling "psychology site:gamasutra.com" turns up results such as:
> 10 votes

# Answer
Very addictive is so called flow feeling. It means that the game is challenging but also not that hard and great is when combined with possibility of recieving some rewards. First reward is super easy, next harder and so on.

Stackexchange is great example of this. You came here, ask question and receive some reputation and badges. And then you want more. And its harder to get them. You start answering questions to receive more reputation and badges. And next badges and site privileques needs some of your work, but you know that you can get them. It's pretty addictive :)

Or maybe better example is brainwashing FarmVille on facebook.

flow on wikipedia
> 3 votes

# Answer
There's this thread on puzzle games in particular. Since I don't know bubble explode, I can't say if it's exactly what you want.
And this one on score-based games, which is slightly less useful but still a good source.

But some general ideas from there:

* Make it easy to replay
* Make it **fun**
* Simple controls
* Make it challenging, so the player wants to continue
* But not too challenging, so they don't want to give up
> 3 votes

---
Tags: game-design
---


# Question
Title: which is the best physics engine for flash as3?
i am a game programmer and i use actionscript to do all my collision checking, boundary checking etc...but recently i noticed there are things called "physics engines" that help me concentrate more on game making rather than physics making. so i would like to know more. i heard there are few engines called "box2dflash" and "APE".

# Answer
> 5 votes
There's no such thing as *best* physics engine. It heavily depends on what you need. Take Box2D as an Example: It is a fully featured 2D Physics Engine, originally developed in C++ and ported to ActionScript. It is great for realistic 2D physics simulation, including gravity, forces, friction, continuous collision detection and much more.

An Engine like Box2D is going to use quite a lot of your CPU cycles, especially when using it in Flash. It is also not trivial to set up and to create appropriate *collider-bodies* for your Entities.

If you wanted to create a game like *Breakout*, an Engine like Box2D would be overkill. A game that heavily uses physics for gameplay like Totem-Destroyer, is probably easier to implement when you can make use of a good Physics-Engine though :-)

There are also other implementations like the one provided with the Flixel Game-Engine. It isn't a physics-engine per se, but it contains a solid collision-detection algorithm. The engine also updates entity velocity and gravity.

In most cases, the tools provided by Flixel or similar engines are good enough. Just keep in mind that using a physic engine is going to be CPU intensive and you should choose the implementation that best fits your game.

# Answer
> 1 votes
If you are looking into box2d at all, be sure to check out World Construction Kit. http://www.sideroller.com/wck/

It uses an Alchemy port of Box2d, meaning it is converted from pure C code using Alchemy which really enhances the performance.

If you are authoring your game in the Flash IDE and not in pure as3, it basically makes the Flash IDE into a level editor by adding components for physics based shapes and joints. Definitely at least worth checking out the demo.

If you are using pure as3, the component classes could still come in handy.

If nothing else, playing with the components in the IDE and messing with the demos would be a nice introduction to using a physics engine and an easy way to familiarize yourself with the concepts.

# Answer
> 0 votes
Box2d is used in a lot of games, also outside of the flash world. It was made originally in C and has been ported to a lot of languages, from objective-c to javascript.

I think it's a testiment to the engine which is very easy to use, has good documentation, loads of examples (although sometimes in different language) and is very fast.

The only downside is that it is limited to 2d. But this downside is a plus if in fact you are making a 2d game (which most of the time is the case in flash world probably)

# Answer
> 0 votes
As others here have said, Box2D is a pretty full featured physics engine, although it does take a lot of work to get it set up properly.

And as others here have said again Box2D is resource intensive.

Also I can almost tell immediately if a game uses Box2D, because of the way the physics behaves.

So my approach is to make my own small physics engine that looks unique when compared to other games, is easier for me to work with, and easier to wrap my head around.

# Answer
> 0 votes
Go with box2d, ape and fisix projects you mentioned are both dead. Box2d for flash has to one of resources and by learning it youre learning something you can take to almost anywhere.

I've made games in Ape it was good but as I said it's a dead project. I've made games in box2d, it's more upfront work but your returns are solid.

To the person who mentioned they could tell a game used box 2d by how it felt. I really doubt that, if anything you could tell it is using some kind of rigid body physics engine but that's about it.

Also check out motor2, another box2d port by a really smart guy.

Sent on iphone

---
Tags: flash, physics, actionscript-3, physics-engine
---


title: C# XNA - Sky Sphere Question

text:
# Question
Title: C# XNA - Sky Sphere Question
I have been banging my head against the wall trying to get a sky sphere to work appropriately in XNA 4.0. I have the sphere loading correctly, and even textured, but i would like something a little more dynamic that can support a day/night cycle.

My issue is that, while i know a good amount of C# and XNA, i know next to nothing about HLSL. (I could make an ambient light shader if my life depended on it...) I also have not been able to find a tutorial on how to build a sky sphere like this. Of course i don't expect to be able to make an amazing one right off the bat, i would like to start small, with a dynamic coloring sky i'll work out the clouds and sun later.

My first question: Does anyone know of any good tutorial sites that could help me get a decent grasp around HLSL?

Second: Does anyone have a good example of or know where to find one of a gradient sky using XNA and C#?

# Answer
You can get a `Skysphere` here. I have managed to convert it and you can see it working here.
> 1 votes

# Answer
I had to do one of these. Easiest method is to texture the sphere (make sure the normals are facing *inward*, otherwise you won't be able to see it). Then if you want clouds n' the like, just move another texture over it in a shader (there's a good number of fairly easy HLSL tutorials out there. Others have recommended some, I would recommend Riemers even if it's not specifically skysphere related as a good starting point)

If you want a day/night cycle, it's heavily going to be influenced just by the lighting you cast on the rest of your scene. However, if the lights in the sky are looking kinda flat, make a second texture that just has the light sources in white (intensity = whiteness) then do an additive blend based on how much you want them to light up.

In any case, good luck. Wanting a skysphere is something that drove me into getting a lot more involved with shaders. It won't be too scary once you start digging into it.
> 1 votes

---
Tags: c#, xna-4.0, hlsl, sky
---


# Question
Title: How do I find the intersections between colliding circles?
I want to find whether 2 circles with radii `r1` and `r2` intersect, and if so, *where they do so*. Is there a simple solution?

# Answer
> 17 votes
# Simple collision: detecting whether two circles intersect at all

Determining whether two circles intersect at all is fairly simple: we calculate whether the distance between their center points is less than or equal to the sum of their two radiuses.<sup>(note below)</sup>

Let's consider the two circles to be \\$A\\$ and \\$B\\$: we'll define their center points as vectors \\$c\_A\\$ and \\$c\_B\\$, and their radii as \\$r\_A\\$ and \\$r\_B\\$. The circles are colliding if:

$$ \tag{0} \lvert c\_A - c\_B \rvert \le r\_A + r\_B $$

... where \\$\lvert this \rvert\\$ represents a vector's magnitude (length).

Here's that equation represented as pseudocode:

```
class Circle {
  center: Vector2
  radius: Float
}

function Colliding(a: Circle, b: Circle) returns Boolean {
  Vector2 diff = a.center - b.center
  Float maxDistance = a.radius + b.radius
  return diff.magnitude <= maxDistance
}

```

Note: We're counting the edges *exactly* touching—the distance being exactly the sum of the two radiuses—as a collision. If you don't want to count this as a collision then in the above formula and code sample, where they use \\$\le\\$ or `<=`, you should instead use \\$\<\\$ or `<`.

# Determining the exact intersection points

*(This section is heavy on mathematics. For code, skip to the next section.)*

“Intersection of Two Circles” by Paul Bourke (1997) describes an algorithm for determining the exact intersection points. It provides this diagram:

In this diagram, \\$P\_0\\$ and \\$P\_1\\$ are the center points of the two circles, and \\$r\_0\\$ and \\$r\_1\\$ are their radii.

First we determine the distance (\\$d\\$) between the circles:

$$ \tag{1} d = \lvert P\_1 - P\_0 \rvert $$

Then we'll check a couple of potential cases which result in no intersections.

$$ \tag{2} \begin{array}{lll} \text{case 1:} & d \> r\_0 + r\_1 \\ \text{case 2:} & d \< \lVert r\_0 - r\_1 \rVert \\; \text{or} \\; d = 0 \end{array} $$

* If **case 1** is true, the circles are wholly separate and there is no edge intersection.
* If **case 2** is true, one circle wholly contains the other, and there is no edge intersection to calculate, or rather the intersection is 100% of the smallest circle. (Note we're subtracting not adding; \\$\lVert this \rVert\\$ represents absolute value.)

If neither is true, we'll proceed.

In that diagram, there are two triangles we can observe: one is \\$P\_0 P\_2 P\_3\\$, which has \\$r\_0\\$, \\$a\\$, and \\$h\\$ for its edges. The other is \\$P\_1 P\_2 P\_3\\$ which has edges \\$r\_1\\$, \\$b\\$, and \\$h\\$. We need to calculate \\$P\_2\\$, \\$a\\$, and \\$h\\$, and then eventually we can work out \\$P\_3\\$ which represents the intersection points we're looking for. We never use \\$b\\$ so we'll leave that aside.

First we'll calculate \\$a\\$:

$$ \tag{3} a = \frac{r\_0^2 - r\_1^2 + d^2}{2d} $$

Then \\$h\\$: $$ \tag{4} \begin{array}{rl} \text{given} & a^2 + h^2 = r\_0^2, \\ \text{then} & h^2 = r\_0^2 - a^2 \\ \text{therefore} & h = \sqrt{r\_0^2 - a^2} \\ \end{array} $$

Then \\$P\_2\\$:

$$ \tag{5} P\_2 = P\_0 + \frac {a(P\_1 - P\_0)}{d} $$

If the circles are exactly as far apart as our combined radiuses, \\$P\_2\\$ is our single (only) collision point:

$$ \tag{6} \begin{array}{ll} \text{case 3:} & d = r\_0 + r\_1 \end{array} $$

If **case 3** is true we just use \\$P\_2\\$; **done.**

Otherwise we have two collision points, represented in the diagram as \\$P\_3\\$. We'll calculate \\$P\_3\\$ by its coordinates \\$(x\_3, y\_3)\\$. In the following, \\$x\_0\\$/\\$y\_0\\$ thru \\$x\_2\\$/\\$y\_2\\$ represent the x- and y-coords of \\$P\_0\\$ thru \\$P\_2\\$.

$$ \tag{7} \begin{align} x\_3 &= x\_2 \pm \frac{h(y\_1 - y\_0)}{d} \\ y\_3 &= y\_2 \mp \frac{h(x\_1 - x\_0)}{d} \end{align} $$

So, \\$P\_3\\$ is actually two points, right? Let's call them \\$\alpha\\$ and \\$\beta\\$ (alpha and beta). We follow equation 7 to calculate them as follows:

$$ \tag{8} \text{for }\alpha\text{:} \\ \begin{align} x\_\alpha &= x\_2 + \frac{h(y\_1 - y\_0)}{d} \\ y\_\alpha &= y\_2 - \frac{h(x\_1 - x\_0)}{d} \end{align} $$

$$ \tag{9} \text{for }\beta\text{:} \\ \begin{align} x\_\beta &= x\_2 - \frac{h(y\_1 - y\_0)}{d} \\ y\_\beta &= y\_2 + \frac{h(x\_1 - x\_0)}{d} \end{align} $$

Note: plus and minus, then minus and plus.

Now we have our intersection points, \\$\alpha\\$ and \\$\beta\\$.

# Code implementation

Here's the above algorithm as code, written in Python 2.7.

```
from math import sqrt

# Determines whether two circles collide and, if applicable,
# the points at which their borders intersect.
# Based on an algorithm described by Paul Bourke:
# https://web.archive.org/web/20060911063359/http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/
# Arguments:
#   P0 (Vector2): the centre point of the first circle
#   P1 (Vector2): the centre point of the second circle
#   r0 (number): radius of the first circle
#   r1 (number): radius of the second circle
# Returns:
#   False if the circles do not collide
#   True if one circle wholly contains another such that the borders
#       do not overlap, or overlap exactly (e.g. two identical circles)
#   An array of two vectors containing the intersection points
#       if the circle's borders intersect.
def Intersection(P0, P1, r0, r1):
  if type(P0) != Vector2 or type(P1) != Vector2:
    raise TypeError("P0 and P1 must be vectors")

  # equation 1
  offset = P1 - P0
  d = offset.magnitude()

  # equation 2: simple cases
  if d > (r0 + r1):
    # no collision
    return False
  elif d == 0 or d < abs(r0 - r1):
    # full containment
    return True

  # equation 3
  a = (r0**2 - r1**2 + d**2) / (2 * d)

  # equation 4
  h = sqrt(r0**2 - a**2)

  # equation 5
  P2 = P0 + a * (P1 - P0) / d

  # equation 6
  if (d == r0 + r1):
    return [P2]

  # equation 8
  alpha_x = P2.x + h * (P1.y - P0.y) / d
  alpha_y = P2.y - h * (P1.x - P0.x) / d
  alpha = Vector2(alpha_x, alpha_y)

  # equation 9
  beta_x = P2.x - h * (P1.y - P0.y) / d
  beta_y = P2.y + h * (P1.x - P0.x) / d
  beta = Vector2(beta_x, beta_y)

  return [alpha, beta]

# Simple 2D vector class.
# Based on work by @mcleonard on github:
# https://gist.github.com/mcleonard/5351452
class Vector2(object):
  def __init__(self, x, y):
    """Create a vector, e.g. v = Vector2(10, 15)"""
    self.x = x
    self.y = y

  def magnitude(self):
    """Returns the magnitude of this vector."""
    return sqrt(self.x**2 + self.y**2)

  def __add__(self, other):
    """Returns the vector addition of self and other."""
    newx = self.x + other.x
    newy = self.y + other.y
    return Vector2(newx, newy)

  def __sub__(self, other):
    """Returns the vector difference of self and other."""
    newx = self.x - other.x
    newy = self.y - other.y
    return Vector2(newx, newy)

  def __mul__(self, other):
    """Multiplies each component if other is a scalar"""
    if type (other) == type(1) or type(other) == type(1.0):
      return Vector2(self.x * other, self.y * other)
    else:
      raise NotImplementedError

  def __rmul__(self, other):
    return self.__mul__(other)

  def __div__(self, other):
    """Divides each component if other is a scalar"""
    if type (other) == type(1) or type(other) == type(1.0):
      return Vector2(self.x / other, self.y / other)
    else:
      raise NotImplementedError

  def __str__(self):
    """Returns this vector as a string of the form: (x, y)"""
    return "(%(x)d, %(y)d)" % { "x": self.x, "y": self.y }

def format(input):
  if isinstance(input, list):
    return "\n  " + "\n  ".join(str(v) for v in input)
  else:
    return "\n  " + str(input)

def run_test(label, expected, actual):
  print label
  print "Expected:", format(expected)
  print "Actual:", format(actual)
  print "\n"

def run_all_tests():
  run_test("Intersection 1", \
    ["(0.5, -1.93649)", "(0.5, 1.93649)"], \
    Intersection(Vector2(0,0), Vector2(1, 0), 2, 2) \
  )

  run_test("Intersection 2", \
    ["(3.39254, -0.749778)", "(-1.99992, 3.02495)"], \
    Intersection(Vector2(2, 3), Vector2(5.5, 8), 4, 9) \
  )

  run_test("Intersection 3", \
    ["(5.14024, 9.90651)", "(9.93669, 6.70888)"], \
    Intersection(Vector2(8, 9), Vector2(4, 3), 3, 7) \
  )

  run_test("Single-point edge collision", \
    ["(2, 0)"], \
    Intersection(Vector2(0,0), Vector2(4, 0), 2, 2) \
  )

  run_test("Wholly inside", \
    "True", \
    Intersection(Vector2(0,0), Vector2(1, 0), 5, 2) \
  )

  run_test("No collision", \
    "False", \
    Intersection(Vector2(0,0), Vector2(5, 0), 2, 2) \
  )

  run_test("The same circle twice", \
    "True", \
    Intersection(Vector2(0,0), Vector2(0,0), 5, 5) \
  )

  print "Expected values are approximations.\n"

run_all_tests()

```

**Run this code on trinket.io here.**

Some tests are defined at the bottom of the file. You can verify your results in Wolfram Alpha by running a query to determine the intersection of two circles like this:

`intersection ((x - h)^2 + (y - k)^2 = r^2), ((x - h)^2 + (y - k)^2 = r^2)`

Where for each of the two circles, `h` = x-coord, `k` = y-coord, and `r` = the radius.

Here's the Wolfram results for each of those intersection test cases:

# Answer
> 10 votes
Do you mean if the circles are overlapping? That's easy, just figure out the distance between the two and compare it to the r1 and r2. Or more specifically, calculate the squared distance between the two (it's faster) and compare it to (r1 + r2)^2.

If you mean what the actual intersection points are of the two circles, then I don't know the math for that offhand.

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