Entity Manager (Searchable)

Game Mechanics
#1

So I set out to make an entity manager that would allow individual entities search for other entities and get limited amounts of entities for processing, like collision detection. Well here is what I came up with:



package mbs.exodus.managers;

import java.util.ArrayList;

import mbs.exodus.game.entities.Entity;

public class EntityManager
{
	public static ArrayList<Entity> entities = new ArrayList<Entity>();
	
	public static void registerEntity(Entity e)
	{
		if(e != null)
		{
			entities.add(e);
		}
	}
	
	public static void removeEntity(Entity e)
	{
		if(e != null)
		{
			e.destroy();
			entities.remove(e);
		}
	}
	
	public static Entity[] getEntitiesByOwner(String ownerID)
	{
		Entity[] e = new Entity[entities.size()];
		entities.toArray(e);
		return getEntitiesByOwner(ownerID,e);
	}
	
	public static Entity[] getEntitiesByOwner(String ownerID, Entity[] sample)
	{
		ArrayList<Entity> list = new ArrayList<Entity>();
		for(Entity e : sample)
		{
			if(e.getOwnerID().equals(ownerID))
			{
				list.add(e);
			}
		}
		Entity[] entityArray = new Entity[list.size()];
		list.toArray(entityArray);
		return entityArray;
	}
	
	public static Entity[] getEntitiesByLocation(int x, int y, int radius)
	{
		Entity[] e = new Entity[entities.size()];
		entities.toArray(e);
		return getEntitiesByLocation(x,y,radius,e);
	}
	
	public static Entity[] getEntitiesByLocation(int x, int y, int radius, Entity[] sample)
	{
		ArrayList<Entity> list = new ArrayList<Entity>();
		for(Entity e : sample)
		{
			if(Math.abs(Math.sqrt((Math.pow((x - (e.getX() + e.getSizeX()/2)), 2)) + 
					(Math.pow((y - (e.getY() + e.getSizeY()/2)), 2)))) < radius)
			{
				list.add(e);
			}
		}
		Entity[] entityArray = new Entity[list.size()];
		list.toArray(entityArray);
		return entityArray;
	}
	
	public static Entity getEntityByClick(int x, int y)
	{
		Entity entity = null;
		for(Entity e : entities)
		{
			if(x < (e.getX() + e.getSizeX()) && x > e.getX() && y < (e.getY() + e.getSizeY()) && y > e.getY())
			{
				entity = e;
				break;
			}
		}
		return entity;
	}
}

So an individual entity can ask the manager for only the entities within firing range for example (no need to do operations on things out of range)
or you can ask for only the entities within visible range, so you only render entities visible on the screen
lot of things you can do…

My only concern is when there are thousands of entities registered with the manager… if asking for limited entity sets every update is actually slower than doing operations and decision logic on all the thousands of entities every update instead. I will only know when I have thousands of entities! haha!

Anyway I thought I would share, and hopefully get some pointers, and maybe inspire someone to climb one step higher in the quest for the perfect entity manager!

#2

If you are worried about performance, a small think you can do is to change the if comparison in getEntitiesByLocation to:


float x1= x - e.getX() + e.getSizeX()/2;
float y1= y - e.getY() + e.getSizeY()/2;

if (x1*x1 + y1*y1 < radius*radius) {
  list.add(e);
}

You get rid of the relatively expensive square root operation and replace two Math.pow operations for faster multiplication calls. It’s a micro optimization but could make a difference when dealing with large numbers of entities. Also is there a reason you flip between lists and arrays? Given that you are already storing the entities as lists, why not have the functions return lists of entities rather than converting them to arrays?

#3

For dealing with thousands of entities in a frequently called game loop, I wouldn’t create array copies each and every time. Theoretically its good for protecting the private members (if entities was private here…).
Instead, a visitor callback would be an alternative.
If you want to return copies, lists are more flexible and abstract than arrays.
Then, using enhanced loops creates lots of avoidable iterators in the background.
If you absolutely need static access, instead of making each method static, rather deal with a static entity manager in a whole.

So far for my suggestions :slight_smile:

#4

Using purely algebraic reductions that you’re familiar with is a good habit to get into. Calling Math.pow with an integer (esp small) exponent should be avoided (bad habit)…it’s much much slower and less accurate (plus it’s more typing). Not that the accuracy is likely to be important.

#5 
public static Entity getEntityByClick(int x, int y)
   {
      Entity entity = null;
      for(Entity e : entities)
      {
         if(x < (e.getX() + e.getSizeX()) && x > e.getX() && y < (e.getY() + e.getSizeY()) && y > e.getY())
         {
            entity = e;
            break;
         }
      }
      return entity;
   }

I think that break would only break out of the if-clause. Thats better IMO:

public static Entity getEntityByClick(int x, int y)
   {
      Entity entity = null;
      for(Entity e : entities)
      {
         if(x < (e.getX() + e.getSizeX()) && x > e.getX() && y < (e.getY() + e.getSizeY()) && y > e.getY())
         {
               return e;
         }
      }
      return null;
   }
#6

No, it will break out of the for loop.

#7

Okey… that version was strange anyways. So if that code would break out the for loop, why do it that way, and not just return ?

#8

Not sure for the OP’s motivation, but some believe that a function or method should only have a single exit point (let’s forget exceptions for the moment). You can Google function single exit point to find links to various discussions. In a method this short I don’t think it matters.

#9

LOL… Then I did that wrong for sooooo much functions… :smiley:

#10

Personally, I don’t see anything wrong with having multiple exit points. If your methods are relatively succinct (as they should be!) then I don’t see any practical or theoretical negative consequence of having multiple return statements.

#11

I’m a big believer in early returns for edge cases right up at the top so you don’t have the rest of the code stuffed inside conditionals ending with a diagonal wall of curly braces. Even scala, which eliminated ‘break’ and ‘continue’, has a ‘return’ statement that can break out early (you don’t otherwise need it at the end).

Structured programming is a good guideline for clarity, but it shouldn’t get in the way of clarity.

#12

The EntityManager looks pretty neat, although it would be cool if its functionality was broken out into multiple areas. For example, collisions usually should be handled altogether, so once per frame you might calculate all collisions and store the results somehow with very quick access later. Your code means that every single entity is going to need to perform a check that could be very redundant, so your code will be extremely expensive in comparison.

But if you don’t have that many entities, who cares?

#13

Eli: That sounds distinctly like knowing in advance something is going to be a performance issue and coding to handle it in advance.

BTW: Spatial partitioning approaches exponentially faster for spatial queries. A nice simple method is to simply have the entities stored in a uniform grid. Another simply option is sweep-and-prune.

#14

Pffffft. Don’t bring that argument into another thread. And notice I said “but if you don’t have that many entities, who cares?”

Writing collision with arbiters is just as much work and is faster too. So why not bring it up? It’s a suggestion only.

#15

Thanks for all the tips! Yeah, to be honest, I have no idea why I was converting to regular arrays! I even create new ArrayLists in each method! Thanks, Actual, for the tip on the math for the getEntitiesByLocation method, small performance boost, Ill take it! As far as the static access is concerned, It is just easier for the rest for the program to have static access. I could make it into a nested static class, but I couldn’t be bothered! haha! I plan to add a few more methods to help with collision detection, but I won’t work on that until later.