title: 2D Tile Based Collision Detection

text:
# Question
Title: 2D Tile Based Collision Detection
There are a lot of topics about this and it seems each one addresses a different problem, this topic does the same.

I was looking into tile collision detection and found this where David Gouveia explains a great way to get around the person's problem by separating the two axis. So I implemented the solution and it all worked perfectly from all the testes I through at it. Then I implemented more advanced platforming physics and the collision detection broke down. Unfortunately I have not been able to get it to work again which is where you guys come in :)!

I will present the code first:

```
    public void Update(GameTime gameTime) {
        if(Input.GetKeyDown(Keys.A)) {
            velocity.X -= moveAcceleration;
        }
        else if(Input.GetKeyDown(Keys.D)) {
            velocity.X += moveAcceleration;
        }

        if(Input.GetKeyDown(Keys.Space)) {
            if((onGround && isPressable) || (!onGround && airTime <= maxAirTime && isPressable)) {
                onGround = false;
                airTime += (float)gameTime.ElapsedGameTime.TotalSeconds;
                velocity.Y = initialJumpVelocity * (1.0f - (float)Math.Pow(airTime / maxAirTime, Math.PI));
            }
        }
        else if(Input.GetKeyReleased(Keys.Space)) {
            isPressable = false;
        }

        if(onGround) {
            velocity.X *= groundDrag;
            velocity.Y = 0.0f;
        }
        else {
            velocity.X *= airDrag;
            velocity.Y += gravityAcceleration;
        }

        velocity.Y = MathHelper.Clamp(velocity.Y, -maxFallSpeed, maxFallSpeed);
        velocity.X = MathHelper.Clamp(velocity.X, -maxMoveSpeed, maxMoveSpeed);

        position += velocity * (float)gameTime.ElapsedGameTime.TotalSeconds;
        position = new Vector2((float)Math.Round(position.X), (float)Math.Round(position.Y));

        if(Math.Round(velocity.X) != 0.0f) {
            HandleCollisions2(Direction.Horizontal);
        }
        if(Math.Round(velocity.Y) != 0.0f) {
            HandleCollisions2(Direction.Vertical);
        }
    }

private void HandleCollisions2(Direction direction) {
    int topTile = (int)Math.Floor((float)Bounds.Top / Tile.PixelTileSize);
    int bottomTile = (int)Math.Ceiling((float)Bounds.Bottom / Tile.PixelTileSize) - 1;
    int leftTile = (int)Math.Floor((float)Bounds.Left / Tile.PixelTileSize);
    int rightTile = (int)Math.Ceiling((float)Bounds.Right / Tile.PixelTileSize) - 1;

    for(int x = leftTile; x <= rightTile; x++) {
        for(int y = topTile; y <= bottomTile; y++) {
            Rectangle tileBounds = new Rectangle(x * Tile.PixelTileSize, y * Tile.PixelTileSize, Tile.PixelTileSize, Tile.PixelTileSize);
            Vector2 depth;

            if(Tile.IsSolid(x, y) && Intersects(tileBounds, direction, out depth)) {
                if(direction == Direction.Horizontal) {
                    position.X += depth.X;
                }
                else {
                    onGround = true;
                    isPressable = true;
                    airTime = 0.0f;
                    position.Y += depth.Y;
                }
            }
        }
    }
}

```

From the code you can see when `velocity.X` is not equal to zero the `HandleCollisions()` Method is called along the horizontal axis and likewise for the vertical axis. When `velocity.X` is not equal to zero and `velocity.Y` is equal to zero it works fine. When `velocity.Y` is not equal to zero and `velocity.X` is equal to zero everything also works fine. However when both axis are not equal to zero that's when it doesn't work and I don't know why. I basically teleport to the left side of a tile when both axis are not equal to zero and there is a air block next to me.

Hopefully someone can see the problem with this because I sure don't as far as I'm aware nothing has even changed from what I'm doing to what the linked post's solution is doing.

Thanks.

# Answer
> 2 votes
I'll try to give a quick answer, assuming that you want to keep using the same technique I suggested on the other post (which by the way is not perfect, but in practice I haven't run into any noticeable problems yet in the context of a game).

Basically you changed the most important part of the code when you applied the velocity all at once to the position. What you need to do after calculating `velocity`, is to apply it in two steps to your `position` such as:

```
// Correct example
float elapsed = (float) gameTime.ElapsedGameTime.TotalSeconds;
if(velocity.X != 0f)
{
    position += velocity.X * Vector2.UnitX * elapsed;
    position = new Vector2((float)Math.Round(position.X), position .Y);
    HandleCollisions2(Direction.Horizontal);
}
if(velocity.Y != 0f)
{
    position += velocity.Y * Vector2.UnitY * elapsed;
    position = new Vector2(position.X, (float)Math.Round(position.Y));
    HandleCollisions2(Direction.Vertical);
}

```

As opposed to what you were doing, which was something like the following code (mirroring the same structure as the code above):

```
// Wrong example
float elapsed = (float) gameTime.ElapsedGameTime.TotalSeconds;
position += velocity * elapsed;
position = new Vector2((float)Math.Round(position.X), (float)Math.Round(position .Y));
if(velocity.X != 0f)
{
    HandleCollisions2(Direction.Horizontal);
}
if(velocity.Y != 0f)
{
    HandleCollisions2(Direction.Vertical);
}

```

# Answer
> 0 votes
The code looks alright, i'm going to assume it works, i don't code in XNA, so i don't know which objects are yours. The issue is that you're not checking which collision resolution is the smallest. If either x or y velocity is 0 then

```
    if(Math.Round(velocity.X) != 0.0f) {
        HandleCollisions2(Direction.Horizontal);
    }
    if(Math.Round(velocity.Y) != 0.0f) {
        HandleCollisions2(Direction.Vertical);
    }

```

