Game's internal trigger implementation

[lightmax]

Hello everybody! Long time no see!

I hope some gurus are still here!
Here are my questions :
- How are triggers implemented in the game source code? Is there any place to find reversed code (sorry if those terms cannot be said here)?
- Is every trigger invocation threaded? Is there a thread per event type? Is there a thread for 10 trigger invocations, whatever the trigger? Is it run on the main thread (I guess not)? Is there a sole thread, and a scheduler switching between every trigger invocation?
- How is the unit/doodads pool managed? I mean, if the triggers invocations are being threaded, how is data race managed?

I hope I'm not frightening anybody here . If you have any complementary information I might not have thought of, feel free to share .

 

[Wietlol]

The triggers are one massive .j file (all triggers are made in JASS form and then placed under each other) just like you would write all code in the header file.
That file is then ran on map loading and so the triggers are created.
So during gametime, the triggers cannot change.

Reversed code?
As far as I know there is no such thing in the world.
You might mean Reverse Engineering.
In that case... yea I think that that is a forbidden word to use in your context.

WC3 runs 1 thread at the same time... with exception of sleeping threads.
When an event fires, all triggers that run on that event pause the current thread, then create their own and run that one.
When it is finished, their thread is destroyed and the "current" (the one that was paused by this thread) is "resumed".

ThreadSleepAction does not destroy the current thread. However it does resume the one before it. When the sleep ends, the current one is then paused and the old one continues.

- How is the unit/doodads pool managed? I mean, if the triggers invocations are being threaded, how is data race managed?

I don't really know what that means but this might help you out.

(If I am wrong on anything just tell me because this is only how I think it is done.
I haven't tried anything with the hardcoded part of WC3 and this is only based on my experience and what I understand of other people.)

 

[Xonok]

I can say that data race is handled by treating the game as if it was turn-based.
Essentially the game is spread into ticks and every client knows several ticks in advance what happens. If any of the clients falls behind, then all of them will pause the game in order to let the client catch up.
Falling behind appears to be detected by a lack of a certain type of packet - the so-called "keep-alive" packet. So if a client ceases sending those, it will first be considered to have fallen behind and then disconnected.

 

[lightmax]

Reversed code?
As far as I know there is no such thing in the world.
You might mean Reverse Engineering.
In that case... yea I think that that is a forbidden word to use in your context.

Well, you can reverse engineer a program, and produce "back" the C/C++/etc code. But it won't be the exact same code (due to compiler's optimizations, constant replacement, etc). This is what I call reversed code, but I might be the only one using this term .

WC3 runs 1 thread at the same time... with exception of sleeping threads.
When an event fires, all triggers that run on that event pause the current thread, then create their own and run that one.
When it is finished, their thread is destroyed and the "current" (the one that was paused by this thread) is "resumed".

ThreadSleepAction does not destroy the current thread. However it does resume the one before it. When the sleep ends, the current one is then paused and the old one continues.

Yeah, I had thought of a system like this, but the problem is then : there must a thread for GUI, a thread for the game core, and a thread for the triggers. But how do they interact between all of them? Especially regarding data race? How does the GUI communicate orders given to a unit?

 

[lightmax]

I can say that data race is handled by treating the game as if it was turn-based.
Essentially the game is spread into ticks and every client knows several ticks in advance what happens. If any of the clients falls behind, then all of them will pause the game in order to let the client catch up.
Falling behind appears to be detected by a lack of a certain type of packet - the so-called "keep-alive" packet. So if a client ceases sending those, it will first be considered to have fallen behind and then disconnected.

I've been looking for this kind of thing after reading your post, and I found a very interesting article about AoE I&II : http://www.gamasutra.com/view/feature/3094/1500_archers_on_a_288_network_.php

Do you think the same system is used in WarCraft III?


My goal is to produce a RTS creator with the same type of capabilities, editor-wise. I'm looking for how to implement it.

 

[Xonok]

The article that you linked tells the approach for RTS games in general, so it should also apply to WC3.

 

