Traversable Game State/Engine Code
Posted: 07 Sep 2014, 23:35
Hey guys,
I've been toying around with some code and data structures that would let Forge have a fully traversable game state and I have an extremely rudimentary implementation currently that kind of functions as a proof-of-concept (you can pass priority and that's it). The goal behind this would be to allow for the creation of minimax AI that would be a whole lot smarter than what we have now (while simultaneously allowing perfect playback of previous games and undoing of any action).
The way it works in my example code is as follows:
Since all this is a lot to take in and is probably confusing since I'm awful at explaining things, I'll go through the start of an example game real quick (lots of text warning) right here. This is the output of a simulated game using some simple actions and events (no AI, input is hardcoded) and is likely much easier to follow than anything I could put into text.
Now, here's the same game, except after it finishes (gets to the point above), I undo every action back to the beginning of the game.
Finally, here's the same game again, except after it finishes, I undo every action back to the tapping of the forest and decide to cast a Llanowar Elves card instead.
A similar concept to the EventMarkerAction can be implemented to rewind the game state for AI if necessary, though a better way (possibly?) would be to clone() the game (which clones the queues/stacks) and then add new events to those. It would really depend on memory vs. processing time.
Obviously, this wouldn't be a simple task as every effect, trigger, etc would need rewriting to use this (or a similar) system. It might be something I just work on every so often, but I'm not sure I could ever complete it on my own while I'm employed.
So at this point I'm mostly just wondering what people think and if they have any ideas/comments.
The source code of the above examples is here if you want to take a look: https://github.com/KrazyTheFox/Forge-Engine-Example
I've been toying around with some code and data structures that would let Forge have a fully traversable game state and I have an extremely rudimentary implementation currently that kind of functions as a proof-of-concept (you can pass priority and that's it). The goal behind this would be to allow for the creation of minimax AI that would be a whole lot smarter than what we have now (while simultaneously allowing perfect playback of previous games and undoing of any action).
The way it works in my example code is as follows:
- The Game has a Stack and a LinkedList: one for GameEvents (List) and another for GameActions (Stack). The List is stored in another class that tracks the index of the last executed Event.
- A GameAction is a single command (think command pattern) that changes the state of one thing and can undo that change.
- A GameEvent (in this context; forget about the existing GameEvent classes for now) is a collection of GameActions that are all executed in order, allowing for complex interactions with small parts.
- When something in the game happens, nearly all of the time a GameEvent will be passed to the game to be processed. The game creates an EventMarkerAction, signifying the start of a new event (important later) and puts it on the GameAction stack. The GameEvent is then told to execute and put its own GameActions on the stack.
- To undo an event, the GameEvent list is told to move its index back one and GameActions are popped off the stack and are undone until an EventMarkerAction is removed. Once an EventMarkerAction is removed, we know that a full Event has been undone and we can safely continue.
- If a GameEvent is undone, it can be redone by grabbing the next GameEvent from the event list and re-applying the Actions to the game state.
- If a GameEvent is undone and a new GameEvent is executed (the player does something different instead of redoing a GameEvent), the GameEvents ahead of the current index are removed and the new GameEvent is put on the end.
- For actions such as shuffling a deck that require random numbers, I've created a "ForgeRandom" class that tracks the seed of the Random generator so that it can be set to the same thing every time an action needs redoing.
Since all this is a lot to take in and is probably confusing since I'm awful at explaining things, I'll go through the start of an example game real quick (lots of text warning) right here. This is the output of a simulated game using some simple actions and events (no AI, input is hardcoded) and is likely much easier to follow than anything I could put into text.
Now, here's the same game, except after it finishes (gets to the point above), I undo every action back to the beginning of the game.
Finally, here's the same game again, except after it finishes, I undo every action back to the tapping of the forest and decide to cast a Llanowar Elves card instead.
A similar concept to the EventMarkerAction can be implemented to rewind the game state for AI if necessary, though a better way (possibly?) would be to clone() the game (which clones the queues/stacks) and then add new events to those. It would really depend on memory vs. processing time.
Obviously, this wouldn't be a simple task as every effect, trigger, etc would need rewriting to use this (or a similar) system. It might be something I just work on every so often, but I'm not sure I could ever complete it on my own while I'm employed.
So at this point I'm mostly just wondering what people think and if they have any ideas/comments.
The source code of the above examples is here if you want to take a look: https://github.com/KrazyTheFox/Forge-Engine-Example