• Advertisement

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? 

Thanks for the advice!

Share this post

Link to post
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 this post

Link to post
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 this post

Link to post
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.

Thanks for the advice!

Share this post

Link to post
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 this post

Link to post
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 :)


Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By francoisdiy
      So I wrote a programming language called C-Lesh to program games for my game maker Platformisis. It is a scripting language which tiles into the JavaScript game engine via a memory mapper using memory mapped I/O. Currently, I am porting the language as a standalone interpreter to be able to run on the PC and possibly other devices excluding the phone. The interpreter is being written in C++ so for those of you who are C++ fans you can see the different components implemented. Some background of the language and how to program in C-Lesh can be found here:

      As I program this thing I will post code from different components and explain.
    • By isu diss
      I'm trying to duplicate vertices using std::map to be used in a vertex buffer. I don't get the correct index buffer(myInds) or vertex buffer(myVerts). I can get the index array from FBX but it differs from what I get in the following std::map code. Any help is much appreciated.
      struct FBXVTX { XMFLOAT3 Position; XMFLOAT2 TextureCoord; XMFLOAT3 Normal; }; std::map< FBXVTX, int > myVertsMap; std::vector<FBXVTX> myVerts; std::vector<int> myInds; HRESULT FBXLoader::Open(HWND hWnd, char* Filename, bool UsePositionOnly) { HRESULT hr = S_OK; if (FBXM) { FBXIOS = FbxIOSettings::Create(FBXM, IOSROOT); FBXM->SetIOSettings(FBXIOS); FBXI = FbxImporter::Create(FBXM, ""); if (!(FBXI->Initialize(Filename, -1, FBXIOS))) { hr = E_FAIL; MessageBox(hWnd, (wchar_t*)FBXI->GetStatus().GetErrorString(), TEXT("ALM"), MB_OK); } FBXS = FbxScene::Create(FBXM, "REALMS"); if (!FBXS) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the scene"), TEXT("ALM"), MB_OK); } if (!(FBXI->Import(FBXS))) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to import fbx file content into the scene"), TEXT("ALM"), MB_OK); } FbxAxisSystem OurAxisSystem = FbxAxisSystem::DirectX; FbxAxisSystem SceneAxisSystem = FBXS->GetGlobalSettings().GetAxisSystem(); if(SceneAxisSystem != OurAxisSystem) { FbxAxisSystem::DirectX.ConvertScene(FBXS); } FbxSystemUnit SceneSystemUnit = FBXS->GetGlobalSettings().GetSystemUnit(); if( SceneSystemUnit.GetScaleFactor() != 1.0 ) { FbxSystemUnit::cm.ConvertScene( FBXS ); } if (FBXI) FBXI->Destroy(); FbxNode* MainNode = FBXS->GetRootNode(); int NumKids = MainNode->GetChildCount(); FbxNode* ChildNode = NULL; for (int i=0; i<NumKids; i++) { ChildNode = MainNode->GetChild(i); FbxNodeAttribute* NodeAttribute = ChildNode->GetNodeAttribute(); if (NodeAttribute->GetAttributeType() == FbxNodeAttribute::eMesh) { FbxMesh* Mesh = ChildNode->GetMesh(); if (UsePositionOnly) { NumVertices = Mesh->GetControlPointsCount();//number of vertices MyV = new XMFLOAT3[NumVertices]; for (DWORD j = 0; j < NumVertices; j++) { FbxVector4 Vertex = Mesh->GetControlPointAt(j);//Gets the control point at the specified index. MyV[j] = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); } NumIndices = Mesh->GetPolygonVertexCount();//number of indices MyI = (DWORD*)Mesh->GetPolygonVertices();//index array } else { FbxLayerElementArrayTemplate<FbxVector2>* uvVertices = NULL; Mesh->GetTextureUV(&uvVertices); int idx = 0; for (int i = 0; i < Mesh->GetPolygonCount(); i++)//polygon(=mostly triangle) count { for (int j = 0; j < Mesh->GetPolygonSize(i); j++)//retrieves number of vertices in a polygon { FBXVTX myVert; int p_index = 3*i+j; int t_index = Mesh->GetTextureUVIndex(i, j); FbxVector4 Vertex = Mesh->GetControlPointAt(p_index);//Gets the control point at the specified index. myVert.Position = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); FbxVector4 Normal; Mesh->GetPolygonVertexNormal(i, j, Normal); myVert.Normal = XMFLOAT3((float)Normal.mData[0], (float)Normal.mData[1], (float)Normal.mData[2]); FbxVector2 uv = uvVertices->GetAt(t_index); myVert.TextureCoord = XMFLOAT2((float)uv.mData[0], (float)uv.mData[1]); if ( myVertsMap.find( myVert ) != myVertsMap.end() ) myInds.push_back( myVertsMap[ myVert ]); else { myVertsMap.insert( std::pair<FBXVTX, int> (myVert, idx ) ); myVerts.push_back(myVert); myInds.push_back(idx); idx++; } } } } } } } else { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the FBX Manager"), TEXT("ALM"), MB_OK); } return hr; } bool operator < ( const FBXVTX &lValue, const FBXVTX &rValue) { if (lValue.Position.x != rValue.Position.x) return(lValue.Position.x < rValue.Position.x); if (lValue.Position.y != rValue.Position.y) return(lValue.Position.y < rValue.Position.y); if (lValue.Position.z != rValue.Position.z) return(lValue.Position.z < rValue.Position.z); if (lValue.TextureCoord.x != rValue.TextureCoord.x) return(lValue.TextureCoord.x < rValue.TextureCoord.x); if (lValue.TextureCoord.y != rValue.TextureCoord.y) return(lValue.TextureCoord.y < rValue.TextureCoord.y); if (lValue.Normal.x != rValue.Normal.x) return(lValue.Normal.x < rValue.Normal.x); if (lValue.Normal.y != rValue.Normal.y) return(lValue.Normal.y < rValue.Normal.y); return(lValue.Normal.z < rValue.Normal.z); }  
    • By Descent
      Wow what a wild game by GalaXa Games Entertainment Interactive. Play now... it's really fun but IF you have epilepsy then don't play. It does not feature flashing pictures, but there is lots of animated stuff that might get ya. Anyway, 4 levels, 2 endings, insane action, BY INFERNAL. Please play it, right nao! Also , nice midi music composed by me is in the game.
    • By Stewie.G
      I've been trying to implement a basic gaussian blur using the gaussian formula, and here is what it looks like so far:
      float gaussian(float x, float sigma)
          float pi = 3.14159;
          float sigma_square = sigma * sigma;
          float a = 1 / sqrt(2 * pi*sigma_square);
          float b = exp(-((x*x) / (2 * sigma_square)));
          return a * b;
      My problem is that I don't quite know what sigma should be.
      It seems that if I provide a random value for sigma, weights in my kernel won't add up to 1.
      So I ended up calling my gaussian function with sigma == 1, which gives me weights adding up to 1, but also a very subtle blur.
      Here is what my kernel looks like with sigma == 1
              [0]    0.0033238872995488885    
              [1]    0.023804742479357766    
              [2]    0.09713820127276819    
              [3]    0.22585307043511713    
              [4]    0.29920669915475656    
              [5]    0.22585307043511713    
              [6]    0.09713820127276819    
              [7]    0.023804742479357766    
              [8]    0.0033238872995488885    
      I would have liked it to be more "rounded" at the top, or a better spread instead of wasting [0], [1], [2] with values bellow 0.1.
      Based on my experiments, the key to this is to provide a different sigma, but if I do, my kernel values no longer adds up to 1, which results to a darker blur.
      I've found this post 
      ... which helped me a bit, but I am really confused with this the part where he divide sigma by 3.
      Can someone please explain how sigma works? How is it related to my kernel size, how can I balance my weights with different sigmas, ect...
      Thanks :-)
    • By MonterMan
      Hi all. I have been looking for a real-time global illumination algorithm to use in my game. I've found voxel cone tracing and I'm debating whether or not it's an algorithm worth investing my time researching and implementing. I have this doubt due to the following reasons:
      . I see a lot of people say it's really hard to implement.
      . Apparently this algorithm requires some Nvidia extension to work efficiently according to the original paper (I highly doubt it though)
      . Barely real-time performance, meaning it's too slow to be implemented in a game 
      So in order to determine if I should invest time in voxel cone tracing, I want to ask the following questions:
      . Is the algorithm itself flexible enough so that I can increase the performance by tweaking it (probably lowering the GI quality at the same time, but I don't care)
      . Can I implement it without any driver requirement or special extensions, like the paper claims?
  • Advertisement