[Wietlol]

WC3 runs 1 thread at the same time... with exception of sleeping threads.
When an event fires, all triggers that run on that event pause the current thread, then create their own and run that one.
When it is finished, their thread is destroyed and the "current" (the one that was paused by this thread) is "resumed".

ThreadSleepAction does not destroy the current thread. However it does resume the one before it. When the sleep ends, the current one is then paused and the old one continues.

Yeah, I had thought of a system like this, but the problem is then : there must a thread for GUI, a thread for the game core, and a thread for the triggers. But how do they interact between all of them? Especially regarding data race? How does the GUI communicate orders given to a unit?

You understood wrong.
1. GUI IS triggers.
2. Triggers don't have their own thread next to the game core. Instead they replace the game core thread by one they make on their own (for each action and condition rather than for each trigger) and once that is done they return to the game core thread.

When you take an in-depth look in triggers (GUI too) then you end up at natives where the road ends.
JASS is translated to the language that is used for WC3... I am not very surprised if that is C or C++.

Natives are code that directly modifies the object's data... or whatever the native is for.
GetLocationX() directly gets the value of the "x" variable of the targeted instance.
SetWidgetLife() directly sets the value of the "currentHealth" variable of the targeted instance.
etc. etc. etc.

That is how JASS(GUI) gives actions to the game.

My goal is to produce a RTS creator with the same type of capabilities, editor-wise. I'm looking for how to implement it.

I have never tried to create a RTS game before... and it will take some time until that happens.

First of all you might want to have some experience with game engines.
Then you should consider if you have knowledge and experience with objects and object control in games. (codewise)

I have made a similar system like the trigger system of WC3... however I wrote it in JAVA because I can write and read that faster than any other language (even english or dutch, my native language)
It is not that hard to make it. However to create your own editor like GUI or make your own Language like JASS is harder to do. (expecially the latter)
So if you need help with making stuff like tiggers then I could be able to help you out a bit.

 

[Xonok]

@Wietlol
The things called "triggers" in GUI are not actual triggers, but rather a visualization of them. For the purpose of considering something a trigger you should look at the JASS type only.

Also, triggers do have virtual threads. The threads run in the core thread of course, but their individual threads do exist.

 

[Cokemonkey11]

The threads run in the core thread of course, but their individual threads do exist.

Are you sure? Even if this is correct, it's very important to specify that there's a GIL.

 

[edo494]

well if we think about the sole fact that the game was made in 2001(afaik no engine changes in ROC -> TFT), I doubt they would implement something like this.

My understanding of the game is that everything is run in one physical thread, and it runs all the things(game logic as well as graphics output, most likely networking too, but async, so polling the results and not waiting for them to arrive) and basically the game logic runs all the time it can, until it is time to draw stuff to the screen(60 times a second).

In the game logic, you have the inner game logic itself, and the Jass Interpreter, which runs between game logic updates and acts as a "Scheduler" of sort, that it keeps track of some blizzard-defined executions, which we on hiveworkshop call threads(silly name, and misleading) and every such execution has its own point of running code, multi-stack frame as well as oplimit.

The Interpreter is not threaded, so there is never data race.

As to inners of trigger itself, I have no idea.

I think that whenever you do:
TriggerEvaluate
TriggerExecute
ExecuteFunc
Enum...

