title: Physics system imploding under force

text:
# Question
Title: Physics system imploding under force
I have a basic physics body system (incomplete/very basic; as collision resolution and detection are not implemented, just mass, position, velocity, acceleration, force and impulse).

I implemented position, velocity, acceleration, force and impulse as described in `Game Coding Complete 3rd. Ed. by Mike "Mr. Mike" McShaffrty et al.` specifically `Chapter 15: Collision and Simple Physics by Jeff Lake` which is: (paraphrasing from text and code, US copyright law and all that.)

> Gravity is a Force.
>
> Application of a Force vector adds it to a std::list of forces.
>
> Application of an Impulse vector adds it to a std::list of impulses.
>
> Upon calling Update on the physics body:
>
> 1. Add all forces and all impulses together (F).
> 2. Clear the impulses list.
> 3. Set acceleration to (F / mass)
> 4. Set velocity to (velocity + (acceleration * deltaTime))
> 5. Set position to (position + (velocity * deltaTime))

(See code below)

The problem I'm having is when gravity is applied as a force the list grows linearly...forever. Eventually it overcomes any attempt to directly set the position of an object to the point that A) The object is always affected by gravity no matter if or how fast the position is changed (clamping to the screen is a good example) B) The list grows so large that the system implodes and chugs. C) If, before the system implodes, the object is stopped at a specific position, the acceleration due to gravity continually increases making it ever harder to change the acceleration/velocity/position of the object (specifically applying an impulse or force upwards).

If I change the noted line in GravityHandler to `elem->ApplyImpulse(deltaG);` it works satisfactorily but is this correct or am I missing something?

My implementation according to his example:

RigidBody and its state:

```
void State::ApplyImpulse(const Vector2D& impulse) {
    _impulse.push_back(impulse);
}

void State::ApplyForce(const Vector2D& force) {
    _forces.push_back(force);
}

//RigidBody is a `friend` of State.
void RigidBody::ApplyForce(const Vector2D& force) {
    _curState.ApplyForce(force);
}
void RigidBody::ApplyImpulse(const Vector2D& impulse) {
    _curState.ApplyImpulse(impulse);
}

```

GravityHandler:

```
void GravityHandler::Update(double deltaTime) {

    class UpdateObject {
    public:
        UpdateObject(double deltaTime) : _deltaTime(deltaTime) { };
        void operator() (RigidBody* elem) {
            double mass = elem->GetMass();
            if(Math::IsEqual(mass, 0.0)) return;

            double gxm = elem->GetXGravityModifier();
            double gym = elem->GetYGravityModifier();

            Vector2D deltaG(_GRAVITY_VALUE.GetX() * gxm * mass * _deltaTime, _GRAVITY_VALUE.GetY() * gym * mass * _deltaTime);
            elem->ApplyForce(deltaG); //The problem seems to be here.
        };
    private:
        double _deltaTime;
    };

    _accumulator += deltaTime;
    if(_accumulator < (1.0 / 60.0)) return;
    _accumulator -= deltaTime;
    if(!_isActive) return;
    std::for_each(_subscribers->begin(), _subscribers->end(), UpdateObject(deltaTime));
}

```

RigidBody:

```
void RigidBody::Update(double deltaTime) {

    double mass = GetMass();
    //If static body, do nothing.
    if(Math::IsEqual(mass, 0.0)) return;

    Vector2D F;
    F += std::accumulate(_curState._forces.begin(), _curState._forces.end(), Vector2D());
    F += std::accumulate(_curState._impulses.begin(), _curState._impulses.end(), Vector2D());
    _curState._impulses.clear();
    SetAcceleration(F / mass);
    SetVelocity(GetVelocity() + GetAcceleration() * deltaTime);
    SetPosition(GetPosition() + GetVelocity() * deltaTime);

}

```

# Answer
In the line you noted, `elem->ApplyForce(deltaG); //The problem seems to be here.` you are continuously adding a Force, every time the object updates. Lets use a static value to see what I mean

1. You add a force of 9.8. The list contains 1 Force for a total force of 9.8.
2. You add a force of 9.8. The list contains 2 Forces for a total force of 19.6.
3. You add a force of 9.8. The list contains 3 Forces for a total force of 29.4
4. Etcetera, etcetera, etcetera.

You can see how your total force increases each update, by update 120, only two seconds into the simulation, you have a downward force of `120 * gravity`. To fix this, you only add the Force once, like when the object enters the world and is subjected to gravity, and remove it once it leaves the world.
> 3 votes

# Answer
A simpler solution is to just add all force vectors together every frame. As all acting forces will have one vector as the force resultant it makes sense to add them all together every frame (don't forget to reset this vector once you have handled it in your integration step).

If your force generators all will stay the same you only have to do this once but chances are you will have a lot of force generators changing every frame such as springs changing lengths, player controller rocket thrusters turning on and off etc.

So have one vector called \_forceResultant and adjust your applyForce method as follows:

```
    void State::ApplyForce(const Vector2D& force) {
    _forceResultant += force;
    }

```
> 1 votes

---
Tags: c++, physics
---


# Question
Title: How to tune steering behaviours to pick the best target around obstacles?
I want to chase an enemy, but there are obstacles in the world. Imagine there's an obstacle stopping me reaching the closest enemy, but in another, unobstructed, direction is another enemy but at a further distance:

```
***************
E ** P        E
***************

* - obstacle
E - enemy
P - player

```

My enemy-chasing behaviour returns a vector pointing towards the left-most enemy, and my obstacle avoidance behaviour returns a vector pointing to the right, away from the obstacles. At some point they balance out and I have stalemate!

This could all be avoided if there was an elegant way of choosing the other enemy at the beginning.

Is this a common problem in steering behaviours? How is it regularly solved? I may have a lot of enemies, so pathfinding to each first may be inefficient.

# Answer
> 2 votes
As Byte56 mentioned in the comments use path finding. If you only want to get the closest enemy then use breadth first search, preferably with limited depth, and use the first encountered enemy as your target. Also, as Byte already mentioned, you will need waypoints for your steering, you can't just start steering towards the enemy position as the path to get there might not be in the direction towards that entity in case there are obstacles in the way.

# Answer
> 1 votes
Instead of path finding, you can also prioritize your steering components. Instead of weighting them 50:50 make it 40:60 with prioritizing obstacle avoidance. That will let you end up in wall some time however.

You can also alter your steering output. If obstacle avoidance has nothing to avoid, use the other vectors(weighted or not), but if obstacle avoidance has something it needs to avoid, only use that. This however might give you jittery movement when you alternate between collision avoidance and not.

A good solution I have found is to compute the other vectors first and then use them to influence the obstacle avoidance. The avoidance vector sets the lower bounds (right and left) needed to not collide and with the vector from the rest of the input, you can choose which vector is better(smallest angle). Add hysteresis, so you don't change from one direction to the other and you will get mostly smooth movement, without path finding. It is however still difficult getting the avoidance bounds right for concave objects.

---
Tags: ai, steering-behaviors
---


# Question
Title: What is a good university for computer science and game development?
I am starting my computer science degree at a local community college in programming using C++. However, I will be transferring to a 4-year university. Does anyone have any insight on university programs?

I know Cal State Fullerton has a degree with a minor in Game Development. however, is that as important as getting a degree from a really great school? If I could shoot for something like Cal Poly would that be better? Or even Stanford or SF State being so close to so many gaming companies up there in the Bay area?

# Answer
> 12 votes
A lot of universities who don't have formal "game development" programs are still great places to get a general Computer Science education, and many of them might have clubs or classes that will help you in that direction. I noticed you mentioned Cal Poly, and since I'm a Masters student at Poly with a focus in computer graphics maybe I can provide some insight.

Cal Poly doesn't have a formal "game development" degree or program (although we're in the process of building a game dev track into the CS curriculum), but there are tons of resources here for people interested in games. Dr. Wood teaches a series of graphics courses which are great, including a 2 quarter real-time graphics course in which you build a game from scratch.

We've also got a fairly new Game Development Club which has seen an explosion of members in just the two years we've been around. We hosted one of the California Global Game Jam sites and had over 50 people attend and make games. A big part of our job as a club (I'm an officer) has been building relationships with industry to help our members find jobs making games when they graduate. (Without making this sound *too* much like a commercial, that's something that Poly is really good at.)

None of this stuff is something you would find in a general brochure, or probably anywhere on Poly's main website.

Basically my point is that there may be a **lot** of game dev stuff happening at different places that might not be publicized. With a general CS degree it opens the doors to work in game dev, but also allows you work in other areas as well if you end up getting burned out in the game industry (which is actually fairly common). Your best bet is to get in touch with the actual CS departments at universities you're interested and ask them directly if there's any game dev stuff going on.

And if you have any questions about Poly specifically, I'm happy to answer them. :)

# Answer
> 30 votes
Just do straight computer science, ignore any gamedev specific stuff. You need to be a good programmer first, before you can make games. No employer will turn their noses up at you because you haven't done a course on XNA development or whatever.

Having said that, do as much programming and game dev in your spare time as possible. Go to X48 and take part in a Global Games Jam. Make a portfolio website listing your games and source code. These will help your CV get noticed, but once they take a closer look your straight CS degree will get you the interview.

# Answer
> 6 votes
Don't worry about game-centric schools. Go to the best school for computers you can get into/afford. Work on games and take game classes.

**Public Schools:**

The University of Waterloo in Ontario, Canada is very good, and Google / RIM / Microsoft recruit directly from there.

University of California, Berkeley (San Fran), invented much of the internet.

Larry Page and Bill Joy both went to the University of Michigan (near Detroit)

**Private Schools:**

Carnegie Mellon (Pittsburgh) is very good for AI and robotics computing.

MIT (Boston) has a tremendous reputation, as does Caltech (Near LA), though Caltech is more about space exploration

Let's not forget that Gates and Zuckerberg both went to, and dropped out of Harvard (Boston).

And Brin and Page started their PhDs at Stanford (San Fran).

For actual game programming, I would take whatever courses the school you chose offers, and read as many books as you can.

# Answer
> 3 votes
As a guy with a CS degree who got a job in the industry straight out of school with no prior game dev experience, I feel as though I may have some good advice.

Go to a school with a reputable CS program. If they offer a course on graphics, take it. If they offer a course in game programming, take it. All of these will help prepare you. Your degree will teach you how to think about software development and other problems and see different (and discover optimal) ways of solving them. These skills are an absolute must-have for any programmer.

Having said that, you will then need to spend your spare time working on developing games. Most of what I learned about the skills needed for game programming (C++, OpenGL / DirectX, Geometric Methods and Data Structures, etc.) I learned on my own, as CS degrees tend to focus on more general software engineering practices.

With the combination of my school-taught knowledge and that I gained on my own, I was able to communicate my knowledge well in the interview and then aced the practical test. I didn't know everything I needed to know (not by a long shot), but I was able to prove that I was a motivated self-learner, and that mattered.

# Answer
> 2 votes
I recommend at least checking out the DigiPen Institute of Technology.

It is a very small school that focuses on games, but unlike the various dicey "game design" schools advertised all over the Web it offers an actual full four-year computer science degree. The faculty includes world-class professors as well as game industry veterans. The curriculum is largely the same math, computer science, and general ed as you'd get at any other well known university but it also includes a mandatory set of courses on low-level graphics programming, quite advanced C++, physics, and so on.

