Fastest detection algorithm?

Recommended Posts

What you want to do is beyond what any games currently do. The Total War games work with far fewer units and they almost certainly perform hacks to simplify their logic.

I will add this: your grid is too small to give you much benefit and I expect the cache coherence is almost zero with rows that long. A more complex spatial database - perhaps even just a large grid of smaller grids - may give you significantly faster lookups much of the time, if it means that the 8 grid squares you're examining are almost always in the same cache line. But what you gain there, you might lose on having the 2 stage lookup, or on having to occasionally search across multiple large grid squares.

Share this post


Link to post
Share on other sites

I'm assuming your end game is some sort of gameplay like this 

 

or total war.

 

Btw, that video, though it's Unity specific, does talk alot about how one should set up their data structures for maximum throughput.  Though they only manage about 40k units at 60-70fps.

Share this post


Link to post
Share on other sites
3 hours ago, ferrous said:

I'm assuming your end game is some sort of gameplay like this 

Somewhat. I want the epic scale, but with physical rigidity.

9 hours ago, Kylotan said:

I expect the cache coherence is almost zero with rows that long. A more complex spatial database - perhaps even just a large grid of smaller grids - may give you significantly faster lookups much of the time

Indeed. I hadn't thought about it before, but since 8 cells are on 3 different rows, that means there's 3 cache line miss per collision detection. But what if instead of using a more complex system, I would just dumb down the collision detection accuracy? If I let enemy entities walk into a same cell, then all I have to scan is my own cell to see if there's any enemy up close. I'm not sure if that would still look anything like total war though.

9 hours ago, Kylotan said:

your grid is too small to give you much benefit

Why is that?

Edited by Michael Aganier

Share this post


Link to post
Share on other sites
4 minutes ago, ferrous said:

What do you mean by 'physical rigidity' ?

I think he means that there's only 1 unit per cell, in other words the units/positions are all quantized and there's no continuous movement of units across the map.  So, it's "rigid" in the sense that there's hard collisions at cell boundaries.

At least I think that's what he means.

11 hours ago, Kylotan said:

What you want to do is beyond what any games currently do. The Total War games work with far fewer units and they almost certainly perform hacks to simplify their logic.

I will add this: your grid is too small to give you much benefit and I expect the cache coherence is almost zero with rows that long. A more complex spatial database - perhaps even just a large grid of smaller grids - may give you significantly faster lookups much of the time, if it means that the 8 grid squares you're examining are almost always in the same cache line. But what you gain there, you might lose on having the 2 stage lookup, or on having to occasionally search across multiple large grid squares.

Maybe some sort of swizzled arrangement of the grid like for textures.  The lookups would involve more math, but you get better cache-coherency.   It might be a big win in this type of situation where the entire game is one huge grid with 1 unit per grid square.

Share this post


Link to post
Share on other sites

You could probably do some sort of culling.  IE in the following layout

 

xxxxxxxxxxxxxx

x00000000000x

xxxxxxxxxxxxxxx

 

Why are the 0s doing any scanning?  If you had them grouped as a 'regiment', then kept a list of the outer boundary of the regiment, you might get a bit of a speedup.  Though I don't know how much work it would be to determine the perimeter.  Though you also wouldn't have to do that every frame, either, just call it reaction time / battle awareness for your soldiers to realize that their rear line has disintegrated and they're now the rear line =)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now