will start new thread per function invocation(for instance if you have 10 functions registered inside the trigger as conditions, it will create one separate "thread" per function evaluated(this can be kind of proven by trying to crash one of the running functions by hitting oplimit and insepcting if the others run, which they indeed do)

Keep in mind everything written above is speculation, and my opinion based on the nature of the game as well as my knowledge of how Jass works(which is not really any bigger than any other experienced user) and all of this information could be wrong, so dont quote me on this.

 

[Wietlol]

@Wietlol
The things called "triggers" in GUI are not actual triggers, but rather a visualization of them. For the purpose of considering something a trigger you should look at the JASS type only.

Also, triggers do have virtual threads. The threads run in the core thread of course, but their individual threads do exist.

Well... triggers are the same... Triggers in GUI create a new trigger in JASS and add the conditions and actions to it.
There is no difference between them.
Triggers do not have threads... as far as I know.
Every Condition and Action create a new thread when they are called.
A trigger is a collection of conditions and actions.

 

[chobibo]

Triggers can have multiple events too.

 

[Wietlol]

Yes so? GUI triggers can have multiple events too.

 

[chobibo]

Yeah, I just added that to your last statement, chillax.

 

[edo494]

GUI trigger is subset of Jass Trigger(notice T), becaus Jass Trigger can have multiple GUI-like triggers, but GUI trigger can always generate at most one Jass Trigger.

 

[Wietlol]

The only difference between JASS triggers and GUI triggers is that you cannot change the InitTrig_Your_Trigger function in GUI... and you cannot add functions above the only action that you can add to that trigger.
But you can create triggers in GUI.

At least I think we both know enough about how triggers work to make our stuff
If we do not agree on what triggers do in GUI vs JASS then we are just sayin the same stuff but understanding it both wrong

 

[Cokemonkey11]

trigger is a data type. GUI Trigger Editor allows you to do basic event response by providing an interface to the trigger data type. That being said, there are absolutely things the trigger data type is capable of, which are impossible with the GUI interface. One example is dynamic triggering.

 

[edo494]

hence it is subset

 

[Cokemonkey11]

Calling it a subset would be sidestepping the issue. The GUI Trigger Editor implements a subset of the features supported by the trigger datatype

 

[lightmax]

From what I've seen in my use of the editor (notably when I was working on Dope's HnA map), the triggers that you can make with the GUI are translated into JASS, but you don't have access to the whole API when making them with the GUI.

JASS is translated into bytecode, not into C/C++. It'd need to be recompiled at runtime, and even if it's doable, it's not the best way. Furthermore, you could embed viruses totally easily into the map, using this system. JASS's bytecode is a Blizzard custom-made bytecode, that is executed by an interpreter at runtime.

I've been thinking about how to implement triggers for some time now, and one of my thoughts was to create a sole thread, and use a custom-made scheduler to switch between the different triggers being executed.
Thing is, I fear that doing it this way, and on the same thread as the render and game core are, is what makes the game freeze and units moving order to be processed very slowly one after another, when there are ~300 units on the map. Whereas a game like StarCraft II allows for ~1000 units on the map without any problem (2 * 200 * 8 zerglings = 3200 units, so it must be able to do even more than just 1000 units).

Also, as far as I remenber, this way of implementing triggers was buggy : when two persons typed the same command, the second to write it had the effects done first if the trigger was long enough, execution time-wise. Bad work here Blizzard?

About making a language like JASS, it's not hard, really. I've written a language based on C, adding some object-oriented programming features. Well, not hard, when you know how, right. I've written a first shot about a JASS-like language, and I've made a bytecode interpreter for the generated bytecode (well, textcode would be more appropriate). In Java .
I'd like to see your implementation of triggers in Java, it might give me some ideas or "pre-feedback" about what I want to do.

If someone sees clearly enough into WarCraft III structure, would it be possible to have a diagram-like of the parts, and what they do?

 

[Dr Super Good]

- How are triggers implemented in the game source code?

The JASS Virtual Machine was written in C++. JASS compiles on map load into JASS instructions with named linking. The reason it is so slow is due to name resolution at run time as opposed to static address linked virtual machine code (such as Galaxy which is why it is faster). Since JASS instructions cannot be executed natively they are interpreted by some JASS emulation layer (still quite fast but not native code speed).

A better implementation of such a system can be found in source code for the official JAVA virtual machine. This uses JIT compiling to get rid of a lot of the performance problems present in JASS so is a preferred implementation.

Is there any place to find reversed code (sorry if those terms cannot be said here)?

It is implemented in "game.dll" in the installation directory. Since WC3 is closed source you can only look at the disassembly of it (all multiple hundred thousand uncommented lines of x86 assembly).