DigiPen also requires students to actually work on real game projects (written from scratch, not with a premade engine or toolkit) in small teams, which is immensely useful (note all the other replies that stress the importance of actually writing games independent of the CS curriculum; DigiPen just enforces that). The only language taught is C++; there's no Java or Scheme or other nonsense that game companies don't use or care about.

DigiPen also has an excellent reputation and strong relationships with many major companies in the games industry. It is located in the Redmond/Seattle, which is one of the major centers for game companies. The close proximity to many exceptional games companies (not to mention Microsoft) means you can get your internships and work experience out of the way during your summers, making it much easier to get hired in as a "real" developer by the time you're done with your four years of schooling (compare to most universities where you get the same education but no practical experience, so you're stuck fighting for entry-level jobs when you graduate).

There are some serious caveats, of course. The school is very expensive. The course load is very intense and will eat you alive if you're not really dedicated to being a real game programmer. The school is not regionally accredited (but has national accreditation) and so going on to graduate school may be difficult (it has no negative impact on getting hired in the industry, at all). The campus is very small and you'll miss out on a lot of the "college experience" you'd get at a big university.

Note that DigiPen also has four-year programs in both art and game design, but I cannot personally attest to the quality of those.

# Answer
> 0 votes
I have recently finished the coursework for an MS in Computing with emphasis in videogame programming from the University of Utah. They also offer an undergrad emphasis that I don't know a lot about.

I found that having a BS in vanilla Computer Science from another school helped me have better understanding of pure programming concepts than learning game-specific programming may have been. Focusing those skills toward programming for a masters degree helped me add to that knowledge in pretty valuable ways but, for me, a foundation of non-focused programming has been integral for my success in the master's courses.

# Answer
> 0 votes
A lot of people will approach a trade school for game related degrees. I'm prepared to be laughed out of the room for saying this, but Chico State is a really good school for game development. We have a strong engineering department with a great computer science program, and we also have a video game development program. We practice game design and programming simultaneously, so if you feel like jumping in and building games you can.

Like everyone also here, I am a little worried that my post makes me sound like a recruitment officer. I have really enjoyed my large scale development courses, and they have helped keep me engaged. We have a student run studio that puts games out every 1 to 1 1/2 years, that holds more than 50 students at a time. This is one of the only schools that follows studio models, and isn't a trade school.

If you a a programmer who is interested in being a part of the game design , I would consider this school. If you a programmer who strictly wants to program, you might be better off with an education that is more computer science oriented. But what do I know, I'm just a level designer?

---
Tags: education
---


# Question
Title: Android 2D game, shooting and getting animation to stop
I'm developing a game as a learning-process, and since everything I do is new to me, I have alot of problems, usually I can fix it myself but right now I'm stuck and need help.

Link to a recording of my game: http://www.youtube.com/watch?v=nejaMtug09A&feature=youtube\_gdata

As you can see in this video I have my joystick working and my animation 80% complete.

!!EDIT : SOLVED!! So first question: How do I get my animation to stop? I have a variable called "dragging" that is set to "true" whenever I move, so it shouldnt be that hard,

when dragging == false (stop animation and display the correct image of my sprite standing still, in the correct direction);

!!EDIT : NOT SOLVED!! My second question: As you can see in the video I get a bullet to spawn when I press the circle in the bottom right corner, I can get it to spawn on my sprite ( or at the end of my sprites gun) if I want, but what I cant do is setting a speed for my bullet, and also I want to be able to have multiple bullets on the screen at once, not just one, with some delay between bullets ofc.

If you can answer anyone of these questions you've made my life alot easier :) Posting code here:

the code for my sprite-animation:

```
    private static final int BMP_ROWS = 4;
private static final int BMP_COLUMNS = 3;
private int currentFrame = 0;

    public int getAnimationRow() {
    direction = (int) Math.round(controls.getAngle()) % happy.getBmpRows();
    return DIRECTION_TO_ANIMATION_MAP[direction];}

    private void update() {

    currentFrame = ++currentFrame % BMP_COLUMNS;
}

public void draw(Canvas canvas, int x, int y) {
    update();
    int srcX = currentFrame * width;
    int srcY = panel.getAnimationRow() * height;
    Rect src = new Rect(srcX, srcY, srcX + width, srcY + height);
    Rect dst = new Rect(x, y, x + width, y + height);
    canvas.drawBitmap(bitmap, src, dst, null);
}

```

the code for my controls:

```
    if (event.getAction() == MotionEvent.ACTION_DOWN && (int) event.getX() > 0 && (int) event.getX() < 100
            && (int) event.getY() > 300 && (int) event.getY() < 400) {
        dragging = true;

    } else if (event.getAction() == MotionEvent.ACTION_UP) {
        dragging = false;
        shooting=false;
    }

    if (dragging) {
        // get the pos
        touchingPoint.x = (int) event.getX();
        touchingPoint.y = (int) event.getY();

        double angle = Math.atan2(touchingPoint.y - inity,
                touchingPoint.x - initx) / (Math.PI / 180);
        spriteAngle = Math.atan2(touchingPoint.y - inity,
                touchingPoint.x - initx) / (Math.PI / 2) + 2;

        pointerPosition.y += Math.sin(angle * (Math.PI / 180))
                * (touchingPoint.y / 70);
        pointerPosition.x += Math.cos(angle * (Math.PI / 180))
                * (touchingPoint.y / 70);

    if (event.getAction() == MotionEvent.ACTION_DOWN && (int) event.getX() > 650 && (int) event.getX() < 750
            && (int) event.getY() > 300 && (int) event.getY() < 400){
        shooting = true;
    }

```

Lastly, my render-method:

```
    public void render(Canvas canvas) {
    canvas.drawColor(Color.BLUE);
    canvas.drawBitmap(joystick.get_joystickBg(), controls.initx - 50, controls.inity - 50, null);
    happy.draw(canvas, controls.pointerPosition.x, controls.pointerPosition.y);
    canvas.drawBitmap(joystick.get_joystick(), controls.touchingPoint.x - 26, controls.touchingPoint.y - 26, null);
    canvas.drawBitmap(joystick.get_trigger(), controls.triggerX - 50, controls.triggerY - 50, null);

    if(controls.getShooting() == true){
        canvas.drawBitmap(bullet.getStartBullet(), 200, 200, null);
    }

    displayFps(canvas, avgFps);

```

If you've read all this then you are a very patient person, I posted alot of code but I think you will need it all to be able to help, if you need more let me know and Ill post ASAP :)

Thank you!

Will post the code of the fixed problem down here for any1 that might have the same issue in the future:

Code that fixed my animation-question:

```
    public void render(Canvas canvas) {
    canvas.drawColor(Color.BLUE);
    canvas.drawBitmap(joystick.get_joystickBg(), controls.initx - 50, controls.inity - 50, null);
    if(controls.getDragging() == true){
        happy.update();
    }else{
        happy.setFrame(1);
    }
    happy.draw(canvas, controls.pointerPosition.x, controls.pointerPosition.y);

```

# Answer
> 2 votes
In your `draw()` method, you're calling `update()`, which is incrementing the current animation frame, `currentFrame = ++currentFrame % BMP_COLUMNS;` You are calling this every frame, regardless if the player is actually moving or not.

You essentially just want to call that `update()` method only when the player is `dragging` or providing moving input. Moving the `update()` call inside the `if (dragging)` block, and resetting the current animation frame to the first frame in the sprite sheet if not dragging should give you your desired results. Very simple pseduocode would look like this.

```
if (dragging)
   update();
else
   currentFrame = firstFrame;

```

As for your bullet question, you essentially want to move the bullet sprite in similar fashion as you do your current player sprite, but instead of relying on user input to provide velocity and direction, you travel the bullet at a steady velocity and given direction each frame. Very *very* simple pseduocode of firing a bullet when user inputs would look something like this.

```
if (shotTimer >= minShotTimer) {
    bulletSprite.location += location + velocity;
    shotTimer = 0.0f;
}

```

Both `location` and `velocity` are 2D Vectors. Obviously, that's seriously simplified, but hopefully, it'll nudge you in the right direction.

---
Tags: 2d, android, animation, sprites, game-mechanics
---


# Question
Title: Collision detection between many objects
I'm working in a 2d environment and have hundreds of objects, brute force collision checking would be out of the question, but would my method below work?

For example, lets say I have a `std::vector<GameObj*> objectsVector` to hold all objects and a `std::multimap<Point2D, GameObj*> objectsMap` (basically a map which takes a 2d point representing a GameObject's coordinate as a key and the object itself as a value) to get any object associated with a point. If I want to do collision checking for an object, I could use a function that looks like this:

```
void World::checkForCollisions()
{
    for (int i = 0; i < objectsVector; ++i) {
        GameObj* currObj = objectsVector[i];
        for (
                int x = (int)currObj->getX() - (int)currObject->getWidth();
                x < currObj->getX() + 2*currObj->getWidth();
                x++
            )
        {
            for (
                    int y = (int)currObj->getY() - (int)currObject->getHeight();
                    y < currObj->getY() + 2*currObj->getHeight();
                    y++
                )
            {
                pair<multimap<Point2D, GameObj*>::iterator,multimap<Point2D, GameObj*>> range = objectsMap.equal_range(Point2D(x, y));
                for (
                        multimap<Point2D, GameObj*>::iterator it=range.first;
                        it!=range.second;
                        ++it
                    )
                {
                    if (checkCollision(currObj, it->second))
                        currObj->handleCollision(it->second);
                }
            }
        }
    }
}

```

Is this even *remotely* efficient? Because it doesn't seem to be. It basically just scrolls through the vector and checks to see if it collides with nearby objects. Problem is, I have to use 2 containers AND when things move, I have to pretty much reinitialize the entire map, because the keys would be invalid! Is there any way to improve this collision-checking function, or should I scrap the whole thing altogether and use spatial hashes or a quad-tree?

# Answer
> 1 votes
It seems that you didn't try the 'brute' force approach yet. Try checking for all objects in a O(n²) algorithm, it may solve your issue.

These techniques that you are mentioning, like a Sweep and Prune, in their worst case, will check all the objects too. Before going to this complex trees way, I suggest you to use a simple grid to se if you get any improvement (be sure to do the most simple way first for comparisons).

In this algorithm you are proposing, you're making hops of one unit from x to x+width (same thing for y), then checking if there's any object on all this points. You're checking more then necessary, but I'm not sure if i quite understood your idea. You should make a better use of your objects geometry to make few calls to checkCollision(currObj, it-\>second).

Real Time Collision Detection as mentioned by raigan, can help you a lot on this task.

# Answer
> 1 votes
I wanted to post this as a comment to Vandell's answer, but I don't have the privilege to comment yet I guess.

As he said, you probably didn't try the brute force approach yet. I'm using it in my game, and on a Intel i5-750 @2.67GHz, it is running smoothly with no problem with around 300-400 entities. (Might be able to support even more, didn't test it.)

If your target platform is a mobile device, then I don't know how well it will run however.

This is my code:

```
public void detectCollision(float tmpx, float tmpy) {

Rectangle tmpRect = this.getRectangle(tmpx, tmpy);

if (tmpRect == null) //If the entity doesn't have a bound box
    return;

for (int i = 0; i < MainGameState.objectList.size(); i++) {
    if (!this.equals(MainGameState.objectList.get(i)))
      if (tmpRect.intersects(MainGameState.objectList.get(i).getRectangle())) {
            MainGameState.objectList.get(i).doCollision(this);
            return;
       }

}

if ((tmpx > 0 && tmpx < 3600) && (tmpy > 0 && tmpy < 3000)) { //Within map bounds
     this.setX(tmpx);
     this.setY(tmpy);
     jumpSpeed += CConstants.GRAVITY * weight;
     return;
}

```

I *think* your problem, which is the same one I had before I fixed it, is that you are recalculating the bound box every iteration? I'm too rusty with pointers and it's kinda late here.

Try you're using an AABB bound box (if you aren't), in which case you just need to create it one time at the game initialization, and then just update its center coordinates to that of the bound object, like this for example:

```
public void init(GameContainer gc) throws SlickException {
    rectangle = new Rectangle(this.getX(), this.getY(), currentAnimation.getCurrentFrame().getWidth(), currentAnimation.getCurrentFrame().getHeight()); //Assumes that all the animation frames will be the same size.

```

}

