Best way to efficiently update 2D Grid of collisions

Good afternoon,

I’m looking for some help theory crafting the most efficient way of updating the occupation status of tiles in a 2D Grid for an RTS (Warcraft 3 will be my RTS of choice and the one I’m trying to re-create).

Example: Lets say you have a large map comprised of 1000x1000 tiles (1,000,000 total tiles) that could have up to 10,000 units running around at any time.
Note: The large arbitrary map size & units is just for discussion purposes.

Question: What is the most efficient way of updating the 2D Grid of what tiles are occupied or unoccupied. (For the reasons of Pathfinding & dynamic visual feedback when placing a building)


A brute force way might be to…

  • Have a Tick on each of the 10,000 Actors that periodically tells the Grid its Location. Which tells the Grid to update the cell(s) its located in.
  • Have the Grid hold a reference to all 10,000 actors and iterate through them on Tick periodically and updating the tiles.

I started to think of some smarter ways of doing this. I thought…

  • Having a Event Dispatcher on an Actor that emits a signal whenever its position changes could work. But I haven’t yet found a way to detect a position change to call a ED, does one exist that I have overlooked?
  • I thought about having the Character Movement component emitting a Delegate as well. But I haven’t found anything in the C++ code yet. Although this might not be enough as characters can be moved around by external forces (Blinks, Pushback, etc…)

The easiest way is to do a line trace towards a position the moment you want to build a building somewhere and see if it returns another building or not. Pathfinding is more complex, if you’d do something like AStar you need to run over an entire grid to check for obstacles and store optimal path data until it finishes. Units should also not all pathfind individually, merge this into squads or a single manager. You can also assume everywhere can be walked on unless a 2D position is stored in an “unwalkable” array. Last option I think of is caching any available path found by your pathfinding algo to move any nearby squad over, this path would be cached until the map changes in a way that invalidates the path(s).

Just for discussion purposes…

You can get the actors position relative to the grids center and calculate the index of the surrounding tiles without having to trace or iterating the grid array. An actor can “look ahead” for enemies (occupied tiles) at a certain region, check for surrounding tiles at location to place buildings, etc.

For example:


GridItr

This is for a grid that is an array of structs and not actors or components placed in the world. The spawned actors in this example are just for visual aid.

To add to this, if you don’t want to add all grid spaces to the array initially, you could also use a TMap of 2D int vector to value, where the key is the XY on the grid. This is more common if the initial state of the grid spaces is irrelevant.

// Shown as bool here "CanWalk on key?" you could store a struct there containing any data you need.
TMap<FIntPoint, bool> GridData;
1 Like

Thanks everyone!

Units should also not all pathfind individually, merge this into squads or a single manager.

Do you have any examples to why this would be a better idea over each unit pathfinding individually? I’m trying to think of what the pros vs cons of going with either way.

You can get the actors position relative to the grids center and calculate the index of the surrounding tiles without having to trace or iterating the grid array. An actor can “look ahead” for enemies (occupied tiles) at a certain region, check for surrounding tiles at location to place buildings, etc.

Thanks! I really appreciate the Image & GIF you posted their. I will give this a try!

Speed. If you use a pathing algorithm just to define walkable tiles you can do that once and let your units read from the map it stores: Is X3Y6 walkable?

Further speed improvements if you use a pathing algorithm to actually get a fastest path to get a unit from A to B if you put that unit in a squad at the same position and let the squad path forward instead of the 20 units you put in a squad. You wouldn’t want to AStar on 20.000 units simultaneously if you are actually controlling 4 squads packed together at squad locations. Going from running the algorithm from 20.000 to 4 times is something you can’t ignore.

At most you would want to path a unit to stay in formation to a close spot, avoiding near walls, and only when moving.