- Is every trigger invocation threaded?

A new JASS virtual machine thread is created in response to an event running a trigger. Some trigger executions will make a thread as well however others will not (not sure). Do note that this does not correspond to a physical OS level thread since the entire JASS virtual machine runs as a job in the main thread of WC3 (WC3 executes mostly single threaded with exception of some handlers as was common practice at the time of development).

Is there a thread per event type?

Question illogical. A thread represents a separate execution state (stack, registers and program counter) as such it makes no sense that it would be tied per event type.

Is there a thread for 10 trigger invocations, whatever the trigger?

Each event when running a trigger will create a new JASS virtual machine thread no mater how many events are attached to the trigger or how many triggers use similar events (each event you create is a different object so no two triggers can have the same event).

Is it run on the main thread (I guess not)?

All JASS Virtual Machine threads are run as a job of the WC3 main thread. As mentioned earlier this was due to common programming practices of the time (consumer multi-core systems did not exist). WC3 as a process does generate multiple threads however they are either part of system calls or are used specifically for various I/O purposes so are considered light weight. SC2 Galaxy virtual machine uses a similar scheduling design except SC2 has two main threads (deterministic and local) and is scheduled only on the deterministic thread (local handles graphics).

Is there a sole thread, and a scheduler switching between every trigger invocation?

Yes WC3 main thread runs the JASS virtual machine job and that handles the scheduling of all JASS tasks (in the form of threads). It does so in a non-pre-emptive manner meaning that it will not interrupt currently executing threads. JASS threads can either "block" (TriggerSleepAction and sync actions) or "yield" (create another thread) by calling appropriate natives which is how concurrency is handled.

The result of this is a very easy to use memory model. Unless you call a native that blocks or yields the thread it will execute until completion or until an "op-limit" is reached. When a thread does block or yield its results at the time it did so are instantly available to all other threads (no need of mutexes or other synchronization structures).

How is the unit/doodads pool managed?

The JASS virtual machine makes changes as it executes instructions that tell it to.

I mean, if the triggers invocations are being threaded, how is data race managed?

There is no race condition as only 1 job is ever accessing the data at the same time due to the single threaded nature of WC3.

 

[Cokemonkey11]

A couple small things: doodads are baked into the terrain and an initial pathing map is generated. Units and destructables are managed at runtime. Destructables and units are widgets, but doodads are not.

Whereas a game like StarCraft II allows for ~1000 units on the map without any problem (2 * 200 * 8 zerglings = 3200 units, so it must be able to do even more than just 1000 units).

StarCraft 2 uses a lot of very modern techniques to manage large quantities of units including quadtrees at rendering phase to reduce cost of drawing many scattered unit groups and group based pathing to manage movement. There are many blogs about this, I suggest looking them up if you're interested in implementing an engine capable of so many entities.

Sorry for not providing a link myself, I'm on mobile

 

[Dr Super Good]

StarCraft 2 uses a lot of very modern techniques to manage large quantities of units including quadtrees at rendering phase to reduce cost of drawing many scattered unit groups and group based pathing to manage movement. There are many blogs about this, I suggest looking them up if you're interested in implementing an engine capable of so many entities.

StarCraft II actually cannot handle that number of units. The amount of resources it requires is beyond what most consumer computer systems can provide. A reasonable number of units in SC2 is anywhere between 500 and 1,000 total, anything more and performance will fall through the floor.

WC3 does not suffer this performance problem and can easily run to multiple thousand units without performance difficulties. However that is because it does not allow all units to move constantly (likely why it does not allow that in the first place). Where as in SC2 I have no problem moving my 500 zerglings all at once, in WC3 I would struggle to move 50 at a similar relative speed as the way they path find would not support it.

