How to make monsters not bump into walls and each other. Introduction to sectors

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: 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.

This is where OOP really shines. Differently looking `Monsters` may share same `MonsterInstance` and demonstrate same behavior or one `Monster` may spawn different `MonsterInstance` instances. So, monsters of the same kind will have different personalities. Not to mention that you can create your own hierarchy of inheritance for `Monster` and `MonsterInstance` classes. Limitless possibilities!

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: 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.

  1. Real coordinates. It’s the absolute position of the entity in BabylonJS. Nothing special here.
  2. 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.
  3. 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 + NstepsToTop from 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.

  1. 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).
  2. 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 WorldBuilder will be stored here later.
  3. 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: our MonsterInstance class is a child class of ChainEntity.
If we just want to check monster collisions there is no real need to use Linked Lists. It can be just an Array like the one in static grid. However Linked Lists might be useful when we want to compute mutual effects of the nearby monsters. One of examples is described in the book I mentioned above. So, I decided to keep that Linked Lists approach.

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.

It is worth filtering out unaffected sectors for diagonal walls. It will add an additional computation, but it happens only once for static monster blockers. Or you can just not use diagonal walls which occupies more than 1 sector. You can try to split long diagonal walls into the sequence of small ones.

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) {

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. :slight_smile: 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.

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.


Hey! Very impressive piece of code! :muscle:

I don’t want to discredit you or ruin your day :slight_smile: but I think this can be easily achieved by Yuka. To avoid the walls/areas one can use a navmesh with spatial index and to avoid bumping to each other or avoid dynamic obstacles there is an obstacle avoidance steering behavior or other behaviors which might fit into this scenario. Yuka is pretty damn optimized and fast.

@labris what do you think? Is this doable just with Yuka?

1 Like

Of course, other solutions exist. I just did my own (for educational purposes).
Currently I am developing the complete gaming engine with all mechanics on BabylonJS (mostly for self-education) and this is just a piece of that. It became that big already, so I wanted to share it.

Yuka looks interesting, I will definitely take a look at it more. What I noticed: on Yuka’s navigation example meshes still can intersect each other.

On First Person Shooter example please address this issue I can see those choppy movements.

As of now my engine already can do most of the things that Yuka can do, except that mine doesn’t look that visually beautiful, because I am really lacking 3D modelling and texturing skills.

1 Like

best way to learn new stuff…

because there are no behavior attached to them in the demo

there are tons of free models online, why don’t use use them?

Most of them are not ready to use right away (especially free ones). Most of them still require rigging or animations. Or they should be fixed one way or another before the BabylonJS plugin can export them correctly and I can smoothly add it to my engine. I do it when I can, but it still takes a lot of time for me, because I am not very fluent in Blender (which is very non-user friendly, to be honest). So, for now I stick to very simple forms, that I actually can edit. That’s why my scenes still look very minimalistic, despite the fact that there are a lot of complex mechanics that I made and that actually work.

1 Like

Despite of this there are many working rigged and animated models available free online.

I disagree… :roll_eyes:

However no one was criticizing the graphics in your example nor the functionality so no worries. :handshake:

Sometimes it’s just not worth to reinvent the wheel, but as you said you do it to educate yourself so keep doing it and show us more of your work in the future!

Thank you!


Yo @splash27 Would it be possible to add an abstract or so? (There is a lot of text :dizzy_face: )

Well, basically the playground itself and the picture is an abstract.
And the text contains detailed explanations.
It’s hard to explain mechanics without explaining mechanics.

1 Like

Thanks for sharing, this is very helpful to me!

Nice writeup so far!

How would you expand this to handle hit detection and 2d/3d auras? (Like in a pvp game where characters maybe buff/debuff/aoe everyone within some radius)

What changes would you make to run on the server? (Main benefit of being cpu based imo)

Incredible writeup! Techniques like sectors are essential to programming “big” games, so I commend you on taking the time to learn and spread the knowledge further along! The example PG is very good and a great visual showing of the technique :slight_smile:

1 Like

@jeremy-coleman, to calculate mutual effects between entities you just need to change the processChain method a little bit:

processChain(head) {
    let currentEntity = head;
    while (currentEntity) {
        let otherEntity =;
        while (otherEntity) {
            this.calculateMutualEffects(currentEntity, otherEntity);
            otherEntity =;
        currentEntity =;

The advantage of the Linked List here is that you always move forward along it. The otherEntity is never behind the currentEntity in the list. It ensures that every mutual effect will be calculated only once. With regular array you would end up calculating effects twice on same instances being swapped in currentEntity and otherEntity. Also, in regular array you need to ensure that currentEntity != otherEntity. Linked List fixes all those problems right out the box.

calculateMutualEffects method should check the distance between entities and apply corresponding effects. But please ensure that maximum effect distance is smaller than sectorWidth.

AOE is even easier. When you dispatch your, let’s say, explosion:

  1. Check in which sector explosion has occurred.
  2. Use findNeighborSectors method to find out if any neighboring sectors are affected.
  3. Check the guys from the current sector and neighboring sectors if they are in the radius of explosion. Again, the maximum radius of explosion should not be bigget than sectorWidth.

Unfortunately, I can’t say anything about server stuff. I have 0 knowledge about network multiplayer programming. However, the advices above are still applicable for “split screen”, “hot seat” kinds of multiplayer games.