Decisions… Decisions…
The past month I have been working on bot logic and a decision graph implementation along with the various refactoring needed for it to seamlessly integrate and easily extract the data it needs mid game. Good news is, it is finished and works great from my testing so far, bad news (for me anyway) is it kind of grew some legs and became a mess. Luckily it is still manageable, and I’m not going to spend time on re-writing it atm just to appease my code OCD.
I started off with a simple node structure that each house a list of decisions that need evaluate true for a node to “activate” after which if it was a decision node. If the decisions evaluated true it begins traversal of it children nodes, and continuing down until either reaching an action node (sending the bots action to the game state) which returns true and pops back up to the root node, or reaching a node that return false, in which case it would pop back up until reaching a parent node with un-traversed children remaining and traversing down them. This process repeats with the goal reaching a decision state that leads to a valid and playable action node based of that decision. The action nodes each contain one action that relates to an action in game (potion, attack, ability) that is then broadcast with parameters from mutable state that is pass along during the traversal and updated/overwritten via the decisions node as to correspond with the action to be performed.
The state part is what added a lot of the mess, as the decisions and nodes part is easy, but to integrate the action parameters that are need to inform the actions of what their goals and targets should be is messy, as this now becomes a “decision” at the end of certain decision list, that always evaluates true, and just updates the state with the parameters it needs. While this is simple in theory it adds a slew of de-bugging issue if any mistakes are made during the implementation of these. Luckily this hasn’t been an issue so far, but it definitely starts making things messy quick. To help offset de-bugging issues and to allow for validation I added in json logging of bot decisions that let me see the flow of decisions and updates to the state, which in the end is a good thing and will help a lot when reimplementing different logic. I plan later to rewrite the state interactions, as to allow the bot the have programmable strategies and larger “awareness” to it state. Due to doing this all in code, there is also the mess of a lot of boilerplate. All of the decisions need to be an overridden object, and all of the nodes need to be instanced, and then the graph can be made by combining the nodes to each other to form the graph . The graph is only like 100 lines of code, with most being extra formatting I added for easier reading. The decisions don’t matter that much as they are gonna be a fair amount of code either way. But there is a ton of boilerplate of instancing the nodes and adding the decisions to them, before I can even add their children.
To start the implementation and to be able to visualize everything to keep things in order, I used a flow chart representing the graph and kept it updated during the implementation of the decisions and nodes needed as to have a reference of that was need and to refer to when combining them.
This ended up thinning out more during implementation as I noticed I could simplify things at times and the brackets are single decisions that are combined into a decision list for a single node.
For the code, there are Actions Node, Actions, Decisions Nodes and Decisions, with the Nodes extending a Node class. The Action node extended to include it’s action, and the decision node to include a list of decisions. These all override the base method of Node which was “travel”. The the Actions and Decisions classes each were abstract and had an overridden method to implement their logic.
// Node Base Class
public abstract class Node {
protected final String name;
protected final Type type;
protected final ArrayList<Node> adjacentNodes = new ArrayList<>(10);
public Node(Type type, String name) {
this.type = Type.ROOT;
this.name = name;
}
public abstract boolean travel(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex);
public Type getType() {
return type;
}
public ArrayList<Node> getAdjacentNodes() {
return adjacentNodes;
}
public String getName() {
return name;
}
public void addAdjacent(Node node) {
if (type == Type.ACTION) return;
if (adjacentNodes.contains(node)) return;
adjacentNodes.add(node);
}
public enum Type {
ROOT,
DECISION,
ACTION
}
}
// Decision Node
public class DecisionNode extends Node{
private final Decision[] decisions;
public DecisionNode(String name, Decision[] decisions) {
super(DECISION, name);
this.decisions = decisions;
}
@Override
public boolean travel(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex) {
for (Decision decision : decisions) {
var rtn = decision.getDecision(botPlayerState, focusState , selfIndex);
if (rtn) focusState.decisions.add(name);
if (!rtn) return false;
}
for (Node node : adjacentNodes) {
if (node.travel(botPlayerState, focusState, selfIndex)) {
return true;
}
}
return false;
}
}
// Action Node
public ActionNode(Action action, String name) {
super(ACTION, name);
this.action = action;
}
@Override
public boolean travel(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex) {
var rtn = action.doAction(botPlayerState, focusState, selfIndex);
if (rtn) focusState.action = name;
return rtn;
}
}
// Decision
public abstract class Decision {
private final String name;
public Decision(String name) {
this.name = name;
}
public abstract boolean getDecision(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex);
public String getName() {
return name;
}
}
//Action
public abstract class Action {
public abstract boolean doAction(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex);
}
Then the actions and decisions had their implementations declared in an Actions and Decisions class. Decisions would get their data from the BotPlayerState, and here I used a lot of java streams for imperative processing of data used for the basis of the decisions, with the use of short circuiting to avoid pointless calculations once futile.
Then a final implementation looked like this (These are just parts, cant reveal the whole bot logic).
public final Node canBuff50Pct = new DecisionNode("CanBUff50/50", new Decision[]{
Decisions.chance50Pct,
Decisions.canBuff
});
public final Node doBuff = new ActionNode(Actions.selectBestBuff, "DoBuff");
// Formatted like this for easier visual parsing
// Can is the decisions node, do is the action
// Then the were all chained together, with the burden of
// staying mindful to existing ones, as multiple nodes feed into each other.
playerEqualHP.addAdjacent(canBuff50Pct);
{
canBuff50Pct.addAdjacent(doBuff);
}
It all started a simple tree structure, but evolved to a graph, then kind of became a mess realizing I needed to add a state to it, as I battled implementing it half way through and felt the final results could’ve been better if designing around it.
Next Up
Next up and pretty much the final task before being able to release an alpha is getting the gui/client up and running. Originally I was going to Use JavaFX and already had fleshed out a base client and various components that would be needed in it. But I feel like to reach a proper audience, the game needs to be able to be played from a browser, and GWT compilation for JavaFX is a spotty and hands on process. So the client side is going to be implemented in the Godot engine, I have some experience with it, but not much. I’m hoping for this process to go fairly quick as I have worked with it a little before, and the client is pretty simple as it just needs to send/receive data from the back end, display it and render animations. Nothing is really logic heavy on its end. Hoping for the best, as things most of the time don’t go as planned. If I can figure out its GUI tools quick it should be a no brainer though, as it uses its own scripting language similar to python and is fairly simple in structure compared to the mess that unity is.
I know this project is taking forever, and trust me I feel the same. But a lot of progress is slowly being made.
Filed under: Uncategorized - @ September 17, 2022 11:22 pm