Using quad trees is how RTS games have always been made. I am pretty sure even Age of Empires used them as it is hardly a recent development (most data structures are pretty old now). SC2's major claim to fame is that it uses a mesh pathing system to navigate units meaning that units with a large collision side will automatically avoid narrow passages they cannot fit through (as opposed to WC3 where they would always try and go through them). Mesh pathing systems are not easy to implement with even World of Warcraft using a node system instead (which was exploitable to farm stuff). Mesh pathing is more recent as it is both difficult to implement and hard to manage/use effectively (even though it ultimately is similar to node pathing which is common practice even still).

SC2 does support maps larger than 256*256 as people have proved. Just the mesh pathing system it uses does not (units move erratically with such a large map) rendering such maps unplayable.

 

[Cokemonkey11]

> StarCraft II actually cannot handle that number of units. The amount of resources it requires is beyond what most consumer computer systems can provide. A reasonable number of units in SC2 is anywhere between 500 and 1,000 total, anything more and performance will fall through the floor.

this isn't really substantial when the quote referenced doesn't site any precise number. There is no RTS engine to date that handles the number of units with flow based pathing and the number of polys per unit better than sc2.

> WC3 does not suffer this performance problem and can easily run to multiple thousand units without performance difficulties. However that is because it does not allow all units to move constantly (likely why it does not allow that in the first place). Where as in SC2 I have no problem moving my 500 zerglings all at once, in WC3 I would struggle to move 50 at a similar relative speed as the way they path find would not support it.

you're talking about two different issues. the lag related to the number of units in sc is graphical lag related to the rendering quadtree used. the fact that wc3 doesn't lag with more units is not "because all units are not allowed to move constantly", rather, its because the culling process for wc3 is entirely different than sc2. wc3 culls faces that are not visible with GL calls. sc2 culls faces that aren't in neighboring quadtree groups algorithmically.

> Using quad trees is how RTS games have always been made. I am pretty sure even Age of Empires used them as it is hardly a recent development (most data structures are pretty old now).

aoe may or may not use quad trees, and indeed they are an old data structure, but no engine has used them for pathing in the way sc2 has. quadtrees are normally used for space partitioning and rendering, which sc2 also has, but additional pathing logic is also included.

quadtrees (and in general kd trees) are not the only way of space partitioning. BSP is used for many 3D engines, for example.

> SC2's major claim to fame is that it uses a mesh pathing system to navigate units meaning that units with a large collision side will automatically avoid narrow passages they cannot fit through (as opposed to WC3 where they would always try and go through them). Mesh pathing systems are not easy to implement with even World of Warcraft using a node system instead (which was exploitable to farm stuff). Mesh pathing is more recent as it is both difficult to implement and hard to manage/use effectively (even though it ultimately is similar to node pathing which is common practice even still).

that's hardly sc2s claim to fame, and doesn't even include flow based pathing. flow pathing uses fluid simulation research to allow units to push past one another and optimize throughput at pathing bottlenecks.

> SC2 does support maps larger than 256*256 as people have proved. Just the mesh pathing system it uses does not (units move erratically with such a large map) rendering such maps unplayable.

this is related to 32 bit floating point numbers, not the broad system. the same problem occurs in wc3.

 

[Dr Super Good]

this isn't really substantial when the quote referenced doesn't site any precise number. There is no RTS engine to date that handles the number of units with flow based pathing and the number of polys per unit better than sc2.

Empires Dawn of the Modern World. Could easily hit >5,000 units at once and did not suffer movement problems like WC3. Maybe it is not "flow" based movement and I admit the pathing was pretty stupid at times however it beat games like Age of Mythology hands down and was released before WC3.

Model complexity has nothing to do with it as clipping removes out of view models and in the case of SC2 graphics are produced by a separate thread.

you're talking about two different issues. the lag related to the number of units in sc is graphical lag related to the rendering quadtree used. the fact that wc3 doesn't lag with more units is not "because all units are not allowed to move constantly", rather, its because the culling process for wc3 is entirely different than sc2. wc3 culls faces that are not visible with GL calls. sc2 culls faces that aren't in neighboring quadtree groups algorithmically.