is going to sort it for you (since there's possible collision only along the vertical or horizontal axis). However, if both of those velocities are different than zero then the collision is going to get solved for the horizontal axis first, then there won't be any collision so the vertical collision function won't do anything.

If you want to fix this, check both vertical and horizontal collision and find the smallest displacement vector, then resolve collision.

If you want to do what David explained in this answer (which the answer you linked is based on) then you'll have to separate your x and y **movement and collision checking**. Right now, you're calling `position += velocity * (float)gameTime.ElapsedGameTime.TotalSeconds;` which is not what David was advocating.

# Answer
> 0 votes
Is depth.X always positive? I only ask because maybe its pushing you into the object then you show up on the left size. Granted, that's usually a negative direction, but its worth checking.

If that's true you need to do "position.X -= depth.X" depending on which side you are on or fix Intersection.

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


# Question
Title: How can I generate a 2d navigation mesh in a dynamic environment at runtime?
So I've grasped how to use A\* for path-finding, and I am able to use it on a grid. However, my game world is huge and I have many enemies moving toward the player, which is a moving target, so a grid system is too slow for path-finding. I need to simplify my node graph by using a navigational mesh.

I grasp the concept of "how" a mesh works (finding a path through nodes on the vertices and/or the centers of the edges of polygons).

My game uses dynamic obstacles that are procedurally generated at run-time.

I can't quite wrap my head around how to take a plane that has multiple obstacles in it and programatically divide the walkable area up into polygons for the navigation mesh, like the following image.

Where do I start? How do I know when a segment of walk-able area is already defined, or worse, when I realize I need to subdivide a previously defined walk-able area as the algorithm "walks" through the map?

I'm using javascript in nodejs, if it matters.

# Answer
> 3 votes
*@Stephen* \- *Long Comment* \- That paper looks like it might be worth a read when I have some time. Basically what I would have suggested is something along the lines of the Hertel-Mehlhorn Algorithm which is mentioned in the paper (a reference for this specific algorithm can be found here http://www.bringyou.to/compgeom/) with the addition of subdividing the map sides (outside boundary of the play area) some number of time to reduce the occurrences of multiple small triangles formed in the corners. Those small triangles can be problematic as they can end up being smaller than the thing you’re preforming path-finding for. The Hertel-Mehlhorn is for the reduction of the polygons produced by a triangular partitioning if you’re interested here is more on triangulation: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm.

Also, if you’d rather not reinvent the wheel, I think this library will actually do everything you need: http://code.google.com/p/polypartition/. It preforms the triangulations and reductions with one of a number of different options including Hertel-Mehlhorn. It’s an MIT License which means it can be used for closed-source and commercial projects if that is an issue.

If you do decide to keep working on your own implementation, I’d love to see what you come up with.

# Answer
> 6 votes
Rather than a mesh, you might just consider a hierarchical A\* approach. A mesh's biggest advantage is in dealing with game worlds that aren't grid aligned, rather than in reducing complexity from a grid.

With a hierarchical approach, you subdivide your world repeatedly (much like a quad tree), and generate connectivity information between the nodes. You can then quickly generate a path between large chunks of the world, and only use the high-resolution grid to path find within a larger chunk.

The hierarchical approach will give orders of magnitude better performance, while a mesh at best is only going to give you a small linear improvement.

The naive approach is to just divide your world into X by X larger grid aligned chunks, generate the connectivity info between them (e.g., is there a path between through chunk 2x1 from 3x1 to 2x2, and what is the distance of the average path).

Note that you may not always get ideal paths with this approach in some particular circumstances. Generating variable-sized layers of chunks alleviates the problem, but honestly it's usually just way easier to avoid the ever making makes with the problem paths and to rely on the fact that the player is highly unlikely to notice any enemies taking suboptimal paths except in the most degenerate of cases.

# Answer
> 3 votes
I think you might be overcomplicating this. You probably don't need to generate navigation meshes on the fly. Instead have a static navigation mesh for your base world.

Pathing around obstacles can be solved using steering behaviours (use obstacle avoidance). If on the off chance your obstacle is so large it fills or completely blocks off travel from one nav-poly to the next, then have some way of checking for this edge case and recompute the path between the poly you're currently in and the one you're blocked off from.

---
Tags: path-finding, node.js, automation, navmesh
---


# Question
Title: Should the main game object be static in c++
I am creating a 2d platformer using SDL and I was thinking that my game object could be static, but I wasn't sure if this was a good idea.

The pros (that I can see):

* Accessing settings options (such as screen size and keyboard bindings) would be easier accessed
* There should only ever be one main game loop, so this makes sure for me.

The cons:

* From what I've heard, static classes in C++ are a bear to work with
* I've read that this may cause problems later in development (things don't work right or can't be used properly

# Answer
A singleton for your main engine class is perfectly normal.

It's even quite acceptable to have one singleton for each of your game's major systems, like graphics and input. I personally prefer a single Engine singleton with all systems as members of that object, but really there's very little difference.

A singleton can just be a static global object, although its usually more of a special kind of class with a static accessor method. E.g.

```
class Engine {
private:
  Engine();
  ~Engine();

public:
  static Engine& Instance() {
    static Engine engine;
    return engine;
  }
};

```

There are of course a million variations on that theme. In particular, some singleton implementations allow or even require explicit calls to construct or destruct the object (useful if you put each system in its own singleton and need to deal with dependencies between them). You can make a reusable templated version. You can make the singleton a separate object from the class being used as a singleton. And so on.
> 8 votes

# Answer
This is a general post about why static classes cause you more trouble than they are worth. And this includes singleton classes which are just a fancy way of doing the same thing that avoids construction order problems. No advice fits all cases, so take it as advice, not as an instruction that it is always better to do it this way.

In general code shouldn't reach out to get the data that it needs to provide it's job, it should be provided with that data.

I'll give an example from what you said -

```
**Accessing settings options (such as screen size and keyboard bindings) would be easier accessed**

```

So you write you main rendering loop and in there you call something like Game::getSetting(ScreenWidth);

That all works well and is nice and easy. Then one day you decide "wouldn't it be nice to let the player make screenshots. And it would be good to do them at higher resolution than the screen so they look good!". Now you have a problem. All your code depends on getting the screen size from the static getSetting function. If instead you'd provided your rendering code with the screen size instead you could simply call it with different parameters.

Another problem -

You write an amazingly cool user interface class for your game. It needs to know what font the user has chosen so you call Game::getSetting(UIFont) to get it. Nice and easy. But then you decide to write a separate game editor... Now in order to use your amazingly cool UI class there is a dependency on your static Game class so you need to drag in the whole of the Game class too... Which probably has dependencies on other components.

Sure you can change the code to work differently, but then you have two copies to maintain. If only you'd provided the font as a parameter to the class instead of letting it go get it itsself it would be much easier.

In general having functions go out and get the data they need to do their job introduces coupling between components and makes your code harder to maintain and change, and reuse, and you are better providing from outside the data that is needed either as a function call parameter or when you construct an object or whenever.

And the main advantage of static data or singletons is that they are easily located in random bits of code. If you don't need random bits of code to reach out to the static data then it doesn't need to be static any more...

Note that this doesn't mean you need to pass dozens of separate bits of data. You might create a group of related settings where you generally need all of them for related purposes and pass that. For example make a UserInterfaceSettingsContext structure and store the related settings needed to draw a user interface in there and pass an instance of that to anything that needs it...
> 5 votes

# Answer
The main problem with static and global objects in C++ is that they are created before the application's entry point (i.e. `main`), but their constructors are called in a completely *unpredictable order*. The same is true for their destructors, at the end of the application. This is clearly a problem because often we will have objects that depend on each other, and require a certain order of initialization and shutdown for the application to work correctly!

While you could use a singleton, which usually delays the construction of the object until it is first accessed, the destruction order will still be undefined, unless you make your singleton class more complex to handle that situation too.

On the book Game Engine Architecture they discuss a few alternatives to this, but it's the *simple* solution (in the sense that it uses no patterns, or any special control mechanisms) that they recommend the most. The book even states that this is the approach used in Uncharted for the PS3, so if it was enough for a huge AAA game like that, it will probably be enough for you too. Basically:

* Leave constructors and destructors empty
* Add explicit `Initialize` and `Release` methods
* Creating global objects for your subsystems (since constructors/destructors are empty the order does not matter anymore)
* Manually call `Initialize` and `Release` for each subsystem in the order you want

The main advantage is that besides being simple, you have complete control over the construction order, and most importantly, you can just *look* at the code and see in which order things are being created.
> 5 votes

# Answer
I would recommend against the singleton, as it's become quite the anti-pattern. A better solution, in my eyes, would be to use the service pattern. Here you have a service locator that is available to everyone. (OK so that might have to be a static singleton depending on your code). Other objects query the service locator which then provides one. For example if I'm looking for the GraphicsDeviceService I query the service locator for an IGraphicsDeviceService. It will then return an existing current instance or construct one (Factory pattern) if there is no matching service available.

Now this is of course more complex than just using singletons, but the big benefit is that implementations of the service ,can change on the fly. Here is a sample implementation: http://www.blackwasp.co.uk/ServiceLocator.aspx
> 2 votes

---
Tags: c++, sdl, windows, linux, macos
---


# Question
Title: viewing fbx files in windows via xna 4.0
I've made some models in Blender and exported them in Autodesk fbx format. I'm trying to view them using XNA 4.0 Refresh.

Loading them isn't much an issue, but I'm not familiar enough with XNA 4.0 to, well basically I want to load in the model at say the origin (0,0,0) world coordinates, and then rotate and/or zoom the camera about the world coordinates origin as well so that I can test the model. Typically the mouse, and maybe some arrow keys for zooming/rotating the camera.

Anyways, this seems like a simple task and I shouldn't have to re-invent this, isn't there a skeleton code somewhere for this kind of thing for XNA 4.0? I couldn't find a solid example for this on the web. I found a couple that seemed like they might work for xbox, but I'm trying to do this on windows only.

Anyways, just looking to be pointed in the right direction on this one, thanks.

# Answer
First, start with something that can load FBX files. If you've got this working - then by all means use your own code. But I suggest also looking at the WinForms 2 sample which shows a rotating FBX model.

Next is handling user input. In XNA you will want to look at the `Mouse` class (MSDN). The basic pattern for using it is to keep the current and previous mouse states and then compare the difference in positions.

```
MouseState lastMouseState;
protected override void Update(GameTime gameTime)
{
    MouseState mouseState = Mouse.GetState();
    int deltaX = mouseState.X - lastMouseState.X;
    int deltaY = mouseState.Y - lastMouseState.Y;
    // ...
}

```

For `Keyboard` (MSDN) the process is pretty much the same - compare the last and current states.

If you are using WinForms (as per that sample), you'll have to hook up events to the model viewer control and handle those instead.

Finally, what you are trying to implement here is called an **orbit camera**. I don't think there's any definitive way to implement this. It's just a series of matrix transformations.

The WinForms 2 sample I linked implements most of what you want already. Look at `ModelViewerControl.Draw` in that sample for where it sets up its matrices. Here's a modified version that you can work from:

```
Matrix world = Matrix.CreateRotationY(rotateY) * Matrix.CreateRotationX(rotateX);
Matrix view = Matrix.CreateLookAt(modelCenter + new Vector2(0, 0, modelRadius + zoom),
                                  modelCenter, Vector3.Up);

```

Then it's simply a matter of taking those delta inputs from earlier and then accumulating those deltas in the appropriate variable. For example:

```
const float rotateSpeedFactor = 0.05f; // this is a guess
rotateX += deltaX * rotateSpeedFactor;
rotateY += deltaY * rotateSpeedFactor;

```

---

**Edit:** Another one to look at is the Skinned Model sample, which implements almost exactly what you are looking for (with keyboard control - arrows rotate, Z/X to zoom).
> 0 votes

---
Tags: xna-4.0, fbx
---


title: Touching a CGRect

text:
# Question
Title: Touching a CGRect
In my cocos2d app I am trying to determine when a CCSprite is touched Here is what I have:

```
-(BOOL)ccTouchBegan:(UITouch *)touch withEvent:(UIEvent *)event{
NSMutableArray *targetsToDelete = [[NSMutableArray alloc] init];
for (CCSprite *target in _targets) {
    CGRect targetRect = CGRectMake(target.position.x - (target.contentSize.width/2),
                                   target.position.y - (target.contentSize.height/2),
                                   27,
                                   40);

CGPoint touchLocation = [self convertTouchToNodeSpace:touch];
if (CGRectContainsPoint(targetRect, touchLocation)) {
    NSLog(@"Moo cheese!");
    }
}
return YES;
}

```

For some reason it does not work. Can someone help me?

# Answer
```
bool Puzzle::ccTouchBegan(CCTouch *pTouch, CCEvent *pEvent) {
    if(isOnShapeTouched(pTouch)) {
        return true;
    }

    return false;
}

bool Puzzle::isOnShapeTouched(CCTouch* pTouch) {
    for(int i=0; i < mSprites.size(); i++) {
        if(CCRect::CCRectContainsPoint(mSprites.at(mSprites.size()-i-1)->boundingBox(), CCDirector::sharedDirector()->convertToGL(pTouch->locationInView()) ) ) {
            mCurrentSprite = mSprites.at(mSprites.size()-i-1);

            return true;
        }
    }
    return false;
}

```
> 1 votes

---
Tags: cocos2d-iphone, ios, cocos2d, touch
---


# Question
Title: Should I used Box2D for a Flash platformer or use something for gaming like Fixel or Flashpunk?
I'm trying to make a platformer with Flash/AS3 and have been looking for something to help with some of the collision etc. I've look at a few engines and Box2D/WCK seems the most sophisticated. Do I need that level of sophistication or should I just stick to something simple like Fixel or Flashpunk? OR should I just do everything myself?

# Answer
> 4 votes
Box2D is a physics engine; Flixel and Flashpunk are game frameworks. You can use both Flixel and Flashpunk with Box2D.

I highly recommend using a framework like Flixel or Flashpunk. It will simplify and accelerate your coding experience.

For a platformer, Box2D is probably not necessary unless you want interesting physics to be a part of your gameplay. If you do, Box2D will probably be useful, but I recommend using it on top of a framework.

# Answer
> 1 votes
Doing everything on your own will make you learn new things, but it's always better to not to reinvent the wheel. I've only used `Box2D` in my projects and let me tell you, it's so easy to use that you'll never want to do collision coding on your own.

You may fall into performance problem, but it's easy to solve them (Mainly you'll get lower performance only when you'll add lot's of bodies or when you chose wrong scaling factor. You should read official faq for that).

# Answer
> 1 votes
You can also try with the Citrus Engine, http://citrusengine.com which it's specifically made for platform games and implements box2d for the physics. It's also open source

Cheers!

# Answer
> 0 votes
It's hard to know what is best for you, but I'd recommend you target the GPU for better result and take a look at starling.

http://gamua.com/starling/

It's painstakingly easy to hit the wall in terms of performance with the software renderer in flash player. Particularly to get a decent frame rate.

Some people have successfully implemented box2d in Starling, that's what I would look at using personally.

http://www.aymericlamboley.fr/blog/citrusengine-goes-stage3d-with-starling/

http://www.aymericlamboley.fr/blog/wp-content/uploads/2012/01/index.html

---
Tags: physics, flash, box2d
---


title: How should I represent matrices in C++?

text:
# Question
Title: How should I represent matrices in C++?
I'm teaching myself 3D mathematics and in the process building my own rudimentary engine (of sorts). I was wondering what would be the best way to structure my C++ matrix class. There are a few options:

1. Separate member variables:

```
struct Mat4 {
    float
        m11, m12, m13, m14,
        m21, m22, m23, m24,
        m31, m32, m33, m34,
        m41, m42, m43, m44;

    // methods

}

```
2. A multi-dimensional array:

```
struct Mat4 {
    float[4][4] m;

    // methods

}

```
3. An array of vectors

```
struct Mat4 {
    Vec4[4] m;

    // methods

}

```

I'm guessing there would be positives and negatives to each.

From 3D Math Primer for Graphics and Game Development, 2nd Edition p.155:

> Matrices use 1-based indices, so the first row and column are numbered 1. For example, `a12` (read “`a` one two,” not “`a` twelve”) is the element in the first row, second column. Notice that this is different from programming languages such as C++ and Java, which use 0-based array indices. A matrix does not have a column 0 or row 0. This difference in indexing can cause some confusion if matrices are stored using an actual array data type. For this reason, it’s common for classes that store small, fixed size matrices of the type used for geometric purposes to give each element its own named member variable, such as `float a11`, instead of using the language’s native array support with something like float `elem[3][3]`.

So that's one vote for method one.

Is this *really* the accepted way to do things? It seems rather unwieldy if the only benefit would be sticking with the conventional math notation.

# Answer
Why choose? You can have both. (Without any added complexity to logic and without any additional memory requirement thanks to unions.)

```
struct Mat4
{
    union
    {
        struct
        {
          float m11, m12, m13, m14,
                m21, m22, m23, m24,
                m31, m32, m33, m34,
                m41, m42, m43, m44;
        };
        float[4][4] m;
    };
// methods
}

```
> 13 votes

---
Tags: mathematics, matrix, linear-algebra
---


title: Building a Flash Platformer

text:
# Question
Title: Building a Flash Platformer
I am basically making a game where the whole game is run in the onEnterFrame method. This is causing a delay in my code that makes debugging and testing difficult. Should programming an entire platformer in this method be efficient enough for me to run hundreds of lines of code?

Also, do variables in flash get updated immediately? Are there just lots of threads listening at the same time?

Here is the code...

```
stage.addEventListener(Event.ENTER_FRAME, onEnter);

function onEnter(e:Event):void
{
//Jumping

if (Yoshi.y > groundBaseLevel)
{
    dy = 0;
    canJump = true;
    onGround = true; //This line is not updated in time
}

if (Key.isDown(Key.UP) && canJump)
{
    dy = -10;
    canJump = false;
    onGround = false; //This line is not updated in time
}
if(!onGround)
{
    dy +=  gravity;
    Yoshi.y +=  dy;
}

//limit screen boundaries

//character movement
if (! Yoshi.hitTestObject(Platform)) //no collision detected
{
    if (Key.isDown(Key.RIGHT))
    {
        speed +=  4;
        speed *=  friction;
        Yoshi.x = Yoshi.x + movementIncrement + speed;
        Yoshi.scaleX = 1;
        Yoshi.gotoAndStop('Walking');

    }
    else if (Key.isDown(Key.LEFT))
    {
        speed -=  4;
        speed *=  friction;
        Yoshi.x = Yoshi.x - movementIncrement + speed;
        Yoshi.scaleX = -1;
        Yoshi.gotoAndStop('Walking');

    }
    else
    {
        speed *=  friction;
        Yoshi.x = Yoshi.x + speed;
        Yoshi.gotoAndStop('Still');
    }

}
else //bounce back collision detected
{
    if(Yoshi.hitTestPoint(Platform.x - Platform.width/2, Platform.y - Platform.height/2, false))
    {
        trace('collision left');
        Yoshi.x -=20;

    }
    if(Yoshi.hitTestPoint(Platform.x, Platform.y - Platform.height/2, false))
    {
        trace('collision top');
        onGround=true;  //This update is not happening in time
        speed = 0;

    }

}
}

```

# Answer
> 3 votes
I don't think that writing the entire game logic in one event in a single class is the best way. It's better to divide the game logic in several classes and follow the best practices of OOP. Like having some base classes, like `Level`, `Player`, `Enemy`, `Weapon` etc. that separate game logic, collision detection, input handling, event handling etc. on a more logical way.

For Flash, there's another engine for making games: FlashPunk. It is free, has a big community and good tutorials to get started. Here's one tutorial for platformers that can be useful to you.

The problem is that there are differences between the current and older versions of FlashPunk so watch out for dates and versions on the forums and blogs when you see code samples.

# Answer
> 2 votes
If you're making a platformer, maybe you can try with the Citrus Engine. http://citrusengine.com It's a game engine specifically made for platform games and it open source

Cheers!

---
Tags: flash, actionscript-3
---


# Question
Title: Is the new windows 8 sdk usable with visual c++ express 2010 on windows 7?
This is inspired by and related to Is the June 2010 DX SDK really the latest? asked recently but it's a different question.

I won't likely be purchasing the full visual studio 2012 for C++, I intend to use the free visual c++ express 2012 that targets desktop applications when it is released so for now I'm using visual c++ express 2010 running on windows 7.

The latest directx11 sdk is the one included in the windows 8 SDK now, it's not a separate release any more.

So my question is, can I use the windows 8 SDK to build directx11 programs that work on windows 7 using visual studio express 2010 running on windows 7. Or do I need to stick to the final DirectX SDK release for now?

# Answer
According to this blog post, yes you can.

EDIT: http://msdn.microsoft.com/en-us/windows/desktop/hh852363.aspx#Requirements lists Windows 7 as a supported OS
> 1 votes

---
Tags: directx11, windows
---


# Question
Title: What's a viable way to get public properties from child objects?
I have a GameObject (RoomOrganizer in the picture below) with a "RoomManager" script, and one or more child objects, each with a 'HasParallelagram' component attached, likeso:

I've also got the following in the aforementioned "RoomManager"

```
void Awake ()
{
    Rect tempRect;
    HasParallelogram tempsc;

    foreach (Transform child in transform)
    {
        try
        {
            tempsc = child.GetComponent<HasParallelogram>();
            tempRect = tempsc.myRect;

            blockedZoneList.Add(new Parallelogram(tempRect));
            Debug.Log(tempRect.ToString());
        }
        catch( System.NullReferenceException)
        {
            Debug.Log("Null Reference Caught");
        }
    }
}

```

HasParallelgram is an empty script with a public Rect set in the editor and nothing else.

Unfortunately, attempting to assign `tempRect = tempsc.myRect` causes a null pointer at run time.

I've done some more digging, and the reason for the null pointer is relatively simple - the RoomManager script gets woken ("Awake") before the HasParallelagram script gets instantiated ("Start").

It's an issue of timing - I need to wait until all objects have been instantiated before calling the RoomManager. Does Unity support a means of doing that?

What's the proper way to get a child's component?

# Answer
What is the exact error? All objects that you declare via the IDE should exist at the time that Awake is called. (http://docs.unity3d.com/Documentation/ScriptReference/MonoBehaviour.Awake.html) So it should not be the case that the HasParallelagram script has not been instantiated. However, Start() will not have been called yet, and that's to be expected - Awake calls run before Start calls, and you can use that knowledge to ensure that internal data is set up in Awake before you perform operations in Start.
> 2 votes

---
Tags: unity
---


# Question
Title: How can I run and jump at the same time?
I'm having some trouble with the game I started. http://testing.fyrastudio.com/lab/tweetOlympics/v0.002/ The thing is that i have an athlete running and he must jump at the same time. A race with obstacles.

I have him running (with pressing the letter Q repeateadly). I also have him jumping (with letter P) But the thing is that when he runs and jumps at the same time, he seems to be jumping at the same place, instead of going forward with the jump... any ideas how can I fix this??

This is the code I'm using for running and jumping on a continuos loop.

```
//if accelearing and the last time that he accelerated was less than X seconds ago, hes running an accelaring
     if (athlete.accelerating && timeCurrent - athlete.last_acceleration > athlete.delay_acceleration) {
      athlete.accelerating = false;
      athlete.last_acceleration = timeCurrent;
      athlete.running = true;
     }
     if (!athlete.accelerating && timeCurrent - athlete.last_acceleration > athlete.delay_acceleration) {
      athlete.decelerating = true;
     }
     if(athlete.decelerating && timeCurrent - athlete.last_deceleration > athlete.delay_deceleration){
      if(athlete.speed >= 1){
       //athlete starts to decelarate
       athlete.last_deceleration = timeCurrent;
       athlete.decelerate();
      }else {
       athlete.running = false;
      }
     }
     if (athlete.running) {
      athlete.position += athlete.speed;
     }
     if (athlete.jumping) {
      if (athlete.jump_height < 1) {
       athlete.jump_height = 1;
      }else {
       if (athlete.jump_height >= athlete.jump_max_height) {
            athlete.jump_height = athlete.jump_max_height;
            athlete.jumping = false;
       }else {
            athlete.jump_height = athlete.jump_height * athlete.jump_speed;
       }
      }

     }
     if (!athlete.jumping) {

      if(athlete.jump_height > 1){
       athlete.jump_height = athlete.jump_height * 0.9;
      }else {
       athlete.jump_height = 1;
      }
     }

     athlete.scaleX = athlete.scaleY = athlete.jump_height;
     athlete.x = athlete.position;

```

Thanks!

# Answer
It looks like I was using a wrong algorithm to calculate the jump and falling down. It was doing it in a linear fashion, and using the scale was not helping to find it out. After looking at some sites and much thought this is what I came up with the following code for a side view and is working great. It would have to be changed a bit for a top-down view, but now it's doing the jump much more fluently.

You can see it working here! http://testing.fyrastudio.com/lab/tweetOlympics/v0.003/ Thanks!

```
                if(timeCurrent - athlete.last_acceleration > athlete.delay_acceleration)
                {
                    if (athlete.accelerating) {
                        athlete.accelerating = false;
                        athlete.last_acceleration = timeCurrent;
                        athlete.running = true;
                     } else {
                        athlete.decelerating = true;
                     }
                }

                if(athlete.decelerating && timeCurrent - athlete.last_deceleration > athlete.delay_deceleration){
                    if(athlete.speed >= 1){
                        athlete.last_deceleration = timeCurrent;
                        athlete.decelerate();
                    }else {
                        athlete.speed = 0;
                        athlete.running = false;
                    }
                }

                if (athlete.running) {
                    athlete.position += athlete.speed;
                }
                if (athlete.jumping) {

                    athlete.jump_height += athlete.jump_speed;
                    athlete.jump_speed -= GRAVITY;
                    if (athlete.jump_height <= 0) {
                        athlete.jump_height = 0;
                        athlete.jumping = false;
                    }
                }
                athlete.y = -athlete.jump_height + 300;
                athlete.x = athlete.position;

```
> 0 votes

# Answer
Your code appears to work fine, though it's a bit messy. I tested your code and read it, both showed that the sprite continued to move when jumping. I do see that you're setting the scale of the sprite instead of changing the y value when it's jumping. You're changing the X scale at the same time, so this may give the illusion of your sprite not moving forward. Try moving the sprite up instead of changing its scale, or just change the scale in the Y axis. That'll make it easier to see what's happening.

Additionally, this cleaned up code is a bit easier to follow:

```
if(timeCurrent - athlete.last_acceleration > athlete.delay_acceleration)
{
    if (athlete.accelerating) {
        athlete.accelerating = false;
        athlete.last_acceleration = timeCurrent;
        athlete.running = true;
     } else {
        athlete.decelerating = true;
     }
}
if(athlete.decelerating && timeCurrent - athlete.last_deceleration > athlete.delay_deceleration){
    if(athlete.speed >= 1){
        //athlete starts to decelarate
        athlete.last_deceleration = timeCurrent;
        athlete.decelerate();
    } else {
        athlete.running = false;
    }
}

if (athlete.running) {
    athlete.position += athlete.speed;
}

if (athlete.jumping) {
    if (athlete.jump_height < 1) {
        athlete.jump_height = 1;
    } else {
        if (athlete.jump_height >= athlete.jump_max_height) {
            athlete.jump_height = athlete.jump_max_height;
            athlete.jumping = false;
       } else {
            athlete.jump_height = athlete.jump_height * athlete.jump_speed;
        }
    }
} else { //not jumping
    if(athlete.jump_height > 1){
        athlete.jump_height = athlete.jump_height * 0.9;
    } else {
        athlete.jump_height = 1;
    }
}

athlete.y = athlete.jump_height;
athlete.x = athlete.position;

```
> 0 votes

---
Tags: 2d, algorithm
---


# Question
Title: Breakout ball collision detection, bouncing against the walls
I'm currently trying to program a breakout game to distribute it as an example game for my own game engine. http://game-engine-for-java.googlecode.com/

But the problem here is that I can't get the bouncing condition working properly. Here's what I'm using.

```
public void collision(GObject other){
    if (other instanceof Bat || other instanceof Block){
        bounce();
    } else if (other instanceof Stone){
        other.destroy();
        bounce();
    }
    //Breakout.HIT.play();
}

```

And here's by bounce() method

```
public void bounce(){
    boolean left = false;
    boolean right = false;
    boolean up = false;
    boolean down = false;
    if (dx < 0) {
        left = true;
    } else if (dx > 0) {
        right = true;
    }
    if (dy < 0) {
        up = true;
    } else if (dy > 0) {
        down = true;
    }
    if (left && up) {
        dx = -dx;
    }
    if (left && down) {
        dy = -dy;
    }
    if (right && up) {
        dx = -dx;
    }
    if (right && down) {
        dy = -dy;
    }
}

```

The ball bounces the bat and blocks but when the block is on top of the ball, it won't bounce and moves upwards out of the game.

What I'm missing? Is there anything to implement? Please help me..

Thanks

EDIT:

Have changed the bounce method.

```
public void bounce(GObject other){
    //System.out.println("y : " + getY() + "     other.y + other.height - 2 : " + (other.getY() + other.getHeight() - 2));
    if (getX()+getWidth()>other.getX()+2){
        setHorizontalDirection(Direction.DIRECTION_RIGHT);
    } else if (getX()<(other.getX()+other.getWidth()-2)){
        setHorizontalDirection(Direction.DIRECTION_LEFT);
    }
    if (getY()+getHeight()>other.getY()+2){
        setVerticalDirection(Direction.DIRECTION_UP);
    } else if (getY()<(other.getY()+other.getHeight()-2)){
        setVerticalDirection(Direction.DIRECTION_DOWN);
    }
}

```

EDIT:

Solved now. See the changed method in my answer.

# Answer
Had solved this problem by changing the bounce method to the following

```
public void bounce(GObject other){
    // The right most point
    float rightx = getX()+getWidth()+1;
    float righty = getY();
    // The left most point
    float leftx = getX()-1;
    float lefty = getY();
    // The top most point
    float topx = getX();
    float topy = getY()-1;
    // The bottom most point
    float bottomx = getX();
    float bottomy = getY()+getHeight()+1;
    if (other.getBounds().contains(rightx, righty)){
        // The right point intersects. So move left
        setHorizontalDirection(Direction.DIRECTION_LEFT);
    } else if (other.getBounds().contains(leftx, lefty)){
        // The left point intersects. So move right
        setHorizontalDirection(Direction.DIRECTION_RIGHT);
    }
    if (other.getBounds().contains(topx, topy)){
        // The top point intersects. So move down
        setVerticalDirection(Direction.DIRECTION_DOWN);
    } else if (other.getBounds().contains(bottomx, bottomy)){
        // The bottom point intersects. So move up
        setVerticalDirection(Direction.DIRECTION_UP);
    }
}

```

Found the solution here.

http://zetcode.com/tutorials/javagamestutorial/breakout/

Changed the solution ( This works perfectly )

```
/**
 * This object bounces back from the other object in a natural way. Please
 * realize that the bounce is not completely accurate because this depends
 * on many properties. But in many situations the effect is good enough. Had
 * some bugs in pixel perfect detection mode if the image has a larger area
 * of complete alpha. If using PPCD, make the object fit the image size by
 * removing the alpha and resizing the image.
 */
public void bounce(GObject other){
    int xd = (int) ((other.x + other.getWidth() / 2) - (x + getWidth() / 2));
    int yd = (int) ((other.y + other.getHeight() / 2) - (y + getHeight() / 2));
    if (xd < 0) {
        xd = -xd;
    }
    if (yd < 0) {
        yd = -yd;
    }
    if (xd > yd) {
        dx = -dx;
    } else {
        dy = -dy;
    }
}

```
> 2 votes

# Answer
I would start with a very low resolution collision detection for example if you imagined everything had a rectangle around it (even the ball) you could store a Rectangle shape (keep it updated as the ball etc moves) then use

```
ballRect.intersects(blockRect)

```

From there if you check it returns true you can do a more detailed detect to determine the balls reaction to the hit for example sending it off at a different angle.

As for the walls you simply have a constant that is your left wall for example and then check

```
if(ball.x > LEFTWALL) {
  //bounce off wall logic here.
}

```

A simple way to redirect the ball is to flip an direction for example

```
if(ball.x > LEFTWALL) {
      dx *= -1; //will reverse the direction with no affect to speed of the x-axis
}

```

The only thing you need to know is what axis the bounce will affect if not both

Hope this helps :)
> 0 votes

---
Tags: java, game-design, collision-detection
---


title: Box 2D Collision Question

text:
# Question
Title: Box 2D Collision Question
I am very new to Box 2D Physics world. I wanted to know how to collide 2 bodies when one is Dynamic and other is Kinematic.

The whole Scenario is explained below: I have 3 balls in total. I want to balls to remain in their places and the third ball to be able to move. When the third ball hits the other two balls then they should move according to the speed and direction from which they were hit. My gravity of the world is 0 because I only want z-axis gravity.

I would also like some one to point me towards some good tutorials regarding Box 2D basics which is language independent.

I hope I have explained my scenario well.

Thanks for the help in advance.

# Answer
> 1 votes
Kinematic bodies aren't really suited for this. The idea of kinematic bodies is that you move them instead of letting the physics-engine dictate the movement. But this is apparently not what you want.

I would create all your bodies as dynamic, but use joints (for example the Weld-joint) to fix the 2 static balls in place. Then whenever you register a collision on one of the fixed balls, break the joint (using `DestroyJoint`).

# Answer
> -1 votes
You should look at this tutorial if you are just starting with box2d. It will really help you :)

