CrayonApe 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.
xyz 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.
CrayonApe 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.
xyz 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?
CrayonApe 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.
xyz 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.
CrayonApe 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.
CrayonApe 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:
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.
