Projectile system / Spatial Hashing

Hello. Im making a medieval battle simulator, which of course requires projectile system. The one i wrote was not too optimal (to say the least lol). What my projectile system did was:

  1. spawn a projectile
  2. (in update loop) iterate through all projectiles, and for each iterated projectile go through ALL enemies , and check if someone was hit
  3. if noone was hit, move the projectile forward.

You can imagine how laggy it got with hundred(s) of enemies. So here i am with a question. What is the cheapest way to achieve the exact same results i got with my system? It needs to be as “cheap” as possible so that there can be hundreds of units on screen. Where should i look for solution?

EDIT: what i am desperate to achieve is a projectile that stops on first enemy hit. Is this destined to be calculation heavy and is this approach not recommended for battle simulators?

1 Like

What you are looking for is a broad-phase algorithm.
Broad-phase algorithms reduce the number of pairwise collision-checks you need to do by only checking objects that are close enough to each other. (similar question on stack-overflow: algorithm - Broad-phase collision detection methods? - Stack Overflow)
There are many ways to do this:
-find and use a library
-make a grid, put each object into a grid cell and only check projectiles against objects in their own and neighboring cells.
-do the same as above but with a tree structure, eg. Binary space partitioning - Wikipedia
-Sweep and prune - Wikipedia
-…

Note: broad-phase also usually check collisions with bounding shapes first before doing expensive accurate checks. Eg. bounding spheres/circles are fast to check and easy to work with.

-make a grid, put each object into a grid cell and only check projectiles against objects in their own and neighboring cells.

do you mean spatial hashing? thats the solution that i found suiting my needs, as many games using lots of units use this.
And thanks for other suggestions! i’ll certainly consider all of them

I did not mean spatial hashing, but its a better version of the grid solution i suggested. :+1:

Another common method is to raycast from the source of the projectial, get the closet hit from the raycast. Then animate the projectial moving from the source to the destination. Very fast to calculate and easy to implement.

You might want to take a look at octree data sctructure.

Octrees (and spatial trees in general) are generally poor ways to do this. Tons of size overhead and neighbor checks are ROUGH.

Invariably, you clamp the octree to never split beyond some certain size. And then in that case, you are almost always better off just making a grid of that size. No traverals required. Instant access with some “math”.

…which is already very close to the spatial hashing except it has maybe one or two more use-cases.

1 Like

