Jump to content

  • Log In with Google      Sign In   
  • Create Account


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.

  • You cannot reply to this topic
4 replies to this topic

#1 lrh9   Members   -  Reputation: 174

Like
0Likes
Like

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.


Sponsor:

#2 nigo   Members   -  Reputation: 156

Like
-1Likes
Like

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.

#3 Alpha_ProgDes   Crossbones+   -  Reputation: 4680

Like
0Likes
Like

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.

:D


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

Beginner in Game Development? Read here.
 
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 Posted Image
 
Spoiler

#4 ApochPiQ   Moderators   -  Reputation: 14256

Like
1Likes
Like

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.

#5 nigo   Members   -  Reputation: 156

Like
0Likes
Like

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.

:D


Your point being?




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.



PARTNERS