Line data Source code
1 : // Hierarchical finite state machine implementation.
2 : //
3 : // FSMs are specified as a JS data structure;
4 : // see e.g. UnitAI.js for an example of the syntax.
5 : //
6 : // FSMs are implicitly linked with an external object.
7 : // That object stores all FSM-related state.
8 : // (This means we can serialise FSM-based components as
9 : // plain old JS objects, with no need to serialise the complex
10 : // FSM structure itself or to add custom serialisation code.)
11 :
12 : /**
13 :
14 : FSM API:
15 :
16 : Users define the FSM behaviour like:
17 :
18 : var FsmSpec = {
19 :
20 : // Define some default message handlers:
21 :
22 : "MessageName1": function(msg) {
23 : // This function will be called in response to calls to
24 : // Fsm.ProcessMessage(this, { "type": "MessageName1", "data": msg });
25 : //
26 : // In this function, 'this' is the component object passed into
27 : // ProcessMessage, so you can access 'this.propertyName'
28 : // and 'this.methodName()' etc.
29 : },
30 :
31 : "MessageName2": function(msg) {
32 : // Another message handler.
33 : },
34 :
35 : // Define the behaviour for the 'STATENAME' state:
36 : // Names of states may only contain the characters A-Z
37 : "STATENAME": {
38 :
39 : "MessageName1": function(msg) {
40 : // This overrides the previous MessageName1 that was
41 : // defined earlier, and will be called instead of it
42 : // in response to ProcessMessage.
43 : },
44 :
45 : // We don't override MessageName2, so the default one
46 : // will be called instead.
47 :
48 : // Define the 'STATENAME.SUBSTATENAME' state:
49 : // (we support arbitrarily-nested hierarchies of states)
50 : "SUBSTATENAME": {
51 :
52 : "MessageName2": function(msg) {
53 : // Override the default MessageName2.
54 : // But we don't override MessageName1, so the one from
55 : // STATENAME will be used instead.
56 : },
57 :
58 : "enter": function() {
59 : // This is a special function called when transitioning
60 : // into this state, or into a substate of this state.
61 : //
62 : // If it returns true, the transition will be aborted:
63 : // do this if you've called SetNextState inside this enter
64 : // handler, because otherwise the new state transition
65 : // will get mixed up with the previous ongoing one.
66 : // In normal cases, you can return false or nothing.
67 : },
68 :
69 : "leave": function() {
70 : // Called when transitioning out of this state.
71 : },
72 : },
73 :
74 : // Define a new state which is an exact copy of another
75 : // state that is defined elsewhere in this FSM:
76 : "OTHERSUBSTATENAME": "STATENAME.SUBSTATENAME",
77 : }
78 :
79 : }
80 :
81 :
82 : Objects can then make themselves act as an instance of the FSM by running
83 : FsmSpec.Init(this, "STATENAME");
84 : which will define a few properties on 'this' (with names prefixed "fsm"),
85 : and then they can call the FSM functions on the object like
86 : FsmSpec.SetNextState(this, "STATENAME.SUBSTATENAME");
87 :
88 : These objects must also define a function property that can be called as
89 : this.FsmStateNameChanged(name);
90 :
91 : (This design aims to avoid storing any per-instance state that cannot be
92 : easily serialized - it only stores state-name strings.)
93 :
94 : */
95 :
96 : function FSM(spec)
97 : {
98 : // The (relatively) human-readable FSM specification needs to get
99 : // compiled into a more-efficient-to-execute version.
100 : //
101 : // In particular, message handling should require minimal
102 : // property lookups in the common case (even when the FSM has
103 : // a deeply nested hierarchy), and there should never be any
104 : // string manipulation at run-time.
105 :
106 1 : this.decompose = { "": [] };
107 : /* 'decompose' will store:
108 : {
109 : "": [],
110 : "A": ["A"],
111 : "A.B": ["A", "A.B"],
112 : "A.B.C": ["A", "A.B", "A.B.C"],
113 : "A.B.D": ["A", "A.B", "A.B.D"],
114 : ...
115 : };
116 : This is used when switching between states in different branches
117 : of the hierarchy, to determine the list of sub-states to leave/enter
118 : */
119 :
120 1 : this.states = { };
121 : /* 'states' will store:
122 : {
123 : ...
124 : "A": {
125 : "_name": "A",
126 : "_parent": "",
127 : "_refs": { // local -> global name lookups (for SetNextState)
128 : "B": "A.B",
129 : "B.C": "A.B.C",
130 : "B.D": "A.B.D",
131 : },
132 : },
133 : "A.B": {
134 : "_name": "A.B",
135 : "_parent": "A",
136 : "_refs": {
137 : "C": "A.B.C",
138 : "D": "A.B.D",
139 : },
140 : "MessageType": function(msg) { ... },
141 : },
142 : "A.B.C": {
143 : "_name": "A.B.C",
144 : "_parent": "A.B",
145 : "_refs": {},
146 : "enter": function() { ... },
147 : "MessageType": function(msg) { ... },
148 : },
149 : "A.B.D": {
150 : "_name": "A.B.D",
151 : "_parent": "A.B",
152 : "_refs": {},
153 : "enter": function() { ... },
154 : "leave": function() { ... },
155 : "MessageType": function(msg) { ... },
156 : },
157 : ...
158 : }
159 : */
160 :
161 : function process(fsm, node, path, handlers)
162 : {
163 : // Handle string references to nodes defined elsewhere in the FSM spec
164 77 : if (typeof node === "string")
165 : {
166 3 : var refpath = node.split(".");
167 3 : var refd = spec;
168 3 : for (var p of refpath)
169 : {
170 7 : refd = refd[p];
171 7 : if (!refd)
172 : {
173 0 : error("FSM node "+path.join(".")+" referred to non-defined node "+node);
174 0 : return {};
175 : }
176 : }
177 3 : node = refd;
178 : }
179 :
180 77 : var state = {};
181 77 : fsm.states[path.join(".")] = state;
182 :
183 77 : var newhandlers = {};
184 77 : for (var e in handlers)
185 3013 : newhandlers[e] = handlers[e];
186 :
187 77 : state._name = path.join(".");
188 77 : state._parent = path.slice(0, -1).join(".");
189 77 : state._refs = {};
190 :
191 77 : for (var key in node)
192 : {
193 363 : if (key === "enter" || key === "leave")
194 : {
195 123 : state[key] = node[key];
196 : }
197 240 : else if (key.match(/^[A-Z]+$/))
198 : {
199 76 : state._refs[key] = (state._name ? state._name + "." : "") + key;
200 :
201 : // (the rest of this will be handled later once we've grabbed
202 : // all the event handlers)
203 : }
204 : else
205 : {
206 164 : newhandlers[key] = node[key];
207 : }
208 : }
209 :
210 77 : for (var e in newhandlers)
211 3088 : state[e] = newhandlers[e];
212 :
213 77 : for (var key in node)
214 : {
215 363 : if (key.match(/^[A-Z]+$/))
216 : {
217 76 : var newpath = path.concat([key]);
218 :
219 76 : var decomposed = [newpath[0]];
220 76 : for (var i = 1; i < newpath.length; ++i)
221 119 : decomposed.push(decomposed[i-1] + "." + newpath[i]);
222 76 : fsm.decompose[newpath.join(".")] = decomposed;
223 :
224 76 : var childstate = process(fsm, node[key], newpath, newhandlers);
225 :
226 76 : for (var r in childstate._refs)
227 : {
228 119 : var cname = key + "." + r;
229 119 : state._refs[cname] = childstate._refs[r];
230 : }
231 : }
232 : }
233 :
234 77 : return state;
235 : }
236 :
237 1 : process(this, spec, [], {});
238 : }
239 :
240 72 : FSM.prototype.Init = function(obj, initialState)
241 : {
242 19 : this.deferFromState = undefined;
243 :
244 19 : obj.fsmStateName = "";
245 19 : obj.fsmNextState = undefined;
246 19 : this.SwitchToNextState(obj, initialState);
247 : };
248 :
249 72 : FSM.prototype.SetNextState = function(obj, state)
250 : {
251 46 : obj.fsmNextState = state;
252 : };
253 :
254 72 : FSM.prototype.ProcessMessage = function(obj, msg)
255 : {
256 : // warn("ProcessMessage(obj, "+uneval(msg)+")");
257 :
258 54 : var func = this.states[obj.fsmStateName][msg.type];
259 54 : if (!func)
260 : {
261 0 : error("Tried to process unhandled event '" + msg.type + "' in state '" + obj.fsmStateName + "'");
262 0 : return undefined;
263 : }
264 :
265 54 : var ret = func.apply(obj, [msg]);
266 :
267 : // If func called SetNextState then switch into the new state,
268 : // and continue switching if the new state's 'enter' called SetNextState again
269 54 : while (obj.fsmNextState)
270 : {
271 43 : var nextStateName = this.LookupState(obj.fsmStateName, obj.fsmNextState);
272 43 : obj.fsmNextState = undefined;
273 :
274 43 : this.SwitchToNextState(obj, nextStateName);
275 : }
276 :
277 54 : return ret;
278 : };
279 :
280 72 : FSM.prototype.DeferMessage = function(obj, msg)
281 : {
282 : // We need to work out which sub-state we were running the message handler from,
283 : // and then try again in its parent state.
284 0 : var old = this.deferFromState;
285 : var from;
286 0 : if (old) // if we're recursively deferring and saved the last used state, use that
287 0 : from = old;
288 : else // if this is the first defer then we must have last processed the message in the current FSM state
289 0 : from = obj.fsmStateName;
290 :
291 : // Find and save the parent, for use in recursive defers
292 0 : this.deferFromState = this.states[from]._parent;
293 :
294 : // Run the function from the parent state
295 0 : var state = this.states[this.deferFromState];
296 0 : var func = state[msg.type];
297 0 : if (!func)
298 0 : error("Failed to defer event '" + msg.type + "' from state '" + obj.fsmStateName + "'");
299 0 : func.apply(obj, [msg]);
300 :
301 : // Restore the changes we made
302 0 : this.deferFromState = old;
303 :
304 : // TODO: if an inherited handler defers, it calls exactly the same handler
305 : // on the parent state, which is probably useless and inefficient
306 :
307 : // NOTE: this will break if two units try to execute AI at the same time;
308 : // as long as AI messages are queue and processed asynchronously it should be fine
309 : };
310 :
311 72 : FSM.prototype.LookupState = function(currentStateName, stateName)
312 : {
313 : // print("LookupState("+currentStateName+", "+stateName+")\n");
314 43 : for (var s = currentStateName; s; s = this.states[s]._parent)
315 97 : if (stateName in this.states[s]._refs)
316 7 : return this.states[s]._refs[stateName];
317 36 : return stateName;
318 : };
319 :
320 72 : FSM.prototype.GetCurrentState = function(obj)
321 : {
322 8 : return obj.fsmStateName;
323 : };
324 :
325 72 : FSM.prototype.SwitchToNextState = function(obj, nextStateName)
326 : {
327 66 : var fromState = this.decompose[obj.fsmStateName];
328 66 : var toState = this.decompose[nextStateName];
329 :
330 66 : if (!toState)
331 0 : error("Tried to change to non-existent state '" + nextStateName + "'");
332 :
333 : // Find the set of states in the hierarchy tree to leave then enter,
334 : // to traverse from the old state to the new one.
335 : // If any enter/leave function returns true then abort the process
336 : // (this lets them intercept the transition and start a new transition)
337 :
338 66 : for (var equalPrefix = 0; fromState[equalPrefix] && fromState[equalPrefix] === toState[equalPrefix]; ++equalPrefix)
339 : {
340 : }
341 :
342 : // If the next-state is the same as the current state, leave/enter up one level so cleanup gets triggered.
343 66 : if (equalPrefix > 0 && equalPrefix === toState.length)
344 2 : --equalPrefix;
345 :
346 66 : for (var i = fromState.length-1; i >= equalPrefix; --i)
347 : {
348 82 : var leave = this.states[fromState[i]].leave;
349 82 : if (leave)
350 : {
351 66 : obj.fsmStateName = fromState[i];
352 66 : if (leave.apply(obj))
353 : {
354 0 : obj.FsmStateNameChanged(obj.fsmStateName);
355 0 : return;
356 : }
357 : }
358 : }
359 :
360 66 : for (var i = equalPrefix; i < toState.length; ++i)
361 : {
362 122 : var enter = this.states[toState[i]].enter;
363 122 : if (enter)
364 : {
365 73 : obj.fsmStateName = toState[i];
366 73 : if (enter.apply(obj))
367 : {
368 2 : obj.FsmStateNameChanged(obj.fsmStateName);
369 2 : return;
370 : }
371 : }
372 : }
373 :
374 64 : obj.fsmStateName = nextStateName;
375 64 : obj.FsmStateNameChanged(obj.fsmStateName);
376 : };
|
