• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# FSM Implemented with Graph Data Structure

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

4 replies to this topic

### #1lrh9  Members

Posted 05 June 2012 - 03:39 AM

I've been reading about finite state machines, and - as I understand it - they can be represented by graphs. I wonder if FSMs implemented on a graph data structure would have any special or unique practical applications. I have a gut feeling that finding paths between two states and finding predecessors or successors of a given state might have practical applications, but I can't imagine any detailed use cases. I could see finding the shortest path between two states as a way to determine the minimal set of states an actor must traverse when going from one state to another, and I could see predecessors or successors used to enable systems to reason about the previous and next states of a system based on the current state. Thoughts?

Edited by lrh9, 05 June 2012 - 03:42 AM.

### #2nigo  Members

Posted 05 June 2012 - 12:22 PM

A FSM graph is the same thing than a chunk of code, where your transition rules are the IFs, your cycles are your FORs & WHILEs and nodes are procedural chunks of code, or basic blocks (look it up).

The similarities are most obvious when you look at code to parse computer language grammars, like say, a java parser. A parser generated by yacc/bison would generate a traditional table based FSM while a recursively descent parser generated by, say, CoCo/R or a human, would look like traditional code.

Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.

### #3Alpheus  GDNet+

Posted 05 June 2012 - 12:37 PM

Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.

I'm sorry Lisp is out of the office right now. But if you can please leave a message, it'll get back to you with that self-evaluating and self-evolving program at its earliest convenience.

Edited by Alpha_ProgDes, 05 June 2012 - 12:38 PM.

External Articulation of Concepts Materializes Innate Knowledge of One's Craft and Science

Super Mario Bros clone tutorial written in XNA 4.0 [MonoGame, ANX, and MonoXNA] by Scott Haley

If you have found any of the posts helpful, please show your appreciation by clicking the up arrow on those posts

Spoiler

### #4ApochPiQ  Moderators

Posted 05 June 2012 - 12:51 PM

Could you represent a practical FSM as a graph data structure? Sure. But why would you want to?

Most FSMs in practice are just simple transition logic around a lot of interesting state logic. There's not much purpose to building a "framework" there unless you want to make a visual FSM editing tool for designers or something similar; even that has limited usefulness in my experience, because designing the states and transitions is the borderline-trivial part of doing FSM-based AI. The interesting part is implementing the state logic and doing the correct reasoning to invoke the transitions.

Just looking at a pretty graph structure doesn't really give you that much insight into what a FSM implementation is all about.
Wielder of the Sacred Wands

### #5nigo  Members

Posted 05 June 2012 - 01:24 PM

There is no way a Lisp program would achieve intelligence without human intervention and I am still waiting after so many decades.

Rule evaluation != reasoning.

Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.

I'm sorry Lisp is out of the office right now. But if you can please leave a message, it'll get back to you with that self-evaluating and self-evolving program at its earliest convenience.