So, you are ready to populate your world with different kinds of creatures. And before you immerse yourself in mysterious AI trials, there is one important problem to solve. How to actually run this populated sandbox? How to make all inhabitants aware of each other and make them respect each other’s private space and not noclipping through solid walls while executing their own behavior.
The obvious approach is that each monster before taking a step should ensure that it’s new position will not cause intersection with anything else on the scene. Practically, this approach assumes that all the sandbox is just a 2-level nested ‘for’-loop. The outer loop will walk over monsters’ collection making them attempt a step, the inner loop walks over scene.meshes collection (which also assumes monsters meshes), to confirm the eligibility of the step. And honestly, I think you should follow that approach if your scene is relatively simple, small, and monster population is no more than couple of hundreds. Don’t overthink it, when it’s unnecessary.
But sometimes (most of the time) we want to see big spacious interconnected levels with Ks and 10Ks of monsters. Sometimes we’re talking slaughter maps. Since your game definitely lacks “that one” secret level, sooner or later you will need them. You will need sectors.
Fair warning. If your monsters are using very detailed meshes, then on high populations the rendering algorithm most likely will die before the collision algorithm. But who says that your monster meshes should be complex? Who said they should be meshes at all?Sectors not only relieving your monster step computations, they are also handy when we want to check which monsters were affected by your rocket explosion or which monsters should regenerate while within healer range and other things like that. But we will not address it here.
Not gonna pretend, the sectors under the hood are not an easy concept. Come on, it’s a real hardcore. But I will try to explain everything below in as detail as possible. No fear, you will get that.
Code is here: https://playground.babylonjs.com/#DF4HVX#55. The explanation is below.
And before we start to dig into the sectors themselves let’s configure some supplemental manager classes.
0. Pre setup.
Class WorldBuilder is just a collection of factory methods that create static objects on the scene. For now, it can create a solid wall and a monster blocker which is just a wall but invisible. Invisible monster blockers can be used to prevent monsters from going to places where they should not go. For example, they don’t allow stupid monsters to fall from the edges. The only real purpose for WorldBuilder class is tracking what we’ve created. You may notice that regular walls are added to both this.walls and to this.monsterBlockers collections. It’s because walls can block monsters as well (quelle surprise). Class Wall in hindsight is just a wrapped over BABYLON.MeshBuilder.CreateBox method.
Class MonsterManager is used to populate the world with monsters. And its updateFunction is pretty much our monster sandbox runner. We will call it each step to progress the monster’s world.
Two other important classes are Monster and MonsterInstance. Monster class is a monster descriptor, that defines monster’s mesh and other appearance or constant properties. Monster.spawnInstance method creates a MonsterInstance instance. MonsterInstance is a class that contains dynamic properties like position and behavioral methods. MonsterInstance class has its own updateFunction which makes current instance do something. In our case the MonsterInstance instance will try to do a step in random direction. It will do 6 attempts, then give up till the next cycle. Actually, this is how later you can detect monsters that are potentially stuck between the walls.
You may notice that our basic MonsterInstance extends ChainEntity class. Our ChainEntity is a typical Linked List data structure item. It contains expected prev and next properties as well as something expected in BabylonJS world, like instanced mesh (or even regular Mesh), position, etc. this.type is supposed to be a reference to an actual class that was instantiated (meaning any child class of ChainEntity). It might be useful if we want to have access to static methods of the class from the instance of that class.
1. Design decisions.
Basically, sectors are spacious partition design pattern. I took inspiration from this book: https://gameprogrammingpatterns.com/spatial-partition.html. I highly recommend reading it completely. At least read the article from the link. There is only a very brief and simple introduction into the pattern (and this is good about that article). We will go far beyond that, but knowledge from that article will help you to understand better the idea of what sectors are.
Our partitioning will happen only in 2D space (on the XZ plane). And this is enough for almost all possible situations. Because most of the levels in 3D games are relatively flat. Even if action is happening inside of the skyscraper, it’s very rare that a level contains more than 5 floors when one floor is exactly above the other. Even in 3D space simulators verticality is not really overused. Just because it’s practically unplayable, because player can’t see forward and up or down at the same time and the necessity of excessive memorization of level layers might be overwhelming. I am trying to say that it’s highly unlikely that your game will have high entity density along the Y axis. So, let’s not overcomplicate things (as if it’s not complicated enough yet).
Things could be a bit easier and faster if we would agree to put all in-game entities only in positive quadrant (x>0, y>0, z>0), but I don’t want to limit creator here, so our sectors grid is supposed to work even when crossing the axis.
2. Initial terms.
Let’s assume that our desired sector width is 50 and maximum map size AKA grid resolution is 1000x1000 sectors. My code allows you to set other desired values, but for simplicity I will always refer to default values mentioned here.
Also let’s assume that we look at our sectors grid from the top, so we see the XZ plane, and X axis increases to the right, Z axis increases to the top.
Let’s introduce some terms.
- Real coordinates. It’s the absolute position of the entity in BabylonJS. Nothing special here.
- Sector coordinates. It’s coordinates of left bottom corner of the current sector, meaning the point with lowest x and z coordinate in the current sector. We are defining sectors from that point.
- Sector number is a positive integer. The most bottom left sector has number 0. If we move to the sector on the right, we add 1000 to the sector number. If we move to the sector at the top, we add 1 to the sector number. So, sector number refers to relative sector position, it might be represented by formula
NstepsToRight*1000 + NstepsToTopfrom the sector number 0.
For any world entity we can compute all three terms. Terms are in the following relationship (arrow directions show what we can compute from current term):
Real coordinates->Sector coordinates<-->Sector number
So, from entity absolute position we can calculate the current sector coordinates and sector number. Since we know where our grid starts, we can revert the sector number back to sector coordinates using known sector width.
You must put grid manually for now, by providing real coordinates of bottom left corner and up right corner. In code we call these coordinates minX, minZ, maxX, maxZ. While providing grid coordinates you should not worry that they should fit the whole amount of sectors. Algorithm can adjust the provided coordinates to make the grid complete (fully automatic grid dispatch: work in progress).
Just keep in mind that sector coordinates are coordinates of sector’s bottom left corner. So, on the right and top sides maxX and maxZ define the limits where the lowest point of the sector should lie. Thus, the borders of top row and right row will be actually outside of provided minX, minZ, maxX, maxZ rectangle.
Confused? I think it’s a good moment to put the concept picture here.
So, the grid limits (minX, minZ, maxX, maxZ) are the solid outline. And the top and most right sectors are outside of this outline (their limits are dotted outline). But don’t worry about the dotted outline. Algorithm will take those sectors into account itself. Just remember, when providing grid limits you are describing solid outline from the picture.
Picture also shows how sector numeration works. You may notice that if we will try to get neighbor sectors for the left most sectors, we may get negative numbers. No problem, though. Such sector numbers are not registered in the grid and will be ignored. As well as sectors above the top row and everywhere else around the grid. Entities should not appear beyond sectors grid, so potential neighbor sectors in that space should be ignored.
3. Building the grid.
First you need to init SectorManager with sectorWidth (50 by default), maxResolution (1000 by default) and gridLimits (explained above). To actually generate the grid, you need to call the method calculateSectorGrid(). It will calculate some internal params (currently unused) and generate grids.
One of the most important methods is getSectorCoordinate(coordinate). It transforms any given real coordinate (X or Z) into corresponding sector coordinate. Function works the same way for both X and Z coordinates, because our sectors are perfect squares. getSectorNumber(x, z) gets the sector number for the provided real coordinates. As you can see it uses getSectorCoordinate(coordinate) method inside.
Our algorithm actually generates the 3 grids. All of them are JavaScript Map instances.
- Reference grid has sector number as a key and null as initial value. This grid is always empty. Keep it just for reference of initial sector structure (just in case for now, probably will never be needed).
- Static grid has sector number as a key and empty array as initial value. This grid will store static objects that never move from sector to sector. Practically monsterBlockers from
WorldBuilderwill be stored here later. - Dynamic grid has sector number as a key and null as initial value. This grid will store heads of Linked Lists, particularly the first
ChainEntity-like object of the list. Reminder: ourMonsterInstanceclass is a child class ofChainEntity.
After we finish building our world with WorldBuilder we need to call sectorManager.addStaticNodes(worldBuilder.monsterBlockers). The algorithm will extract vertices data from each mesh. Will sort vertices first by Z, then by X, then by Y. Then will filter out vertices’ duplicates.
Our monster blocker can occupy several sectors at once. So, the algorithm will get the sector numbers for vertices A,B,C of rectange and will find out which sectors were crossed by monster blocker. Technically it works even for diagonal walls, but the algorithm will include all sectors of horizontal and vertical differences. Ideally, we should detect if our monster blocker is isInclined() and filter out all sectors that are not actually crossed. Mathematically it’s possible, but I will not try to put it here, since this article is already big enough. Our algorithm will work even without that filtering.
When the MonsterManager spawns the MonsterInstance it puts it on dynamic grid as well. A new monster instance will be added to the head of the Linked List of the corresponding sector in dynamic grid.
4. Running sandbox.
This will process the monster movements:
scene.onBeforeStepObservable.add(function () {
if (!pause.pause) {
monsterManager.updateFunction();
}
});
Monster manager goes through all sectors and calls updateFunction() on each MonsterInstance. Monster instance generates new random position, puts the mesh into that position, updates world matrix. Checks if this movement is valid. If not, the monster will be returned to its previous position. The 6 attempts to move will be made. If all attempts fail, the monster instance will stay at the current position at least till the next turn.
testPosition(entity) is the method of SectorManager that checks if current entity position is valid. First it checks the current sector of the entity. Then if the entity is very close to some neighboring sectors, then those sectors will be checked as well. findNeightbourSectors(sector, x, z, radius) checks if any neighbors of the given sector should be included. Radius is the half of diagonal of monster bounding box (the longest distance from monster center where something might be intersected by the current monster entity). Current and all neighbor sectors are checked by testPositionInSector. Look at the magic &&= operator in testPosition method. It accumulates the test results. If some sector failed, then the whole result will be false.
testPositionInSector practically checks collisions with all items in static and dynamic grids in the given sector. This is exactly where we are gaining performance. Because we don’t need to check collisions of the current monster with all other monsters and walls. We are only checking monsters and walls that are assigned to the current sector (and neighbor sectors when we are close to the edge).
Collision is checked with standard BabylonJS Mesh method meshInstance.intersectsMesh(meshInstance, true).
Our approach is extremely precise, because we actually put the current instance into a new position and check it, then revert if something is wrong. A faster approach might be to teleport the original invisible mesh from Monster class to every target position (in this case we will call computeWorldMatrix(true) only once), but the original mesh may not possess rotation and pose of the current instance. If all your entities and monster blockers are axes-aligned, you can even use intersectsPoint method, but precision will be much worse and also intersectsPoint doesn’t support object-aligned bounding boxes. So, with diagonal walls it will not work correctly.
If testPosition(entity) passed and new position was applied, we need to change the current sector of the entity if it left the borders of original sector. Method swapSector of SectorManager checks old and new position of the entity and if new position is in another sector, then the entity will be moved to another sector in dynamic grid. The method carefully exatracts chain entity from Linked List; fixes the gap in that list; if our entity was first in the list then link to the new first element in the sector will be adjusted as well. Then method adds entity to another sector in dynamic grid.
5. Further improvements (not shown in the demo, here are just general thoughts).
We never check collisions with ground in sector manager, because in most cases monsters will always touch ground. Grounds should be handled separately. Each monster instance can generate downward ray and check the distance to the first ground-like collision. If distance is too long, then we should progress some movement along negative Y axis direction. Collisions with ground should never be blocking. For this reason, every surface that is potentially walkable should be explicitly marked as such, otherwise monster will get stuck if accidentally land on the crate or barrel. As an alternative, in case if collision with barrel detected, we can do a check how exactly monster touches the barrel. If only with the lower vertices (where the legs are supposed to be), then probably it’s fine. We already have a code that sorts vertices, so it can be reused for checks like that.
Stairs is another tricky example. But if we will make a wrapper class for stairs that will be used in WorldBuilder (same like we did with walls), then monster instance can detect that he is facing the stairs, not just a wall, and react accordingly. We will need to check somehow from which side monster is approaching the stairs and if it’s walkable side of the stairs he can init ascending/descending. As an alternative, we can calculate the height difference between “feet” vertices of monster instance and top vertices of obstacle. If the difference is not too big, we can allow to climb it. I would still mark stairs separately in order not to do checks for regular walls that are not supposed to be climbed.
6. Misc
If you are facing performance issues, then before trying to optimise the algorithm try to close browser DevTools console, remove all console.log entries and disable debugMode for WorldBuilder and SectorManager. They are more resourceful than you may think. (TODO: consider to use ThinInstance in drawGrid).
The sector width should be chosen very carefully in order to have a noticeable performance boost and avoid bugs. If you have monsters with bounding boxes bigger than 0.5*sectorWidth, monsters can still collide if there is an empty sector between them. You can also face the infamous “monster paralysis” bug when big and small monsters are on the diagonal sectors trying to jump into the same adjacent sector. This situation can be managed if the radius parameter for all monster instances will be equal to half of the diagonal of bounding box of the biggest monster in the scene. Or you can just leave this bug to see how those hardcore players are trying to exploit it (naturally this bug happens pretty rarely). But if you really want to have a big boss in your level and want to avoid those coincidences, put that boss on the platform unreachable for other monsters. As an option you can surround the platform with invisible monster blockers.
The movement logic is very primitive in my example, it’s just to show how sector works. Later it should become more meaningful, for example monsters should try to approach the player. To start figuring out that movement logic we all know whos videos to watch.
It’s still a prototype. So far it looks very robust, but I haven’t tested it yet in many situations. For example, when the whole grid doesn’t touch/cross axes. Potentially there still might be surprises and improvements.
Of course, the idea is known and my code still may need some polishing, but the original idea is so brilliant, so I definitely wanted to have my own take on it. It’s literally the most impressive thing I ever coded myself. I hope it will inspire someone else as well.
And check the “Debugging corner” at the end of the code. 
You can click on monster instance to reveal its name and position. Or you can just click on sector to print its inhabitants. You can also pause the processing.
Here is the link again, to avoid scrolling back and forth.
https://playground.babylonjs.com/#DF4HVX#55
Edit 2023-09-10: I found out that approach
const vertices = BABYLON.VertexData.ExtractFromMesh(node).transform(node.getWorldMatrix());
is destructive. It breaks node.checkCollisions = true functionality and makes you to be able to go through walls.
Safe approach:
const vertices = BABYLON.VertexData.ExtractFromMesh(node).clone().transform(node.getWorldMatrix());
I updated links to playground in the main post.
)