Tag Archives: ai

AI and dialogue using node graphs and custom language

One of the significant progress milestones I’ve done since the beginning of March was the implementation of a system I call Convo and a rudimentary NPC AI that allows NPCs to move/wander and do things randomly, if their base purpose allows it.

To achieve the implementation, two fundamental concepts had to be developed. The first is SNTX, and the second is the usage of the TGF to express nodal networks that are are interpreted at runtime.

SNTX

SNTX is a procedural markup language designed to be injected into dicts. The resulting dict keys are procedurally looked-up to get to a resulting value.

SNTX is a significant upgrade to the TalkDialogue system that I developed in 2015.  The difference lies in the robustness of handling Conditions, as well as clarity. The idea behind the TalkDialogue and SNTX markups was the ability to author a dialogue tree using a text file. By and large this has been possible, but the branching nature of dialogue trees makes writing everything down in one linear text file still confusing. It was this reason that I looked to yEd in order to visualise the dialogue tree .

Conditions

One of the important aspects of SNTX is the concept of Conditions. Conditions are simply asking: is this node valid? If a node has a Condition, the Condition must be True in order for the node to be processed by the system.

Conditions check 3 things:

  • Accomps – a global dict that represent arbitrary ‘accomplishments’.
  • State – the NPC’s ‘state’ variable which is essentially a CSV string, and can comprise any number string tokens describing its state
  • INV – the Player’s Inventory can be searched for a particular item, for a particular quantity.

Doers

The other side of Conditions are Doers. Doers set Accomps or an NPC’s State. Within the Convo (and Astrip) systems, a node is capable of executing a command telling to either add/remove/modify a key in the Accomps, or amend an NPC’s State. It also allows transferring of items from NPC to Player, and vice-versa.

With Doers and Conditions combined, it allows me to script an interactive storyline.

In fact, I have completed a sample quest using all these systems as an early-stage trial for the prototype. I’m happy to say that it also involves having to kill a Robot.

yEd and TGF

yEd is a very capable diagramming application. It has become my weapon of choice because it is one of the very few programs that allow TGF export. TGF (Trivial Graph Format) is a super-lightweight nodal graph format that, when coupled with a well-thought-out markup, can solve a large number of data relationship issues.

My usage of yEd and TGFs began with simply creating nodes that were labeled as SNTX keys. I drew edges that served as annotations to their relationships, though they didn’t actually define the relationship. That is, except for Choices: for every Topic a line can be drawn to a Choice, which will then be recognised by the TGF2Convo converter tool (explained later).

A Convo graph. ‘choice’-labelled edges are the only edges that are processed in the TGF.

The above image shows Topics (yellow), Choices (green), Doers (cyan), ChoiceGroups (pink), Entry (white).

The labels in the nodes reflect directly as it is written in SNTX. When it is written in TGF it looks something like:

4 ==intro -1 ~text:: [The man seems to be so worried that he hardly notices you when you come up to talk.]\nWha? Oh, hi. You must be the new recruit. My name's Zak.
5 ->::intro
6 ++worried ~text:: Worried
7 ~dostate::+met_player
8 -> ?@met_player,$!zak_quest_rejected::intro_hi_again
9 ==intro_hi_again -1 ~text::Hi, again. 
10 ==worried -1 ~text:: I've lost the Sub- Rail pass that I was issued with. My team leader is going to kill me.
11 ++subrailpass ~text:: Sub-Rail Pass
12 ==subrailpass -1 ~text:: I don't know where I might have dropped it. I swear it was in my pocket.
13 ++quest ?@!questaccepted ~text:: [...]

This is translated using a Python script called TGF2Convo, and the output looks like this:

# EntryTopic: Entry for cond -----
->::intro

# EntryTopic: Entry for cond ?@met_player,$!zak_quest_rejected -----
-> ?@met_player,$!zak_quest_rejected::intro_hi_again
# Topic: intro -----------------------

# ~text
==intro -1 ~text::[The man seems to be so worried that he hardly notices you when you come up to talk.]\nWha? Oh, hi. You must be the new recruit. My name's Zak.

# ~choices
==intro -1 ~choices::worried

