Algorithm Grouping NPCs

Recommended Posts

Hey folks,

I'm about to start work on a system that involves grouping NPCs located within a certain distance from the player in to cells; eventually each cell may exhibit different behaviors based on the 'mood' of the contained NPCs, although the NPCs themselves will have control over their own position & orientation (so no flocking).

Before I begin work on this system I wanted to reach out and see if there are any algorithms that I should check out with regard to creating the NPC cells.

At the moment my plan is pick a random NPC from a list of those around the player, and search within a small radius (from the chosen NPC) to find other nearby NPCs and create a cell. For each NPC added to a cell I repeat this radius check until there are no more valid NPCs for the current cell. Then repeat the cell creation process for any remaining NPCs in my list of those around the player:

So is that a reasonable approach to take?

Share on other sites

This sounds like a canonical example of where a clustering algorithm would be used. One example might be hierarchical clustering, combining NPCs into clusters, merging them together until the remaining clusters are sufficiently far apart to be considered separate. Whether that is fast enough for your game, I don't know.

Share on other sites
On 27.11.2017 at 9:49 PM, Capoeirista said:

So is that a reasonable approach to take?

In principle: yes. Although the condition "grouping NPCs located within a certain distance from the player in to cells" need yet to be considered in the algorithm.

In the following I assume that clustering is a somewhat dynamic process.

If you have many entities to cluster, performance may benefit from temporal coherence. I.e. 2 particular entities that are in the same cluster for the previous time frame are likely also in the same cluster for the current / next frame. However, the benefit will occur only if the sole "is still member" computation is noticeably less expensive than "is new member" computation.

The above thought brings another topic to my mind: Depending on how the clusters are used in the end, it may happen that somehow noticeable behavior swapping in and out may occur. E.g. if an entity moves close to the border of a cluster, then it may happen that it is inside for one time frame, outside for the current, and again inside for the next. Because this entity is itself a seed for clustering, this means that also entire clusters may appear and disappear in a more or less fast pace. So, as soon as the behavior of the entities is computed from the cluster's population, the behavior may alter in the same rate. Something like this should be avoided (e.g. by using a hysteresis for entering and leaving, what again calls for clustering not be done each time from scratch), because it usually looks dumb.

Share on other sites

Hey haegarr, Kylotan,

Thanks for the responses - and apologies for the late reply, been out of town for the last week.

I'll have a maximum of around 50 NPCs to sort in to groups for any given frame, so I will probably have to do most of the processing in separate thread. This shouldn't pose too much of a problem though; the results of the clustering don't have to be precises and individual NPCs swapping from cluster to cluster will have a negligible effect.  This system is going to be driving audio events so there are plenty of things I can do to mask any small changes in the data being generated.

I'm not sure I can use a hierarchical  clustering algorithm in this case, as the distance between each NPC from other NPCs in a given cluster is more important to the grouping than the distance from the player... I'm doing a simple radius-around-the player check to find any NPCs within range, and then grouping those NPCs in to clusters based on their proximity to each other.

The clustering is definitely a dynamic process.

Share on other sites

