Let’s say I wanted to store a history of a state system. I want to store a list of States, and a list of Transitions.
(Yes, there’s redundancy there, as a list of Transitions is sufficient to know the list of States, but let’s just say I really need to cache this data (or store additional data for each State)).
Is there an established pattern for doing this? Google hath forsaken me.
I doubt there is an “established” pattern. It is the sort of thing you should craft as needed to meet the precise needs (which is rather why I dislike the whole paradigm of patterns.)
It is such a simple idea, that what you have is fine. One might argue that in the abstract you don’t capture the sequential nature of the process - the history is an indexable list that you only append to. It also grows without bound, which could be an issue.
So the history might be better crafted as a type that supports append and truncation, but is not otherwise mutable, but is indexable to allow recovery of an old state.
There is a lot of work on the nature of logging snapshotting and replay, most of it vastly more complex than this - which is why such a simple version is not tunring up in your searches.
Well, one issue with the struct as given is that it implies a state is tightly bound with the preceding transition, and loosely bound to the next transition. This isn’t true; transitions are between states; they don’t belong to states, and the coupling between previous and next transition is of equal weight.
…it gets around some of the issues, but now there is more redundancy. Typically here I would need to put the actual transitions in a separate array, and just access them by reference in the history array.
But surely the flip side of that coin is: there are situations where it doesn’t pay for everyone to roll their own and reinvent the wheel (three metaphors in one sentence means I must be right ;)).
Clearly patterns can be useful and effective. In the abstract, much of what programmers do is follow patterns; indenting code based on scope, for example, is a pattern.
You definitely need an ordered list, as Og intended all lists to be. But if you’re dealing with something like an NFA then you’ll need references like in your second example, and nextTransition would need to be another list. For a simpler structure if you have sufficient polymorphism you can make an order list of alternating state and transition objects.
Indenting isn’t a programming pattern though. Patterns are good for commonly used processes within a narrow range of complexity. Those tend to get encapsulated in higher level structures over time anyway. In this case the process is not that commonly used, and it isn’t complex.
Let me make sure I’m understanding this right. You have a current state, and you can calculate a previous state sequentially backwards from the current state, but you want to possibly hold pointers to a given state with additional information. There’s a few ways you could do it, depending on what sort performance you’re looking for.
The one that immediately hits me is a pattern based on set membership, it would be a little more complicated than a linked list, but it would amortize the performance based upon various queries. The idea would be that you maintain a linked list not unlike what you already have, but whenever you work backward to a previous state, you maintain the computation, and then you link it back to the root with that computation attached to the link so if you have to query that state again or one further back, you then get a link directly to that state, or can start there and work backward. This is advantageous is, given n is the number of states, and m is the number of state queries, then if m>n, I think you get an amortized constant time. I don’t have the textbook with me, or I’d give you some pseudocode for it.
A common implemented model for this type of thing is a stack frame: consistent state structure pushed onto a stack.
The only problem I can see is that a stack-based system (realworld, not a virtual perfect stack machine) has limited capacity for state history. The upside is that the state history is self-organized and chronological.
I guess I don’t understand the overall run model you have here. Why are you recording state history?
See this article on MSDN, it covers pretty much the entire concept and provides some sample code in C#. (You didn’t mention the language…)
EDIT: It occurs to me, the way you defined the problem, maybe what you have is a tree instead of a graph. Basically the same thing, except all links are 1-directional. This article covers trees. In fact, just read that whole MSDN section.
… with this additional qualification: All the edges (“transitions”) must be directed edges (that is, they have an arrow-head at one end), as they lead only in the direction from the “Prior state” towards the “Successor state”. As such, I would agree with OP’s first thought, that a transition should be packaged along with the Prior State: That is, given a single node ( containing Prior state and Transition), you could apply that transition to that state to re-derive the successor state.
OTOH, if you packaged each Transition with the Successor state, it would be less useful: You can’t, in general, use that information to re-derive the Prior state, nor (I imagine) would you often want to. (Depending on the specific needs of your problem.)
NOW: Is your entire state history one long linear chain with no branches? That is, is it strictly:
State1 -> Trans1 -> State2 -> Trans2 -> State3 -> Trans3 -> State4 -> . . .
Does your graph have any sort of “branches” or loops or any other “funny” stuff (“funny stuff” in the sense that it’s odd to have in a strict state transition diagram of actual states). Are you trying to build a graph of all potential states and all potential transitions (like the infamous “railroad diagram” flowchart format)? Or just a graph of historical states and transitions that actually happened?
And is the process being recorded a simple synchronous process? Are there any parallel or otherwise asynchronous processes going on? That is, can your graph have multiple branches that have all actually happened? How complex is all this, in your application?
A tree, by definition, is an undirected graph with no cycles. The problem he is describing has direction in the state transitions and does not forbid cycles, so it’s not a tree, but just a directed graph.
Not at the moment, but it seems like the kind of design decision I should be thinking of very carefully, because the wrong choice could mean significant refactoring down the line.
What I’m making btw is an engine for making and then playing turn-based 2D cell games.
The states are complete board layouts (i.e. a map of which pieces are in which cells), and the transitions are moves. While one can be calculated from the other for most games (e.g. chess), I can’t rely on that – the engine has to provide history of both layouts and transitions.
So in answer to Senegoid, it is not necessarily one linear chain; the AI will among other things need to use a minmax algorithm, and therefore a tree of states and transitions may be the right approach.
Also my assumption also that 1 transition = 1 move is dubious. For example, for moves like castling, I’m just storing the move as what the user did via the UI e.g. King from e1->c1, only. At the moment there is no need to store that the rook also moved as that is obvious from looking at the next state, but this may be necessary for some kinds of game and so could be an unnecessary constraint in my design.
It sounds like there are two separate problems: Representing part of a tree for processing it; and Caching prior calculations, presumably for speed.
Often, in such applications, the cache need store only a summary (e.g. “value”) about each saved position – the summary might be sufficient to reject a path to the cached position during minimax search. If the position is instead selected, associated data (e.g. tree for lookahead) might be generated quickly.
In that case, your design problem might be to fit as many such cached positions as possible into a given amount of memory. But that is a very different problem than posed in OP.