```
public Rectangle getRectangle() {

    rectangle.setX(x);
    rectangle.setY(y);
    return rectangle;
}

public Rectangle getRectangle(float tmpx, float tmpy) {

   rectangle.setX(tmpx);
   rectangle.setY(tmpy);

return rectangle;
}

```

My game is still in the pretty early stages in development, as so I can't guarantee the scalability of the code when more things are being done, but as I said I'm getting 60fps with Vsync, and around 200-300fps without it.

Feel free to look at my source code in github. But be warned, it's horrible code. :P

# Answer
> 0 votes
Christer Ericson's "Real-Time Collision Detection" is probably the best game-programming-related book I've found; read the chapter on grids/spatial hashing and you'll have several options and ideas for how to approach broad-phase collision detection.

# Answer
> 0 votes
Something I have wondered about but I have not tested. It's O(n) but an expensive constant:

Maintain a separate copy of the screen. When you move an object on the real screen it moves on the other screen also. It's just the other screen draws only collidable objects and draws them in color # (object number). If you try to draw on anything but a black pixel you collided with object # (pixel color).

---
Tags: c++, collision-detection, optimization
---


# Question
Title: there is a BLOB standard to store images in memory?
I would like to abstract all the images in memory, to do so i would like to have just 1 format of reference without talking about the usual file formats for the filesystem like JPG, TGA, and so on.

I hear about BLOB in RGBA format but i don't get what is this format, RGBA for me is just a way to abstract color reproduction not a way to serialize image in memory. This also can be the case where one word "RGBA" is used for defining a more general concept and approach.

The possible explanation for me is that a BLOB in RGBA is just a matrix of pixels, but how is formed and what is the order that i'm supposed to use for reading them ? Technology like OpenGL can directly manage this BLOB ?

# Answer
> 2 votes
Normally you use a library e.g. SOIL to load and upload your textures. It takes care of decoding incoming image formats for you, and is used by real games (as was its predecessor, sb\_image).

SOIL supports DDS compressed textures as well as classic JPG and PNG formats etc.

# Answer
> 4 votes
I can't help you with OpenGL, as I have never used it, but blobs of image data are usually just byte arrays, that are created row-wise from top to bottom. If you lock textures or images, the returned array might be bigger as expected because rows are usually stored aligned which is called the image stride. Those are effectively wasted bytes at the end of each row due to memory alignment.

What format will be returned depends on how you create/load the texture/file. If you create a texture with `GL_RGBA?` each pixel will be represented by 4 bytes `RGBARGBARGBA...`. The byte array in that case is at least `width * height * 4`. It might be bigger due to image stride.

I have found this question on SO that describes how to load such an array directly in to an OpenGL texture.

A general rule for row-wise reading/writing pixels looks like this

```
for(int y = 0; y < imageHeight; ++y)
for(int x = 0; x < imageWidth; ++x){
  //channels is usually 4 for RGBA, 3 for RGB, 1 for grayscale or palette, though other formats exist.
  int arrayPos = (y * imageStride + x) * imageChannels;

  byte red = imageData[arrayPos + 0];
  byte green = imageData[arrayPos + 1];
  byte blue = imageData[arrayPos + 2];
  byte alpha = imageData[arrayPos + 3];

  //if you get back an integer(int32 = 4 bytes) array instead of a byte array
  int arrayPos = y * imageStride + x;

  byte red = (imageData[arrayPos] >> 24) & 0xFF;
  byte green = (imageData[arrayPos] >> 16) & 0xFF;
  byte blue = (imageData[arrayPos] >> 8) & 0xFF;
  byte alpha = (imageData[arrayPos] >> 0) & 0xFF;
}

```

There are quite a bit of image formats for use, that might make sense depending on the data you want to store, or if you need to save memory. R5G6B5 for example is RGB with only 16 bits. R5G5B5A1 with a transparency bit for RGB textures that need only binary transparency.

That said, it might make sense to store all images in an OpenGL format that includes mipmaps so they don't have to be generated at runtime.

---
Tags: c++, opengl, textures, image
---


title: OpenGL ES high-quality 2D scaling

text:
# Question
Title: OpenGL ES high-quality 2D scaling
Let's say I'm making a 2D game and I want to implement a zoom in/out feature. Normally this is as simple as modifying the projection matrix to get more or less of the world to show. However, this results in quite blurry resizing, and I suspect the culprit is the GL\_LINEAR parameter you supply to glTexParameteri as explained here.

I've done my fair share of video resizing and I know much better algorithms exist such as bicubic filtering, lanczos, spline, etc, however the only one OpenGL offers is (tri?)linear. What would be the best way of improving 2d scaling? I suppose this would involve shaders but I'm not familiar with the approach. Any reference to working code would be a nice plus.

# Answer
To sample a texture in a fragment shader you use `texture2D(tex,pt)`. So to gather the adjacent pixels in order to do your own interpolation you need to compute what the points to sample are. To do this, you need to know the size of the texture; then the width and height of an individual texel is `1.0/width` and `1.0/height` respectively.

```
vec2 texSz = vec2(1.0,1.0)/textureSize;
for(int i=-2; i<=2; i++) {
    for(int j=-2; j<=2; j++) {
        vec3 texel = texture2D(texSampler,texCoord+vec2(texSz.x*j,texSz.y*i));
         ....

```

This CodeProject article is excellent, with GLSL for a variety of interpolation functions.
> 3 votes

# Answer
It really depends on what you're doing.

If you're zooming out an image, it may be beneficial to invest time into learning about shaders so you can implement a better filtering algorithm in a pixel shader.

However, if you're making a game with dynamic elements (objects flying around, particle effects going off) then it's really more of an art question.

A common approach is mipmapping, where you make multiple versions of textures, each scaled down to half the previous level. This helps tremendously with oversampling.

The other approach is dynamic level-of-detail. For example, in our 3D space RTS, we had three versions of every spaceship:

* High detail - Model used for close-ups. This had a limit of about 2500 triangles.
* Low detail - Model used when zoomed out. The limit here was about 500 triangles.
* Icon - When the model is so small that it's only the size of a few pixels, it gets replaced by an iconic representation.

For your game, you could do the same. It really depends on the type of game and how important zooming is to the gameplay what the best solution is for your situation.
> 1 votes

---
Tags: opengl, 2d, shaders
---


title: User input in game loop

text:
# Question
Title: User input in game loop
I am building a simple multi-player fly-around-a-3D-world game in Javascript/webGL/websocket (Chrome, Firefox mostly).

How should I handle and process user input?

My preliminary design (untested) is to first just track which keys are down in the event handler:

```
var keys = [];

document.onkeydown = document.onkeyup = function(evt) {
   keys[evt.charCode] = evt.type == "keydown";
   keys[CTRL] = evt.ctrlKey;
   keys[SHIFT] = evt.shiftKey;
   websock.send(JSON({time: (new Date()).gettime(),
      down: evt.type == "keydown",
      key: evt.charCode,
      shift: evt.shiftKey, ctrl: evt.ctrlKey }));
};

```

and then, in my `requestAnimationFrame` callback, compute how many time-slices (say 20 per second?) have elapsed since the last render callback, and then compute that many time-steps using the booleans in the `keys` array to determine if to apply a left bank, right bank, up down and accelerate and so that time-step for each player.

How effective / responsive is this? Is there a better way? And is there a neater way to deal with latency than just backdating changes for other user's ships?

# Answer
**Edit:** there's a bug in your code.

At the new Date().getTime() part (you can write it like that, no need for extra parenthesis).

1. Not all your clients are going to have the same time.
2. One could easily change the date values being sent to your server.

So, that value isn't very reliable (in case you plan to use it for something important), you better calculate it on the server side.

Never, ever trust the client with anything other than their current state of input.

I strongly suggest that your movement has nothing to do with rendering.

I usually have one function called `logic`, and that function basically calls all the objects' `update` methods, and gives them the time passed. The player class, then, has an input listener, and in its function it checks which keys pressed, and depending on the time, reacts accordingly.

```
if (player.input.right)
{
    velocity.x = const;
}

//Do some physics.

position.x += velocity.x * dt

```

I call this logic function ~30 times per second, so it's responsive enough. As for the netcode, it's best to record input and only send that to the server. The server only sends back the difference in the game state since the last message (see: Backbone.js diff).
> 1 votes

---
Tags: javascript, game-loop, events
---


# Question
Title: How do I keep a triangle strip between geometry shader invocations?
I'm using a small geometry shader to build a "ribbon" from a set of points. For each point, I create 4 vertices that represent a section of the ribbon:

```
[maxvertexcount(4)]
void    GS( point GS_Input v[1],
            inout TriangleStream<PS_Input> ptStream )
{
    float4  vertices[4];
    vertices[0] = float4(v[0].pos.x - 2, 0, v[0].pos.z + 2, 1);
    vertices[1] = float4(v[0].pos.x + 2, 0, v[0].pos.z + 2, 1);
    vertices[2] = float4(v[0].pos.x - 2, 0, v[0].pos.z - 2, 1);
    vertices[3] = float4(v[0].pos.x + 2, 0, v[0].pos.z - 2, 1);

    PS_Input ov = (PS_Input)0;
    for (int i = 0; i < MVC; i++)
    {
        ov.posW = mul(vertices[i], g_world);
        ov.posH = mul(vertices[i], g_wvp);
        ov.normalW = mul(float4(v[0].normal, 0), g_world);
        ov.color = v[0].color;
        ptStream.Append(ov);
    }
}

```

As mentioned on the MSDN: "A geometry shader generating triangle strips will start a new strip on every invocation", and because of this, I don't get a ribbon, all I get is a set of quads, just like as if I was doing some particle billboarding. Is there any way to circumvent that in order to keep the same strip from on invocation to the next ?

# Answer
> 3 votes
No, there is not. Geometry shaders, like most shader stages, are separate from one another.

What you seem to want, since you specified DX11, is tessellation. That allows you to take a "patch" and subdivide it. A "patch" could be a string of points of some arbitrary length, which you would "subdivide" into multiple subdivisions.

# Answer
> 2 votes
It is possible in some sense. If you use a primitive type with adjacency information (D3D\_PRIMITIVE\_TOPOLOGY\_LINESTRIP\_ADJ) you can construct quads that fit together nicely, even if they aren't technically in the same strip. I've used this technique with some success myself.

Please excuse the awesome ASCII art; '.' are points, and '|' and '\\' are edges.

In your shader, the GS invocations go something like this (1 per point):

```
   [.] .  .  .  .
    . [.] .  .  .
    .  . [.] .  .
    .  .  . [.] .
    .  .  .  . [.]
giving:
    |  |  |  |  |

```

