I’m working on a heavy duty NPC system
Their functionality is similar to Restaurant Tycoon 2 NPC’s
I decided I want to have a LOT of NPC’s at once, so I didn’t want to use physics or use humanoids. I also try to avoid the usage of instances (indexing properties is slow!) in favor of everything being data oriented (there’s a name for this?), and finally didn’t want the server have to do any real-time replication of moving NPC’s.
Paths are easy to construct
The paths are constructed via an array of “Actions”. I’m very fond of how easily paths are constructed; it is simply calling a function to add a Wait, a Position, a FloorChange, etc, and everything else is done behind the scenes.
In the case of the game this is for, the NPC must travel to the closest elevator, go up it, and then travel to the destination.
Due to the simplistic nature of how paths are represented, my pathfinder is just this:
The NPC wants to get to a point, and starts from another point.
Screenshot of path that is constructed:
It starts at the white circle, travels around the wall, walks to the elevator, waits a second, travels up the elevator, waits a second, and finally navigates around the wall and to its destination, the beautiful green circle.
It then serialized the path into a string, and sends it off to the client!
The path serialized is this:
f1/p0[0/a1/t7741.7=p0[0/p1.7[-36.6/p8.3[-36.6/p10[0/p10[0/t1/f3/p10[0/t1/p10[0/p21.2[6.7/p21.3[11.2/p10[20/p10[20 (if you can depict what the data represents then im impressed)
The client receives it, finds the record, and starts rendering the NPC. Here’s the NPC being moved along the path by the client:
Keep in mind things aren’t very worked on visually, just the data side of things are done. In the future the NPC won’t be named NPC and fly through the air while stiff like a board.
Caching speeds things up by a LOT
Paths are relatively predictable as long as the NPC is going to a destination that has already been pathed to atleast once before. To speed things up, I implemented caching which simplifies the work done in both the server and client context by a ton.
Without caching, the following happens:
Server:
- Construct initial data
- Construct path
- Calculate total path duration
- Serialize path
Client:
- Deserialize initial data
- Deserialize path (VERY time consuming)
- Calculate per-waypoint duration
With caching, this happens:
Server:
- Construct initial data
- Data is already cached, so reuse it (nearly instant)
Client:
- Deserialize initial data
- Data is already cached, so reuse it (nearly instant)
Creating 1000 NPC’s at once (all their paths calculated at the same time)
Without caching, it takes around 5 minutes of rocky framerate (it’s hard to measure exactly the time taken / context). This is because roblox’s PathfindingService is not instant; the time is takes to compute paths ranges ultimately expands the computation time by a huge amount.
With caching enabled, the server creates them all in ~5 ms, and the client receives them in ~3.5 ms. This is VERY significant, and I’m looking for ways to optimize this even further.
The client is responsible for visuals
The nice thing with how the system is structured is there’s nearly no network usage. Paths are replicated as just string values, and the client does the rest. The server only calculates the path data and keeps a record that the NPC exists. This makes it easier to add extra optimizations that the client is totally responsible for.
In the video, you’ll notice how the NPC starts out smooth, but then as it reaches it’s target floor it starts to move choppy. This is because the client will purposefully update NPC’s slower the farther away they are from the players current floor.
