Sparse Spatial Grid Plugin by Stormtide Ltd.

Available now on the Unreal Engine Marketplace!

What Is it?
Sparse Grid is a high-performance spatial sorting system for Unreal Engine 4, allowing developers to perform ultra-fast searches for nearby objects without the need to use collision sweeps or actor iterators.

The plugin quickly integrates into any existing C++ or BP project. Simply use the editor tool to define the play area of your world (or update it on-the-fly), and add the Sparse Grid Component to any actor you want to register with the grid. You can then use the built-in search queries (or write your own) to lookup those actors incredibly quickly.

Why do I need it?
We use this plugin for all our internal projects - it greatly benefits the following:

  • Any area-based searching (AI, Seeking Projectiles, Damage, Impulses etc.)
  • Large worlds or worlds with high actor counts.
  • Large projects with complex or unique collision settings.
  • Reduces the N[SUP]2[/SUP] problem significantly. (Lots of objects all querying lots of other objects)
  • Developers of RTS or similar high-unit-count games.
  • Or if you just need a super-fast way to find nearby actors often!

Technical Details

  • Written entirely in C++
  • Neatly exposed to Blueprint.
  • Built for performance and flexibility. Sorting is extremely fast and transparent, requires no network bandwidth and memory allocation can be carefully tailored to suit each world.
  • Intended for all platforms (Tested on Android, Windows, PS4)
  • Seamless support for Multiplayer, Large Worlds, Streaming Levels, Procedural Worlds and World Composition.
  • Five built-in search queries (Sphere, AABB, Box, Cone, Capsule).
  • Exposed methods allow you to build you own project-specific search queries (C++ and BP), and benefit from the grids performance.
  • Includes several custom macros for ease-of-use in Blueprint.
  • Extendable API and full source code – customise the plug-in to your project needs.
  • Fully documented code. Tutorials and Documentation coming soon!
  • Full support for UE4 profiling tools and includes several custom debugging/monitoring tools, such as heat mapping.
  • E-Mail support.
  • Available for UE 4.18 (excluding Mac/IOS) and above (All Platforms)

What does it include?

  • Sparse Grid World Manager
  • Sparse Grid Actor Component
  • Sparse Grid Editor Toolset & Debugging Tools
  • Sparse Grid Blueprint Macro Library
  • Sparse Grid Blueprint Function Library

Preview Images




3 Likes

Version 1.1[4.18-4.20]:

  • Fixed compiler warnings for UE4.20 and 4.29 when using source build.

Version 1.3 [4.18-4.20]:

  • Fixed an issue where inactive components would be registered incorrectly.
  • Fixed an issue where the grid bounds were not being updated properly, rejecting searches with small numbers of objects.

Version 2.0 [4.21]:

  • **NEW! **Rewrite of the Sparse Grid System. Grids are now templates providing more flexibility to C++ users.
  • **NEW! **You can now create multiple grids for different object types (C++ Only).

I am throwing money at the screen but nothing is happening!

Man, this is awesome! Congrats :slight_smile: Can’t wait for release :smiley:

Expand this to the third dimension and i’ll definitely buy it.

Searching takes place in 3D, sorting does not (see post below).

It’s generally been that case that sorting into the third dimension actually just adds complexity without offering any performance gain (usually the opposite!)

I would like to see 3D Sorting if possible. I am currently building a space combat and trading game and it would be greatly appreciated if that was added :slight_smile:

Also I forgot to ask - What is the planned price for this?

I haven’t put much thought into the pricing yet, as I’m still adding features and tools. It won’t be expensive, somewhere in the $20-35 USD range if that seems reasonable? It’s hard to know how to price things on Marketplace to be honest - I’m not sure how well C++ plugins sell, and it’d be nice to at least break even on the time investment :slight_smile:

Working on the tools right now - you can now view density heatmaps for each world :slight_smile:

Good to see that 3D is going to be for this :slight_smile:

A day one pick up for me :slight_smile:

Quick update folks.

I’ll cut to the chase - I’m not going to continue with the 3D sorting for now. I’ve spent some time partially implementing it - but in practice and with some profiling it’s turned out to just be a detriment to performance in all situations. Both sorting and searching is considerably faster without it even with a highish number of evenly distributed entities on X, Y and Z. 3D sorting also has a significantly higher memory requirement.

The extra cost involved also has some backlash on the existing version too, as allowing for other grid types increases the number of virtual calls and makes exposing the system to blueprint much more complex.

To keep things simple and maintain performance, the initial release will only contain the 2D grid. I will however keep the extensibility that I’ve added so far, so that users can add custom grids if they like (3D, Quadtree’s, Octree’s etc.) - and expose them how they see fit.

Should be ready in a week or two :slight_smile:

Update - just added the ability to export heatmaps. Working on adding this as an automation feature, so you can debug object density over time.

https://forums.unrealengine.com/filedata/fetch?filedataid=131866&type=thumb

Update

Okay the system is finally ready for testing! I’m working away on documentation, meanwhile I have a couple of users testing the system out to ensure it does what it’s supposed to. Should be submitting the plug-in soon.

I’ve updated the OP with some new screenshots. Enjoy!

This seems very interesting, and could probably be sold at an even higher price IMHO.

Good job, keep us informed!

First submission is in!

I’ve set an initial price of $34.99 which feels like a bargain given all the things that can be learned from it and the problems it solves, I may adjust that later on as I add or adjust features!

Any ETA on this hitting the marketplace?

Soon, I had a few compiler errors to fix for Mac and also switched over to the IWYU model. Everything appears to be working correctly now. Submitted what is hopefully the final version last night, so within a day or two I hope!

Note: I’ve had no choice but to suspend Mac / IOS support for the 4.18 version - but 4.19 supports it fine. There is a compiler error when using XCode 9.3 and above which was fixed in 4.19 but not 4.18. If you want to ship to Mac/IOS in 4.18 you can, but it requires building the plug-in yourself with an earlier version of XCode and adding the whitelist platforms back in.

That one made my day :smiley: Grabbing one too.

@TheJamsh I was thinking on the 3D case, maybe a fast solution would be select a number of cells to search for N steps above and bellow by M distance each step. This would reduce the overhead to do it completely for the whole plane projected in 3D, reducing to the interest areas only for a certain depth. The precision would be adjusted by the steps * distance affecting only the selected cells.

I am too looking for an application for aerial/space combat, and that would be great.

That’s already the way it works when it comes to finding the cell tile to search, so any cell outside the bounds of the search has no cost whatsoever - they aren’t looked up. I applied the same logic to the 3D case when I tried it.

It seems counter-intuitive to what you’d expect, but sorting cells into 3D never gave any benefit even with objects spread far and wide on the Z axis. BTW - objects are still filtered in 3D space, so while the first stage of searching takes place in 2D, the result is still the same as a 3D search :slight_smile:

2 Likes

Thats even more awesome. Hope see it released soon then!