Hot questions for Using Lightweight Java Game Library in collision

Question:

I am making a 3D Java game with the LWJGL library, and I was wondering how to add collision detection, so that the player does not go through models.

I am using OBJ models. Here is the OBJLoader class, which loads the models:

package renderEngine;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;

import models.RawModel;

import org.lwjgl.util.vector.Vector2f;
import org.lwjgl.util.vector.Vector3f;

public class OBJLoader {


    public static RawModel loadObjModel(String fileName, Loader loader){
        FileReader fr = null;
        try {
            fr = new FileReader(new File("res/"+fileName+".obj"));
        } catch (FileNotFoundException e) {
            System.err.println("Couldn't load file!");
            e.printStackTrace();
        }
        BufferedReader reader = new BufferedReader(fr);
        String line;
        List<Vector3f> vertices = new ArrayList<Vector3f>();
        List<Vector2f> textures = new ArrayList<Vector2f>();
        List<Vector3f> normals = new ArrayList<Vector3f>();
        List<Integer> indices = new ArrayList<Integer>();
        float[] verticesArray = null;
        float[] normalsArray = null;
        float[] textureArray = null;
        int[] indicesArray = null;
        try{
            while(true){
                line = reader.readLine();
                String[] currentLine = line.split(" ");
                if(line.startsWith("v ")){
                    Vector3f vertex = new Vector3f(Float.parseFloat(currentLine[1]), 
                            Float.parseFloat(currentLine[2]), Float.parseFloat(currentLine[3]));
                    vertices.add(vertex);
                }else if(line.startsWith("vt ")){
                    Vector2f texture = new Vector2f(Float.parseFloat(currentLine[1]), 
                            Float.parseFloat(currentLine[2]));
                    textures.add(texture);
                }else if(line.startsWith("vn ")){
                    Vector3f normal = new Vector3f(Float.parseFloat(currentLine[1]), 
                            Float.parseFloat(currentLine[2]), Float.parseFloat(currentLine[3]));
                    normals.add(normal);
                }else if(line.startsWith("f ")){
                    textureArray = new float[vertices.size() * 2];
                    normalsArray = new float[vertices.size() * 3];
                    break;
                }
            }

            while(line != null){
                if(!line.startsWith("f ")){
                    line = reader.readLine();
                    continue;
                }
                String[] currentLine = line.split(" ");
                String[] vertex1 = currentLine[1].split("/");
                String[] vertex2 = currentLine[2].split("/");
                String[] vertex3 = currentLine[3].split("/");

                processVertex(vertex1, indices, textures, normals, textureArray, normalsArray);
                processVertex(vertex2, indices, textures, normals, textureArray, normalsArray);
                processVertex(vertex3, indices, textures, normals, textureArray, normalsArray);
                line = reader.readLine();
            }

            reader.close();
        }catch(Exception e){
            e.printStackTrace();
        }
        verticesArray = new float[vertices.size()*3];
        indicesArray = new int[indices.size()];


        int vertexPointer = 0;
        for(Vector3f vertex:vertices){
            verticesArray[vertexPointer++] = vertex.x;
            verticesArray[vertexPointer++] = vertex.y;
            verticesArray[vertexPointer++] = vertex.z;
        }
        for(int i=0;i<indices.size(); i++){
            indicesArray[i] = indices.get(i);
        }
        return loader.loadToVAO(verticesArray, textureArray, normalsArray, indicesArray);
    }

    private static void processVertex(String[] vertexData, List<Integer> indices, 
            List<Vector2f> textures, 
            List<Vector3f> normals, float[] textureArray, float[] normalsArray){

        int currentVertexPointer = Integer.parseInt(vertexData[0]) - 1;
        indices.add(currentVertexPointer);
        Vector2f currentTex = textures.get(Integer.parseInt(vertexData[1]) - 1);
        textureArray[currentVertexPointer*2] = currentTex.x;
        textureArray[currentVertexPointer*2+1] = 1 - currentTex.y;
        Vector3f currentNorm = normals.get(Integer.parseInt(vertexData[2])-1);
        normalsArray[currentVertexPointer*3] = currentNorm.x;
        normalsArray[currentVertexPointer*3+1] = currentNorm.y;
        normalsArray[currentVertexPointer*3+2] = currentNorm.z;
    }

}

Thanks!


Answer:

You have a few options here. The easiest is to simply create an axis-aligned bounding box (AABB) around the object; this can be done algorithmically by simply finding the minimum and maximum values for each axis. For some applications this will work fine, but this obviously isn't very precise. It's worth noting, though, that if two AABBs do not intersect, then the objects themselves definitely don't intersect either; you can use this fact as an early-exit for your collision-checking algorithm.

In addition to bounding boxes, some game engines employ other basic types of bounding volumes, such as bounding spheres. Detecting if a point is in a sphere is as simple as checking if the distance between the center of the sphere and the point is less than or equal to the radius of the sphere. Investigate the bounding volume Wikipedia page for other types. You can often approximate the true boundaries of your object by creating compound bounding volumes -- that is, bounding volumes composed of several simpler volumes, like spheres, boxes, cylinders, etc. This is how the Unity game engine handles collision detection.

You might also want to investigate 2D collision detection algorithms, like the separating axis theorem example (see further reading section). These algorithms can almost always be scaled to higher dimensions.

If all this seems too complicated, I'd recommend picking up a prebaked solution, such as Bullet (Java port). Google around a bit; you'll probably find something that fits your use case. Don't feel bad if you feel overwhelmed; collision detection is a complicated subject backed by decades of research.

Further reading:

Question:

I am trying to make a 3D game, but I am having a hard time with the collision. I have worked on a system, but it is not really good. I already have a system for collision with the terrain, but it cannot be used to collide with entities(since the terrain only has height to collide with). I am using blender-models and they consist of triangles. 100% accurate collision would be to use some form of collision detection for each triangle, but there are so many and therefore, the game will lose it's performance. Most of the code is based on ThinMatrix tutorial on YouTube, except some of it which I have created myself. Here is some of the code I use for the current collision:

public boolean collision(Entity e1, Entity e2){


    if(e1.getPosition().x >= e2.getPosition().x && e1.getPosition().x < e2.getPosition().x + e2.getWidth()){
        if(e1.getPosition().z >= e2.getPosition().z && e1.getPosition().z < e2.getPosition().z + e2.getWidth()){
            System.out.println("XXX||&&&||ZZZ");
            return true;
        }
    }

    return false;


}

This method is the collision method. It is based on the X and Z position, and is therefore very inaccurate. In the player-class, I call it:

    public void tick(){
        for(Entity e : entities){
            if(super.collsion(this, e)){
                I haven't gotten to this
            }

        }
    }

This system works, but it has very many problems, one of them being that it is to inaccurate.

EDIT: I have been working on using a new vector(that I made) which I called Vector6f. Using multiple values, it should be easier to store and get the values. It takes the parameters x, y, z, xwidth, zwidth, height. With these, I made a new method I called getBounds, which returns the entities bounds. if the entity does not have bounds, it will not do collision


Answer:

You could easily bring the Y value into the check you have to make it a bit more precise. Although, this just creates a 3d bounding box around the object, rather than 3d convex hull, which probably should be used. Here's some pseudocode close to java, where lX - length in X axis, hlX - half length in X axis, considering we use the center point of entities to define their position.

boolean isColliding(Entity other) {
if (center.y + hlY < other.center.y - other.hlY ||
    center.y - hlY > other.center.y + other.hlY)
    return false;

Rectangle r1 = { center.x - hlX, center.z - hlZ, lX, lZ };
Rectangle r2 = { other.center.x - other.hlX, other.center.z - other.hlZ, other.lX, other.lZ };

return r1.intersects(r2);
}

As for the update tick regarding collisions:

    for (int i = 0; i < collidables.size(); i++) {
        Entity e1 = collidables.get(i);

        for (int j = i + 1; j < collidables.size(); j++) {
            Entity e2 = collidables.get(j);

            if (e1.isColliding(e2)) {
                CollisionHandler handler = ... // get handler if registered for type of e1 vs type of e2
                if (handler != null)
                    handler.onCollision(e1, e2);
            }
        }
    }

which gives you n * (n - 1) / 2 loop cycles, where n - number of collidable entities

Question:

I just started a new 2D game using Java, LWJGL, and Slick Util but I can't seem to figure out a good way to make collision detection. If I wanted to, it would be easy to detect collision between 2 entities with the Rectangle intersect method, but it can only check the collision with a certain area you specify. I have thought that I could make a list of every entity and its coordinates as its created and then run the intersect method through the list, but then it would check for collision with every entity on the entire map for every time the game updated and I think that would be too inefficient.

Does anyone know a more efficient way to create collision detection? If there was some way i could check if there was an entity at every point the character moved that would probably be the best.

If I have not enough information or I made this sound too confusing please tell me and I can try to clarify things. Also as a side question, what are the benefits of using slick util or slick 2D over one another. Thanks for the help!


