Example: artificial intelligence for units in a tower defense
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 in whatever order is fastest for the CPU, rather than the order you originally specified. 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.
(At a technical level, the reason multithreading can speed things up is as follows. One trigger action might require a lengthy delay for your computer to read from memory, so the CPU can switch to another thread you're doing arithmetic in, and CPU's can often do 40 math operations in the time it takes 1 memory read to complete. So by the time it gets the data back from memory it needed, you've already done all the math operations, halving the total execution time of your tasks. Situations aren't always as perfect as this, but threading in general keeps your CPU utilization closer to its maximum potential. It's also very helpful at simplifying complex tasks like AI, discussed later.)
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:
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, and allow one action to use it at a time, locking out other actions from the variable until done. To do this, create a new global boolean variable "Lock i". Then use the "Critical Section" trigger action, like this:
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.
Now create a clock trigger telling your AI's when to proceed.
Create a global countdown timer, with a time set to something like 10 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, pass it the parameter of the unit to control and destination. 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.
Something I couldnt see in there was deadlock. (sorry if I missed it or if you left it out for simplisity)
Deadlock is a trap for young players when multi-threading, it will cause both threads to grind to a halt indefinatly. Here is how it occurs...
As Thalassicus stated, to protect a variable that is used by more than one thread you have a lock for it.
If two different threads both want to change the same two variables they can result in deadlock.
- First thread aquires lock for vairable A
- Second thread aquires a lock for variable B
- First thread wants to aquire the lock for variable B
- AND Second thread wants to aquire the lock for variable A
NOW FIRST AND SECOND THREAD WAIT FOR EVER!
To avoid this (if you are new to multi-threading and dont know more advanced tactics) ALWAYS get locks for variables in order. If you want the locks on both A and B at the same time in a thread then always get A before you get B. If you do this, then only one thread can get to resources that both threads want!
Deadlock actualy occuring can be rare (you run your map hundreds of times before you finaly run out of luck and it occurs), so its nearly impossible to debug in something like starcraft!!! please avoid it in advance, because you will never find out whats wrong if you try and diagnose the problem debugging!!!
NB, this is also caused by more complex loops T1(wants A then B) T2(wants B then C) T3(wants C then A)... Again just re order to take A before B before C in your threads and you will be fine : )
Good point UmbraLamina and thank you, that's something I forgot to mention. If there's a need for more than 1 type of lock in a thread, it's a good idea to research advanced topics in multithreading - can check the wiki articles and other resources for starters:
If a thread only requests 1 type of lock (like the examples in the tutorial), there's no worry of deadlocks, since circular waits like described above won't occur. Requesting and releasing the same lock several times in a thread is ok too.
I don't really like how Blizzard made the implementation of these action definitions..
The only way to create a new thread seems by starting the function as a trigger.
Since triggers can't have parameters (apart from the two standard ones) the GUI creates variables for these parameters. It looks rather messy imo. But of course if you stick to GUI this won't be a bother to you.
Maybe we'll get something like WC3's ExecuteFunc("") for the final release of the GE.
The only thing i can mention is that alot context switches (locks) are expensive. so you need wisely to design your threading. otherwise you can even get lower with performance. etc. etc. so actually it's a complex task.
but yes it's cool what gaylaxy allows to thread your script...
The only thing i can mention is that alot context switches (locks) are expensive. so you need wisely to design your threading. otherwise you can even get lower with performance. etc. etc. so actually it's a complex task. but yes it's cool what gaylaxy allows to thread your script...
Good point. That's why I made the wait between checks have a slight random range to alleviate potential performance hits with many simultaneous accesses; same principal as collision avoidance in ethernet. The frequency and spread of the checks can be varied to balance performance with responsiveness.
The separate timer and critical section aren't even necessary for this situation, but I included them to give an example of synchronization. It'd be more efficient (and unit responses would look more realistic) for all the threads to simply wait a random 5-10 seconds between processing cycles.
I was asked a question in PM's, and with the sender's permission I'm reposting my response here.
Quote from tardcartrider:
Saw your post on multithreading & AI. First, great post I certainly appreciate it and I'm sure many others do as well. I am very interested in learning more about how to write an AI - specifically unit behaviors for a map that I am working on. Nothing too complicated (yet) I'd like to start with some simple actions like having a high templar cast Psi Storm when he encounters a group of enemies and then retreat during cooldown. I can pick up on a lot of the framework from your post, but obviously not enough to accomplish what I am trying to achieve.
I am sure you are busy with your own projects (if you're looking for more let me know =P ), so I would like to know if you know of any other resources that would help me to learn this. Thanks again for the post you made and I would appreciate any other information you can point me in the direction of,
Well, here's what I'd do off the top of my head. It might not be the most efficient method since my experience is with other things, not really any in-depth AI, but this is some basics that might help.
A global preset (data > new preset) like this:
In the AI action, create local variables like these:
Current Action <Action>
Target <Point array>
Nearby Units <Unit Group>
Then in the "core AI" section indicated in the tutorial, add actions like these:
switch (Current Action)
set Nearby Units = all enemy units within (sight range of templar)
if (number of units in Nearby Units > somenumber) and (templar has enough energy)
cast psi storm on (random unit from Nearby Units)
set Current Action = Retreating
set Target[Retreating] = pick some point, could be directly away from Target[Advancing]. To calculate distance, you can get the cooldown of psi storm and movement speed of the templar, and time * speed = distance. I think the Data Table functions might be able to do it directly, or you could store them in variables.
wait 2 seconds or so for psi storm to cast
order the templar to move to Target[Retreating]
order templar to move to Target[Advancing]
if (distance from position of unit to Target <= some range)
set Current Action = Advancing
order templar to move to Target[Advancing]
order templar to move to Target[Retreating]
You'll also want to put your stuff in there telling the unit what point it should be advancing to and such, check if its psi storm target is visible, maybe even loop through all NearbyUnits to check if a certain number of units are around that picked unit, to make sure Psi Storm would be effective there. There's a "center of unit group" function that could be useful for that. Depending on your map terrain, you might also need to be careful with picking the Target[Retreating] so your unit doesn't try to go up cliffs or somewhere else inaccessible. There might be a way to do some of this with orders directly, but after looking into that a bit it seemed difficult to set up, so I went with simple presets.
You can send your unit AI instructions from outside the function by using custom values on the unit (set unit custom value action). I'd create another preset to store the indexes of various things you might want to use to control the unit, like this:
Then set those custom values from outside the function (set custom unit value "Advance Point X" to somevalue) and read them from inside the function (set (X of point Target[Advancing]) = custom unit value "Advance Point X").
I don't really know where to find a general guide to AI, but you can probably locate a lot of info with google searches. Sorry I can't help you more, my knowledge is mostly with other things, not AI specifically.
Do you mind if I copy this into the thread for others with similar questions?
i don't have time to explain in detail, however a simple way to design AIs is using finite state machines.
The rough idea is this:
first, you check in what state the AI is currently, and for each state you will have different things to do, but the pattern is the same:
you check your "input" (variables, events, changes in the game, etc.) and consequently you decide what is the "output" (what to do with your local or global variables, triggering events or whatever) and what is the next state the AI will swich (including the current state, i.e. we remain in the current state).
Thalassicus wrote a simple example with two states, "advancing" and "retreating", but you could have far more complex scenarios like managing a whole computer player with it, although it would probably become easy to predict computer moves after a few games, like age of empires and other old rts games of the 90s...
Just remember you have to manage the state of the entity you are designing the AI for, and the transitions from one state to another. A good idea is to use pen&paper and draw a graph, with states as nodes and transitions as edges.
Maybe the pic on this wiki page could help understanding: Mealy Machine
Automata is one reason I wish we could use pointers... my preferred method to do fsm's is a function pointer table. The table cross-references current state and inputs - each element of the array is a function pointer (function pointers in C-style languages are just a function call without the parenthesis). Then it's a simple matter of calling the dereferenced pointer at the desired position in the table to transition states, without any logic checks at all.
It might be useful to note that "multithreading" is a misnomer in the Starcraft 2 sense. There is no way to actually create a thread.
SC2 just creates the "illusion" of a thread. In all likelihood, there's just a trigger Thread Pool, or maybe just a single-threaded implementation switching contexts a lot.
In any case, this severely limits the usefulness of it (not entirely!) and makes enforcing critical sections significantly less important.
ED: Or wait...it does pause the function at that point until the coast is clear to enter and lock behind it doesn't it, and the lock is opened again once everything inside that area finishes doesn't it. If that's the case you can disregard the book below...I think its working out now that I've gotten a chance to experiment a bit. :P
Okay I've got a question about this stuff. I'm understanding why locks are important and generally how they should be working but even with those two examples I'm not entirely clear on how to implement them with SC2 triggers. I understand the global variable that it used by the Enter critical action...but I don't get how that variable is being used by it and what exactly the Enter critical is doing. Is it flipping the variable on its own, is that being done somewhere else within these critical sections? Also does the Enter Critical halt the trigger's thread until that variable is in whatever state lets it continue or are you also implementing that concept within the second example some how? Fraid I really don't get the time lock one at all and I'm just failing to understand why it'd be a better alternative to just one boolean acting as the gate keeper with even 30+ threads vying to process that section of their code. I'm sure there's good reason but bah its going over my head.
My reasons for needing to know more: I've made threaded AI for individual units on two teams on the map(total of about 30-40 at any given time), they handle their tasks based upon an action they (and other stuff) call upon when certain events or conditions are met and in turn these handlers dole out new orders and tracks all of that with a few global arrays. Now this morning I decided to stream line the functions and use more parameters in the functions to combine the functions for each team's handlers into one instead and just use an extra parameter to let it know which team its dealing with in addition to the rest. I did the same for the data arrays too by adding a second layer to represent team( Ie unitorders[team's constant][unit's order value])...but now I'm hitting many of what I believe to be deadlocks because of the new combined structure :P
So I'm thinking the best course of action would be to lock up those team handler calls so that only one can execute at a time, but again I'm pretty fuzzy on how to do that with the galaxy editor. Any help? :)