It depends entirely on what kind of cutscene you want.
Is your cutscene a movie (think FFVII)?
Is your cutscene an in-game scene acted out by sprites (think FFVI, Chrono Trigger)?
Is your cutscene a series of images (.bmp, .jpg, .png...)?

If your cutscene is a movie, just play the movie.
If your cutscene is an in-game scene, a series of triggers and events would be best. Alternatively, you could use clever timing to get it done (after 20 frames, sprite turns left. after 60 frames, sprite moves diagonally.).
If your cutscene is a series of images, something like what you suggested would probably work.

That would be nice, but I'm not sure how it's supposed to work. What is map?

I know the KQ project did these kinds of cut scenes (this was more-or-less where I borrowed this suggestion from). They use LUA to implement the scripting, and all of their "move up 3 spaces, then right 2 spaces, then wait 50 clicks, then ..." could be applied to all the NPCs (and player's character) simultaneously if all of the IDs were specified in the "process_entities()" list.

NPCs had several states: WALK_RANDOM, WALK_SCRIPTED, WALK_STANDSTILL. When their state was "WALK_SCRIPTED", it took a string of inputs as cues to fulfill.

The main Map would contain all of the NPCs positions, including "current_tile, target_tile, current_[xy]". So if you start an NPC moving in a certain direction, its current_tile may be (10,7) and its target_tile may be (10,8). Its current_x would be 160 (10 tiles * 16-pixel tile width) and current_y would be 112 (7*16), then 113 (7*16 + 1), then 114 (7*16 + 2), ...

So "map" is just whatever map you're drawing to the screen. It's the main controller for all the NPCs contained in it. It's responsible for all the bounds-checking to ensure an NPC doesn't step on an invalid tile (or one occupied by another NPC).

How does someone go about making a movies that APEG can play?

It's the recording a video part that I don't get. I know I can use CamStudio or the like to record a video, but how would I make a cutscene video?

I guess my real question is how would I animate a video for a cutscene, but I think Ive hi-jacked this thread for long enough.

Me and my friend Per have implemented a really simple cut scene system for one of our games that yet hasn't been finished. It might give you some ideas. The cut scene is an entity in our engine just as an enemy or the player. You initialize the cut scene by pushing events to it and the events are carried out in the order they were pushed.

Each entity has a logic function that is called each logic frame. The cut scene counts frames and draws itself accordingly.

You can look at the code here (sorry for the formatting):
cutscene.hpp
cutscene.cpp
entityfactory.cpp

If the player is to be animated, the player is simply disabled and replaced by an animation. When the cut scene is over the player is put back in place and enabled.

For an action based system I would make two general types of actions:
blocking actions
and non-blocking actions

A blocking action blocks the action queue and unblocks it when it's finished.
A non-blocking action, well, doesn't block.
Note that at one point in time there can be only one blocking action getting executed.

So you have one action queue (your cutscene), a list of actions "in progress" and a main thread like this (pseudo-code):

do:
  if script.ready:
    Action nextAction = script.nextAction()
    currentActions.add(nextActions)
    if nextAction.blocking:
      script.ready = false
  foreach action in currentActions:
    action.advance() // Process 1 frame
    if action.finished: //Action has finished
      if action.blocking:
        script.ready = true
      currentActions.remove(action)

An action could be a simple command ("Move char A to (X,Y)") or even a sequence of actions, though this could be difficult to implement.
If you want to do several things simultaneously you would just insert a few non-blocking actions to the queue and add another one that is blocking (e.g. "move A to (X,Y) non-blocking", "move B to (X,Y) non-blocking", "move C to (X,Y) non-blocking", "wait 1000 blocking").

Just an idea. On a second thought it is similar to Næssén's system.

I would agree with Simon's approach of the list of non-blocked (followed by the blocked) action, because if you have three or four NPCs that you want to march out of a room, or fly away in a set formation, or whatever, you can't do that: you have to send one away, followed by the next, then the next.

The queue would be a bit of a better approach as you wouldn't need to code in too much extra to implement it, and it would make program flow a lot easier...

Triggers are often more convenient than co-ordinating scripts manually. e.g. Set a trigger such that "When npc1 is at positon x, npc2.action = walkto y". The active triggers are kept in a list and each of their conditions is tested every frame, after the updates.

Activating and deactivating the triggers is defined in the script, so a mixture of direct commands and triggers can be used in any script.

I think a simple script would be a char[] array:

To move in any four direction, specify "UDLR" (or if you want compass coordinates, "NEWS"), followed by the number of steps in that direction:

char script_buffer[128];
// ...
strncat(script_buffer, "U10", 3);
// ...

Then, step through each character of the array until you hit the '\0'-terminator. If the character is a letter, call the appropriate case __: statement to start collecting the important information afterward (usually, this just means to check the NEXT characters to see if they're numbers, and if so, parse the actual int value from them).

It may be easiest to actually turn this into an expanded string once you have made all of the movement adjustments, such as turning "U4D3" into "UUUUDDD", if it makes the process loop easier for you.

An XML (or whatever) based system might be nice;
This is probably how I would design it (not giving it to much thought right now though)

Should be fairly easy to implement; You'd need an action factory and a condition factory, and some semi-clever logic to make it all work together