No SC2 seldom bottlenecks the GPU. It is mostly bottlenecked by the CPU. The performance problems (not lag) are mostly down to unit movement since it is a lot more demanding. The best and most easily reproduced way is ordering 1,000 zerglings to a single point. The game will boarder line hang for several seconds.

The reason is not actually the pathing but the collision handling. In this case the zerglings will push each other with collision resulting in huge performance problems. This is exactly the same performance problem you get in WC3 if you have 100s of air units in the same space and then order them to stop so they start pushing each other. WC3 ground units had no displacement collision mechanics so were not subject to this performance strain, instead they dealt with collisions simply by stopping and waiting to try again.

Graphics has practically nothing to do with it. Sure viewing 1,000 Zerglings will cause the GPU to drop frames due to the complexity of the scene however that alone will not cause the game to slow down. The game will slow down if you move 1,000 Zerglings to the same point and that is due to the complexity of the operation even if your camera is centred nowhere near them and GPU is mostly idle.

SC2 separates graphics from state. Sure graphics will slow state advancement down however that would be due to memory I/O bandwidth and other bottlenecks and not the actual graphics itself. This is different from WC3 where they both shared the same task with their own internal scheduler.

aoe may or may not use quad trees, and indeed they are an old data structure, but no engine has used them for pathing in the way sc2 has. quadtrees are normally used for space partitioning and rendering, which sc2 also has, but additional pathing logic is also included.

quadtrees (and in general kd trees) are not the only way of space partitioning. BSP is used for many 3D engines, for example.

SC2 does not use quad trees for pathing? It uses mesh based pathing. Sure the mesh lookup (which mesh the unit is in) could be done via quad tree however a pointer would be far more efficient. The pathing algorithm of SC2 is that of mesh pathing which is an expansion of node pathing to include area information (so it can handle big and small units separately so the big units do not get stuck in a small gap like in WC3).

that's hardly sc2s claim to fame, and doesn't even include flow based pathing. flow pathing uses fluid simulation research to allow units to push past one another and optimize throughput at pathing bottlenecks.

SC2 has no such optimization. Units will bottleneck and flow rates are not optimized. They appear to flow purely due to the collision algorithm I mentioned earlier which pushes them around. You will still find marines walking left and right if they hit a wall of marines firing (which become unpushable by most units, same as if they hold position) at a target to try and get to the target. This is why you need to push units like marines forward before attacking.

this is related to 32 bit floating point numbers, not the broad system. the same problem occurs in wc3.

No it is not. SC2 does not even use floating point numbers as they are platform dependent (a major source of pain in WC3 as MAC and Windows handle them slightly differently in some circumstances). It uses fixed point numbers instead which are platform independent. The fixed point number range is considerably larger than even a 2048*2048 map so that is not a problem.

Please stop making assumptions and actually try the game.

 

[Cokemonkey11]

Empires Dawn of the Modern World. Could easily hit >5,000 units at once and did not suffer movement problems like WC3. Maybe it is not "flow" based movement and I admit the pathing was pretty stupid at times however it beat games like Age of Mythology hands down and was released before WC3.

So basically you're refuting my point by ignoring two of the axioms I based it on.

Model complexity has nothing to do with it as clipping removes out of view models and in the case of SC2 graphics are produced by a separate thread.

They're absolutely related. Culling works differently in the two engines. In wc3, GL natives are used for culling (high constant cost). In SC2, the quadtree is used for culling (O(lg(n)))

No SC2 seldom bottlenecks the GPU. It is mostly bottlenecked by the CPU. The performance problems (not lag) are mostly down to unit movement since it is a lot more demanding. The best and most easily reproduced way is ordering 1,000 zerglings to a single point. The game will boarder line hang for several seconds.

The reason is not actually the pathing but the collision handling. In this case the zerglings will push each other with collision resulting in huge performance problems. This is exactly the same performance problem you get in WC3 if you have 100s of air units in the same space and then order them to stop so they start pushing each other. WC3 ground units had no displacement collision mechanics so were not subject to this performance strain, instead they dealt with collisions simply by stopping and waiting to try again.

