Octrees

It was finally time to add some more efficient ways of finding ships based on their location. Things like finding closest ships to some location or all ships inside some radius around that location is needed in many places. For example when a ship wants to find the closest enemy or when some phenomenon affects all ships within some distance. So I implemented an octree to be used in the battle for this purpose. The benefits of the octree is that when looking for ships near some location, the algorithm can first iterate the bigger cubes and check if anything inside that can be close enough to the location. If not, every ship under that cube and its subcubes can be ignored, otherwise each subcube is again considered. Managing the octree of course takes some work, but with lots of ships the benefits greatly outweigh the costs.

In the video you can see visualization of the octrees and an example of its use. There are 200 ships per side, and for each frame and for each ship the closest ship from the enemy army is found. The closest ship is visualized with a blue line for the first army and with a red line for the second army. In a real case, the nearest ship search is done much more rarely, maybe closer to once per frame than 400 times per frame like here. Also, usually there should be some max distance in the search which also makes it a bit cheaper. This is not a real performance test since it is only run in the Unity editor, which makes this a bit slow for other reasons.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: