How to implement "intelligent" NPCs?

Question

For example, I have a map and a player. As a developer, I can never know what the player will do at particular times (wandering, fishing, or whatever). Meanwhile, there is a NPC who walks from location A to location B. Let's say the NPC leaves A at 6 a.m. and arrives at B at 8 a.m. Right now the player is in map 1 and the npc is in map 2. I want the NPC to be in the correct location whenever the player enters map 2, i.e., if the player enters map 2 at 6 a.m, the npc should be in location A, if the player enters map 2 at 8 a.m, the NPC should be in location B, and if the player enters map 2 at 7 a.m, the NPC should be in the middle of the two locations.
I have two main questions:

1. godot has built-in navigation, but can it calculate a "specific" location based on time? If not, how do I implement it?
2. the "Behavior Tree" seems to be what I want, is it the best option?

Darcee

Answer 1

It's not that hard 🙂

In general you'd need to maintain a sequence of daily movement for an npc. Npcs move along routes and most of the routes are probably shared among multiple npcs. So for each map you can define a number of typical routes then assign some combination of them to each npc.

So each npc would store a sequence representing their daily movement. Something like this:

• daily cycle begins
• wait 3 hours
• move along route 14, with speed 4
• wait 2 hours
• move along route 20, with speed 5
• move along route 4, with speed 2
• wait until the end of daily cycle

From such a schedule the exact position of an npc can be queried for any timestamp in the day. Note that the only data needed is this sequence and route definitions consisting of waypoints.

Nuclear

Answer 2

Behavior tree or state machines manages the current state of npc, such as wandering, chasing, fleeing or attacking. A NPC might have 1 primary state and a few sub-state, e.g: primary: moving sub-state:attacking, that will make an RTS unit attack-move to a certain point on map.

For real-time path planning, you could just use one of the plugins or implementations of A* in asset library, but it's rather costly if you use it every frame, so it's best to use them on timed interval or only invoke such path-planning upon NPC move order event.

Subdue

Answer 3

There won't be too many NPCs (less than 10), so maybe AStar is what I want. I'll check the documentation later, thanks for the suggestion.

Darcee

Answer 4

Precalculate paths prior to runtime and store path points sampled in some time resolution (or A* points) into a dictionary structure keyed by timestamps. When player enters a map, find two consecutive time keys that bracket the current time, retrieve npc's position at those times and lerp between them to get the exact position at current time.

Nuclear

Answer 5

This sounds very effective, and also this is my first thought, but if I have many npcs (although they won't appear at the same time), this may be very complex and hard to implement because I have to maintain a really long dictionary.
ALthough this may be the best solution to my question, this is also the last wayI would take.

Darcee

Answer 6

I have to maintain a really long dictionary

You keep a separate dictionary per npc route. I doubt that'd be that long. How many linear segments can there be in a route? Even if there are couple thousands, the lookup will still be instantaneous.

Nuclear

Answer 7

Lookup would not be my concern, my concern is I have to "draw" every step in the dictionary, it will be very time-consuming, especially I want the npcs have different behaviors based on season/ whether.

Darcee

Answer 8

What do you mean by "draw" and "every step". If a route is a list of waypoints connected by linear segments, you only need to store those waypoints, not every single step. You can have hundreds or thousands of routes stored without any problems. The time in keys can be relative to route start so you can "slide" the route in time. Even if route calculation ends up being time consuming (which I doubt), it wouldn't really matter as you'd precalculate them outside of runtime.

Nuclear

Answer 9

I have a lot of maps in my game, so if an npc moves from A to B, the path can be long. As you suggested, I have to record each key point of the npc (based on time) so I can narrow down the current time frame I want. I have to record each step manually, so if there are a lot of npcs, I have to repeat this for every one, this would be time-consuming and tedious. Or am I misunderstanding what you mean?

Darcee

Answer 10

Why would you need to do it manually? If a route is a list of waypoints with known coordinates, and you know the speed at which a npc moves along the route, you can calculate precisely at what time the npc will be at each waypoint.

You wouldn't even need a dictionary if, at average, there isn't too many waypoints in a route. You could only store route waypoints and get away with linear search. For example make a linear search function that takes as arguments; the route waypoints, the current time, the route start time and the npc speed, and returns the exact position the npc will be at, at given current time.

Nuclear

Answer 11

But the "waypoints" have to be hardcoded into my script, right? I see where I'm going wrong, if I want the npc to go through several maps, I still need to hardcode two waypoints for every map, the start waypoint and the end waypoint. But if I hardcode a couple of key waypoints, I don't need the extra algorithm because I just look up the key waypoints based on the time and then use the speed to calculate the location.

Darcee

Answer 12

Waypoints define a route. It's just data that's fed into the system. You can acquire/define this data in multiple ways depending on your movement logic and pathfinding system. In your original question you haven't really specified how you plan to establish a route; it could be edited in manually or calculated via A* from start/end points, or something else entirely. But regardless, once you have a waypoints list, positioning a npc along it in space/time is relatively simple, as well as combining multiple routes in space and time. It's just simple sequencing via more of the timestamped lists or dictionaries.

Nuclear

Answer 13

As a beginner, so many things to learn. Game dev is so hard.

Darcee

Answer 14

This is indeed a good optimization method. I'll try later.

Darcee