# ~dostate
==intro -1 ~dostate::+met_player
> Choice
```yml
# Choice: worried -----------------------
# ~text
++worried ~text:: Worried

# Choice: subrailpass -----------------------
# ~text
++subrailpass ~text:: Sub-Rail Pass

The TGF2Convo tool uses Markdown syntax so that when a Markdown viewer is used, it is easier to understand.

Ultimately, the dict is populated with these values, and the runtime uses the dict to determine the path of the dialogue.

However, this is not my ideal way. I had developed SNTX ahead of using TGF. Since using TGF with AI, I realised that utilising TGF fully would be a better way to go for dialogues, but this requires a re-working of the Convo system. This might be done at the end of the prototype phase.

AI and TGF

After the Convo system and SNTX were developed, I had to jump into AI. At that point I had two choices: I could go and write the AI in C2 as events, or I could attempt something much harder, ultimately more flexible, and platform-agnostic. I chose the latter.

When looking at what I wanted to do with the AI, I decided that I just needed a very simple system of controlling the actions and movements of NPCs (not the enemy NPCs). I outlined the requirements of what it would take for an NPC (Zak) who has lost something and is wandering around a given area.

First, there is the point of movement. The NPC should be able to use waypoints. Second, the NPC should have some random ability to use waypoints. Third, the NPC should have some random wait times. Fourth, the NPC should have random animation.

With all that in mind I went into the specifics of what components need to exist to make that happen. I needed:

  • ability to set NPC variables
  • ability to query NPC variables from within the AI graph
  • ability to initiate a ‘move’ (pathfinding) command from the AI graph to the runtime
  • likewise, the ability to ‘wait’
  • the ability to stop
  • the ability to have AI graph randomly choose between named choices
  • the ability to receive event handlers from the runtime
A portion of Zak’s AI graph
The AI at work. Zak is the guy with red pants. 🙂

Event handlers

When I started developing the AI, I would click on Zak to talk to him. A ‘Talk’ icon would appear, but Zak kept on moving. Though I could have effectively paused the game so that I could properly select the icon before Zak walked away, I thought it would be better to tell the AI to stop Zak.

That’s when event handlers came into the picture, which also brought forth a host of different possibilities. For example, I created an event handler called onastrip, which is called when you try to initiate an interaction. In the AI graph, this event handler is connected to make Zak stop. If the icons are ‘aborted’, the event onastripend is fired, and the AI graph is wired to make Zak resume where he left off. When a Convo is initiatedonconvo is fired, and this stops him, too. When Convo is ended, onconvoend is fired.

If a waypoint is missing, there is a wpmissing event that fires, which allows the AI to adjust itself in order to get a proper waypoint index.

The idea of ‘events handlers’ also gradually slid into the other aspects of the AI graph, where ‘events’ are triggered as a result of an operation (a Doer). For example, a choose node chooses between one of any number of events to fire. As long as that event handler is present, then it is a valid event.

Example of a `choose` node. `0`, `1`, and `2` are not really numbers; they are event names and when `choose` chooses an event the handler should be named `onchosen <event_name>`.

There is an immense satisfaction in working this way. There’s definitely a lot more work involved, but it brings the systems I’m working on at a higher level of flexibility, while at the same time, it’s still within the realm of my understanding since I’m the one developing it.

Although I don’t know how much of the AI, in particular, will make it through the Unity alpha, it is undoubtedly a very useful  piece of development because it informs me of the kinds of behaviours I may need to do; which aspects to simplify, and which aspects need more complex behaviours.

 

Advertisements

Workflow: Interaction triggers

In the RND test project one of the most important systems I developed was the interaction trigger system.

This system is simply a method of binding an action (ie “Interact”) and a specifier, and then wrapped to make a ‘broadcast signal’.

This broadcast signal is then sent. Because the broadcast signal can optionally contain a ‘target’, only those matching the target description can be made to respond to the signal.

The importance of a system like this is the ability to make level-specific scripts. I’ll give a test case from the RND project.

  • In Tiled, a marker is created with a name. This is the trigger name, which can be anything as long as it can be uniquely identified.
  • In C2, a ‘On GridMove reach target’ action is bound so that it wraps the reaching of the tile with the trigger name of the marker it has reached.
  • On reach target, the trigger is sent to a BroadcastTrigger function, which accepts the trigger name, and the intended target of the trigger, if any. The target is comma-delimited, so multiple targets can be specified.
  • The BroadcastTrigger function looks at the targets, tokenises them, and then applies the ‘receivedtrigger’ variable of each of the instances that are able to accept triggers. It applies them only to the targets specified, or all instances if no target was specified.
  • Note that a family called f_trigger_receiver was made and the receivedtrigger variable is called ‘f_receivedtrigger’ in order that BroadcastTrigger can efficiently send it to those concerned.
  • In the level-specific script, the intended target is waiting for its specific f_receivedtrigger to change. BroadcastTrigger would have changed it.
  • When it does, it fires off the events there.

In addition to the trigger, level-specific behaviours are specified, and can override the default AI of any object. This is why this is important, because the scripting is done in a separate event sheet (ie logic) and not predefined in the main logic.

Now, other actions are bound, as needed, to the BroadcastTrigger. For example, in the RND project, the On reach target trigger condition was the first one I implemented. But quickly afterwards, it was easy enough to bind the TalkToNPC function, or the InteractWithNPC function to the broadcast.

Of course, the trigger name changed. In the TalkToNPC trigger, the trigger name was "talk "&cmover.name in which the ‘talk’ keyword was appended by the actual variable name of the NPC that was talked to. The name of the NPC talked to was embedded in the signal and no target was specified because the logic was that either the player or the game world was the receiver. But, it is also possible, or even more beneficial if indeed the recipient of the ‘talk’ action was put in to the trigger target, as I did with the next implementation.

I implemented an ‘InteractWithNPC’ action in the same way, but included the recipient of the ‘interact’ action as the target. In the level script it was intended to add to the accomps to keep track who had been interacted with.

The BroadcastTrigger concept is just a concept, but seems to be a very flexible one, as I am using it currently to design a generic kind of interaction behaviour between a single ‘Useitem’ action to a host of different possible objects, each with their varying results. It’s this reason why BroadcastTrigger is useful, because behaviours are defined in the event sheet, and can be contextual as well as part of the main logic.

 

Workflow: Test project RnD 2017 03 25

I’ve been testing a lot of concepts (some old, some new) with a test project and this post is about what I’ve learned, and what else needs to be explored.

CSVToDictionary and AJAX

It’s easier to maintain a separate text file for populating lookup dicts. Use the AJAX object to read the text and then CSVToDictionary to populate the dict. Remove the double-quote marks when using a text file. This makes it easier to read.

Newlines in text files

When extracting text using AJAX, newlines might be necessary, but escape characters do not seem to be recognised. Therefore, I ended up using escape characters, but had to process it (using search-replace) during extraction.

Containers

Containers have been extremely useful especially in terms of debugging messages. For every object I need to debug, a debug Text object is created, and querying the instance of the object will always point to the same objects of the container. No additional picking is necessary. This is probably the most important aspect of my testing.

Enumerations

There are no real enumerations in C2, but simply assigning a constant number to a recognisable variable name is good enough. For example, in the case where the z-layer of a logical position needs to be identified by keyword, I use Z_TILE=0, Z_WALLS=1, etc.

AI

Although a topic unto itself, the main takeaway from doing AI, is how triggers are setup in Tiled and how it’s set up in C2 to respond to triggers.

There are area triggers, which are set up in Tiled. These are positional, and in the test project, they included a ‘facing’ property, which meant that the trigger is fired only when the player is facing a certain direction. The trigger’s name is the string that will end up being called by C2. I opted to use the ‘name’ attribute in Tiled instead of the relegating it to a property because it’s clearer to see the object name in the Tiled viewport.

Some triggers are set up in C2, especially other kinds of interactions. For example, talking to an NPC will yield a trigger specific to the interaction.

The C2 trigger itself is tied to a particular entity, whether it is another NPC, or some other object. That object is responsible for keeping track of the global trigger calls, and what is relevant to itself. For example, if a certain trigger is called 3 times, the object must keep track that it has heard those 3 triggers, and act accordingly. As such, two variables are meant to store AI-specific data: scriptmem, scriptmem_float. The scriptmem variable is meant for strings, and the scriptmem_float is for float value. For example, scriptmem_float was used a generic timer (for waiting). On the other hand, scriptmem was used to store how many times the AI has heard a specific trigger by checking and appending keywords onto the string.

Another important thing about AI is the switch between scripted AI and ‘nominal’ AI. Nominal AI is one that is already pre-programmed in C2 where if there are no scripts directing the AI, it will follow a certain logic (which also depends on the type of AI it is). Two things needed to happen. First the AI needed to know which AI it was allowed to switch to, and this was put in a C2 variable called ai. For example, one agent was assigned ai=script,see. This allowed the agent to switch to ‘script’ mode, but also allow state changes to occur when the C2 ‘see player’ trigger was fired. There was a ‘hear player’ trigger that existed, but because this was not included in the variable, the agent did not respond to hearing, only seeing, and only triggers involving scripts. This ai variable assignment is first done in Tiled, and then propagated to the agent during TMX load.

In addition to the ai variable, the agent had to be put into an FSM state called “script” when it is in scripted AI mode, which allows the system to distinguish which part of the AI sequence it is in. The C2 events which constitute the AI for that agent must consider other FSM states, like “idle”, which is often the ending state after a move.

AI is a bigger topic and I will delve into it more when needed.

Grouping

I find, more and more, that groups are quite useful not only in organising and commenting, but allows simpler conditional actions to be done in-game. The only example I have is the deactivation of user input if a particular state is on-going. This makes it trivial to block input rather than having check conditions of state all through the user input event.

SLG movement cost

SLG movement cost functions can actually be quite simple. At first I thought it needed to accommodate many aspects, but in the end, despite the relatively complex requirement of the test AI, pathfinding, at most, needed only to query the LOS status of a tile. Impassability was bypassed by excluding impassable tiles from the MBoard, making pathfinding simpler and, I think, faster.

It’s also probably best to name SLG movement cost functions with the following convention: <char> <purpose> path. Eg: “npc evade path”, or “npc attack path”, whereby in the “npc evade path” the NPC avoids LOS, and “npc attack path” does not avoid LOS at all.

Orthogonal and Isometric measurements

I’ve researched and learned a lot of about how to transfer orthogonal measurements to isometric values. The positional values were simple enough, but the real progress was in computing angles.

Here is a list of important considerations when dealing with isometric stuff:

  • Converting a C2 object angle (orthogonal space) to an isometric angle (OrthoAngle2IsoAngle). This is used to draw a line in isometric view if that line’s angle was the same as in orthogonal view.
  • Converting an angle depicted in isometric view to orthogonal space (IsoAngle2OrthoAngle). This is used to determine what an angle would like when viewed from top-down. So when you measure the angle between two points, it’s not truly the angle when viewed in orthogonal space because the isometric view is skewing things. IsoAngle2OrthoAngle allows the reverse computation so that, for example, LOS could be determined for a particular point.
  • Converting orthogonal XY positions to logical XY (OXY2LXY). There is no Board function that allows this mainly because this is a peculiarity of the way Tiled positions objects of the Board. The positioning of objects is written in orthgonal space, but when Rex’s SquareTx projection is set to isometric, then all measurements become isometric. Thus this function is needed for this lack.
  • Movement Board and Graphics Board versions of OXY2LXY. This is required because SquareTx for each Board is different, and thus the logical positions will yield a different location.
  • Computing isometric distance to orthogonal distance. This measures two points in isometric space and gives out the distance as though you were looking from above. This is useful in determining the distance between foreground and background objects. This uses a SquareTx as a point of reference for the width/height ratio, but can use the MBoard or GBoard, because they are assumed to have the same ratio.
  • Computing snap angle (Angle2SnapeAngle). Looks at the object’s angle, and finds the nearest angle to snap to (assuming 8 directions). This is required so that the proper animation is set.
  • Converting MBoard logical positions to GBoard logical positions and vice-versa (MLXY2GLXY, GLXY2MLXY). This is very important as it is able to relate the MBoard to the GBoard. Because the MBoard has smaller cell sizes, querying the logical positions of the MBoard using bigger GBoard logical positions will always yield the top-left cell of the MBoard.
  • Convert GridMove direction to C2 angle (GetGridMoveDirection). The GridMove values are quite different. This function converts it for use with other things, like animation, or other function related to facing, which use the C2 angle, or snap angle.

LOS

The last part of this post is about LOS. I’ve already wrote about some aspects of this. But the main path of the research lay in the following:

  • A Line-of-sight behaviour is applied to the player.
  • The player’s facing angle is taken as orthogonal.
  • An LOS field-of-view is defined (eg 90 degrees) for the player.
  • At a given angle (facing_direction), left-side and right-side fov lines are drawn based on the defined fov (90 degrees). Note that these lines are virtually drawn orthogonally.
  • The left and right lines are then converted to isometric angles.
  • Because the left and right lines have been transformed, the difference between these two angles have changed. This new difference is the new LOS field-of-view.
  • The center between these two lines is the LOS center line. The player’s LOS is rotated towards the center.
  • With the new LOS field-of-view, and a new center, this corresponds to an isometric LOS based off a 90-degree LOS when viewed orthogonally.
  • The facing_direction mentioned above bears special mention. When a player clicks on tile in-game, he is actually picking with a view that he is viewing it in isometric view. Therefore, the facing_direction is an isometric angle, which must be converted to an orthogonal angle. It is only then that the left and right fov lines can be properly oriented, because they, in their turn, will be converted back to isometric after the computation is done.

What needs to be explored

ZSorting seems to take a lot of cpu time (~50%), and I’m wondering whether there is a way I can optimise this. So far, the best solution I’ve come up with is to use On GridMove as a condition for sorting. But I think the most ideal way is to localise the sorting around the areas where movement is taking place.