---
Tags: collision-detection, box2d
---


# Question
Title: How can I keep straight alpha during rendering particles?
Rencently,I was trying to save textures of 3D particles so that I can reuse the in 2D rendering.Now I had some problem with alpha channel.Some artist told me I that my textures should have unpremultiplied alpha channel.When I try to get the rgb value back,I got strange result.Some area went lighter and even totally white.
I mainly focus on additive and blend mode,that is:

```
ADDITIVE: srcAlpha  VS  1
BLEND:    srcAlpha  VS  1-srcAlpha

```

I tried a technique called premultiplied alpha.This technique just got you the right rgb value,its all you need on screen.As for alpha value,it worked well with BLEND mode,but not ADDITIVE mode.As you can see in parameters,BLEND mode always controlled its value within 1.While ADDITIVE mode cannot guarantee.
I want proper alpha,but it just got too big or too small consider to rgb.Now what can I do?Any help will be great thankful.
PS:If you don't understand what I am trying to do,there is a commercial software called "Particle Illusion".You can create various particles and then save the scene to texture,where you can choose to remove background of particles.
Now,I changed the title.For some software like maya or AE,what I want is called \[straight alpha\].

# Answer
Additive mode for premultiplied alpha is just 1,1 because you have already multiplied the src colour by alpha, hence the name.
> 2 votes