Instead, you'd want to use a linestrip with adjacency (1 invocation per 4 points, overlapping). The same diagram would then be:

```
[.  .  .  .] .  .  .
 . [.  .  .  .] .  .
 .  .[ .  .  .  .] .
 .  .  . [.  .  .  .]
giving:
   |\||\||\||\||\|

```

So, you construct a quad (for a 2D strip) with each invocation using the average of the first two and last two points \[EDIT: I'm overcomplicating things: no averaging is actually required, just draw a quad between any two adjacent points on each invocation\]. The code might look something like this (I'm not entirely sure what your original code is trying to do):

```
[maxvertexcount(8)]
void    GS( lineadj GS_Input v[4],
            inout TriangleStream<PS_Input> ptStream )
{
    float4 middlePos = 0.5*(v[0].pos+v[1].pos);
    float4  vertices[4];

    vertices[0] = float4(middlePos.x - 2, 0, middlePos.z + 2, 1);
    vertices[1] = float4(middlePos.x + 2, 0, middlePos.z + 2, 1);
    vertices[2] = float4(middlePos.x - 2, 0, middlePos.z - 2, 1);
    vertices[3] = float4(middlePos.x + 2, 0, middlePos.z - 2, 1);
    //construct and emit first 4 PS_input's
    middlePos = 0.5*(v[1].pos+v[2].pos);
    vertices[0] = float4(middlePos.x - 2, 0, middlePos.z + 2, 1);
    vertices[1] = float4(middlePos.x + 2, 0, middlePos.z + 2, 1);
    vertices[2] = float4(middlePos.x - 2, 0, middlePos.z - 2, 1);
    vertices[3] = float4(middlePos.x + 2, 0, middlePos.z - 2, 1);
    //construct and emit another 4 PS_input's
}

```

Also, you'll probably want to duplicate the first and triplicate the last points in your list for this to behave similarly to the original point list.

---
Tags: directx, hlsl, directx11, geometry-shader
---


title: Strongly Typed Skills

text:
# Question
Title: Strongly Typed Skills
I am working on a skill system for use in a game project I'm chipping away at. The project is entirely in C# so I'm using .NET to its advantage.

In my preliminary implementation of a Skill Category -\> Skill types system I'm using subclasses of ISkill and SkillCategory (base class with some virtuals) and using System.Type based reflection to generate a map of these at runtime (on demand).

