On 04/12/2017 at 1:59 PM, frob said:

How many units have you got in order for this to be repeated tens of thousands of times?  Each unit doing the scan should only scan the four neighboring cells for a list, and choose one from the list if the list is not empty. 

It's a 2D game with a very basic art style because I want to push a maximum number of units. As of now, I'm only picking the first target and ignoring the others to save on CPU cycles.

On 04/12/2017 at 1:59 PM, frob said:

If you're doing those things already and still have "tens of thousands of times" every second, it would mean you've got 20,000+ units out there all looking for actions.   

Yes. The initial prototype of the game with nothing but unit movement would have 500 000 units at ~20fps (only a fraction are on screen, but they're all moving). As I started to add combat and collision, it quickly started going down. Right now, I'm trying to find the balance between simulation accuracy and unit number.

On 04/12/2017 at 1:59 PM, frob said:

Why is every unit constantly scanning? Shouldn't they only scan when their current action is complete, which typically means once every 1-2 seconds?

That's gonna sound ridiculous, but my game stutters if my units aren't scanning constantly. I think it has to do with my threaded code because it stops stuttering with multi thread disabled, but my framerate drops by a lot. Right now, I'd rather keep the constant scanning + multi thread because it gives me both higher framerate and no stuttering which can be improved by reducing the scanning time without reducing its occurrence.

21 hours ago, JoeJ said:

Maybe bad memory layout or too much indirection. Maybe you should sort entities so they match grid memory order to improve caching.

My grid contains cells that own lists of pointers to entities that are in the cell. Cells are packed in the grid, but I can't pack entities in cells because they're can be many entities in one cell.

9 hours ago, Kylotan said:

How do you determine which the 8 surrounding grid squares are? These should be O(1) operations but it's possible to get this wrong.

I dynamically calculate the bounding box coordinates around the unit and iterate through these as indexes inside the grid. I did it that way so that if I want units to have a longer range than 1 cell, I can just give it a radius in cells and it gives the bounding box around the unit which can be scanned for enemies.

9 hours ago, Kylotan said:

How is cell.get_entity implemented? If there's only one entity possible there, this too should be O(1), but again, maybe this is wrong.

Many enemies can be in a cell, but you'll always only see one. The collision guarantees that if there's an enemy in the cell, then there can be no friendly.

Entity cell.get_entity()
{
        return this->entities.first(); // entities being a list of pointers
}     

9 hours ago, Kylotan said:

How is isEnemy implemented?

By team id comparison.

bool Entity.is_enemy(Entity other) {
	return this.team_id != other.team_id;
}

51 minutes ago, Michael Aganier said:

22 hours ago, JoeJ said:

Maybe bad memory layout or too much indirection. Maybe you should sort entities so they match grid memory order to improve caching.

My grid contains cells that own lists of pointers to entities that are in the cell. Cells are packed in the grid, but I can't pack entities in cells because they're can be many entities in one cell.

Probably that's it. The lists will be dynamically resized, so dynamic allocation. Lists will be scattered through memory, so bad cache utilization, and probably garbage collection does the rest.

If your entities are small enough, you can use a linked list instead:

cell.ptr -> entity55.next_ptr -> entity87.next_ptr -> null

Inserting is fast (just insert at the cell), and removal too (faster with double linked list - worth if lists are large). 

Downside: Each entity can only be linked to a single cell. This works if the entity bounding box is not larger than the cell size. For each cell you need to check neighbours to find all entities that intersect it, but i assume you get a big speed up. (Same concept as in a loose quadtree, which would solve the max size limitation.)

1 hour ago, Michael Aganier said:

That's gonna sound ridiculous, but my game stutters if my units aren't scanning constantly. I think it has to do with my threaded code because it stops stuttering with multi thread disabled, but my framerate drops by a lot. Right now, I'd rather keep the constant scanning + multi thread because it gives me both higher framerate and no stuttering which can be improved by reducing the scanning time without reducing its occurrence.

You should really consider detaching your logic and rendering timesteps from one another. There's no reason that logic updates should have any impact on the framerate.

Ideally, you'd perform logic updates (for the moment continuously) on a background thread. Copy data for only units which (a) are within the camera bounds, and (b) have taken an action recently into a separate data structure to be used by the main rendering thread.

1 hour ago, Michael Aganier said:

On 4.12.2017 at 7:59 PM, frob said:

Why is every unit constantly scanning? Shouldn't they only scan when their current action is complete, which typically means once every 1-2 seconds?

That's gonna sound ridiculous, but my game stutters if my units aren't scanning constantly. I think it has to do with my threaded code because it stops stuttering with multi thread disabled, but my framerate drops by a lot. Right now, I'd rather keep the constant scanning + multi thread because it gives me both higher framerate and no stuttering which can be improved by reducing the scanning time without reducing its occurrence.

If you don't want to deal with threading now, you could distribute the work equally over multiple frames e.g.:

frame 1: update entities 0-999

frame 2: update entities 1000-1999

etc.

2 hours ago, Michael Aganier said:

I dynamically calculate the bounding box coordinates around the unit and iterate through these as indexes inside the grid. I did it that way so that if I want units to have a longer range than 1 cell, I can just give it a radius in cells and it gives the bounding box around the unit which can be scanned for enemies.

You explaining how the code works is not the same as posting the exact code. If you want precise feedback instead of vague guesses every time you add more information that someone randomly asks for, post the exact code.

---

The is_enemy function should probably take an entity by (potentially const) reference or pointer -- might be cheaper than copying it around. At least if it's a big class/struct.

I'm not really familiar with this type of game, so take this with a healthy pinch of salt...

But why do you need to have pointers to each individual unit? Surely you only need to keep track of the number of units of a given type (infantry, cavalry, artillery men, medics etc.) within the cell - it's not like each soldier has a name and personality you need to take into account. You could handle health by just keeping track of the average health of each type within a cell, rather than individually. If the player moves some troops out of the cell, just subtract the numbers from the original cell, and add them to a new one.

This would massively reduce the number of checks you need to do, and combined with a quad tree for your cells would reduce it even further.

9 hours ago, Michael Aganier said:

500 000 units at ~20fps (only a fraction are on screen, but they're all moving).

That's a large number.  It takes significant care to reach that kind of number, about 10M updates per second.  There are some CPU-based particle systems and heavy computing systems that handle it, but it requires attention to details like cache effects and data sizes.

If you're randomly hopping around in memory you won't hit that on modern systems. You'll likely be running into memory bandwidth and timing issues unless you're carefully organizing data to properly stream to the CPU.

I don't understand the question. You're using a grid for collision detection, so you can't really do better than that. Most generic physics engines divide collision detection in two phases, the first just reduces to a possible set of collisions, the second does the proper collision detection... and on top of that, they mostly use BVHs and SweepAndPrune algorithms that scale "logarithmically" instead of "linearly" (a grid). 

2 hours ago, RnzCpp said:

I don't understand the question. You're using a grid for collision detection, so you can't really do better than that.

That was basically the question. I'm not very familiar to how other games do it so I wanted to know if there was a better way to do it. Since it seems like the fastest say, the next point was about how to improve my implementation.

10 hours ago, Lactose said:

You explaining how the code works is not the same as posting the exact code. If you want precise feedback instead of vague guesses every time you add more information that someone randomly asks for, post the exact code.

You are right. I'm reluctant to posting the exact code because it calls many sub functions who themselves call more functions. I would have to copy bits of code from everywhere to get the whole thing. I know I'm being vague, but everyone's advice has been helpful nonetheless.

Having followed this thread and your other on sprite rendering.. the bigger question that comes to mind is why you want to run AI / physics / individual rendering on 500K units? Granted, considering such large numbers can be an interesting optimization and theoretical exercise, but there may be unforeseen issues in valmorphanizing this into a game.

Aside from the psychology aspects of this, I think one of the key points is that games often don't do what you think they do. Games are all about smoke and mirrors. A good game programmer will make you think they are individually processing 500K units, but really be processing maybe 50 groups, and using a bunch of statistics / randomization / precalculated results, to give you something that *looks like* that number.