---
Tags: rendering, directx9, particles
---


title: Rolling a 3d die in cocos2d

text:
# Question
Title: Rolling a 3d die in cocos2d
How can I have a 6 sided die in my cocos2d game and when the device is shaked the die rolls and shows a number? I would also use UIKit if it was necessary.

# Answer
> 4 votes
There are several ways to go about this. Here are some ideas:

### Pre-rendered animations

Use a 3D rendering and animation software to animate 6 different die rolls. The advantage of this is that you don't need any 3D library, as you can show the rendered animations in a 2D context. Also pre-rendered animations give you lots of artistic freedom.

In your game you would wait for a gesture (eg. shaking the device), run a random-number generator to get the result of the roll and then play the matching animation.

### Using realtime 3D rendering

Animate a die roll in a 3D modelling software and then use something like Cocos3D to show the animation in your game. This is almost the same as the suggestion with the pre-rendered animations, but instead of having 6 different animations, you could have just one and get the different results by applying one of 6 different textures to the cube. Also this will be much smaller in file-size, as you're using realtime rendering.

Triggering and playing the animation would work pretty much the same as with the pre-renderer animations.

### Using realtime 3D in combination with a 3D physics-engine

Use realtime 3D rendering (such as Cocos3D) together with a 3D physics engine (such as bullet) to simulate die movement. The advantage of this is that you could feed real device motion data into the simulation and have a different animation everytime.

In your game you would probably want to give the die/cube a random start-rotation (or randomly pick one of the 6 sides that should point up initially). Then wait for a user gesture and apply the device motion to the die and start the physics simulation. Wait for the die to stop movement and figure out which side is pointing upwards to get the result.