Thanks for suggestions. I decided to try spatial hashing. Here’s the code for now (translated from c# to java and seems to work, apart from GetNearby() method) if someone was looking for spatial hashing in java but couldnt find a thing:

import com.jme3.math.Vector2f;
import java.util.ArrayList;
import java.util.HashMap;

/**
 *
 * @author Makary
 */
public class SpatialManager {
    static int SceneWidth;
    static int SceneHeight;
    static int CellSize;
    static int Cols;
    static int Rows;
   static private HashMap<Integer, ArrayList> Buckets = new HashMap<>();
    
    public static void testSpatialHash(){  // test method
        GameObject.projectile1.setRadius(1);
        GameObject.projectile1.setPosition(Vector2f.ZERO);
        GameObject.projectile1.setRadius(1);
        GameObject.projectile1.setPosition(new Vector2f(0.7f,0.7f));

    Setup(100,100,25);
//ClearBuckets();
        RegisterObject(GameObject.projectile2);
//
    RegisterObject(GameObject.projectile1);
    GetNearby(GameObject.projectile1);

}
    
     public static void Setup(int scenewidth, int sceneheight, int cellsize){

    Cols= scenewidth / cellsize;
    Rows= sceneheight / cellsize;
    Buckets = new HashMap<Integer,ArrayList>(Cols*Rows);

    for (int i = 0; i < Cols*Rows; i++)
    {
        Buckets.put(i, new ArrayList<>());
    }

    SceneWidth = scenewidth;
    SceneHeight = sceneheight;
    CellSize = cellsize;
}
     
     static protected void ClearBuckets(){
       Buckets.clear();
       for (int i = 0; i < Cols * Rows; i++)
       {
           Buckets.put(i, new ArrayList<>());   
       }
   }
     
    static private ArrayList GetIdForObj(GameObject obj){
        ArrayList bucketsObjIsIn = new ArrayList<>();
           
        Vector2f min = new Vector2f(obj.getPosition().x-(obj.getRadius()),obj.getPosition().y-(obj.getRadius()));   
        Vector2f max = new Vector2f(obj.getPosition().x+(obj.getRadius()),obj.getPosition().y+(obj.getRadius()));

        float width = SceneWidth / CellSize;   
        //TopLeft
        AddBucket(min,width,bucketsObjIsIn);
        //TopRight
        AddBucket(new Vector2f(max.x, min.y), width, bucketsObjIsIn);
        //BottomRight
        AddBucket(new Vector2f(max.x, max.y), width, bucketsObjIsIn);
        //BottomLeft
        AddBucket(new Vector2f(min.x, max.y), width, bucketsObjIsIn);
        
        System.out.println("the object is in buckets numbered: " + bucketsObjIsIn);

	return bucketsObjIsIn;    
    }
     
     
     
    static private void AddBucket(Vector2f vector,float width,ArrayList buckettoaddto){
        int cellPosition = (int)(
                   (Math.floor(vector.x / CellSize)) +
                   (Math.floor(vector.y / CellSize)) *
                   width   
        );
        if(!buckettoaddto.contains(cellPosition))
            buckettoaddto.add(cellPosition);
            
    }
    
   static protected ArrayList GetNearby(GameObject obj){
        ArrayList objects = new ArrayList();
        ArrayList bucketIds = GetIdForObj(obj);
        
        for (int x = 0; x <bucketIds.size();x++){
        objects.add(Buckets.get(x));
        }
        return objects;   
    }
   static protected void RegisterObject(GameObject obj){
        ArrayList cellIds= GetIdForObj(obj);
        
        for (int x = 0; x<cellIds.size();x++){
            Buckets.put(x, cellIds);
        }

    }

     }

My understanding of the code:
registerObject() adds a GameObject to one (or more) of the buckets (contents of one grid square)
getNearby() gets squares the GameObject is in, therefore allowing for checking for collision only in squares

Do i get it right? And if so, do the methods work the way they should?
i debugged it a bit with System.out.print and it seems to work, the buckets object is in change dynamically when in update loop

Edit: during debugging in update loop

   public void update(float tpf) {
       GameObject.projectile1.setPosition(GameObject.projectile1.getPosition().add(new Vector2f(0.1f,0.1f)));
       SpatialManager.ClearBuckets();
       SpatialManager.RegisterObject(GameObject.projectile1);
               SpatialManager.RegisterObject(GameObject.projectile2);

       SpatialManager.GetNearby(GameObject.projectile1);
       
  }

EDIT:
ArrayList objects = new ArrayList(); is now a list of GameObjects, but how do we get GameObjects from the bucket object we check collision for is in?

It seems like GetNearby() stops the movement of the projectile i have no idea why. Also, i dont really understand how to check for collision itself, like, what am i supposed to refer to when checking collision?

Seeing the hash-based code written out, it’s essentially a fixed grid based approach but with all of the clarity removed. (and some strange method names)

You can replace 90% of this code with two classes: SimMath’s Grid class and Guava’s Multimap class. You would also be able to handle a world of huge sizes with essentially no additional cost.

SimMath can be found here and in jcenter: GitHub - Simsilica/SimMath: A double-based math package similar to JME's float-based math classes.
Google’s Guava can be found here: GitHub - google/guava: Google core libraries for Java

The basic idea for the code you have or the Grid-based code is essentially the same. But the Grid-based code to me makes it a little clearer what’s going on.

Basic idea: turn a location into a grid cell ‘key’ and use that to store the objects in the cells. You can easily look up the objects in some cell later, etc…

The version of code you have does all of the “hashing” directly and preloads a bunch of stuff (possibly unnecessarily). It also manually manages a map of ArrayLists which Guava’s Multimap class would do for you.

SimMath Grid:
If you want the “cell ID” for some position then you just ask the grid for it. If you want the world position of some “cell ID” then you can go that direction also.
Grid.worldToId()
Grid.cellToWorld(Grid.idToCell())

Or instead of raw long-int cell IDs you can opt to use GridCell as your key. This would allow for some more convenient debugging.

As mentioned, Multimap does all of the ‘map’ management for you as it’s a Map implementation where you can have more than one value per key.

Putting it together, the setup looks something like:

Grid grid = new Grid(cellSize);
Multimap<GridCell, GameObject> index = MultimapBuilder.hashKeys().hashSetValues();

So adding an object looks like:

GridCell cell = grid.getContainingCell(gameObj.getLocation());
index.put(cell, gameObj);

Looking up all object’s in a particular cell is easy:

index.get(cell)

Philosophically there are now two approaches one could take:

  1. put the object into all of the cells that it can affect.
  2. put the object into only the cell of its location and look for neighbors only when needed.

In the first approach, when adding the object you loop through all of the cells that it intersects and add to all of those cells.

Rough pseudo code:

Vec3i min = grid.worldToCell(lowest location);
Vec3i max = grid.worldToCell(highest location);
for( int x = min.x; x <= max.x; x++ ) {
    for( int y = min.x; y <= max.x; y++ ) {
        for( int z = min.x; z <= max.x; z++ ) {
            GridCell cell = grid.getCell(x, y, z);
            index.put(cell, gameObject);
        }
    }
}

Then you know for any cell you look in, it will contain any object that potentially intersects that cell.

The down side is that when objects move then you have a lot more maintenance to do with respect to removing objects from the old cells and adding them to the new ones.

In the second approach, you put the “search neighbor cells” burden on the code that is doing the collision checks or whatever other queries it needs. So if you want to know what objects collides with “gameObject” you would do a similar min/max loop to the above to find the cells to look in… then do collisions with any of the objects in those cells.

The bonus is that when moving an object, you only have to take it out of the cell it used to be in and put it into the cell it’s in now. It is never “in” more than one cell.

The down side is that every time you do a collision check you will do those neighbor searches. BUT: it is quite often that you don’t know how big of an area that you want to search until you go to do it. For example, if an object is moving very fast then you might want to search a larger area… or an area biased ahead of the object, etc… These are things you won’t know until after the object is already in the index.

Furthermore, it’s quite common to want to do general “give me all of the objects in this bounding rectangle” for other reasons… and if you already have to write that routine then you might as well use it for object collisions.

Either way, it’s still way better than than the n-squared check you do without a spatial indexing scheme. The tradeoffs to each approach just depend on what you need for your game.

1 Like

Thanks a lot, it seems like it’d cut my work in half .

@pspeed Alright. I set everything up but:

package mygame;

import com.google.common.collect.HashMultimap;
import com.simsilica.mathd.Grid;
import com.simsilica.mathd.GridCell;
import com.simsilica.mathd.Vec3d;

/**
 *
 * @author Makary
 */
public class SpatialHash {
    public static HashMultimap<Object, GameObject> index = HashMultimap.create();
    public static Grid worldGrid;
    public static GridCell cell;
    
    
    public static void Setup(){
       //debug
        GameObject.projectile1.setPosition(new Vec3d(0,0,0));
        GameObject.projectile1.setRadius(1);
        GameObject.projectile2.setPosition(new Vec3d(0,16,367));
        GameObject.projectile2.setRadius(1);
       //debug
        worldGrid = new Grid(5);
       
    }
    
    public static void AddObject(GameObject gameObj){  // puts the object in a cell based on its position.
    cell = worldGrid.getContainingCell(gameObj.getPosition());  
    System.out.println("Putting into the cell: " + cell);
    index.put(cell, gameObj);
    }
    
    public static void checkProjectileCell(GameObject projectile){ // this method finds all objects in the cell in which given object currently is.
    cell = worldGrid.getContainingCell(projectile.getPosition());  
//    index.get(cell);
    System.out.println("GameObjects in this cell" + index.get(cell));
    }
 
    
    
}
  1. is it alright to use HashMultimap in this case? Am i not lacking understanding of some basic concept of the thing im trying to achieve? It seems like it does its purpose (couldnt quite get it to work along the lines of your example of

Multimap<GridCell, GameObject> index = MultimapBuilder.hashKeys().hashSetValues();

  1. The method AddObject seems to put every object in one cell regardless of their current vector. Any idea why is that?

You should use the builder. If you look at the Guava javadoc you can see that I accidentally left off the build() on the end.

No, I don’t know. You should log/println the object’s position and the cell that is found.

I use this class all the time so I know Grid works. So it’s probably a setup or perception issue.

Ad 2. Alright,it’d overwrite the vector due to a newbie mistake in class GameObject.
Ad 1. true, i should’ve looked into the documentation first rather than tinkering around.

Overall, thanks for pointing me the solution. I’ll share my code for if someone was looking for something similar in this topic this evening when i am done with putting object into more than one cell depending on its radius.

1 Like

@pspeed Alright so i;ve been testing out adding the object to different cells as it would best suit my needs, and i cannot think of any effective and cheap solution for my problem.
here’s the code:

public static void check(GameObject gameObj){   //doesnt work with gameObject of radius bigger than grid size
    cell = worldGrid.getContainingCell(gameObj.getPosition());  
    Vec3d position = gameObj.getPosition();
    double maxX = position.x+gameObj.getRadius();  
    double minX = position.x-gameObj.getRadius();  
    double minZ = position.z+gameObj.getRadius();  
    double maxZ = position.z+gameObj.getRadius();  

    
    Vec3d minimum = new Vec3d(minX,minX,minZ);
    Vec3d maximum = new Vec3d(maxX,maxX,maxZ);
    if(maximum.x > cell.getWorldOrigin().x+gridSize){  
        index.put(cell,gameObj);
    GridCell newCell = worldGrid.getContainingCell(new Vec3d(maximum.x,position.y,position.z));
    index.put(newCell,gameObj);

    } if(minimum.x < cell.getWorldOrigin().x){
    index.put(cell,gameObj);
    GridCell newCell = worldGrid.getContainingCell(new Vec3d(minimum.x,position.y,position.z)); 
    index.put(newCell,gameObj);

    } 
    if(minimum.z < cell.getWorldOrigin().z){
    index.put(cell,gameObj);
    GridCell newCell = worldGrid.getContainingCell(new Vec3d(position.x,position.y,minimum.z));
    index.put(newCell,gameObj);

    } if(maximum.z > cell.getWorldOrigin().z+gridSize){
    index.put(cell,gameObj);
    GridCell newCell = worldGrid.getContainingCell(new Vec3d(position.x,position.y,maximum.z));
    index.put(newCell,gameObj);

    }
   GridCell testCell = worldGrid.getContainingCell(new Vec3d(1,0,1));

    System.out.println("000 contents" +index.get(testCell));
    testCell = worldGrid.getContainingCell(new Vec3d(6,0,6));
    System.out.println("101 contents"+index.get(testCell));
    testCell = worldGrid.getContainingCell(new Vec3d(1,0,6));
    System.out.println("001 contents"+index.get(testCell));
    testCell = worldGrid.getContainingCell(new Vec3d(6,0,1));
    System.out.println("100 contents"+index.get(testCell));
    
    
    }

and here’s the geometrical representation


as you can see (and tell from the code), its impossible for the object to occupy 4 fields with this method. What is the most performant way to get the real radius? I guess its NOTcalculating the point between radius’ ends and checking its position, am i right?

From my original post on the subject:

You need to implement a set of loops that loops through all of the min to max grid cells as I’ve done above in 3d.

…then the object would be added to all four cells.

alright, indeed, i made it work. the problem is it really has an impact on performance as with 15 gameObjects frames drop to barely playable.

Yes, if you are doing this add/remove stuff all the time it will be slow… which is why my original post talked about a different way:

In that case, you just keep track of the cell the game object is in, see if it is in a different cell now and move it from the old to the new. It’s very fast. If that slows your game down then you have other problems.

Then you move the cell-traversal to the collision checks… which presumably happen less often than “objects moving”.

Okay, but there’s a couple things i dont understand in such approach. Is it supposed to check neighboring cells every loop update? If so , it are there no prerequisites for a cell to be checked?

How many objects do you have? Which ones move? How big are they on average? Are they all the same size? Do you need collision checks between all of them?

You are going to pay a price sometime. Where you pay it is the only thing in question.

Edit: also, if you only have 15 game objects then something else is wrong because you could have done the brute force approach without issue, ie: no indexing at all. You could scale up to hundreds of objects doing collision checks between all of them without much problem.