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.
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,
TC
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:
ActionValueType:IntegerValuesAdvancingRetreating
In the AI action, create local variables like these:
Current Action <Action>
Target <Point array[2]>
Nearby Units <Unit Group>
Then in the "core AI" section indicated in the tutorial, add actions like these:
switch (Current Action)
if (Advancing)
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]
else
order templar to move to Target[Advancing]
if (Retreating)
if (distance from position of unit to Target <= some range)
set Current Action = Advancing
order templar to move to Target[Advancing]
else
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?
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.
Example: artificial intelligence for units in a tower defense
Multithreading
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.)
Action Definitions
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:
Action1Setvariablei=i+1Action2Setvariablei=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, 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.
@templar4522: Go
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.
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.
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:
Then in the "core AI" section indicated in the tutorial, add actions like these:
switch (Current Action)
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?
@UmbraLamina: Go
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:
http://en.wikipedia.org/wiki/Multithreading
http://en.wikipedia.org/wiki/Deadlock
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.
Contents:
Multithreading
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:
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.)
Action Definitions
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:
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:
Using Multithreading
Now, how to use this to optimize your map initialization?
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:
Create a new action definition for your AI:
Now create a clock trigger telling your AI's when to proceed.
Now you can do the core part of your AI. You might add things like:
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.