The great thing about this implementation is that it entirely decouples specific skill types (such as `Engineering / LaserWeapons` from the SkillLibrary (the container for the generated skill mapping).

The goal is to remove the need to explicitly add each skill at some point as they are automatically detected by the library throughout the entire `AppDomain`.

Only game logic which relies on these skills use concrete types.

**ISkill**

```
public interface ISkill
{
  string GetName();
  string GetDescription();
  int GetSkillLevels();
  float GetMinutesOfTrainingForLevel(int level);
}

[SkillCategory(typeof(EngineeringSkills))]
[PrerequisiteSkill(typeof(ElectronicsSkill))]
public class LaserWeaponSkill : ISkill
{
  public string GetName()
  {
    return "Laser Weapons";
  }

  public string GetDescription()
  {
    return "Allows you to maintain and improve laser based weapons on your ship.";
  }
}

```

**Usage example:**

```
[RequiredUpgradeSkill(typeof(Skills.Engineering.LaserWeapons))]
public class LaserTurretWeapon : IShipWeapon
{
}

```

There's two slight ugliness's with being very `System.Type` based, though. One is that my `Player._skillLevels` dictionary can't serialize as `Dictionary<Type, int>` because Type isn't supported by `DataContractSerializer` (what I'm using at the moment).

So what I'm doing in `SetSkillLevel<TSkill>(int level)` and `GetSkillLevel<TSkill>()` is translating `typeof(TSkill)` to and from a string using `typeof(TSkill).FullName` (i.e. "Game.Skills.Engineering.LaserWeapons").

And the other is potential performance problems, which is something I should profile.

This all works, of course, but it feels like the weak point in an otherwise enum-less, strongly typed skill definition system.

I don't really want to use enums and a "list" of Skill structures, or move it to an external data definition file because then that requires more maintenance of created and deleted enum values and such.

Do you think this is worth it, or do topics such as performance of Type based operations and other considerations make it worth rethinking?

# Answer
> 8 votes
This is not a good use of object orientation or typing. You've fallen into the trap that inheritance and polymorphism and metaprogramming and language features are there to solve every problem.

You should reconsider using a data driven approach. Your current design is partially data driven as you explain it, but the data is embedded in code. You are spending a lot of time thinking about and implementing fancy, complex, indecipherable to anyone but you, and inflexible solutions to what is a very, very simple problem.

What happens when a designer wants to try tweaking a skill cost or attribute for a few battles? He has to edit code and recompile the entire game?

What happens when it comes time to translate the game to other languages?

What happens when the skill system core mechanics change after more extensive play testing and feedback?

What happens when you want to modify a weapon's skill requirements based on in-game state, such as a special ability that lets a player use a certain weapon without the right skill?

Classes should be used for logic. Interfaces should be used to bind together logic. Classes should not be used to encode data, express relationships between data, describe "real world" objects, or function as a data format consumed by the compiler.

Look into storing your skill names, attributes, and so on in data files. Store your items in data files. Store the relationships between skills and items in data files. Build tools for inspecting and modding that data. Improve your iteration time on game ideas and actual fun instead of improving on low-level tech tricks that have no impact on the game itself.

# Answer
> 2 votes
I agree with Sean Middleditch, that your approach should be changed for many reasons. Here's a couple of ideas you should consider:

1. An interface can have properties.
2. I would use an abstract base class for the skills instead of an interface. This way you don't have to implement most of the basic functionalities multiple times.

```
public abstract class SkillInfo
{
  public int ID { get; }
  public string Name{ get; }
  public string Description{ get; }

  public float GetMinutesOfTrainingForLevel(int level)
  {
    //You can write your implementation here,
    // that works with every (or almost every) subclasses of Skill.
  }
}

```
3. Only create instances of a subclass of SkillInfo by serializing data stored in an external file (XML is the obvious choice, if you're using XNA's content serializer). You can also write a generic class to manage serialization of the data.

For example, in the WeaponSkillInfo : SkillInfo class, you'd have this method:

```
  public const int SKILL_ID= 5;
  private const string DEFAULT_FILEPATH= "weaponskill.xml";
  public static WeaponSkillInfo GetSkillInfo()
  {
    WeaponSkillInfo skill = ContentDataManager<SkillInfo>.GetById(SKILL_ID, filepath);
    return (WeaponSkillInfo)skill;
  }

```

and in the ContentDataManager.cs:

```
  public class ContentDataManager<T> where T : SkillInfo
  {
    public static T GetById(int id, string contentPath)
    {
      //Logic to deserialize data from the XML
    }
  }

```

4 . When you have for example 3 players with 5 skills each, you shouldn't store the name and description of those skills for all the players. Something I would do instead is:

```
  public class PlayerSkill
  {
    public int SkillInfoId;
    private SkillInfo _skillInfo;
    public int Level{ get; }
    public int ProgressToNextLevel{ get; }
  }

```

The PlayerSkill's constructor should create a reference to the relevant SkillInfo instance based on the SkillInfoId property. This way, if you serialize the player (when you save the game), only the SkillInfoId will be stored. Consider the scenario, when you want to create a patch for the game, that changes the Weapon skill's description. This way, you only have to upgrade it in one place (weaponskill.xml). And as Sean said, you (or your artists) won't have to recompile the game exe.

5 . The basic principle you should follow: **The source code mustn't have any "content".** Content here refers to descriptions of skills, skill names, NPC names, experience level values, sprites, 3d models, animation durations etc. **Keep the logic and the structure in the code, and the content in external resources.**

---
Tags: c#, .net
---


# Question
Title: How can I prevent pixel artifacts on programatically generated textures?
In the game I'm developing, rooms can be of various sizes, which means I need to vary the size of the floor texture appropriately.

The way I've solved this problem is to generate a Texture2D programatically, and set each pixel to be transparent (or not) as appropriate appropriately.

I get something like this:

Where, if you look at the top left, you'll clearly see the pixel artifacts from the floor texture against the dark blue background.

When I run into this with static textures, the fix is simple. Set the Texture's wrapmode to clamp instead of repeat. But when I try to do that programatically... (and change nothing else!) I get this:

I'm not quite sure what's happening, or why setting the wrapMode changes the results so markedly. Anyway I can avoid the pixel artifacts? I suppose it's possible to add an extra border around the generated texture (so that *all* edges can be transparent), but that doesn't seem a particularly clean solution.

Code is here:

```
void DebugFloorTextureMerge()
    {

        //sizeVector makes up the rectangle circumscribing the room's parallelagram
        Vector2 sizeVector = new Vector2(roomBounds.topRight.x - roomBounds.bottomLeft.x, roomBounds.topLeft.y - roomBounds.bottomLeft.y);

        //get the texture of the filled sprite
        Texture2D patternTexture = (Texture2D) floorTexture.image;

        //make a new texture of the size of the room.
        Texture2D fillTexture = new Texture2D( (int) sizeVector.x, (int) sizeVector.y, TextureFormat.ARGB32, false);

            //COMMENTING THIS LINE OUT MAKES THE TEXTURE WORK WITH ARTIFACTS
        fillTexture.wrapMode = TextureWrapMode.Clamp;
            //LEAVING IT IN MAKES THE FOLLOWING CODE WORTHLESS

        int patternX = 0, patternY = 0;

        Vector2 pointVector;
        Color transparent = new Color(0,0,0,0);

        for(int x = 0; x < sizeVector.x; x++)
        {
            for(int y = 0; y < sizeVector.y; y++)
            {
                pointVector = new Vector2(x,y);
                if(roomBounds.Contains(pointVector))
                {
                    //get the next pixel
                    fillTexture.SetPixel(x,y, patternTexture.GetPixel(patternX, patternY));
                }
                else
                {
                //pixel was not in the room, so set it to transparent.
                    fillTexture.SetPixel(x,y, transparent);
                    //resultx = x; resulty = y;

                }

                //increment the pattern counter and reset if necessary.

                //if you only increment this when Contains is true, you'll warp the texture
                patternY++;
                if(patternY >= floorTexture.fillSize.y) patternY = 0;
            }

            //increment the pattern counter and reset if necessary.
            //also reset y, so the pattern will line up properly.
            patternY = 0;
            patternX++;
            if(patternX >= floorTexture.fillSize.x) patternX = 0;
        }

        //set the PixelChanges.
        fillTexture.Apply();
    }

```

# Answer
Instead of altering the texture and erasing pixels that should not be shown, I suggest you build your geometry in a way that it fits your floor.

Our geometry should look like this (red paint-over):

To do that, we could dynamically create the required mesh in Unity (using the Mesh class). So let's assume that `0,0` of our coordinate-system lies at point `3` and our coordinates from `0` to `3` are `(2,4), (6,4), (4,0), (0,0)` then we would write something like this in Unity:

```
// vertices on XY plane, ignore Z
Vector3[] vertices = new Vector3[4]{
    new Vector3(2.0f, 4.0f, 0.0f),
    new Vector3(6.0f, 4.0f, 0.0f),
    new Vector3(4.0f, 0.0f, 0.0f),
    new Vector3(0.0f, 0.0f, 0.0f)
};

// set the indices that form triangles (ccw)
int[] triangles = new int[6]{
    0, 2, 1, // top right triangle
    0, 3, 2 // bottom left triangle
};

```

Now we have the vertices. Next step would be to define the UV coordinates. A UV coordinate specifies the texture-position a vertex maps to. UV coordinates are normalized from `0..1`. To have our texture fill the generated mesh in it's entirety, our UV coordinates would look like this:

```
0 => (0, 0) # Vertex 0 maps to top left of texture
1 => (1, 0) # Vertex 1 maps to top right
2 => (1, 1) # Vertex 2 maps to bottom right
3 => (0, 1) # Vertex 3 maps to bottom left

```

If you want to tile your texture, you can do that by specifying UV coordinates bigger than 1. So if the texture should tile 3 times across width and height, the coordinates would look like this (this time in C#):

```
Vector2[] uvs = new Vector2[4]{
    new Vector2(0.0f, 0.0f),
    new Vector2(3.0f, 0.0f),
    new Vector2(3.0f, 3.0f),
    new Vector2(0.0f, 3.0f)
};

```

Putting it all together to get an actual mesh:

```
Mesh mesh = new Mesh();
mesh.vertices = vertices;
mesh.uv = uvs;
mesh.triangles = triangles;

// get the mesh filter component and attach the mesh to it
MeshFilter filter = GetComponent<MeshFilter>();
filter.mesh = mesh;

```

Of course you'll also need a `MeshRenderer` Component, otherwise your mesh won't render.

Here's a slightly more advanced script that allows you to specify size, origin and skew values in Unity and the Mesh gets generated on the fly (script is just a quick and dirty example to illustrate the concept). Here's how it looks in Unity with a MeshRenderer that has a checker texture applied (the texture repeats with the `Size` parameter).
> 6 votes

# Answer
If I get it right, you only need to map some pattern texture to arbitrary shape room floor. This should not be the problem of generating texture, but of getting the right texture coordinates for each pixel. In this case you're drawing simple geometry (drawn as triangles). If your texture should not be somehow distorted (perspective, etc.) you can map triangle vector coordinates directly (or with some linear mapping) to texture coordinates with texture wrapping set to REPEAT or MIRROR (as you desire). What kind of graphical API (DirectX/OpenGL/other) are you using?
> 2 votes

---
Tags: unity
---


# Question
Title: Pixel Shader, YUV-RGB Conversion failing
I am tasked with playing back a video hthat comes in in a YUV format as an overlay in a larger game. I am not a specialist in Direct3d, so I am struggling. I managed to get a shader working and am rendering 3 textures (Y, V, U). Sadly I am totally unable to get anything like a decent image. Documentation is also failing me. I am currently loading the different data planes (Y,V,U) in three different textures:

```
m_Textures = new Texture[3];
// Y Plane
m_Textures[0] = new Texture(m_Device, w, h, 1, Usage.None, Format.L8, Pool.Managed);
// V Plane
m_Textures[1] = new Texture(m_Device, w2, h2, 1, Usage.None, Format.L8, Pool.Managed);
// U Plane
m_Textures[2] = new Texture(m_Device, w2, h2, 1, Usage.None, Format.L8, Pool.Managed);

```

When I am rendering them as R, G and B respectively with the following code:

```
float4 Pixel(float2 texCoord: TEXCOORD0) : COLOR0
{
    float y = tex2D (ytexture, texCoord);
    float v = tex2D (vtexture, texCoord);
    float u = tex2D (utexture, texCoord);

    //R = Y + 1.140 (V -128)
    //G = Y - 0.395 (U-128) - 0.581 (V-128)
    //B = Y + 2.028 (U-128)

    float r = y; //y + 1.140 * v;
    float g = v; //y - 0.395 * u - 0.581 * v;
    float b = u; //y + 2.028 * u;

    float4 result;
    result.a = 255;
    result.r = r; //clamp (r, 0, 255);
    result.g = g; //clamp (g, 0, 255);
    result.b = b; //clamp (b, 0, 255);

    return result;
}

```

Then the resulting image is - quite funny. I can see the image, but colors are totally distorted, as it should be.

The formula I should apply shows up in the comment of the pixel shader, but when I do it, the resulting image is pretty brutally magenta only. This gets me to the question - when I read out an L8 texture into a float, with

```
float y = tex2D (ytexture, texCoord);

```

what is the range of values? The "origin" values are 1 byte, 0 to 255, and the forum I have assumes this. Naturally I am totally off when the values returned are somehow normalized. My Clamp operation at the end also will fail if for example colors in a pixel shader are normalized 0 to 1. Anyone an idea how that works? Please point me also to documentation - I have not found anything in this regard.

# Answer
`tex2D(sampler,pos)` return values between 0 and 1.

Multiply by 255.0 to get your expected range.
> 2 votes

---
Tags: hlsl, fragment-shader, sharpdx
---


# Question
Title: Ball bouncing at a certain angle and efficiency computations
I would like to make a pong game with a small twist (for now).

1. Every time the ball bounces off one of the paddles i want it to be under a certain angle (**between a min and a max**). I simply can't wrap my head around how to actually do it (i have some thoughts and such but i simply cannot implement them properly - i feel i'm overcomplicating things). Here's an image with a small explanation .
2. One other problem would be that the conditions for bouncing have to be different for every edge. For example, in the picture, on the two small horizontal edges i do not want a perfectly vertical bounce when in the middle of the edge but rather a constant angle (pi/4 maybe) in either direction depending on the collision point (before the middle of the edge, or after). All of my collisions are done with the Separating Axes Theorem (and seem to work fine).
3. I'm looking for something efficient because i want to add a lot of things later on (maybe polygons with many edges and such). So i need to keep to a minimum the amount of checking done every frame.
4. The collision algorithm begins testing whenever the bounding boxes of the paddle and the ball intersect. Is there something better to test for possible collisions every frame? (more efficient in the long run,with many more objects etc, not necessarily easy to code).

I'm going to post the code for my game:

**Paddle Class**

```
public class Paddle : Microsoft.Xna.Framework.DrawableGameComponent
{
    #region Private Members
    private SpriteBatch spriteBatch;
    private ContentManager contentManager;
    private bool keybEnabled;
    private bool isLeftPaddle;
    private Texture2D paddleSprite;
    private Vector2 paddlePosition;
    private float paddleSpeedY;
    private Vector2 paddleScale = new Vector2(1f, 1f);

    private const float DEFAULT_Y_SPEED = 150;
    private Vector2[] Normals2Edges;
    private Vector2[] Vertices = new Vector2[4];
    private List<Vector2> lst = new List<Vector2>();
    private Vector2 Edge;

    #endregion

    #region Properties

    public float Speed { get {return paddleSpeedY; }  set { paddleSpeedY = value; } }
    public Vector2[] Normal2EdgesVector { get { NormalsToEdges(this.isLeftPaddle); return Normals2Edges; } }
    public Vector2[] VertexVector { get { return Vertices; } }

    public Vector2 Scale
    {
        get { return paddleScale; }
        set { paddleScale = value; NormalsToEdges(this.isLeftPaddle); }
    }

    public float X
    {
        get { return paddlePosition.X; }
        set { paddlePosition.X = value; }
    }

    public float Y
    {
        get { return paddlePosition.Y; }
        set { paddlePosition.Y = value; }
    }

    public float Width
    {
        get { return (Scale.X == 1f ? (float)paddleSprite.Width : paddleSprite.Width * Scale.X); }
    }

    public float Height
    {
        get { return ( Scale.Y==1f ? (float)paddleSprite.Height : paddleSprite.Height*Scale.Y ); }
    }

    public Texture2D GetSprite
    {
        get { return paddleSprite; }
    }

    public Rectangle Boundary
    {
        get
        {
            return new Rectangle((int)paddlePosition.X, (int)paddlePosition.Y,
                (int)this.Width, (int)this.Height);
        }
    }

    public bool KeyboardEnabled
    {
        get { return keybEnabled;  }
    }

    #endregion

    private void NormalsToEdges(bool isLeftPaddle)
    {
        Normals2Edges = null;
        Edge = Vector2.Zero;
        lst.Clear();

        for (int i = 0; i < Vertices.Length; i++)
        {
            Edge = Vertices[i + 1 == Vertices.Length ? 0 : i + 1] - Vertices[i];
            if (Edge != Vector2.Zero)
            {
                Edge.Normalize();
                //outer normal to edge !! (origin in top-left)
                lst.Add(new Vector2(Edge.Y, -Edge.X));
            }
        }
        Normals2Edges = lst.ToArray();
    }

    public float[] ProjectPaddle(Vector2 axis)
    {
        if (Vertices.Length == 0 || axis == Vector2.Zero) return (new float[2] { 0, 0 });

        float min, max;
        min = Vector2.Dot(axis, Vertices[0]); max = min;
        for (int i = 1; i < Vertices.Length; i++)
        {
            float p = Vector2.Dot(axis, Vertices[i]);
            if (p < min) min = p; else if (p > max) max = p;
        }
        return (new float[2] { min, max });
    }

    public Paddle(Game game, bool isLeftPaddle, bool enableKeyboard = true) : base(game)
    {
        contentManager = new ContentManager(game.Services);
        keybEnabled = enableKeyboard;
        this.isLeftPaddle = isLeftPaddle;
    }

    public void setPosition(Vector2 newPos)
    {
        X = newPos.X;
        Y = newPos.Y;
    }

    public override void Initialize()
    {
        base.Initialize();
        this.Speed = DEFAULT_Y_SPEED;
        X = 0;
        Y = 0;
        NormalsToEdges(this.isLeftPaddle);
    }

    protected override void LoadContent()
    {
        spriteBatch = new SpriteBatch(GraphicsDevice);
        paddleSprite = contentManager.Load<Texture2D>(@"Content\pongBar");
    }

    public override void Update(GameTime gameTime)
    {

        //vertices array
        Vertices[0] = this.paddlePosition;
        Vertices[1] = this.paddlePosition + new Vector2(this.Width, 0);
        Vertices[2] = this.paddlePosition + new Vector2(this.Width, this.Height);
        Vertices[3] = this.paddlePosition + new Vector2(0, this.Height);

        // Move paddle, but don't allow movement off the screen
        if (KeyboardEnabled)
        {
            float moveDistance = Speed * (float)gameTime.ElapsedGameTime.TotalSeconds;
            KeyboardState newKeyState = Keyboard.GetState();
            if (newKeyState.IsKeyDown(Keys.Down) && Y + paddleSprite.Height + moveDistance <= Game.GraphicsDevice.Viewport.Height)
            {
                Y += moveDistance;
            }
            else if (newKeyState.IsKeyDown(Keys.Up) && Y - moveDistance >= 0)
            {
                Y -= moveDistance;
            }
        }
        else
        {
            if (this.Y + this.Height > this.GraphicsDevice.Viewport.Height)
            {
                this.Y = this.Game.GraphicsDevice.Viewport.Height - this.Height - 1;
            }
        }
        base.Update(gameTime);
    }

    public override void Draw(GameTime gameTime)
    {
        spriteBatch.Begin(SpriteSortMode.Texture,null);
        spriteBatch.Draw(paddleSprite, paddlePosition, null, Color.White, 0f, Vector2.Zero, Scale, SpriteEffects.None, 0);
        spriteBatch.End();

        base.Draw(gameTime);
    }
}

```

**Ball Class**

```
public class Ball : Microsoft.Xna.Framework.DrawableGameComponent
{
    #region Private Members
    private SpriteBatch spriteBatch;
    private ContentManager contentManager;

    private const float DEFAULT_SPEED = 50;
    private float speedIncrement = 0;
    private Vector2 ballScale = new Vector2(1f, 1f);
    private const float INCREASE_SPEED = 50;

    private Texture2D ballSprite; //initial texture
    private Vector2 ballPosition; //position
    private Vector2 centerOfBall; //center coords
    private Vector2 ballSpeed = new Vector2(DEFAULT_SPEED, DEFAULT_SPEED); //speed
    #endregion

    #region Properties

    public float DEFAULTSPEED
    {
        get { return DEFAULT_SPEED; }
    }

    public Vector2 ballCenter
    {
        get { return centerOfBall; }
    }

    public Vector2 Scale
    {
        get { return ballScale; }
        set { ballScale = value; }
    }

    public float SpeedX
    {
        get { return ballSpeed.X; }
        set { ballSpeed.X = value; }
    }

    public float SpeedY
    {
        get { return ballSpeed.Y; }
        set { ballSpeed.Y = value; }
    }

    public float X
    {
        get { return ballPosition.X; }
        set { ballPosition.X = value; }
    }

    public float Y
    {
        get { return ballPosition.Y; }
        set { ballPosition.Y = value; }
    }

    public Texture2D GetSprite
    {
        get { return ballSprite; }
    }

    public float Width
    {
        get { return (Scale.X == 1f ? (float)ballSprite.Width : ballSprite.Width * Scale.X); }
    }

    public float Height
    {
        get { return (Scale.Y == 1f ? (float)ballSprite.Height : ballSprite.Height * Scale.Y); }
    }

    public float SpeedIncreaseIncrement
    {
        get { return speedIncrement; }
        set { speedIncrement = value; }
    }

    public Rectangle Boundary
    {
        get
        {
            return new Rectangle((int)ballPosition.X, (int)ballPosition.Y,
                (int)this.Width, (int)this.Height);
        }
    }
    #endregion

    public Ball(Game game) : base(game)
    {
        contentManager = new ContentManager(game.Services);
    }

    public void Reset()
    {
        ballSpeed.X = DEFAULT_SPEED;
        ballSpeed.Y = DEFAULT_SPEED;
        ballPosition.X = Game.GraphicsDevice.Viewport.Width / 2 - ballSprite.Width / 2;
        ballPosition.Y = Game.GraphicsDevice.Viewport.Height / 2 - ballSprite.Height / 2;
    }

    public void SpeedUp()
    {
        if (ballSpeed.Y < 0)
            ballSpeed.Y -= (INCREASE_SPEED + speedIncrement);
        else
            ballSpeed.Y += (INCREASE_SPEED + speedIncrement);

        if (ballSpeed.X < 0)
            ballSpeed.X -= (INCREASE_SPEED + speedIncrement);
        else
            ballSpeed.X += (INCREASE_SPEED + speedIncrement);
    }

    public float[] ProjectBall(Vector2 axis)
    {
        if (axis == Vector2.Zero) return (new float[2] { 0, 0 });

        float min, max;
        min = Vector2.Dot(axis, this.ballCenter) - this.Width/2; //center - radius
        max = min + this.Width;    //center + radius
        return (new float[2] { min, max });
    }

    public void ChangeHorzDirection()
    {
        ballSpeed.X *= -1;
    }

    public void ChangeVertDirection()
    {
        ballSpeed.Y *= -1;
    }

    public override void Initialize()
    {
        base.Initialize();
        ballPosition.X = Game.GraphicsDevice.Viewport.Width / 2 - ballSprite.Width / 2;
        ballPosition.Y = Game.GraphicsDevice.Viewport.Height / 2 - ballSprite.Height / 2;
    }

    protected override void LoadContent()
    {
        spriteBatch = new SpriteBatch(GraphicsDevice);
        ballSprite = contentManager.Load<Texture2D>(@"Content\ball");
    }

    public override void Update(GameTime gameTime)
    {
        if (this.Y < 1 || this.Y > GraphicsDevice.Viewport.Height - this.Height - 1)
            this.ChangeVertDirection();

        centerOfBall = new Vector2(ballPosition.X + this.Width / 2, ballPosition.Y + this.Height / 2);
        base.Update(gameTime);
    }

    public override void Draw(GameTime gameTime)
    {
        spriteBatch.Begin();
        spriteBatch.Draw(ballSprite, ballPosition, null, Color.White, 0f, Vector2.Zero, Scale, SpriteEffects.None, 0);
        spriteBatch.End();
        base.Draw(gameTime);
    }
}

```

**Main game class**

```
public class gameStart : Microsoft.Xna.Framework.Game
{
    GraphicsDeviceManager graphics;
    SpriteBatch spriteBatch;

    public gameStart()
    {
        graphics = new GraphicsDeviceManager(this);
        Content.RootDirectory = "Content";
        this.Window.Title = "Pong game";
    }

    protected override void Initialize()
    {
        ball = new Ball(this);
        paddleLeft = new Paddle(this,true,false);
        paddleRight = new Paddle(this,false,true);

        Components.Add(ball);
        Components.Add(paddleLeft);
        Components.Add(paddleRight);
        this.Window.AllowUserResizing = false;
        this.IsMouseVisible = true;
        this.IsFixedTimeStep = false;
        this.isColliding = false;

        base.Initialize();
    }

    #region MyPrivateStuff

    private Ball ball;
    private Paddle paddleLeft, paddleRight;
    private int[] bit = { -1, 1 };
    private Random rnd = new Random();
    private int updates = 0;

    enum nrPaddle { None, Left, Right };
    private nrPaddle PongBar = nrPaddle.None;

    private ArrayList Axes = new ArrayList();
    private Vector2 MTV; //minimum translation vector
    private bool isColliding;
    private float overlap; //smallest distance after projections
    private Vector2 overlapAxis; //axis of overlap

    #endregion

    protected override void LoadContent()
    {
        spriteBatch = new SpriteBatch(GraphicsDevice);
        paddleLeft.setPosition(new Vector2(0, this.GraphicsDevice.Viewport.Height / 2 - paddleLeft.Height / 2));
        paddleRight.setPosition(new Vector2(this.GraphicsDevice.Viewport.Width - paddleRight.Width, this.GraphicsDevice.Viewport.Height / 2 - paddleRight.Height / 2));

        paddleLeft.Scale = new Vector2(1f, 2f); //scale left paddle
    }

    private bool ShapesIntersect(Paddle paddle, Ball ball)
    {
        overlap = 1000000f; //large value
        overlapAxis = Vector2.Zero;
        MTV = Vector2.Zero;

        foreach (Vector2 ax in Axes)
        {
            float[] pad = paddle.ProjectPaddle(ax); //pad0 = min, pad1 = max
            float[] circle = ball.ProjectBall(ax);  //circle0 = min, circle1 = max
            if (pad[1] <= circle[0] || circle[1] <= pad[0]) { return false; }

            if (pad[1] - circle[0] < circle[1] - pad[0])
            {
                if (Math.Abs(overlap) > Math.Abs(-pad[1] + circle[0])) { overlap = -pad[1] + circle[0]; overlapAxis = ax; }
            }
            else
            {
                if (Math.Abs(overlap) > Math.Abs(circle[1] - pad[0])) { overlap = circle[1] - pad[0]; overlapAxis = ax; }
            }
        }

        if (overlapAxis != Vector2.Zero) { MTV = overlapAxis * overlap; }
        return true;
    }

    protected override void Update(GameTime gameTime)
    {
        updates += 1;
        float ftime =  5 * (float)gameTime.ElapsedGameTime.TotalSeconds;

        if (updates == 1)
        {
            isColliding = false;
            int Xrnd = bit[Convert.ToInt32(rnd.Next(0, 2))];
            int Yrnd = bit[Convert.ToInt32(rnd.Next(0, 2))];
            ball.SpeedX = Xrnd * ball.SpeedX;
            ball.SpeedY = Yrnd * ball.SpeedY;
            ball.X += ftime * ball.SpeedX;
            ball.Y += ftime * ball.SpeedY;
        }
        else
        {
            updates = 100;
            ball.X += ftime * ball.SpeedX;
            ball.Y += ftime * ball.SpeedY;
        }

        //autorun :)
        paddleLeft.Y = ball.Y;

        //collision detection
        PongBar = nrPaddle.None;
        if (ball.Boundary.Intersects(paddleLeft.Boundary))
        {
            PongBar = nrPaddle.Left;
            if (!isColliding)
            {
                Axes.Clear();
                Axes.AddRange(paddleLeft.Normal2EdgesVector);
                //axis from nearest vertex to ball's center
                Axes.Add(FORMULAS.NormAxisFromCircle2ClosestVertex(paddleLeft.VertexVector, ball.ballCenter));
            }
        }
        else if (ball.Boundary.Intersects(paddleRight.Boundary))
        {
            PongBar = nrPaddle.Right;
            if (!isColliding)
            {
                Axes.Clear();
                Axes.AddRange(paddleRight.Normal2EdgesVector);
                //axis from nearest vertex to ball's center
                Axes.Add(FORMULAS.NormAxisFromCircle2ClosestVertex(paddleRight.VertexVector, ball.ballCenter));
            }
        }

        if (PongBar != nrPaddle.None && !isColliding)
            switch (PongBar)
            {
                case nrPaddle.Left:
                    if (ShapesIntersect(paddleLeft, ball))
                    {
                        isColliding = true;
                        if (MTV != Vector2.Zero) ball.X += MTV.X; ball.Y += MTV.Y;
                        ball.ChangeHorzDirection();
                    }
                    break;
                case nrPaddle.Right:
                    if (ShapesIntersect(paddleRight, ball))
                    {
                        isColliding = true;
                        if (MTV != Vector2.Zero) ball.X += MTV.X; ball.Y += MTV.Y;
                        ball.ChangeHorzDirection();
                    }
                    break;
                default:
                    break;
            }

        if (!ShapesIntersect(paddleRight, ball) && !ShapesIntersect(paddleLeft, ball)) isColliding = false;

        ball.X += ftime * ball.SpeedX;
        ball.Y += ftime * ball.SpeedY;

        //check ball movement
        if (ball.X > paddleRight.X + paddleRight.Width + 2)
        {
            //IncreaseScore(Left);
            ball.Reset();
            updates = 0;
            return;
        }
        else if (ball.X < paddleLeft.X - 2)
        {
            //IncreaseScore(Right);
            ball.Reset();
            updates = 0;
            return;
        }

        base.Update(gameTime);
    }

    protected override void Draw(GameTime gameTime)
    {
        GraphicsDevice.Clear(Color.Aquamarine);
        spriteBatch.Begin(SpriteSortMode.BackToFront, BlendState.AlphaBlend);
        spriteBatch.End();
        base.Draw(gameTime);
    }
}

```

And one method i've used:

```
public static Vector2 NormAxisFromCircle2ClosestVertex(Vector2[] vertices, Vector2 circle)
    {
        Vector2 temp = Vector2.Zero;
        if (vertices.Length > 0)
        {
            float dist = (circle.X - vertices[0].X) * (circle.X - vertices[0].X) + (circle.Y - vertices[0].Y) * (circle.Y - vertices[0].Y);
            for (int i = 1; i < vertices.Length;i++)
            {
                if (dist > (circle.X - vertices[i].X) * (circle.X - vertices[i].X) + (circle.Y - vertices[i].Y) * (circle.Y - vertices[i].Y))
                {
                    temp = vertices[i]; //memorize the closest vertex
                    dist = (circle.X - vertices[i].X) * (circle.X - vertices[i].X) + (circle.Y - vertices[i].Y) * (circle.Y - vertices[i].Y);
                }
            }
            temp = circle - temp;
            temp.Normalize();
        }
        return temp;
    }

```

Thanks in advance for any tips on the 4 issues.

**EDIT1:**

Something isn't working properly. The collision axis doesn't come out right and the interpolation also seems to have no effect. I've changed the code a bit:

```
private bool ShapesIntersect(Paddle paddle, Ball ball)
    {
        overlap = 1000000f; //large value
        overlapAxis = Vector2.Zero;
        MTV = Vector2.Zero;

        foreach (Vector2 ax in Axes)
        {
            float[] pad = paddle.ProjectPaddle(ax); //pad0 = min, pad1 = max
            float[] circle = ball.ProjectBall(ax);  //circle0 = min, circle1 = max
            if (pad[1] < circle[0] || circle[1] < pad[0]) { return false; }

            if (Math.Abs(pad[1] - circle[0]) < Math.Abs(circle[1] - pad[0]))
            {
                if (Math.Abs(overlap) > Math.Abs(-pad[1] + circle[0])) { overlap = -pad[1] + circle[0]; overlapAxis = ax * (-1); } //to get the proper axis
            }
            else
            {
                if (Math.Abs(overlap) > Math.Abs(circle[1] - pad[0])) { overlap = circle[1] - pad[0]; overlapAxis = ax; }
            }
        }

        if (overlapAxis != Vector2.Zero) { MTV = overlapAxis * Math.Abs(overlap); }
        return true;
    }

```

And part of the Update method:

```
if (ShapesIntersect(paddleRight, ball))
                    {
                        isColliding = true;
                        if (MTV != Vector2.Zero) { ball.X += MTV.X; ball.Y += MTV.Y; }
                        //test
                        if (overlapAxis.X == 0) //collision with horizontal edge
                        {
                        }
                        else if (overlapAxis.Y == 0) //collision with vertical edge
                        {
                            float factor = Math.Abs(ball.ballCenter.Y - paddleRight.Y) / paddleRight.Height;
                            if (factor > 1) factor = 1f;

                            if (overlapAxis.X < 0) //left edge?
                                ball.Speed = ball.DEFAULTSPEED * Vector2.Normalize(Vector2.Reflect(ball.Speed, (Vector2.Lerp(new Vector2(-1, -3), new Vector2(-1, 3), factor))));
                            else //right edge?
                                ball.Speed = ball.DEFAULTSPEED * Vector2.Normalize(Vector2.Reflect(ball.Speed, (Vector2.Lerp(new Vector2(1, -3), new Vector2(1, 3), factor))));
                        }
                        else //vertex collision???
                        {
                            ball.Speed = -ball.Speed;
                        }
                    }

```

What seems to happen is that "overlapAxis" doesn't always return the right one. So instead of (-1,0) i get the (1,0) *(this happened even before i multiplied with -1 there)*. Sometimes there isn't even a collision registered even though the ball passes through the paddle... The interpolation also seems to have no effect as the angles barely change (or the overlapAxis is almost never (-1,0) or (1,0) but something like (0.9783473, 0.02743843)... ). What am i missing here? :(

# Answer
> 0 votes
1. My suggestion to accomplish this would be to adjust the collision normal accordingly. You could have one normal at the top corner pointing, say 45 deg, up/right and one normal in the bottom corner pointing down/right. For any collision between these you can interpolate between these two normals (using Vector2.Lerp) to get an angle that will then point stright to the right in the exact middle of the edge. In case you want a region with perfect horizontal bounce you can use two normals on the borders of this region pointing in the horizontal direction.
2. You can handle this by using different normals for different edges.

3 and 4. You are on the right track. In the future you can implement a sweep and prune algorithm to determine for which entities to make the broad phase collision detect. For your purpose there is no need for it right now as you only need to check the ball against all other entities which is a O(n) operation. If you have many moving entities which may hit each other you might need it as check all these against each other will be a O(m^2) operation (m number of moving entities that can hit each other)

EDIT: Note that when interpolating two unitvectors you are not guaranteed to get a unit vector back, it will probably be a little shorter. So make sure to normalize after interpolation.

EDIT 2: If you are interpolating along the vertical side then you want your *amount* to be zero when at the top and one at the bottom. This should depend on the y-value of the contact point.

```
float amount = (contact.Point.Y - top.Y) / (bottom.Y - top.Y);

```

Assuming that y is positive in the downwards direction (bottom.Y \> top.Y). This will give a value for *amount* that is in the range of \[0..1\]

EDIT 3: To find correct contact points you will have two cases to handle. For ball-edge contact follow the reverse axis of collision (which is the edge normal) from the center of ball to the edge of the ball. That will be your contact point. You might have some overlapping due to movement from last frame and this can be handled by a special interpenetration handling method before handleing the collision. Remember to check if you actually have a *closing velocity* along the axis before handling collision or you might experience some very strange behaviour.

To find contact point for ball-vertex contact do the same thing but the axis in this case is the vecetor from the vertex to the ball center.

---
Tags: xna, collision-detection, vector, angles
---


# Question
Title: How to make NPC AI for my jme3 ninja game
My scene has a main character who is a ninja and an enemy which is a goblin and one monster but the monster has no animation so we can wait with him:

How can I make the goblin actually move instead of just walking (animating) on the spot? I asked in the jme3 forum but I could not understand the answer: http://jmonkeyengine.org/groups/graphics/forum/topic/making-a-computer-controlled-character-move My code is

```
package adventure;

import java.applet.Applet;
import java.applet.AudioClip;
import java.awt.Image;
import java.io.File;
import java.net.MalformedURLException;
import java.net.URL;
import com.jme3.renderer.queue.RenderQueue.ShadowMode;
import com.jme3.animation.AnimChannel;
import com.jme3.animation.AnimControl;
import com.jme3.animation.AnimEventListener;
import com.jme3.animation.LoopMode;
import com.jme3.app.SimpleApplication;
import com.jme3.asset.BlenderKey;
import com.jme3.asset.plugins.HttpZipLocator;
import com.jme3.asset.plugins.ZipLocator;
import com.jme3.bullet.BulletAppState;
import com.jme3.bullet.PhysicsSpace;
import com.jme3.bullet.collision.shapes.CapsuleCollisionShape;
import com.jme3.bullet.control.CharacterControl;
import com.jme3.bullet.control.RigidBodyControl;
import com.jme3.bullet.objects.PhysicsCharacter;
import com.jme3.input.ChaseCamera;
import com.jme3.input.KeyInput;
import com.jme3.input.controls.ActionListener;
import com.jme3.input.controls.KeyTrigger;
import com.jme3.light.AmbientLight;
import com.jme3.light.DirectionalLight;
import com.jme3.material.MaterialList;
import com.jme3.math.ColorRGBA;
import com.jme3.math.Vector3f;
import com.jme3.post.FilterPostProcessor;
import com.jme3.post.filters.BloomFilter;
import com.jme3.scene.Geometry;
import com.jme3.scene.Node;
import com.jme3.scene.Spatial;
import com.jme3.scene.plugins.ogre.OgreMeshKey;
import com.jme3.input.controls.MouseButtonTrigger;
import com.jme3.input.MouseInput;
public class Q3World extends SimpleApplication implements ActionListener,
        AnimEventListener, Playable {
    private Node gameLevel;
    private PhysicsCharacter player;
    private static boolean useHttp = false;
    private static World world;
    private static Person person;
    private static Player dplayer;
    private BulletAppState bulletAppState;
    private AnimChannel channel;
    private AnimControl control;
    // character
    CharacterControl character;
    CharacterControl goblincharacter;
    Node model;
    // temp vectors
    Vector3f walkDirection = new Vector3f();
    Spatial goblin;
    RigidBodyControl terrainPhysicsNode;

    // animation
    AnimChannel animationChannel;
    AnimChannel shootingChannel;
    AnimControl animationControl;
    float airTime = 0;
    // camera
    boolean left = false, right = false, up = false, down = false, attack=false;
    ChaseCamera chaseCam;

    FilterPostProcessor fpp;
    private Spatial sceneModel;

    private RigidBodyControl landscape;

    public static void main(String[] args) {

        File file = new File("quake3level.zip");
        if (!file.exists()) {
            useHttp = true;
        }
        Q3World app = new Q3World();
        app.start();
    }

    @Override
    public void simpleInitApp() {
        bulletAppState = new BulletAppState();
        bulletAppState.setThreadingType(BulletAppState.ThreadingType.PARALLEL);
        stateManager.attach(bulletAppState);
        setupKeys();
        DirectionalLight dl = new DirectionalLight();
        dl.setColor(ColorRGBA.White.clone().multLocal(2));
        dl.setDirection(new Vector3f(-1, -1, -1).normalize());
        rootNode.addLight(dl);
        AmbientLight am = new AmbientLight();
        am.setColor(ColorRGBA.White.mult(2));
        rootNode.addLight(am);

        if (useHttp) {
            assetManager
                    .registerLocator(
                            "http://jmonkeyengine.googlecode.com/files/quake3level.zip",
                            HttpZipLocator.class);
        } else {
            assetManager.registerLocator("quake3level.zip", ZipLocator.class);
        }

        // create the geometry and attach it
        MaterialList matList = (MaterialList) assetManager
                .loadAsset("Scene.material");
        OgreMeshKey key = new OgreMeshKey("main.meshxml", matList);
        gameLevel = (Node) assetManager.loadAsset(key);
        gameLevel.setLocalScale(0.1f);
        gameLevel.addControl(new RigidBodyControl(0));
        getPhysicsSpace().addAll(gameLevel);
        rootNode.attachChild(gameLevel);
        getPhysicsSpace().addAll(gameLevel);
        createCharacters();
        setupChaseCamera();
        setupAnimationController();
        setupFilter();
    }

    private void setupFilter() {
        FilterPostProcessor fpp = new FilterPostProcessor(assetManager);
        BloomFilter bloom = new BloomFilter(BloomFilter.GlowMode.Objects);
        fpp.addFilter(bloom);
        viewPort.addProcessor(fpp);
    }

    private PhysicsSpace getPhysicsSpace() {
        return bulletAppState.getPhysicsSpace();
    }

    private void setupKeys() {
        inputManager.addMapping("wireframe", new KeyTrigger(KeyInput.KEY_T));
        inputManager.addListener(this, "wireframe");
        inputManager.addMapping("CharLeft", new KeyTrigger(KeyInput.KEY_A));
        inputManager.addMapping("CharRight", new KeyTrigger(KeyInput.KEY_D));
        inputManager.addMapping("CharUp", new KeyTrigger(KeyInput.KEY_W));
        inputManager.addMapping("CharDown", new KeyTrigger(KeyInput.KEY_S));
        inputManager.addMapping("CharSpace",
                new KeyTrigger(KeyInput.KEY_SPACE));
        inputManager
                .addMapping("CharShoot",  new MouseButtonTrigger(MouseInput.BUTTON_LEFT));
        inputManager.addListener(this, "CharLeft");
        inputManager.addListener(this, "CharRight");
        inputManager.addListener(this, "CharUp");
        inputManager.addListener(this, "CharDown");
        inputManager.addListener(this, "CharSpace");
        inputManager.addListener(this, "CharShoot");
    }

    private void createCharacters() {
        CapsuleCollisionShape capsule = new CapsuleCollisionShape(0.05f, 0.05f);
        character = new CharacterControl(capsule, 2);
        character.setJumpSpeed(20f);
        model = (Node) assetManager.loadModel("Models/Ninja/Ninja.mesh.xml");
        model.scale(0.05f, 0.05f, 0.05f);
        model.addControl(character);
        character.setPhysicsLocation(new Vector3f(55, 15, -60));
        model.setShadowMode(ShadowMode.CastAndReceive);
        character.setViewDirection(new Vector3f(1, 0, 0));
        rootNode.attachChild(model);
        getPhysicsSpace().add(character);
        BlenderKey blenderKey = new BlenderKey("Models/Oto/Oto.mesh.xml");
        Spatial man = (Spatial) assetManager.loadModel(blenderKey);
        man.setLocalTranslation(new Vector3f(67, 15, -60));
        man.setShadowMode(ShadowMode.CastAndReceive);
        rootNode.attachChild(man);

        goblin = assetManager.loadModel("objects/goblin.j3o");

        goblin.scale(4f, 4f, 4f);
        //goblin.setLocalTranslation(60, 3.5f, -60);
        goblincharacter = new CharacterControl(capsule, 2);
        goblin.addControl(goblincharacter);
        goblincharacter.setPhysicsLocation(new Vector3f(60, 3.5f, -60));
        //goblincharacter.setViewDirection(new Vector3f(1, 0, 0));
        //character.setWalkDirection(new Vector3f(1, 0, 0));

        control = goblin.getControl(AnimControl.class);
        control.addListener(this);
        channel = control.createChannel();

        for (String anim : control.getAnimationNames())
            System.out.println("goblin can:"+anim);
        channel.setAnim("walk");

        rootNode.attachChild(goblin);
        getPhysicsSpace().add(goblincharacter);
        Spatial monster = assetManager.loadModel("objects/creatures/monster/monster.packed.j3o");
        monster.scale(2f, 2f, 2f);
        monster.setLocalTranslation(new Vector3f(53, 3, -55));
        rootNode.attachChild(monster);

    }

    private void setupChaseCamera() {
        flyCam.setEnabled(false);
        chaseCam = new ChaseCamera(cam, model, inputManager);
        chaseCam.setDefaultDistance(27);

    }

    private void setupAnimationController() {
        animationControl = model.getControl(AnimControl.class);
        animationControl.addListener(this);
        animationChannel = animationControl.createChannel();
        //shootingChannel = animationControl.createChannel();

    }

    @Override
    public void simpleUpdate(float tpf) {

        Vector3f modelDirection = goblin.getLocalRotation().toRotationMatrix().getColumn(2);
        //goblin.setLocalTranslation(modelDirection.add(new Vector3f(1, 0, -0)));

        Vector3f camDir = cam.getDirection().clone().multLocal(0.1f);
        Vector3f camLeft = cam.getLeft().clone().multLocal(0.1f);
        camDir.y = 0;
        camLeft.y = 0;
        walkDirection.set(0, 0, 0);
        if (left) {
            walkDirection.addLocal(camLeft);
        }
        if (right) {
            walkDirection.addLocal(camLeft.negate());
        }
        if (up) {
            walkDirection.addLocal(camDir);
        }
        if (down) {
            walkDirection.addLocal(camDir.negate());
        }
        //if (attack) {
            //animationChannel.setAnim("Attack1");
            //animationChannel.setLoopMode(LoopMode.DontLoop);
        //}
        if (!character.onGround()) {
            airTime = airTime + tpf;
        } else {
            airTime = 0;
        }
        if (walkDirection.length() == 0) {
            if (!"Idle1".equals(animationChannel.getAnimationName())) {
                animationChannel.setAnim("Idle1", 1f);
            }
        } else {
            character.setViewDirection(walkDirection.negate());
            if (airTime > .3f) {
                if (!"stand".equals(animationChannel.getAnimationName())) {
                    animationChannel.setAnim("Idle1");
                }
            } else if (!"Walk".equals(animationChannel.getAnimationName())) {
                animationChannel.setAnim("Walk", 1f);
            }
        }
        character.setWalkDirection(walkDirection);
    }

    /*Ninja can: Walk
Ninja can: Kick
Ninja can: JumpNoHeight
Ninja can: Jump
Ninja can: Spin
Ninja can: Attack1
Ninja can: Idle1
Ninja can: Attack3
Ninja can: Idle2
Ninja can: Attack2
Ninja can: Idle3
Ninja can: Stealth
Ninja can: Death2
Ninja can: Death1
Ninja can: HighJump
Ninja can: SideKick
Ninja can: Backflip
Ninja can: Block
Ninja can: Climb
Ninja can: Crouch*/

    public void onAction(String binding, boolean value, float tpf) {
        if (binding.equals("CharLeft")) {
            if (value) {
                left = true;
            } else {
                left = false;
            }
        } else if (binding.equals("CharRight")) {
            if (value) {
                right = true;
            } else {
                right = false;
            }
        } else if (binding.equals("CharUp")) {
            if (value) {
                up = true;
            } else {
                up = false;
            }
        } else if (binding.equals("CharDown")) {
            if (value) {
                down = true;
            } else {
                down = false;
            }
        } else if (binding.equals("CharSpace")) {
            character.jump();
        } else if (binding.equals("CharShoot") && value) {
            //bulletControl();
            Vector3f origin    = cam.getWorldCoordinates(inputManager.getCursorPosition(), 0.0f);
            Vector3f direction = cam.getWorldCoordinates(inputManager.getCursorPosition(), 0.3f);
            //direction.subtractLocal(origin).normalizeLocal();
            //character.setWalkDirection(location);
            System.out.println("origin"+origin);
            System.out.println("direction"+direction);
            character.setViewDirection(direction);
            animationChannel.setAnim("Attack3");
            animationChannel.setLoopMode(LoopMode.DontLoop);
        }
    }

    public void onAnimCycleDone(AnimControl control, AnimChannel channel,
            String animName) {
        if (channel == shootingChannel) {
            channel.setAnim("Idle1");
        }
    }

    public void onAnimChange(AnimControl control, AnimChannel channel,
            String animName) {
    }

    // Load an image from the net, making sure it has already been
    // loaded when the method returns
    public Image loadPicture(String imageName) {
        return null;
    }

    // Load and play a sound from /usr/local/hacks/sounds/
    public void playSound(String name) {
        URL u = null;
        try {
            u = new URL("file:" + "/usr/local/hacks/sounds/" + name + ".au");
        } catch (MalformedURLException e) {
        }
        AudioClip a = Applet.newAudioClip(u);
        a.play();
    }
}

```

I want the goblin to move around and then I want it to be able to fight the ninja. The monster should be able to kill but that can wait until later.

## Update

I narrowed down the problem so that I only need the directions for the relative vectors in the goblin's direction now and forward is working and I don't understand why the others don't work, I'm getting unexpected behavior from the goblin in all directions except forward:

```
    goblinWalkDirection.set(0, 0, 0);

    if (goblinleft) {
        System.out.println("goblin left");
        goblinWalkDirection.addLocal(goblin.getLocalRotation()
                .mult(Vector3f.UNIT_X).multLocal(0.09f));
    }
    if (goblinright) {
        System.out.println("goblin right");
        goblinWalkDirection.addLocal(goblin.getLocalRotation()
                .mult(Vector3f.UNIT_X).multLocal(0.09f));
    }
    if (goblinup) {
        System.out.println("goblin forward");
        // move goblin forward
        goblinWalkDirection.addLocal(goblin.getLocalRotation()
                .mult(Vector3f.UNIT_Z).multLocal(0.09f));
    }
    if (goblindown) {
        System.out.println("goblin backwards");
        goblinWalkDirection.addLocal(goblin.getLocalRotation()
                .mult(Vector3f.UNIT_Z).multLocal(0.09f).negate());
    }
    if (goblinWalkDirection.length() == 0) {
        if (!"idleA".equals(animationChannel.getAnimationName())) {
            goblinChannel.setAnim("idleA", 1f);
        }
    } else {
        goblincharacter.setViewDirection(goblinWalkDirection);
        if (!"walk".equals(goblinChannel.getAnimationName())) {
            goblinChannel.setAnim("walk", 1f);
        }
    }
    goblincharacter.setWalkDirection(goblinWalkDirection);

```

## Update 2

Now the goblin can walk around if I press the corresponding keys and the animations are also correct. I just think that the Vectors that set the directions are only correct in the orward case and that I need research for which vectors to put in the other cases for the other directions the goblin can take. But anyhow it is now basically possible to manage movement of the goblin which is a step farther than comments, my coding effort could control both the ninja and the goblin.

```
    goblinWalkDirection.set(0, 0, 0);

    if (goblinleft) {
        System.out.println("goblin left");
        goblinWalkDirection.addLocal(goblin.getLocalRotation()
                .mult(Vector3f.UNIT_X).multLocal(0.09f));
    }
    if (goblinright) {
        System.out.println("goblin right");
        goblinWalkDirection.addLocal(goblin.getLocalRotation()
                .mult(Vector3f.UNIT_X).multLocal(0.09f));
    }
    if (goblinup) {
        System.out.println("goblin forward");
        // move goblin forward
        goblinWalkDirection.addLocal(goblin.getLocalRotation()
                .mult(Vector3f.UNIT_Z).multLocal(0.09f));
    }
    if (goblindown) {
        System.out.println("goblin backwards");
        goblinWalkDirection.addLocal(goblin.getLocalRotation()
                .mult(Vector3f.UNIT_Z).multLocal(0.09f).negate());
    }

    if (goblinWalkDirection.length() == 0) {
        if (!"idleA".equals(goblinChannel.getAnimationName())) {
            goblinChannel.setAnim("idleA", 1f);
        }
    } else {
        goblincharacter.setViewDirection(goblinWalkDirection);
        if (airTime > .3f) {
            if (!"stand".equals(goblinChannel.getAnimationName())) {
                goblinChannel.setAnim("Idle1");
            }
        } else if (!"walk".equals(goblinChannel.getAnimationName())) {
            goblinChannel.setAnim("walk", 1f);
        }
    }

```

## Update 3

I've been rewriting and refactoring and I've upgraded the player control to the new class bettercharactercontrol and put it on codereview so that I can get help there. I still have an issue trying to make an NPC do something more intelligent than just looping.

# Answer
> 2 votes
Nick, I think you shouldn't start from 'moving goblin right/left' but from understanding how the AI works. Just sit down, close your eyes and imagine the fight with the goblin - how would you like it to look like?

Then split his behavior into pieces - the same way how you do with your 3D code. What you want to do is to give him small brain and some states of mind. The goblin has sight and can hear, he can be looking for the enemy, attacking, fleeing, etc. And you should code all those situations. I know it's not a simple task but the AI is not simple at all.

And the most important - if you don't do this the correct way, from start to end but you try to find some shortcuts, like "make goblin dodge and I'm happy" you'll get into more troubles, just later (like with the holes in Alien head:)). When you later scale your game up, and create 'real' levels, you can find out that every goblin runs on you at the very beginning, or get many other bad situations. And then it wouldn't be so easy to solve them.

---
Tags: java, 3d, ogre, jmonkeyengine
---