---

While the realtime approach with physics is the most realistic one with the most variation, it is also quite demanding in terms of programming and setting up the libraries. If you have never used a 3D physics engine, it might be quite a challenge to get the simulation look "right".

Using six pre-rendered animations is probably the easiest approach. You could ask an artist to create these for you and most game-engines can play animations without the need for additional libraries. And since you'll have six slightly different animations for each result, the user will still get some variation.

---
Tags: cocos2d-iphone, ios, cocos2d
---


# Question
Title: Finding closest object to a location within a specific perpendicular distance to direction vector
I have a location and a direction vector indicating facing, I want to find the closest object to that location that is within some tolerance distance (perpendicular distance) to the ray formed by the location and direction vector. Basically I want to get the object that is being aimed at.

I have thought about finding all objects within a box and then finding the closest object to my vector from them results, but I am sure that there is a more efficient way.

The Z axis is optional, the objects are most likely within a few meters of the search vector.

# Answer
This may not be optimal, but it might give you a start.

Let O be the origin of the ray and D is the NORMALISED direction. The parameteric equation of the line is P = O + tD

For a given point Q, we can find a value of t which will give us the point on the line closest to Q

t = D . (Q-O)

(that's a dot product)

Plugging it into the equaton of the line you can find the point on the line that's closest to Q:

C = O + t D

Then you can get the length of Q-C and test if it's within your desired threshold. I reccommend testing squared values to avoid doing a load of square roots.

Also, you can discard points that give a negative t value (the are behind the observer) and the smallest value of t will give the closest intersection.

Hope that's clear enough. It will work in 2D or 3D.
> 1 votes

---
Tags: c#, 3d, mathematics, vector
---


# Question
Title: Robust line of sight test on the inside of a polygon with tolerance
**Foreword**

This is a followup to this question and the main problem I'm trying to solve. My current solution is an hack which involves inflating the polygon, and doing most calculations on the inflated polygon instead. My goal is to remove this step completely, and correctly solve the problem with calculations only.

**Problem**

> Given a concave polygon and treating all of its edges as if they were walls in a level, determine whether two points A and B are in line of sight of each other, while accounting for some degree of floating point errors.

I'm currently basing my solution on a series of **line-segment interection tests**. In other words:

* If **any** of the end points are **outside** the polygon, they **are not** in line of sight.
* If **both** end points are **inside** the polygon, and the line segment from A to B **crosses** any of the edges from the polygon, then they **are not** in line of sight.
* If **both** end points are **inside** the polygon, and the line segment from A to B **does not cross** any of the edges from the polygon, then they **are** in line of sight.

But the problem is dealing correctly with all the edge cases. In particular, it must be able to deal with all the situations depicted below, where red lines are examples that should be rejected, and green lines are examples that should be accepted. I probably missed a few other situations, such as when the line segment from A to B is colinear with an edge, but one of the end points is outside the polygon.

One point of particular interest is the difference between `1` and `9`. In both cases, both end points are vertices of the polygon, and there are no edges being intersected, but `1` should be rejected while `9` should be accepted. How to distinguish these two? I could check some middle point within the segment to see if it falls inside or not, but it's easy to come up with situations in which it would fail.

Point `7` was also pretty tricky and I had to to treat it as a special case, which checks if two points are adjacent vertices of the polygon directly. But there are also other chances of line segments being col linear with the edges of the polygon, and I'm still not entirely sure how I should handle those cases.

*Is there any well known solution to this problem?*

# Answer
> 1 votes
Their is an fast and robust algorithm which uses preprocessing.

Because of your application I assume your polygon is also a simple polygone (http://en.wikipedia.org/wiki/Simple\_polygon) - if so their exists an efficent algorithm for your problem (otherwise I have no idea)

> Given a *simple* polygon P and treating all of its edges as if they were walls in a level, determine whether two points A and B are in line of sight of each other, while accounting for some degree of floating point errors.

**Preprocessing**

1 ) Calculate the inner triangulation T of your polygon P without insert points (http://en.wikipedia.org/wiki/Polygon\_triangulation). Since I assume your polygon is simple, there exists a various set of algorithms for triangulate it. Most ones with runtime O(n\*log n) (n = number of points of you polygon) *It's important for the rest of the algorithm to note that |T| = O(n) since P is a simple 2D polygone and we do not have inserted points into T.*

2 ) (if your polygon P is not simple you cant perform this step) Calculate the Graph G (called dual graph of the triangulation).

* each triangle p of T becomes a node v\[p\] of G
* if p, q are adjacent triangles in T then insert an edge (v\[p\], v\[q\]) into G.

Ensure that you have an mapping p -\> v\[p\] and a mapping v\[p\] -\> p for all p in T. You will need this later on.

*Since |T| = O(n) also |vertices(G)| = O(n)*

*G is a tree since we are not allowed to insert points into T. (ref: http://www.inf.fu-berlin.de/lehre/SS09/AG/skript.html) (written in german)*

**The algorithm**

Given points *A* and *B*, assuming the preprocessing is done.

1) find the two triangles p and q where p contains A and q contains B. *Naive this runs in O(n) by checking for each triangle p in T whether A, B is in p via 3 "left of line"-checks. I think their could be an even more efficient method if you create a tree-search-structure on T during the preprocessing step*

2) use a breath first search in G from v\[p\] to find v\[q\] (G is a tree)(http://en.wikipedia.org/wiki/Breadth-first\_search)

* during the search, if we go through a node v\[u\] check for the triangle u if the segment AB intersects with u.
    + if the segment AB does not intersect with u: we abort our search through v\[u\], because we can't look from A to B through u.
    + if the segment AB does intersect with u: we continue the breath first search in u. *Note that if we have reached v\[u\] in the algorithm means that there exists and path from p to u, such that we can look through each triangle of the path if we look from A to B*. Thus we can also look though the path and through u if we look from A to B (since we are looking through a path of adjacent triangles).
* we are reaching v\[q\] (perform the check above also for v\[q\]) iff we can look from A to B

*We have only to perform at most one segment-triangle intersection-test for each triangle in T - thus O(n) Also the number of steps of the search is O(n) since G is a tree. In **most cases** the number of steps needed should be **much smaller** since we are using a breath first search approach and stop the search in each direction very early (no sight, solution found).*

**Note** You can even speed up step 2 by using an A\*-ansatz for the search. (http://en.wikipedia.org/wiki/A\*\_search\_algorithm)

**References** I used a script of an algorithmic geometrie lecture of the FU Berlin to distillate the algorithm (written in german). (the one I presented here is modified since you are only want to perform a sight-check between two point. The lecture present a method to find a sub-polygon which can be seen from a given point) http://www.inf.fu-berlin.de/lehre/SS09/AG/skript/s13.pdf, (http://www.inf.fu-berlin.de/lehre/SS09/AG/skript.html)

# Answer
> 2 votes
> How to distinguish these two?

Distinguishing between these two is a common need in triangulation algorithms, for both of those are vertex-to-vertex diagonals, one internal the other external. Typically one writes a primitive **inside** predicate, something like this. Let (*a,b,c*) be three consecutive vertices of the polygon in ccw order, and the potential diagonal *bx*. Then *bx* is internal iff the area of triangle *abx* is \>= 0, and at the same time the area of triangle *xbc* is \>= 0. Here one uses signed area computations. Of course treating the = case is delicate in floating point.

I use this method in my book, Comptutational Geometry in C.

---
Tags: mathematics, geometry, line-of-sight
---


# Question
Title: In an Entity-Component-System Engine, How do I deal with groups of dependent entities?
After going over a few game design patterns, I have settle with Entity-Component-System (ES System) for my game engine. I've reading articles (mainly T=Machine) and review some source code and I think I got enough to get started.

There is just one basic idea I am struggling with. How do I deal with groups of entities that are dependent on each other?

Let me use an example:

Assume I am making a standard overhead shooter (think Jamestown) and I want to construct a "boss entity" with multiple distinct but connected parts. The break down might look like something like this:

* Ship body: Movement, Rendering
* Cannon: Position (locked relative to the Ship body), Tracking\Fire at hero, Taking Damage until disabled
* Core: Position (locked relative to the Ship body), Tracking\Fire at hero, Taking Damage until disabled, Disabling (er...destroying) all other entities in the ship group

My goal would be something that would be identified (and manipulated) as a distinct game element without having to rewrite subsystem form the ground up every time I want to build a new aggregate Element.

How do I implement this kind of design in ES System?

1. Do I implement some kind of parent-child entity relationship (entities can have children)? This seems to contradict the methodology that Entities are just empty container and makes it feel more OOP.
2. Do I implement them as separate entities, with some kind of connecting Component (BossComponent) and related system (BossSubSystem)? I can't help but think that this will be hard to implement since how components communicate seem to be a big bear trap.
3. Do I implement them as one Entity, with a collection of components (ShipComponent, CannonComponents, CoreComponent)? This one seems to veer way of the ES System intent (components here seem too much like heavy weight entities), but I'm know to this so I figured I would put that out there.
4. Do I implement them as something else I have mentioned?

I know that this can be implemented very easily in OOP, but my choosing ES over OOP is one that I will stick with. If I need to break with pure ES theory to implement this design I will (not like I haven't had to compromise pure design before), but I would prefer to do that for performance reason rather than start with bad design.

For extra credit, think of the same design but, each of the "boss entities" were actually connected to a larger "BigBoss entity" made of a main body, main core and 3 "Boss Entities". This would let me see a solution for at least 3 dimensions (grandparent-parent-child)...which should be more than enough for me.

# Answer
> 44 votes
If I were in this situation, I would create each part of the boss as a separate entity. These "sub-entities" would include some kind of `AttachmentPoint` or `ParentEntity` component. This component would include a reference to the parent entity and an offset from the parents position. When updating the position, they check the parent position and apply the offset to generate their own position. Additionally, it could make checks to ensure the parent entity still exists. Further, you can have a `SubEntity` component that tracks the existence of sub entities for the parent entity. This allow you to do things like only make the core of the boss vulnerable when the arms with shields are destroyed.

I currently use a `TargetEntity` component in my game, which is used for turret tracking and when goblins are going to pick up a resource. It can check the target entity's position and change it's behavior accordingly. Entities that have no position are never added as a target, so there's no worries there. However, when getting to be more in depth, like checking the parent or child entity health, shield, power reserves or whatever, you'll have to ensure the parent or child entity actually has the related component.

Making each part it's own entity maintains the flexibility of the entity/component framework by allowing you to add additional and different components to each part of the boss. For example, one part of the boss might have a gun component and a health component while another would have a shield component and a health component.

I found another discussion on this topic here. In which the users are discussing adding multiple components of the same type to one entity (which seems like a bad idea to me). It seems like a useful conversation, though I haven't read the whole discussion.

# Answer
> 7 votes
Without knowing too many details about your existing systems, the way I would model this (and have to some extent in my own entity system) is to have a component like AttachedTo(parentEntity). Any of the children can then be given the AttachedTo(boss) component.

The rendering system (or whatever) then grabs entities with components: Position, AttachedTo, etc. and forms the proper hierarchies.

# Answer
> 5 votes
If you want to have an entity represented by just an ID, then the containment of entities can be done via a special component. You could call it CompositeComponent, and this contains a list of child entity IDs, and interfaces to add/remove children from that list.

Obviously any components that depend on position etc will need to work with this one to place the entity properly. How to implement this will depend somewhat on how you implement positioning currently.

By the way, there is no "pure ES theory" - making entities out of components is a popular approach but the precise method is by no means standardised yet.

---
Tags: entity-system, component-based, entity-component-system
---


title: How change LOD in geometry?

text:
# Question
Title: How change LOD in geometry?
I'm looking for a simple algorithm for LOD, for changing geometry vertexes and decreasing frame time. I've created an octree, but now I want model or terrain vertex modify algorithm, not for increase (looking on tessellation later) but for decrease.

I want something like this:

Questions:

* Can the same algorithm apply to both model and terrain correctly?
* Do indexes need to be modified?
* Must I use octree or simple check distance between camera and object for desired effect?
* Is a new value of indexcount for the DrawIndexed function needed?

Code:

```
     //m_LOD == 10 in the beginning
     //m_RawVerts - array of 3d Vector filled with values from vertex buffer.

     void DecreaseLOD()
     {
         m_LOD--;
         if(m_LOD<1)m_LOD=1;
         RebuildGeometry();
     }

     void IncreaseLOD()
     {
         m_LOD++;
         if(m_LOD>10)m_LOD=10;
         RebuildGeometry();
     }

     void RebuildGeometry()
     {
         void* vertexRawData = new byte[m_VertexBufferSize];
         void* indexRawData = new DWORD[m_IndexCount];
         auto context = mp_D3D->mp_Context;

         D3D11_MAPPED_SUBRESOURCE data;
         ZeroMemory(&data,sizeof(D3D11_MAPPED_SUBRESOURCE));

         context->Map(mp_VertexBuffer->mp_buffer,0,D3D11_MAP_READ,0,&data);
         memcpy(vertexRawData,data.pData,m_VertexBufferSize);
         context->Unmap(mp_VertexBuffer->mp_buffer,0);

         context->Map(mp_IndexBuffer->mp_buffer,0,D3D11_MAP_READ,0,&data);
         memcpy(indexRawData,data.pData,m_IndexBufferSize);
         context->Unmap(mp_IndexBuffer->mp_buffer,0);

         DWORD* dwI = (DWORD*)indexRawData;

         int sz = (m_VertexStride/sizeof(float));//size of vertex element

         //algorithm must be here.
         std::vector<Vector3d> vertices;
         int i = 0;
         for(int j = 0; j < m_VertexCount; j++)
         {
             float x1 = (((float*)vertexRawData)[0+i]);
             float y1 = (((float*)vertexRawData)[1+i]);
             float z1 = (((float*)vertexRawData)[2+i]);
             Vector3d lv = Vector3d(x1,y1,z1);

             //my useless attempts
             if(j+m_LOD+1<m_RawVerts.size())
             {
                 float v1 = VECTORHELPER::Distance(m_RawVerts[dwI[j]],m_RawVerts[dwI[j+m_LOD]]);
                 float v2 = VECTORHELPER::Distance(m_RawVerts[dwI[j]],m_RawVerts[dwI[j+m_LOD+1]]);

                 if(v1>v2)
                     lv = m_RawVerts[dwI[j+1]];
                 else
                     if(v2<v1)
                         lv = m_RawVerts[dwI[j+2]];
             }

             (((float*)vertexRawData)[0+i]) = lv.x;
             (((float*)vertexRawData)[1+i]) = lv.y;
             (((float*)vertexRawData)[2+i]) = lv.z;

             i+=sz;//pass others vertex format values without change
         }

         for(int j = 0; j < m_IndexCount; j++)
         {
             //indices ?
         }

         //set vertexes to device
         UpdateVertexes(vertexRawData,mp_VertexBuffer->getSize());

         delete[] vertexRawData;
         delete[] indexRawData;
     }

```

# Answer
> 1 votes
Hull shaders perform tessellation on the GPU, which makes handling variable level-of-detail pretty straightforward.

See this MSDN article for more information.

---
Tags: c++, level-of-detail
---


# Question
Title: Collision Detection problems in Voxel Engine (XNA)
I am creating a minecraft like terrain engine in XNA and have had some collision problems for quite some time. I have checked and changed my code based on other peoples collision code and I still have the same problem. It always seems to be off by about a block. for instance, if I walk across a bridge which is one block high I fall through it. Also, if you walk towards a "row" of blocks like this:

You are able to stand "inside" the left most one, and you collide with nothing in the right most side (where there is no block and is not visible on this image).

Here is all my collision code:

```
    private void Move(GameTime gameTime, Vector3 direction)
    {
        float speed = playermovespeed * (float)gameTime.ElapsedGameTime.TotalSeconds;

        Matrix rotationMatrix = Matrix.CreateRotationY(player.Camera.LeftRightRotation);
        Vector3 rotatedVector = Vector3.Transform(direction, rotationMatrix);

        rotatedVector.Normalize();

        Vector3 testVector = rotatedVector;
        testVector.Normalize();

        Vector3 movePosition = player.position + testVector * speed;
        Vector3 midBodyPoint = movePosition + new Vector3(0, -0.7f, 0);
        Vector3 headPosition = movePosition + new Vector3(0, 0.1f, 0);

        if (!world.GetBlock(movePosition).IsSolid &&
            !world.GetBlock(midBodyPoint).IsSolid &&
            !world.GetBlock(headPosition).IsSolid)
        {
            player.position += rotatedVector * speed;
        }

        //player.position += rotatedVector * speed;
    }

```

...

```
    public void UpdatePosition(GameTime gameTime)
    {
        player.velocity.Y += playergravity * (float)gameTime.ElapsedGameTime.TotalSeconds;

        Vector3 footPosition = player.Position + new Vector3(0f, -1.5f, 0f);
        Vector3 headPosition = player.Position + new Vector3(0f, 0.1f, 0f);

        // If the block below the player is solid the Y velocity should be zero
        if (world.GetBlock(footPosition).IsSolid ||
            world.GetBlock(headPosition).IsSolid)
        {
            player.velocity.Y = 0;
        }

        UpdateJump(gameTime);
        UpdateCounter(gameTime);
        ProcessInput(gameTime);

        player.Position = player.Position + player.velocity * (float)gameTime.ElapsedGameTime.TotalSeconds;
        velocity = Vector3.Zero;
    }

```

and the one and only function in the camera class:

```
    protected void CalculateView()
    {
        Matrix rotationMatrix = Matrix.CreateRotationX(upDownRotation) * Matrix.CreateRotationY(leftRightRotation);
        lookVector = Vector3.Transform(Vector3.Forward, rotationMatrix);

        cameraFinalTarget = Position + lookVector;

        Vector3 cameraRotatedUpVector = Vector3.Transform(Vector3.Up, rotationMatrix);
        viewMatrix = Matrix.CreateLookAt(Position, cameraFinalTarget, cameraRotatedUpVector);
    }

```

which is called when the rotation variables are changed:

```
    public float LeftRightRotation
    {
        get { return leftRightRotation; }
        set
        {
            leftRightRotation = value;
            CalculateView();
        }
    }

    public float UpDownRotation
    {
        get { return upDownRotation; }
        set
        {
            upDownRotation = value;
            CalculateView();
        }
    }

```

World class:

```
    public Block GetBlock(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            Vector3i regionalPosition = GetRegionalPosition(x, y, z);
            Vector3i region = GetRegionPosition(x, y, z);

            return regions[region.X, region.Y, region.Z].Blocks[regionalPosition.X, regionalPosition.Y, regionalPosition.Z];
        }

        return new Block(BlockType.none);
    }

    public Vector3i GetRegionPosition(int x, int y, int z)
    {
        int regionx = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
        int regiony = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
        int regionz = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;

        return new Vector3i(regionx, regiony, regionz);
    }

    public Vector3i GetRegionalPosition(int x, int y, int z)
    {
        int regionx = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
        int X = x % Variables.REGION_SIZE_X;

        int regiony = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
        int Y = y % Variables.REGION_SIZE_Y;

        int regionz = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;
        int Z = z % Variables.REGION_SIZE_Z;

        return new Vector3i(X, Y, Z);
    }

```

Any ideas how to fix this problem?

**EDIT 1:**

Graphic of the problem:

**EDIT 2**

GetBlock, Vector3 version:

```
    public Block GetBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        Block block = GetBlock(x, y, z);

        return block;
    }

```

Now, the thing is I tested the theroy that the Z is always "off by one" and by ceiling the value it actually works as intended. Altough it still could be greatly more accurate (when you go down holes you can see through the sides, and I doubt it will work with negitive positions). I also does not feel clean Flooring the X and Y values and just Ceiling the Z. I am surely not doing something correctly still.

# Answer
A few things I noticed you can check:

* In `Move()` you subtract 1.4 to get the head position while in `UpdatePosition()` you add 0.1. Double-check that this calculation is correct as I would have assumed you should be adding the same value in the same direction.
* Is the collision issue the same in each direction (+/-, X/Y/Z) or does it matter which direction you're going? For example, if the collision issue was different while travelling in +X vs -X I would guess there's a mismatch between where the collision detection thinks a voxel is and where the game actually displays it. In other words, does you voxel at (0,0) occupy (0,0)-(1,1) or (-0.5, -0.5)-(0.5, 0.5) or (-1,-1)-(0,0). If you make a mistake here you will be off by as much as one block which sounds close to the issue you describe.
* Drawing your collision box may be helpful in debugging as can be stepping through and observing what the variables are and what you think they should be.
* I assume `player.position` vs `player.Position` is just a typo (though I've been bitten by dynamic case-sensitive languages before).

Edit: The way you describe it sounds exactly like an "off-by-one" type error. You also use `GetBlock(Vector3)` but posted code for `GetBlock(int, int, int)`. If you are relying on automatic conversion from float to int it may round/truncate in ways you aren't expecting.

Edit 2: I would follow MindWorX's comment about specifically using floor()/ceil() when you convert from float to int. This may or may not be the issue you are having. You really need to add some diagnostic output to the display (player position, camera position, collision boxes, selected block info, etc...) and trace through everything to make sure it does what it should. At this stage it is dangerous to think "it can't be X". Don't assume anything and make sure you actually read what the code does and not what you think it does.
> 2 votes

# Answer
Casting to int round positive numbers down, and negative numbers up.

So, do a check: `if(x < 0)
 x -= 1;`

I had exactly the same problem with my voxel engine.
> 1 votes

---
Tags: xna, c#, collision-detection, minecraft-modding, voxels
---


title: How do I make game server for UDK game?

text:
# Question
Title: How do I make game server for UDK game?
I'm new in UDK and I'm starting to develop online multiplayer games. There is a one problem, I couldn't find any tutorials about how to make a game server using udk. I suppose, that it uses unreal script. But that's about all I know about it. So I'd really like for some help.

# Answer
To launch a dedicated global server, run:

```
UDK.exe server yourmap

```

For a listen server, launch the game with your desired map as normal and append `?listen`:

```
UDK.exe yourmap?listen

```

For a lan server, append `?lan` to the map name (e.g. `UDK.exe server yourmap?lan`)

To connect to the server, you can start the game with your IP address instead of a map:

```
UDK.exe yourIPaddress

```

or from an already-running game, open the console and type either `open yourIPaddress` or `connect yourIPaddress`.
> 5 votes

---
Tags: udk, scripting, unreal
---


# Question
Title: Working with lots of cubes. Improving performance?
**Edit:** To sum the question up, I have a voxel based world (Minecraft style (Thanks Communist Duck)) which is suffering from poor performance. I am not positive on the source but would like any possible advice on how to get rid of it.

I am working on a project where a world consists of a large quantity of cubes (I would give you a number, but it is user defined worlds). My test one is around (48 x 32 x 48) blocks.

Basically these blocks don't do anything in themselves. They just sit there.

They start being used when it comes to player interaction.

I need to check what cubes the users mouse interacts with (mouse over, clicking, etc.), and for collision detecting as the player moves.

Now I had a massive amount of lag at first, looping through every block.

I have managed to decrease that lag, by looping through all the blocks, and finding which blocks are within a particular range of the character, and then only looping through those blocks for the collision detection, etc.

However, I am still going at a depressing 2fps.

Does anyone have any other ideas on how I could decrease this lag?

Btw, I am using XNA (C#) and yes, it is 3d.

# Answer
Sounds like you're looking to learn about Trees!

And I'm being serious, if you're currently looping over an array of all your cubes, then you really should look into various spatial data structures. For this case, the best way to re-imagine your cube world is as a tree.

Before we go into the reasons as to why, lets think about our problem. We're looking for a solution where, for as little cost as possible, we can retrieve a list of nearby cubes that the player may be colliding with. This list should be as small, yet precise as possible.

Now to determine this zone, we need to map our player's coordinate space to the coordinate space of the cube map; that is, we need to map the floating point position of the player to a discrete index of the multi-dimensional array of cubes (example notation might be `world[31][31][31]`, i.e. exact middle for a 64\*64\*64 multidimensional array).

We could simply calculate the surrounding blocks using this same discrete indexing, perhaps sampling only the nearby cubes, but this still requires constant recalculation, and doesn't allow for any objects that aren't discrete in placement (i.e. may not map to the cube map).

The ideal situation is a set of buckets which contain our sets of cubes for particular sections of our cube map, divided equally so instead of recalculating the surrounding area, we simply move in and out of these *zones*. For any non-trivial calculation, holding our data like this could eliminate iterating all the cubes, and only these individual sets that are nearby.

The question is: How do we implement this?

For the 64\*64\*64 world, imagine it broken down to 8\*8\*8 *zones*. This means that in your world, you will have 8 zones per axis (X, Y, Z). Each of these *zones* will contain 8 cubes, easily retrievable by this new simplified index.

If you needed to perform an operation on a set of nearby cubes, instead of iterating every cube in your world, you could simply iterate over these *zones*, breaking down the maximum number of iterations from the original 64\*64\*64 (262144) to just 520 (8\*8\*8 + 8).

Now zoom out from this world of zones, and place the *zones* into larger *super-zones*; wherein each *super-zone* contains 2\*2\*2 regular *zones*. As your world currently contains 512 (8\*8\*8) *zones*, we can break the 8\*8\*8 *zones* into 64 (4\*4\*4) *super-zones* by dividing 8 *zones* by 2 *zones* per *super-zone*. Applying the same logic from above, this would break the maximum iterations from 512 to 8 to find the *super-zone*; and then a maximum of 64 to find the proceeding *zone* (total max 72)! You can see how this is saving you a lot of iterations already (262144 : 72).

I'm sure you can see now how useful trees are. Each *zone* is a branch on the tree, with each *super-zone* as a preceding branch. You are simply traversing the tree to find what you need; using smaller sets of data to minimize overall cost.

The diagram below should help you visualize the concept. (image from Wikipedia:Octrees):

**Disclaimer:**

In an ideal set up as above, where your voxel-world is already laid out in a fixed size multi-dimensional array, you could simply query the player position, then index surrounding blocks with an O(1) cost! (See Olhovskys explanation) But this becomes more difficult when you start considering that your world is rarely fixed size in a voxel game; and you may need your data-structure to be capable of loading entire *super-zones* from HDD to memory. Unlike a fixed size multi-dimensional array, trees readily allow this without too much time spent on combinatory algorithms.
> 19 votes

# Answer
I agree with Daniels answer, in that iterating through large amounts of boxes is the most likely cause, and that by using spacial partitioning you could speed the game up a lot - but the problem *could* also be elsewhere, and you could be wasting your time.

**In order to increase the speed of your game significantly you need to profile your code.** Identify where the bottleneck is, this will allow you to make the biggest improvements.

There are lots of ways to profile your code, you could roll your own performance analysis class (which could make use of the Stopwatch class (MSDN)), or you could use PIX to get a general idea of how busy the CPU/GPU is.

You can also put PIX event markers in your code, which will show up as colored regions in PIX's readouts. There isn't an official C# interface to these functions, but this thread shows how you can make a C# interface yourself.
> 13 votes

# Answer
If your player is large relative to the size of the cubes, then you probably want an octree or other spatial partitioning structure, as other's have suggested.

However, if your player is small relative to the size of the cubes, then probably the fastest way to detect collision with the cubes is to do a simple linear search of the area around the player.

Since your player is smaller than 1 cube, then you only need to test for collision against the neighboring 27 cubes, at most.

This assumes that you store the cubes in an array that you can index into, with one slot in the array for every cube.

As other's have pointed out, you need to profile your code to see what is actually slowing you down.

If I had to guess though, I'd say that you are probably doing a draw call for every cube, which would be your bottleneck by far. To fix that, you should look into geometry instancing.
> 6 votes

# Answer
One more suggestion to speed things up: Your blocks are approximately fixed--that means that there's no way a player can collide with most of them. Add a boolean to blocks indicating whether they are exposed or not. (This can be recalculated by looking at their neighbors.) A block which isn't exposed need not be checked for collisions.

It's obvious Minecraft does something akin to this--I hit a non-loaded chunk once that gave me a view into the world--I could see right through the solid ground, all that showed up was the open spaces (the far side of them was an exposed surface and therefore rendered.)
> 1 votes

# Answer
I had that issue with my voxel engine.

Solution: (Much simpler than octrees) Instead of looping through all the blocks, just use an equation to determine the position of the block in the blocks array.

`BlockIndex = (x * WorldWidth * WorldHeight) + (z * WorldHeight) + y;`

Then if you want to see if a block exists:

`Blocks[BlockIndex].Type > -1;`

Or however you determine if the block exists.
> -1 votes

---
Tags: xna, 3d, frame-rate, voxels
---


# Question
Title: How to get the blocks seen by the player?
I'm writing a Minecraft-like game using Ogre engine and I have a problem. I must optimize my game, because when I try draw 10000 blocks, I have 2 FPS... So, I got the idea that blocks display of the plane and to hide the invisible blocks. But I have a problem - how do I know which blocks at a time are visible to the player?

And - if you know of other optimization methods for such a game, write what and how to use them in Ogre.

# Answer
Well, Ogre already implements frustum culling (which basically does not draw anything that couldn't be seen from the camera) but I think your problem is a different one.

You should not really be displaying 10000 blocks, what is commonly done (or at least, in the few Ogre3d based minecraft like clones I've seen (of which I am making one too), and in the original ) is creating a mesh (of some NxNxN region of chunks) which has the outer faces of the cubes shown. That is, when you put 2 cubes side by side, the 2 faces touching can't be seen and therefore don't need to be drawn.

These faces should also be drawn in something like this: http://www.ogre3d.org/tikiwiki/tiki-index.php?page=DynamicGrowingBuffers as modern video cards prefer one mesh of 100000 polygons versus 1000 meshes of 100 polygons.
> 17 votes

# Answer
There are a couple of aspects to this problem. Firstly, how are you drawing your 10000 blocks? Are you actually drawing them as 10000 seperate object? If so this is almost certainly your bottle neck, not the lack of occlusion culling. You should group these blocks into a smaller number of meshes (perhaps a few thousand per mesh) in order to reduce draw calls.

As for your actual question, there are three types of occlusion culling which spring to mind.

1) Blocks outside the view frustum. This means blocks which are behind you or two the side. Ogre already removes these via view frustum culling.

2) Blocks which are 'underground' or completely surrounded by other blocks so they can never be seen from any angle. You can identify these by looking at the siz neighbouring blocks. If they are all solid your block is hidden. The GPU should never even hear about these blocks - they should be skipped when you are building the mesh which represent your surface.

3) Blocks which are on the surface and can be seen from some positions in the level, but which are currently hidden by a hill (or something). This is the trickiest case which I haven't addressed myself, but there's a good chance that hardware occlusion queries can be used for this case.

It's a shameless plug, but I have a fairly mature library which several people are using to develop Minecraft clones, including some using Ogre. You define the contents of the volume and it generates the surface mesh which you can then render. Here is the home page:

http://www.thermite3d.org/

And here is a video of someone else's project which is using it:

http://www.youtube.com/watch?v=Jju6WRPEK7o
> 10 votes

# Answer
You can use backface culling to cull vertices and their associated pixels that don't face the player. Depth buffering should take care of the rest. 10k blocks really isn't a lot, my 5770 can render 100k verts at 1500fps. I think that you're doing something else pretty badly wrong.
> 4 votes

# Answer
If you have 10000 separate objects, the bottleneck is probably primitive count, not vertex, polygon, or fill. Bake your objects into smaller number of higher polygon objects for speed.

Minecraft has a concept of blocks of cubes, but I can't find the reference at the moment.

Here's also my experiments on drawing tons of cubes with various techniques. Doesn't include baking (yet).
> 1 votes

# Answer
What I do, is after I create my array of blocks, but before I create the vertices, I run a sub called UpdateBlockVisiblility.

The sub simply checks the neighbours to the block, and updates the Blocks facevisible boolean accordingly.

```
#define BLOCKFACE_NORTH 0

#define BLOCKFACE_SOUTH 1

etc etc etc

if(IsBlockAt(NorthOfBlock))
  Blocks[Whatever].facevisible[BLOCKFACE_NORTH] = false;

```

Then I only create the vertices for the face if it is visible! Simple :)
> 0 votes

---
Tags: ogre, minecraft-modding
---


# Question
Title: Best algorithm for recursive adjacent tiles?
In my game I have a set of tiles placed in a 2D array marked by their Xs and Zs (\[1,1\],\[1,2\], etc).

Now, I want a sort of "Paint Bucket" mechanism: Selecting a tile will destroy all adjacent tiles until a condition stops it, let's say, if it hits an object with `hasFlag`.

Here's what I have so far, I'm sure it's pretty bad, it also freezes everything sometimes:

```
void destroyAdjacentTiles(int x, int z) {
    int GridSize = Cubes.GetLength(0);
    int minX = x == 0 ? x : x-1;
    int maxX = x == GridSize - 1 ? x : x+1;
    int minZ = z == 0 ? z : z-1;
    int maxZ = z == GridSize - 1 ? z : z+1;

    Debug.Log(string.Format("Cube: {0}, {1}; X {2}-{3}; Z {4}-{5}", x, z, minX, maxX, minZ, maxZ));

    for (int curX = minX; curX <= maxX; curX++) {
        for (int curZ = minZ; curZ <= maxZ; curZ++) {
            if (Cubes[curX, curZ] != Cubes[x, z]) {
                Debug.Log(string.Format("        Checking: {0}, {1}", curX, curZ));
                if (Cubes[curX,curZ] && Cubes[curX,curZ].GetComponent<CubeBehavior>().hasFlag) {
                    Destroy(Cubes[curX,curZ]);
                    destroyAdjacentTiles(curX, curZ);
                }
            }
        }
    }
}

```

**Update:** I'm trying the recursive version of the Flood-fill algorithm, but I'm having trouble. In order to check the west adjacent tile, I use x-1, for the east, x+1 etc. Problem is, as soon as x = 0, it will infinitely loop between 0 and 1. I also have to check that that tile exists, so I'm using `if`s to figure it out in order to not get an `IndexOutOfRangeException` (I tried using try/catch, but it's pretty much the same result, I figured this would be simpler). Here's my code right now (yes, I'm reproducing mineSweeper):

```
bool destroyAdjacentTiles(int x, int z) {
    int GridSize = Cubes.GetLength(0);
    int minX = x == 0 ? x : x-1;
    int maxX = x == GridSize - 1 ? x : x+1;
    int minZ = z == 0 ? z : z-1;
    int maxZ = z == GridSize - 1 ? z : z+1;

    Debug.Log(string.Format("Cube: {0}, {1}; X {2}-{3}; Z {4}-{5}", x, z, minX, maxX, minZ, maxZ));

    CubeBehavior thisCube = Cubes[x, z].GetComponent<CubeBehavior>();

    if (thisCube.isMine) { Destroy(thisCube); Cubes[x,z] = null; return false; } // TO DO: Make this = game over
            // BELOW: Always, no matter what, causes the object to destroy, dunno why. So I removed it for the time being.
    //if (thisCube.surroundingMines >= 1) Destroy(thisCube); return true;

            // if the function doesn't return by now, means it's a to-be-destroyed cube, so destroy it
    //Destroy(thisCube.gameObject);
    //Cubes[x,z] = null;

            //
    if (x > 0) {
        if (Cubes[x-1,z].gameObject) destroyAdjacentTiles(x-1, z);
        if (x < GridSize - 1)
            if (Cubes[x+1,z].gameObject) destroyAdjacentTiles(x+1, z);
    }
    if (z > 0) {
        if (Cubes[x,z-1].gameObject) destroyAdjacentTiles(x, z-1);
        if (z < GridSize - 1)
            if (Cubes[x,z+1].gameObject) destroyAdjacentTiles(x, z+1);
    }

    return true;
}

```

# Answer
There's no point in reinventing the wheel. There is an existing algorithm that does what you want. It's called the Flood Fill algorithm. The basic steps from Wikipedia:

```
Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
     Perform Flood-fill (one step to the east of node, target-color, replacement-color).
     Perform Flood-fill (one step to the north of node, target-color, replacement-color).
     Perform Flood-fill (one step to the south of node, target-color, replacement-color).
  4. Return.

```

Of course instead of changing colors, you'll be destroying tiles, but the process is the same. Looks like you're trying to do an 8 way flood fill, the algorithm only changes slightly with you checking all 8 orthogonal and diagonal positions instead of the 4 orthogonal like in the pseudo code shown above.

Also keep in mind, when creating recursive algorithms it's very important to have a clearly defined base condition. The reason you program "freezes up" every once in a while is because you're running into an infinite loop. You should be checking that the tile you're about to perform on is neither destroyed nor has the flag.

Depending on the size of your grid (if it were very, very large), you can use a non-recursive algorithm. I don't think you'd run into an issue with stack overflows, so it's not critical. Another method that's more complex, but pretty interesting is the fixed memory method. It would be interesting to implement, but again, I don't imagine you'd run into memory issues.

**EDIT**

I have simplified your code. You may have been confusing things by trying to change the x and z values depending on where they were. Just globally define the minimum and maximum for your grid, then check against those. You only need to check once if a position is out of bounds. Your base conditions are:

* Square is out of bounds (the first check of x and z compared to their bounds)
* Square is exploded already (I guess you set tiles to null to be exploded)
* Square is not a mine (the tile doesn't have the isMine flag set to true)

If any of those conditions are reached, you're at the bottom of that recursion, so you stop the recursion down that path.

```
bool destroyAdjacentTiles(int x, int z) {

    if(x<minXBound || x > maxXBound || z < minZBound || z > maxZBound) {
        return false;
    }

    CubeBehavior thisCube = Cubes[x, z].GetComponent<CubeBehavior>();

    if(thisCube == null || !thisCube.isMine)
        return false;

    Destroy(thisCube);
    Cubes[x,z] = null;

    destroyAdjacentTiles(x-1, z);
    destroyAdjacentTiles(x+1, z);
    destroyAdjacentTiles(x, z-1);
    destroyAdjacentTiles(x, z+1);

    return true;
}

```
> 12 votes

# Answer
You want to try to avoid recursive algorithms in cases like this. It's better to use stack/queue based methods as they are faster and won't cause stack overflows for large areas. This page details and has source examples for both recursive and stack based flood fill algorithms as well as execution speed comparisons: http://lodev.org/cgtutor/floodfill.html
> 5 votes

---
Tags: c#, algorithm, unity
---


# Question
Title: How can I resolve collisions at different speeds, depending on the direction?
I have, for all intents and purposes, a Triangle class that objects in my scene can collide with (In actuality, the right side of a parallelogram).

My collision detection and resolution code works fine for the purposes of preventing a gameobject from entering into the space of the Triangle, instead directing the movement along the edge.

The trouble is, the maximum speed along the x and y axis is not equivalent in my game, and moving along the Y axis (up or down) should take twice as long as an equivalent distance along the X axis (left or right).

Unfortunately, these speeds apply to the collision resolution too, and movement along the blue path above progresses twice as fast. What can I do in my collision resolution to make sure that the speedlimit for Y axis movement is obeyed in the latter case?

Collision Resolution for this case below (vecInput and velocity are the position and velocity vectors of the game object):

```
// y = mx+c
// solve for y. M = 2, x = input's x coord, c = rightYIntercept
lowY =  2*vecInput.x + parag.rightYIntercept ;

...

else
{
    // y = mx+c
    // vecInput.y = 2(x) + RightYIntercept
    // (vecInput.y - RightYIntercept) / 2 = x;

    //if velocity.Y (positive) greater than velocity.X (negative)
    //pushing from bottom, so push right.
    if(velocity.y > -1*velocity.x)
    {
            //change the input vector's x position to match the
            //y position on the shape's edge. Formula for line: Y = MX+C
            // M is 2, C is rightYIntercept, y is the input y, solve for X.
        vecInput = new Vector2((vecInput.y - parag.rightYIntercept)/2, vecInput.y);
        Debug.Log("adjusted rightwards");
    }
    else
    {
        vecInput = new Vector2( vecInput.x, lowY);
            Debug.Log("adjusted downwards");
    }
}

```

# Answer
assuming `vecInput` is your final result for this problem I suggest you add 4 lines of code at the end of your code. checking if you the results exceed in either x axis value or y axis value.

```
if (math.Abs(vecInput.x) > MaxXSpeed)
    vecInput *= maxXSpeed / vecInput.x;
if (math.Abs(vecInput.y) > MaxYSpeed)
    vecInput *= maxYSpeed / vecInput.y;

```
> 2 votes

---
Tags: xna, c#, collision-detection, collision-resolution
---


# Question
Title: Space Invaders-type game: Keeping the enemies aligned with each other as they turn around?
OK, so here's the lowdown of the problem I'm trying to solve.

I'm developing a game in PyGame that's a cross between Space Invaders and Columns. I'm trying to make the motion of the enemies similar to that of the aliens in Space Invaders; that is, they're all clustered in a grid, and if even one hits the side of the screen, the entire formation moves down and turns around. However, the motion of these aliens is continuous (as continuous as a monitor can be, anyway), not on a discrete grid like in the original.

The enemies are instances of an Enemy class, and in turn they're held by a 2D array in a enemysquadron module (which, if you don't use Python, is in this case essentially a singleton due to the way Python modules work).

Inside the Enemy class I have a class-scope velocity vector that is reversed every time an Enemy object touches the edge of the screen. This won't do, though, because as time goes on the enemies just become disorganized and jumbled (i.e. not in a grid as planned). I haven't implemented the Enemies going downward yet, so let's not worry about that right now.

Any tips?

# Answer
> 4 votes
Basically, the question is, why are your enemies getting disorganized and jumbled? You only describe one factor controlling their movement, so unless there's more relevant information you're not telling us, the only scenario I can think of where they'd lose alignment is one where you're flipping the vector right there in the middle of the movement code as soon as one of them hits the edge. This would cause loss of alignment because you're partway through processing your movement when you change vectors, so some of them have moved with the old vector and some will now move with the new vector.

If that's the case, try this instead: when an enemy hits the edge, turn on a flag, and at the end of your movement cycle, check if the flag is on; if it is, flip the vector and turn off the flag.

---
Tags: ai, sprites, movement, grid
---