Inspiration for State Tracking System

[ebon haven]

Hey guys. I'm working on a state management system for the entities in my game. It doesn't need to be crazy complex, but I'm looking for some help on gaining inspiration on the right data structure to use to store these. I've tried a few ways and I've made it better each time, but I keep hitting roadblocks.

Here is what I need from it:

• There will be a lot of entities, it needs to be as cache friendly as I can
• I need to be able to track the "current state", but also be able to go "back" to a previous state (could also interpret this as setting a "next state" and passing the previous state in, so it'll go "forward" to the previous state upon completion of the current state).
• I need to be able to "queue" up a new state to take over when the current state is finished

Originally, I set up a "stack". I used a dynamic array for this. This approach worked really well for the "going back to a previous state" because all I had to do was pop off the current state and I was automatically back at the previous one right where it left off. Unfortunately, there wasn't a way for me to queue up a state for the future with this approach and it's also not super cache friendly as every frame I'd be loading the entire stack of all entities into the cache as opposed to just the "current" states.

I then switched over to a "map" keyed by entity ID that contained a single "current state" for each entity. I was planning to switch this from a "map" to be a "dense-sparse array" or a "freelist" which would make it very cache friendly. However, this approach loses the ability to return to an old state. It also lacks the ability to queue up a new state on its own.

So, now I'm considering keeping the freelist of current states, but adding a queue for each entity that gives the ability control what the "next" state is. Using this queue, I could queue up the "next" state which could be a new state or the previous state.

Anyone solved a similar problem? Maybe have any other clever ideas?

[shut lion]

how often are you doing this “go back to a previous state” operation?

you could potentially store future/previous states as diffs depending on what performance characteristics you need there

[ebon haven]

I'd expect, on average, anywhere from 5-30 seconds would go by before "going back".

[shut lion]

interesting

I know that storing diffs is how jblow did braid’s time travel but that seems different than your thing

if I were you I’d do “going back” by serializing the state and then unthawing it later if it’s that infrequent but that doesn’t really account for the “future state” thing

[ebon haven]

The use case here is a game similar to Rimworld. The best example I have right now is a state that handles the fetching of resources.

AI enters the "Haul State" which handles finding and delivering resources to a job. When a resource is located via map search, it will set the new state to the "Move State" with the intention to return back to the "Haul State" when it gets to the resource.

Then it picks up the resource when it gets there and locates the location to take the resource. So, it sets the state to the "Move State" again with the intention to return to the "Haul State" when it gets there. etc etc

[shut lion]

ahhh I see

one time I watched a spider building a web, get interrupted by catching a bug and needing to wrap it up, and then resumed web-building, and I marveled that if I built a spider AI it probably wouldn’t have handled that edge case correctly

[ebon haven]

haha! nature has us beat in all things

[shut lion]

the queue idea seems reasonable. The only other possibility that comes to mind is that if states always have clear precedence rules you could let the unit be in multiple states at once and it just only acts on whichever has precedence

[ebon haven]

honestly not sure if the precendence rules will hold forever. i just dont know enough abot the game yet

thanks for chiming in! the discussion is helpful!