Galaxy/Triggers/Multithreading and AI
Coding Concepts & Tutorials
Computers have a capability called multithreading. It allows your program to do multiple tasks simultaneously, rather than one at a time in sequence. Say you have the following situation:
- A map initialization trigger that does a massive amount of tasks (set up players, set global variables, create leaderboards, and so on).
- The order the tasks are done in doesn't matter.
- After all that stuff is done, you want to do more stuff that uses the results of the previous tasks. Your new tasks might rely on player groups AND variables you set up earlier in two different tasks, for example.
By taking advantage of multithreading, your system can do tasks simultaneously in whatever order is best. There's other useful applications of threads too. One example is if you have a bunch of units and there's a separate function controlling the activity of each unit with waits or loops. Situations like this are common in many computer systems, such as the SC2 game itself. One thread can control the UI, another control units, another monitoring network traffic, etc.
To use this multithreading capability, you use action definitions. Action definitions are basically just triggers that only have an "Action" section. Instead of having events, you tell this action definition to run from other triggers just like you would with actions "Create Unit" or "Set Variable." If you select the "options" section of a new action definition, you'll see the "Create Thread" option at the bottom. This is what allows your computer to run the action in its own thread, independent of whatever the rest of your map is doing.
However, sometimes you can't simply set an action's "Create Thread" property to true and reap the benefits. If this action accesses variables that are changed by other actions with "Create Thread" enabled, and you don't synchronize use of the variables, your map can break.
Say you have two actions 1 and 2, an integer variable i which is set to 0, and the actions look like this:
Action 1 Set variable i = i + 1 Action 2 Set variable i = i + 1
Here's a possible order these actions might run, since they're in separate, parallel threads:
- Action 1 reads i and thinks it's 0.
- Action 2 reads i and thinks it's 0.
- Action 2 calculates 0+1 = 1, and stores this new value to i: 1.
- Action 2 finishes.
- Action 1 **already read i**, so still thinks it's 0. It calculates 0+1 = 1, and stores this new value to i: 1.
- Action 1 finishes.
- i is 1.
In multithreading, 1 + 1 can equal 1. How to solve this problem? The variable i is obviously something critical to your program - multiple actions are using it. So you need to tell your computer it's critical. To do this, you allow one action to use it at a time, locking out other actions that want to access the variable until done. To do this, create a new global boolean variable "Lock i". Then use the "Critical Section" trigger action, like this:
Action 1 General - Enter critical section using Lock i Actions Set variable i = i + 1 Action 2 General - Enter critical section using Lock i Actions Set variable i = i + 1
\\ \\ \\
Now, how to use this to speed up your map initialization? \\ \\
- Create two global variables:
- Initializations Complete <integer>
- Init Lock <boolean>.
- Create two triggers, but don't do anything with them yet:
- Init Part 1
- Init Part 2
- Create a function definition for various parts of your initialization, organized however you want. For example, I have these actions in my map:
- Init Players
- Init Units
- Init Leaderboards
- Init Bases
- Init Environment
- In each action definition, click its Options section, and enable "Create Thread."
- At the bottom of each of these action definitions, create a critical section that increases your "Initializations Complete" count by 1, like this:
General - Enter critical section using Init Lock Actions Variable - Modify Initializers Complete: + 1 Trigger - Run Init Part 2 (Check Conditions, Don't Wait until it finishes)
- Now in the "Init Part 1" trigger:
- Give it the event "Map Initialization"
- Add an action for each of your Init actions created above.
- In the "Init Part 2" trigger, put anything that relies on your other initializations being completed.
\\ \\ Now at map initialization, the player's computer will start a thread for each of the Init tasks you wish to complete. Depending on what you need to get done, this can speed up the process significantly. \\ \\ \\
Example: Artificial Intelligence
Multithreading can be used for anything with parallel tasks. This might be useful for units in a tower defense to see if they should attack a nearby tower that's blocking them, or could even be used for coordinating complicated group actions in any map by having multiple layers of threads... one layer for individual units, another for groups, and another to control it on a global scale.
Here's a great example. Say you want units in a tower defense to figure out if they're being blocked. Basically, the AI for each unit waits until it's given the go-ahead every few seconds, performs some simple calculations, then uses available data to determine what the unit should do. The AI will automatically stop running when the unit dies (you could have them stop under other conditions too). I'm writing the method below off the top of my head from what I remember doing for a wireless network, so hopefully I don't miss any details.
Create a global variable:
- GlobalUnitStep counter stores what step you're on
Create a new action definition for your AI:
Unit AI Options: Action, Create Thread Return Type: (None) Parameters Unit = No Unit <Unit> Destination = No Point <Point> Grammar Text: Unit AI(Unit, Destination) Hint Text: (None) Custom Script Code Local Variables Local Time Step = 0 <Integer> Process Actions = false <Boolean> Position = No Point <Point> Velocity = 0.0 <Real> Actions General - Enter critical section using Global Time Step Lock Actions Variable - Set Local Time Step = Global Time Step General - While Conditions (Unit is alive) == true (Distance between Position and Destination) > 3.0 Actions Variable - Set Process Actions = false General - While Conditions Process Actions == false Actions General - Enter critical section using Global Time Step Lock Actions General - If If Global Time Step > Local Time Step Then Variable - Set Process Actions = true Variable - Modify Local Time Step: + 1 General - If If Process Actions == false Then General - Wait 2.0 Game Time seconds ------- ------- Put core AI actions here ------- General - If If (Unit is alive) == true Then ------- Run your action that handles units reaching their destination Else General - Wait 10.0 Game Time seconds Unit - Remove Unit from the game
Now create a clock trigger telling your AI's when to proceed.
- Create a global countdown timer, with a time set to something like 5 seconds, repeating.
- Give your clock trigger an event "timer expires" for your timer
- Create a **critical section** action in the clock trigger that increments GlobalUnitStep + 1
Now you can do the core part of your AI. You might add things like:
- Update what the unit is doing (attacking a tower, moving to point, healing nearby units, etc)
- Update velocity: on average, how much has this unit been moving per second? You can store this as a running average.
- Actions to check if the unit's velocity is low, and if it's trying to move, tell it to now attack a nearby tower instead.
Whenever you create your waves of the tower defense, call your AI action for each created unit and pass it the parameter of the unit to control. The threads will keep track of their own units, handling everything automatically.
Integers like GlobalUnitStep do have an upper bound, which is at least in the 32,000 range, more on some computer systems. Incrementing the integer once every 5 seconds won't get you into problems unless your map runs more than 8 hours though, so you probably won't need to worry about the complexity of wrapping the counter back to 0.
Hopefully I didn't forget to mention anything. Multithreading can be a somewhat tricky concept, and requires careful thinking to make sure different threads aren't overwriting each other's actions. Basically, if all your threads do mostly unrelated tasks and you use critical sections for the tasks that do overlap (such as accessing a counter), you'll be fine. \\
Original Article From Legacy Wiki
- Requires salvage of any still relevant points
The Galaxy virtual machine is capable of supporting multiple threads of execution. These are very similar to threads in other programming languages providing both separate stack space and instruction pointers. Threads are created by running a trigger object either in response to an event or by another thread running the trigger. Threads are automatically destroyed upon return of the root function. It should be noted that there is a maximum limit to concurrent threads (what amount?) after which attempting to create more will fail and generate a script error. Thread execution is controlled by a scheduler inside the Galaxy virtual machine. When a thread is scheduled it is given a fixed maximum run time in the form of an operation limit in order to prevent infinite loops from hanging the session. If a thread fails to die or de-schedule by the time the operation limit is reached it is forcefully terminated and a trigger error is generated. There are a variety of ways threads can be de-scheduled. Creating other threads by executing triggers and waiting for completion allows sub-frame rescheduling to occur if the resulting threads do not de-schedule (unsure). Calling the Wait native will suspend thread execution for a number of frames determined by the specified timeout. Any native that performs synchronization of client side values will suspend thread execution until the server synchronizes the value. It should be noted that multi-threading will not improve execution performance in anyway. The scheduler used by the Galaxy virtual machine is non-preemptive and only has a single execution unit. The reason for this is to produce a very clear and strict memory model which is free of race conditions so easy to use. It is believed that the Galaxy virtual machine physically runs on the deterministic thread of StarCraft II so shares processor time with all deterministic tasks. Performance critical code should avoid excessive thread creation due to the extra time overhead it adds. Although race conditions do not exist in the memory model, they still can occur when dealing with artificial resources. An artificial resource is any concept finite in quantity that a thread may need to use non-instantly. A common example of such a resource is the client display area. Showing 2 dialogs with different choices at the same time over the same area of client display is not helpful so a lock could be used blocking another choice from being shown by another thread until the first choice is dealt with. This would allow the same resources to be shared between both dialogs in a common pool improving efficiency as well. One common purpose of creating threads is to mitigate the operation limit placed by the scheduler.This can be useful for very operation intensive code that executes fast and cannot complete within the operation limit provided. Care must be taken when doing this to avoid hanging clients or causing excessive stalling by executing too much script in a single frame. Consider staggering intensive operations over several frames to spread processor time consumption more evenly. Optimization can be an alternative but has limits. Another useful feature of threads is the dynamic nature of the thread stack. Galaxy does not support dynamic memory allocation with good performance so any form of fast dynamic memory can be very useful. A thread could represent a persistent object with object state retained entirely on stack in the form of local variables. These can then be created as required and left to function autonomously until natural thread death. Only fairly complex and rare objects should use this to avoid hitting the maximum thread limit.
In GUI an easy way to create new threads is by using Action Definitions. Under "options" selecting "Create Thread" will cause the Galaxy Virtual machine to run the specified actions in a new thread when ever the action is called. This is useful when dealing with code that may block so that the caller function can continue execution. It is also useful when dealing with operation intensive code being run in a dynamic loop that could cause an operation limit thread crash if the loop becomes too large. It should be avoided for performance critical or commonly called actions as creating threads does have an overhead. The way GUI implements these actions in Galaxy is to attach a function to a trigger object. Parameters get placed in register like global variables before executing the trigger to create a new thread. The executing function copies the parameters from the global into local variables (stored on the stack) allowing the same call procedure to be applied multiple times even if suspended threads executing the function exist.
Locks are used to prevent race conditions when manipulating a finite resource. Locks are only needed for non-instant code which might run into conflicts from multiple threads and the way they are implemented using Wait can cause threads to be de-scheduled. They should be avoided when possible as they can result in un-bounded thread queuing for highly contended resources which may eventually hit the maximum thread limit. This can be avoided by using a pool of resources to allow multiple threads access to required resources at the same time. An example of for locking could be when an integer is used to determine critical session state such as in an RPG map or party map. To change this state actions are created for when a boss is killed and when a town is entered. They manipulate a single global state integer to various values for a period of time.
Boss Kill Set variable i = 0 Wait 60 game seconds Set variable i = 10
Enter Town Set variable i = i + 1 Wait 30 game seconds Set variable i = i - 1
If both a player were to kill the boss and enter a town at the same time the following could happen: Enter Town is scheduled first so i is set to some value. Enter Town de-schedules for 30 seconds. Boss Kill is scheduled next so i set to 0. The value from Enter Town has been lost. Boss Kill de-schedules for 60 seconds. 30 seconds pass (480 game frames). Enter Town is re-scheduled so i is set to -1. This might not be an expected value. 30 seconds pass (480 game frames). Boss Kill is re-scheduled so i is set to 10. Might go back to normal, or maybe the session has bugged horribly. The values are clearly not doing what is desired as a -1 popped up which might cause unexpected things to occur. In this case using a lock action can help as you can assure that only a single thread will be manipulating the value in a consistent way. To do this, create a new global boolean variable "Lock i". Then use the "Critical Section" trigger action, like this:
Boss Kill General - Enter critical section using Lock i Actions Set variable i = 0 Wait 60 game seconds Set variable i = 10
Enter Town General - Enter critical section using Lock i Actions Set variable i = i + 1 Wait 30 game seconds Set variable i = i - 1
If both a player were to kill the boss and enter a town at the same time the following could happen: Enter Town is scheduled first so grabs the lock and i is set to some value. Enter Town de-schedules for 30 seconds. Boss Kill is scheduled next but cannot grab the lock so is de-scheduled. 30 seconds pass (480 game frames). Enter Town is re-scheduled so i is set to the original value. Boss Kill is re-scheduled as it can grab the lock so i is set to 0. Boss Kill de-schedules for 60 seconds. 60 seconds pass (960 game frames). Boss Kill is re-scheduled so i is set to 10. The result is only expected values at the cost of a loss in parallelism. Any number of such action sequences could manipulate i as long as they grab a lock on it before hand. The "Critical Section" action is implemented using a polling loop that waits a fixed amount of time (how long?) each iteration until the boolean is in the free state. When it passes the loop it will alter the boolean to the in use state to prevent other polling threads from entering such a section. When leaving the section the boolean is returned to the free state. There are no special language or native features behind how it operates so any thread crashes that cause a thread to not run the leave code will result in a deadlock. Nothing also prevents you from externally altering the boolean lock state with standard set actions breaking it as well. Since a pooling loop is run each frame while blocked there is a performance overhead unlike real operating system locks which generate scheduler events.
Outside of the natural multithreading provided by events firing triggers, there are a few cases you would want to purposely create new threads. This could be to avoid the operation limit or to take advantage of the dynamic memory nature of thread stacks.