Navigation in a match-based online RPG

Unity Engine
,
1

Hi,
I’m looking for some advises and ideas from people who have experience for NPC navigation in this context. I’ve found several solutions but for now, I’m not certain what is the best choice.

The context (think Guild Wars 1 for those who knows how the game works) :

  • The game is an RPG, a bit of latency is not an issue

  • The “world” is cut out into not-so-large maps which are individual scene in Unity

  • The player can join a private map (1 to 8 players inside) or public map (with up to 30 players inside). So it is a sort of match-based system.

  • The server (strongly authorative) manage NPCs and sync them between clients.

  • An instance process is created for each map dynamicly when players enter in it and closed when all players left it.

  • The navigables area can be changed during runtime with events like a boulder falling on a road and blocking the way etc.

From my understanding, there are 2 common solutions :

  • Having Unity launched server side and use navigation mesh to manage NPCs.
  • Using a grid-based solution with pathfinding algorithm like A*.

Solution 1 :
Pros - I will have all the tools for raycasting, do some physics calculation which is not mandatory in my game but can be handy.
Cons - Given the game logic with maps, it means that I will have an instance of Unity running server side for each map openned. Considering there can be potentially 100+ map running with low amount of player, it will obliterate the memory and CPU.

Solution 2 :
Pros - Can easily manage many maps and allow to make some useful game logic for my game (add weight on coordinates, easily change navigable areas etc).
Cons - A lot of work to make more advanced NPC behaviour like playing with line of sight with players etc (I don’t want to make a simple “aggro range” circle.

I’ve already played a bit with both solution. I also have a script to export Unity navmesh as Obj and parse it server side, also made an grid-based A* to work etc …
But I can’t decide which road to follow.

Any advice / idea ? Thank you !

2

After several days searching and tinkering, I finally made a working “solution 2”. I share here some infos if it can be useful to someone.

For this online match-making system, instanciating Unity for each match was not viable. So I decided to create a grid-based system with A* algorithm.

First part of the work was to generate a grid file from Unity to load server side easily.
My servers are using NodeJS. I decided to generate a JSON file.
To do this, I used the well known (and free version) asset from Aron Granberg, see : A* Pathfinding Project - A* Pathfinding Project
It generate the grid inside Unity with nice tools. Then, I used this code to extract those informations to a JSON file (put it in Editor folder).

using System.IO;
using System.Text;
using UnityEditor;
using UnityEngine;
using Pathfinding;
using System;
using Newtonsoft.Json;
using UnityEditor.SceneManagement;

public class NavGridExporter : MonoBehaviour
{
    [MenuItem("Tools/Export nav grid to json file")]
    static void Export()
    {
        GridGraph gridGraph = AstarPath.active.data.gridGraph;
        float[,][] node_datas = new float[gridGraph.depth,gridGraph.width][];
  
        for (int x = 0; x < gridGraph.width; x++)
        {
            for (int z = 0; z < gridGraph.depth; z++)
            {
                GridNode node = gridGraph.nodes[z * gridGraph.width + x];
                Vector3 vec = (Vector3)node.position;
                if (node.Walkable)
                {
                    node_datas[z, x] = new float[] { (float)node.Tag, (float)Math.Round(vec.y,1) };
                }
                else
                {
                    node_datas[z, x] = new float[] { 0f, (float)Math.Round(vec.y, 1) };
                }
          
            }
        }

        string filename = Application.dataPath + "/Scenes/" + EditorSceneManager.GetActiveScene().name + "/" + EditorSceneManager.GetActiveScene().name + "_navgrid.json";
        using (StreamWriter sw = new StreamWriter(filename))
        {
            sw.Write(JsonConvert.SerializeObject(node_datas));
        }
    }
}

So now I have a nice JSON file. Each node contains the Tag number (that can be changed in the asset if you want to give more information than just “walkable” or not, like if it is water etc) and the Y axis to get the height information of the node that will be useful to use server side for various game logic.

Then server side, when a match starts, I can load the associated JSON file to init the grid and use all the algorithms my game needs, using one of the many A* javascript libraries.
So far, tested with a 1000*1000 grid + 100 moving entities. It works like a charm, consume a little bit of RAM (around 15M for the 1k grid) and only 1% of a quite weak CPU.

I will see over time if this solution is good, but so far, yes ! :slight_smile:
It only needs a bit more time on the server side because you kinda reinvent the wheel. But that’s not a problem for me and I get exactly what I need.