Jump to content
  • Advertisement
Sign in to follow this  
lrh9

FSM Implemented with Graph Data Structure

This topic is 2297 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

:D[/quote] Edited by Alpha_ProgDes

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

[quote name='nigo' timestamp='1338920546' post='4946539']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.

:D[/quote]
[/quote]

Your point being?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!