Answer:

The usual way to solve this is a scene graph, a hierarchical system of the objects of the game world.

You might want to look at this and this.

Shortened: you logically group your objects under nodes and assign the nodes a bounding rectangle that encompasses all its sub-nodes and leaves(objects). Everything is grouped again under one main node to access the tree. Now you can test a object for collision with a node, usually starting from the main node. If you get a hit you check its sub-nodes and leaves.

This will take some time to implement but can cut down on CPU usage if the tree structure/grouping is done right. It has also the benefit that you can implement local transforms which makes moving objects relative to each other easier.

Question:

I am on the long road of developing my own little mmorpg game using LWJGL. So far I have imported a bunny into my game and sorta just positioned him above the grass. Like this:

What I want to do is have my objects in the game able to interact with. For example clicking on them would bring up a little menu of options, or make it so when you run into them something happens. For this I need collision detection. I have worked with it before on 2D games which is much simpler.

Here is my Bunny.java class:

public class Bunny {


public static Model m = null;
public static int displayList;

public static void init() {

    displayList = glGenLists(1);
    glNewList(displayList, GL_COMPILE);
    {
        try {
            m = OBJLoader.loadModel(new File("res/models/bunny.obj"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            Display.destroy();
            System.exit(1);
        } catch (IOException e) {
            e.printStackTrace();
            Display.destroy();
            System.exit(1);
        }

        glBegin(GL_TRIANGLES);

        for (Face face : m.faces) {
            Vector3f n1 = m.normals.get((int) face.normal.x - 1);
            glNormal3f(n1.x, n1.y, n1.z);
            Vector3f v1 = m.vertices.get((int) face.vertex.x - 1);
            glVertex3f(v1.x, v1.y, v1.z);
            Vector3f n2 = m.normals.get((int) face.normal.y - 1);
            glNormal3f(n2.x, n2.y, n2.z);
            Vector3f v2 = m.vertices.get((int) face.vertex.y - 1);
            glVertex3f(v2.x, v2.y, v2.z);
            Vector3f n3 = m.normals.get((int) face.normal.z - 1);
            glNormal3f(n3.x, n3.y, n3.z);
            Vector3f v3 = m.vertices.get((int) face.vertex.z - 1);
            glVertex3f(v3.x, v3.y, v3.z);
        }
        glEnd();

    }
    glEndList();

}

public static void draw(float x, float y, float z) {
    glPushMatrix();
    glTranslatef(x, y, z);
    glCallList(displayList);
    glPopMatrix();
}

}

And my Main class:

public class Main {
public static float PlayerX = 0;
public static float PlayerY = 0;
public static float PlayerZ = 0;
public static float walkSpeed = 0.016f;
public static float PlayerRot = 0;

private static float[] lightPosition = {-2.19f, 1.36f, 11.45f, 1f};

public float pCenterX = 0;
public float pCenterY = 0;
public float pCenterZ = 0;

public static Model m = null;

public static void main(String[] args) {


    initDisplay();
    Bunny.init();
    gameLoop();
    cleanUp();
}


public static void gameLoop() {
    Texture tex = loadTexture("tex", "png");    
    Texture wood = loadTexture("wood", "png");

    loadLight();

    Camera camera = new Camera(70, (float) Display.getWidth() / (float) Display.getHeight(), 0.3f, 1000);

    while (!Display.isCloseRequested()) {



        if(Keyboard.isKeyDown(Keyboard.KEY_W)) camera.move(walkSpeed, 1);
        if(Keyboard.isKeyDown(Keyboard.KEY_S)) camera.move(-walkSpeed, 1);
        if(Keyboard.isKeyDown(Keyboard.KEY_A)) camera.rotateY(-0.1f);
        if(Keyboard.isKeyDown(Keyboard.KEY_D)) camera.rotateY(0.1f);
        if(Keyboard.isKeyDown(Keyboard.KEY_SPACE)) camera.moveY(0.05f, 1);
        if(Keyboard.isKeyDown(Keyboard.KEY_Z)) camera.moveY(0.05f, 0);


        glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);


//      glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
        glTranslatef(0, 2.5f, 0);

        glLoadIdentity();

        //camera.setX(-PlayerX); camera.setY(-PlayerY - 3); camera.setZ(-PlayerZ - 10);

        glLight(GL_LIGHT0, GL_POSITION, asFloatBuffer(new float[] {-2.19f, 1.36f, 11.45f, 1f}));

        camera.useView();

        //Draw.rect(PlayerX, PlayerY, PlayerZ, 0.5f, 0.5f, 0.5f, tex);
        Draw.rect(1, 0, 1, 100, 0.5f, 100, wood);

        Bunny.draw(10, 2.5f, 10);
        Bunny.draw(50, 2.5f, 50);

        Display.update();

    }
}


public static void cleanUp() {
    Display.destroy();
}

public static void initDisplay() {
    try {
        Display.setDisplayMode(new DisplayMode(800, 600));
        Display.create();
    } catch (LWJGLException e) {
        e.printStackTrace();
    }

}


public static Texture loadTexture(String key, String fileType) {

    try {
        return TextureLoader.getTexture(fileType, new FileInputStream(new File("res/img/" + key + "." + fileType)));
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    }

    return null;

}

private static FloatBuffer asFloatBuffer(float[] values) {
    FloatBuffer buffer = BufferUtils.createFloatBuffer(values.length);
    buffer.put(values);
    buffer.flip();
    return buffer;
}

public static void loadLight() {

    glShadeModel(GL_SMOOTH);
    glEnable(GL_DEPTH_TEST);
    glEnable(GL_LIGHTING);
    glEnable(GL_LIGHT0);
    glLightModel(GL_LIGHT_MODEL_AMBIENT, asFloatBuffer(new float[] {0.05f, 0.05f, 0.05f, 1f}));
    glLight(GL_LIGHT0, GL_DIFFUSE, asFloatBuffer(new float[] {1.5f, 1.5f, 1.5f, 1f}));
    //glEnable(GL_CULL_FACE);
    //glCullFace(GL_BACK);
    glEnable(GL_COLOR_MATERIAL);
    glColorMaterial(GL_FRONT, GL_DIFFUSE);

}
}

How can I get the points of the bunny, and use those in an algorithm to detect when we have collided?


Answer:

You already showed the code for the vertices in the first snippet. So you have them.

As for the second part of the question: What you are looking for is collision detection and picking. Covering them in an answer is just too much, so you will have to look them up.

One way to do this is a scene graph.