Graphics has practically nothing to do with it. Sure viewing 1,000 Zerglings will cause the GPU to drop frames due to the complexity of the scene however that alone will not cause the game to slow down. The game will slow down if you move 1,000 Zerglings to the same point and that is due to the complexity of the operation even if your camera is centred nowhere near them and GPU is mostly idle.

SC2 separates graphics from state. Sure graphics will slow state advancement down however that would be due to memory I/O bandwidth and other bottlenecks and not the actual graphics itself. This is different from WC3 where they both shared the same task with their own internal scheduler.

I've never tried moving 1000 zerglings to a point, so I have no comment.

SC2 does not use quad trees for pathing? It uses mesh based pathing. Sure the mesh lookup (which mesh the unit is in) could be done via quad tree however a pointer would be far more efficient. The pathing algorithm of SC2 is that of mesh pathing which is an expansion of node pathing to include area information (so it can handle big and small units separately so the big units do not get stuck in a small gap like in WC3).

There is a hit to the quad tree when groups of units move about the map (pathing and collision are inherently coupled for groups of units).

SC2 has no such optimization. Units will bottleneck and flow rates are not optimized. They appear to flow purely due to the collision algorithm I mentioned earlier which pushes them around. You will still find marines walking left and right if they hit a wall of marines firing (which become unpushable by most units, same as if they hold position) at a target to try and get to the target. This is why you need to push units like marines forward before attacking.

I've never seen that happen. Perhaps it can be substantiated with a youtube video.

No it is not. SC2 does not even use floating point numbers as they are platform dependent (a major source of pain in WC3 as MAC and Windows handle them slightly differently in some circumstances). It uses fixed point numbers instead which are platform independent. The fixed point number range is considerably larger than even a 2048*2048 map so that is not a problem.

Indeed you are correct. I had forgotten about the silly, "seemingly overly specific" unit speeds in sc2 (which is of course related to the fixed precision numbers) example for anyone following this thread

 

[Dr Super Good]

They're absolutely related. Culling works differently in the two engines. In wc3, GL natives are used for culling (high constant cost). In SC2, the quadtree is used for culling (O(lg(n)))

So they still use Open GL natives for culling when running in Direct 3D mode?

There is a hit to the quad tree when groups of units move about the map (pathing and collision are inherently coupled for groups of units).

Actually that sounds like it is part of the "flow" mechanics. What "flow" means is that when you order a unit from one side of the map to another it computes a "flow" the unit can follow to get there. Other units ordered to a similar destination from a nearby source will join the flow saving the pathfinder from re-computing the route. The RTS game 0A.D. was planning on adding such a feature as they have been common in RTS games for a long time now.

Collision and flow lookups are probably quadtree based I agree however RTS games have been using them for space-related lookups for ages now so it is hardly a new thing.

 

[Cokemonkey11]

So they still use Open GL natives for culling when running in Direct 3D mode?

No, direct3d has equivalent culling natives. Full disclosure, I've never personally used them. https://msdn.microsoft.com/en-us/library/windows/desktop/bb204882(v=vs.85).aspx

Actually that sounds like it is part of the "flow" mechanics. What "flow" means is that when you order a unit from one side of the map to another it computes a "flow" the unit can follow to get there. Other units ordered to a similar destination from a nearby source will join the flow saving the pathfinder from re-computing the route. The RTS game 0A.D. was planning on adding such a feature as they have been common in RTS games for a long time now.

Collision and flow lookups are probably quadtree based I agree however RTS games have been using them for space-related lookups for ages now so it is hardly a new thing.

Warcraft 3, in all likelihood, doesn't use any kind of space partitioning. Otherwise we're in general agreement.

 

[Dr Super Good]

Warcraft 3, in all likelihood, doesn't use any kind of space partitioning.

You should run through the assembly to find out! As far as I was aware RTS games have been using quad trees (or other such position orientated trees) since the early days as otherwise there is no way they would scale.

 

[Cokemonkey11]

Warcraft 3 already doesn't scale