I struggled with a same problem recently.  I decided to create initial groups at spawn since that was when NPCs are guaranteed to be clustered.  Specifically I make a group controller who then spawns the NPCs.  If these controllers periodically update their location to the center of mass of their respective NPCs.  If these controllers get too close, they merge.  If after some merging, the group is too large for calculations (I set an arbitrary limit of 10 simply because of how I'm handling the more complex AI), it gets split evenly and the groups try to split apart physically.

It keeps my calculations low, but as I said, the primary driver was so I could better coordinate small group tactics.

Share on other sites

Hey feorang,

Yeah that sounds like a reasonable approach, unfortunately I have zero control over the actual spawning of the NPCs. I have to execute a search around a particular position with a given radius, and operate on the returned array of NPCs. At least I can specify a max count to return though

Cheers!

Create an account

Register a new account

• 10
• 17
• 9
• 13
• 41
• Similar Content

• I'm making render just for fun (c++, opengl)
Want to add decals support. Here what I found
A couple of slides from doom
http://martindevans.me/game-development/2015/02/27/Drawing-Stuff-… space-Decals/
No implementation details here
https://turanszkij.wordpress.com/2017/10/12/forward-decal-rendering/
As I see there should be a list of decals for each tile same as for light sources. But what to do next?
Let assume that all decals are packed into a spritesheet. Decal will substitute diffuse and normal.
- What data should be stored for each decal on the GPU?
- Articles above describe decals as OBB. Why OBB if decals seem to be flat?
- How to actually render a decal during object render pass (since it's forward)? Is it projected somehow? Don't understand this part completely.
Are there any papers for this topic?

• Here is the original blog post.
Edit: Sorry, I can't get embedded LaTeX to display properly.
The pinned tutorial post says I have to do it in plain HTML without embedded images?
I actually tried embedding pre-rendered equations and they seemed fine when editing,
but once I submit the post it just turned into a huge mess.
So...until I can find a proper way to fix this, please refer to the original blog post for formatted formulas.
I've replaced the original LaTex mess in this post with something at least more readable.
Any advice on fixing this is appreciated.
This post is part of my Game Math Series.
Source files are on GitHub.
Shortcut to sterp implementation.
Shortcut to code used to generate animations in this post.
An Alternative to Slerp
Slerp, spherical linear interpolation, is an operation that interpolates from one orientation to another, using a rotational axis paired with the smallest angle possible.
Quick note: Jonathan Blow explains here how you should avoid using slerp, if normalized quaternion linear interpolation (nlerp) suffices. Long store short, nlerp is faster but does not maintain constant angular velocity, while slerp is slower but maintains constant angular velocity; use nlerp if you’re interpolating across small angles or you don’t care about constant angular velocity; use slerp if you’re interpolating across large angles and you care about constant angular velocity. But for the sake of using a more commonly known and used building block, the remaining post will only mention slerp. Replacing all following occurrences of slerp with nlerp would not change the validity of this post.
In general, slerp is considered superior over interpolating individual components of Euler angles, as the latter method usually yields orientational sways.
But, sometimes slerp might not be ideal. Look at the image below showing two different orientations of a rod. On the left is one orientation, and on the right is the resulting orientation of rotating around the axis shown as a cyan arrow, where the pivot is at one end of the rod.

If we slerp between the two orientations, this is what we get:

Mathematically, slerp takes the “shortest rotational path”. The quaternion representing the rod’s orientation travels along the shortest arc on a 4D hyper sphere. But, given the rod’s elongated appearance, the rod’s moving end seems to be deviating from the shortest arc on a 3D sphere.
My intended effect here is for the rod’s moving end to travel along the shortest arc in 3D, like this:

The difference is more obvious if we compare them side-by-side:

This is where swing-twist decomposition comes in.

Swing-Twist Decomposition
Swing-Twist decomposition is an operation that splits a rotation into two concatenated rotations, swing and twist. Given a twist axis, we would like to separate out the portion of a rotation that contributes to the twist around this axis, and what’s left behind is the remaining swing portion.
There are multiple ways to derive the formulas, but this particular one by Michaele Norel seems to be the most elegant and efficient, and it’s the only one I’ve come across that does not involve any use of trigonometry functions. I will first show the formulas now and then paraphrase his proof later:
Given a rotation represented by a quaternion R = [W_R, vec{V_R}] and a twist axis vec{V_T}, combine the scalar part from R the projection of vec{V_R} onto vec{V_T} to form a new quaternion: T = [W_R, proj_{vec{V_T}}(vec{V_R})]. We want to decompose R into a swing component and a twist component. Let the S denote the swing component, so we can write R = ST. The swing component is then calculated by multiplying R with the inverse (conjugate) of T: S= R T^{-1} Beware that S and T are not yet normalized at this point. It's a good idea to normalize them before use, as unit quaternions are just cuter. Below is my code implementation of swing-twist decomposition. Note that it also takes care of the singularity that occurs when the rotation to be decomposed represents a 180-degree rotation. public static void DecomposeSwingTwist ( Quaternion q, Vector3 twistAxis, out Quaternion swing, out Quaternion twist ) { Vector3 r = new Vector3(q.x, q.y, q.z); // singularity: rotation by 180 degree if (r.sqrMagnitude < MathUtil.Epsilon) { Vector3 rotatedTwistAxis = q * twistAxis; Vector3 swingAxis = Vector3.Cross(twistAxis, rotatedTwistAxis); if (swingAxis.sqrMagnitude > MathUtil.Epsilon) { float swingAngle = Vector3.Angle(twistAxis, rotatedTwistAxis); swing = Quaternion.AngleAxis(swingAngle, swingAxis); } else { // more singularity: // rotation axis parallel to twist axis swing = Quaternion.identity; // no swing } // always twist 180 degree on singularity twist = Quaternion.AngleAxis(180.0f, twistAxis); return; } // meat of swing-twist decomposition Vector3 p = Vector3.Project(r, twistAxis); twist = new Quaternion(p.x, p.y, p.z, q.w); twist = Normalize(twist); swing = q * Quaternion.Inverse(twist); } Now that we have the means to decompose a rotation into swing and twist components, we need a way to use them to interpolate the rod’s orientation, replacing slerp.
Swing-Twist Interpolation
Replacing slerp with the swing and twist components is actually pretty straightforward. Let the Q_0 and Q_1 denote the quaternions representing the rod's two orientations we are interpolating between. Given the interpolation parameter t, we use it to find "fractions" of swing and twist components and combine them together. Such fractiona can be obtained by performing slerp from the identity quaternion, Q_I, to the individual components. So we replace: Slerp(Q_0, Q_1, t) with: Slerp(Q_I, S, t) Slerp(Q_I, T, t) From the rod example, we choose the twist axis to align with the rod's longest side. Let's look at the effect of the individual components Slerp(Q_I, S, t) and Slerp(Q_I, T, t) as t varies over time below, swing on left and twist on right:
And as we concatenate these two components together, we get a swing-twist interpolation that rotates the rod such that its moving end travels in the shortest arc in 3D. Again, here is a side-by-side comparison of slerp (left) and swing-twist interpolation (right):

I decided to name my swing-twist interpolation function sterp. I think it’s cool because it sounds like it belongs to the function family of lerp and slerp. Here’s to hoping that this name catches on.
And here’s my code implementation:
public static Quaternion Sterp ( Quaternion a, Quaternion b, Vector3 twistAxis, float t ) { Quaternion deltaRotation = b * Quaternion.Inverse(a); Quaternion swingFull; Quaternion twistFull; QuaternionUtil.DecomposeSwingTwist ( deltaRotation, twistAxis, out swingFull, out twistFull ); Quaternion swing = Quaternion.Slerp(Quaternion.identity, swingFull, t); Quaternion twist = Quaternion.Slerp(Quaternion.identity, twistFull, t); return twist * swing; } Proof
Lastly, let’s look at the proof for the swing-twist decomposition formulas. All that needs to be proven is that the swing component S does not contribute to any rotation around the twist axis, i.e. the rotational axis of S is orthogonal to the twist axis. Let vec{V_{R_para}} denote the parallel component of vec{V_R} to vec{V_T}, which can be obtained by projecting vec{V_R} onto vec{V_T}: vec{V_{R_para}} = proj_{vec{V_T}}(vec{V_R}) Let vec{V_{R_perp}} denote the orthogonal component of vec{V_R} to vec{V_T}: vec{V_{R_perp}} = vec{V_R} - vec{V_{R_para}} So the scalar-vector form of T becomes: T = [W_R, proj_{vec{V_T}}(vec{V_R})] = [W_R, vec{V_{R_para}}] Using the quaternion multiplication formula, here is the scalar-vector form of the swing quaternion: S = R T^{-1} = [W_R, vec{V_R}] [W_R, -vec{V_{R_para}}] = [W_R^2 - vec{V_R} ‧ (-vec{V_{R_para}}), vec{V_R} X (-vec{V_{R_para}}) + W_R vec{V_R} + W_R (-vec{V_{R_para}})] = [W_R^2 - vec{V_R} ‧ (-vec{V_{R_para}}), vec{V_R} X (-vec{V_{R_para}}) + W_R (vec{V_R} -vec{V_{R_para}})] = [W_R^2 - vec{V_R} ‧ (-vec{V_{R_para}}), vec{V_R} X (-vec{V_{R_para}}) + W_R vec{V_{R_perp}}] Take notice of the vector part of the result: vec{V_R} X (-vec{V_{R_para}}) + W_R vec{V_{R_perp}} This is a vector parallel to the rotational axis of S. Both vec{V_R} X(-vec{V_{R_para}}) and vec{V_{R_perp}} are orthogonal to the twist axis vec{V_T}, so we have shown that the rotational axis of S is orthogonal to the twist axis. Hence, we have proven that the formulas for S and T are valid for swing-twist decomposition. Conclusion
That’s all.
Given a twist axis, I have shown how to decompose a rotation into a swing component and a twist component.
Such decomposition can be used for swing-twist interpolation, an alternative to slerp that interpolates between two orientations, which can be useful if you’d like some point on a rotating object to travel along the shortest arc.
I like to call such interpolation sterp.
Sterp is merely an alternative to slerp, not a replacement. Also, slerp is definitely more efficient than sterp. Most of the time slerp should work just fine, but if you find unwanted orientational sway on an object’s moving end, you might want to give sterp a try.

• Thanx to @Randy Gaul, I succesfully implemented cube/cube collision detection and response.
1- substract the center of each AABB = 3d vector a.
2- if |x| of a is the biggest, this represents a face on each AABB.
3- if x is pointing at the same(or exact opposte) direction of the normal(of a face), two AABB are colliding on those faces.
But these steps only work if two colliders are cubes, because the size of each half-lengths are different in a right square prism.
Thank you!

• I've been digging around online and can't seem to find any formulas for 3D mesh simplification. I'm not sure where to start but I generally want to know how I could make a function that takes in an array of vertices, indices, and a float/double for the decimation rate. And could I preserve the general shape of the object too?
Thanks for the help!
P.S. I was hoping to do something with Quadric Error / Quadric Edge Collapse if that's possible.

• INTRODUCTION - It's the following, for a university chair I'm making an application that will be an accessory to assist in face-to-face RPG tables, it has rooms in which the master and players can manage tokens, I just want to do one more thing, a map where all the players in the room could see and move their "miniatures" in it the master could put their monsters, but without animation, it would be just to replace the paper map that is normally used in face-to-face sessions.
PROBLEM - To do the map explained in the introduction, I looked for some tools but I did not find any good, so I would ask to be told APIs to do this, if someone has already played table RPG knows more or less how I want to do, I will leave an image of the roll 20 that is more or less similar, and some more images of how I want it to stay on the cell phone for those who never played understand , I just need to know a good tool to do this.
I want the master himself to put the image that will be used when starting the map (photo or maybe tiled map).
It can be solutions for web to and call the website into application, literally anything that does what I want will help.
If you can help me, I'll be grateful, sorry for the awful English.