  • Each object gets a bounding box that encompasses all of its points
  • the object in linked into a scene graph by connecting it to a node
  • each node gets a bounding box that encompasses all boxes of its children

This gives you a treelike structure. Now you just check if a collision has happened by testing the bounding boxes of a node against the collision partner. If it hits you check its subnodes and objects for collision. If you have a hit for an object you do another check based on actual model data.

For normal objects you use their bounding boxes and data for the check. For picking you use a ray fired from the in-world coordinates of your mouse click.

This is just on way to do this, but there are a lot more shades to the topic. For example OpenGL offers its own picking support.

Question:

(Will be putting a bounty on this - Also, I'm not 100% sure what tags are relevant for this)

I'm incredibly confused here. I am attempting to use this (simplified) model for my archers to collide with:

However, as you can see, my archers appear to be colliding in mid-air! I would understand if they fell through (e.g. I had not put enough "points" in my collision model), but to actually appear to be colliding with NOTHING is absolutely baffling me.

I'm loading the model on the server with the same code that I'm displaying it there in the client, so that can't be the issue. I've pastebinned it here anyway.

Then, I'm adding it to three int[] arrays, like this:

coordsx = new int[80 * 10];
coordsy = new int[80 * 10];
coordsz = new int[80 * 10];
for (javax.vecmath.Vector3f vec : m.getVertices()){ //Quick note: M is a model. As you can see, I'm just going through all the vertex positions.
    coordsx[DELTA+(int) vec.x] = 1;
    coordsy[DELTA+(int) vec.y] = 1;
    coordsz[DELTA+(int) vec.z] = 1;
}

Quick note: DELTA is the value of ((80 * 10) / 2) or to save you the math, 400. Also, I used three int[]'s and not an int[][][] because an int[][][] caused an OutOfMemory which I couldn't fix.

Now that I have got these arrays of coordinates, I'm using this code to check it:

for (int x = (int) (location.x + 1); x > location.x - 1; x--){
        for (int y = (int) (location.y + 1); y > location.y - 1; y--){
        for (int z = (int) (location.z + 1); z > location.z - 1; z--){
            distancex = x;
            distancez = z;
            distancey = y;

            try{
            int i = 0;
            if (owner.type == 0){

                if (GameServer.DELTA + distancex > 0 && GameServer.DELTA + distancex < 800 && GameServer.coordsx[(int) (GameServer.DELTA + distancex)] == 1){
                    if (GameServer.DELTA + distancey > 0 && GameServer.DELTA + distancey < 800 && GameServer.coordsy[(int) (GameServer.DELTA + distancey)] == 1){
                        if (GameServer.DELTA + distancez > 0 && GameServer.DELTA + distancez < 800 && GameServer.coordsz[(int) (GameServer.DELTA + distancez)] == 1){
                            i = 1;
                        }
                    }
                }
            }
            if (i == 1){
                collision = true;
                YDown = 0;
            }
            }catch (ArrayIndexOutOfBoundsException e1){
                e1.printStackTrace();
            }

        }
        }
    }
    if (collision){
        System.out.println("Collision!");
    }else{
        System.out.println("No Collision!");
        location.y = location.y-=YDown;
    }

location is a Vector3f of the archers' X, Y, and Z relative to the ship's location - I've checked this using de-bug messages, and the location is indeed returning correctly.

As you can see, the variable i is only being set to 1 if there is a coordinate at both the X, Y, and Z location of the point that is being checked. Obviously, I am iterating through all the nearby coordinates as well, since my player is not just a single point.

Since the player appears to be colliding with air, then there is obviously something wrong. But I cannot find what.

Am I on the right track here, or am I doing everything entirely wrong? And if I am on the right track, then what is going wrong here and how can I fix it?


Answer:

There is a problem with your model. Using three arrays may save memory, but it also changes the model, creating "shadows" that your archers can collide with.

Let's say that you have vertices in (1,1,1) and (2,2,2). Using your model, there will also a vertex at (1,2,2) and any other combination where all coordinates is either 1 or 2.

So, back to the drawing board.

Maybe you can save memory by using a single bit instead of a 32 bit int for each coordinate?

Or you could change the way you store the model. What if you use a 2-dimensional array of int and store the z-coordinate(s) of the floor. This would limit your world to one (or just a few) floors at each x,y-coordinate but would save a huge amount of memory.

Question:


Answer:

I would suggest using a 3d engine that recognizes collision for you like jMonkey. jMonkey can use LWJGL. There is an awesome tutorial here : http://wiki.jmonkeyengine.org/doku.php/jme3:beginner:hello_collision

If you want to roll your own like I do, I create a hash of the 3d points in space. If another object has the same hash it has near collision.

import static java.lang.System.out;

public class App {
    public static int hash(float x, float y, float z) {
        double hash = (((x * 31) + (y * 37) + (z * 41)));//31,37 and 41 are prime numbers
        return (int) (hash);//multiplying the hash by 1000 for example may increase the accuracy significantly. Depends on the size of your space
    }

    public static void main(String[] args) {
        for (float count = 0; count < 2; count += 0.01) {
            out.println(hash(0, 0, count));
        }
    }

}

As you can see the hashes in the output show close collision as count increments by 0.01.

0
0
0
1
1
2
2
2
3
3
4
4
4
5
5
6
6
6

You can modify the prime numbers for higher accuracy.

Question:

i have been working with lwjgl and also j3d for the geometry part. i am still working on the collision. what i have so far witht he collision is working decently but there are 2 problems. to sum up my current way of colliding, it tests if the previous coordinate and current coordinate go through a triangle(what things are rendered as) and then it finds the point on the triangle that it just intersected that is closest to your current coordinate and makes you go there. it also makes your y coordinate go up by .001. this workd descent but going up .001 is bad becuase if you go to a triangle that is at a 90* angle going updards you can go left to rigth but you cant back up out of it, almost as if you are stuck in it. here is a drawing of how it works on imgur

http://i.imgur.com/1gMhRut.png

from here i want to add say .001 to the length between the current coordinate and the closest point (i already know these points) and get the new current point.

btw prev is where the person was at before they moved to the cur point and then it tests to see if those 2 points intersect a triangle and then i get the closest point to the prev if it does which is defined as closest in the picture. i can already calculate for all of those points


Answer:

If I understand you correctly you want to add .001 to move away from the triangle. If that is the case then you need a vector of length 0.001 perpendicular to the triangle. In case of a triangle this is usually called the "normal". If you already have a normal for the triangle, then multiply that by .001 and add that. If you don't have a normal yet you can calculate it using cross product (you can Google the details of what a cross product is), something like this, from the vertices of the triangle:

Vector3 perpendicular = crossProduct(vertex3.pos - vertex1.pos, vertex2.pos - vertex1.pos);
Vector3 normal = perpendicular / length(normal);
Vector3 offset = normal * 0.001f;