how simultaneous acs scripts "combine" into 1 linear sequential code?

Doomworld Forums : Powered by vBulletin version 2.2.5

Doomworld Forums > Classic Doom > Doom Editing > how simultaneous acs scripts "combine" into 1 linear sequential code?

Author

All times are GMT. The time now is 14:29.

gggmork
If you can make any sense of this post, congratulations

Posts: 2379
Registered: 06-07

Its awesome how acs scripts are so modular and able to run simultaneously; just curious how this all works/breaks down for the REAL code, if anyone knows. Say I have 2 scripts:

code:
script 1 enter
{
    while(1)
    {
        //thrust some thing +1 on x axis
        delay(6);
    }
}

script 2 enter
{
    while(1)
    {
        //change some light to some array's next value
        delay(7);
    }
}
}

So we have TWO separate while loops going on SIMULTANEOUSLY (one going slightly slower due to a 6 delay instead of 7). But when the scripts get converted into real code (in c or whatever I assume) both these whiles have to get stuffed into a SINGLE while, amirite, I mean unless you have 173 processors running in parallel for 173 simultaneous scripts which almost definitely isn't what's going on.

So, ultimately the real code probably has ONE linear sequential while loop (kinda like how simple atari breakout games etc have only 1 game while loop) that takes AWAY both script while loops and stuffs what they do inside ITS while loop, maybe like:

code:
script1Counter = 0;
script2Counter = 0;
while(1)
{
    if (script1Counter == 6)
    {
        //thrust some thing +1 on x axis
    }

    if (script2Counter == 7)
    {
        //change some light to some array's next value
    }
    script1Counter = (script1Counter+1)%6;
    script2Counter = (script2Counter+1)%7;
}

If it seriously does something like that, "rewriting" all the whiles and ifs of the scripts and reinterpreting them so they work in a single while, that's pretty crazy. And having complex scripts with multiple nested whiles and delays and stuff seems tricky to convert into a single while.

02-20-13 17:27 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Blzut3
Member

Posts: 375
Registered: 06-04

You are correct in that the ACS VM run in a single thread so technically there is one big loop. However, the order that the scripts get executed is implementation specific. While technically trying to run scripts in multiple real threads would likely quickly run into a deadlock, you should imagine each script as its own thread running on a single core system.

As for how this is implemented in C(++). You maintain a list of running scripts. ACS_Execute pushes a script onto the list. The ACS VM iterates through the list executing the script until it reaches a delay or terminates. If it delays it goes onto the blocked queue until the delay condition is met. At which point it is scheduled to run again.

For a more in depth description look at operating system schedulers, in particular the simple FIFO scheduler which would likely be used by every ACS VM. (Since scripts always execute within a tic more complex scheduling algorithms aren't needed.)

An important thing to remember is that ACC compiles to byte code (similar to Java or .NET) so the VM only sees a linear sequence of instructions which it needs to execute (with loops and conditionals telling the VM to jump to another point in the sequence).

02-20-13 18:45 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Gez
Why don't I have a custom title by now?!

Posts: 9143
Registered: 07-07

Compiled ACS turns into a bytecode, which is run by an ACS VM. Each script is an independent object, and each script gets run in turn by the VM. So you have the VM running script 1, and when it reaches the "delay" instruction, the VM puts script 1 in pause, remembering where it stopped but otherwise ceasing to run it, then goes on to run the next script. Each time, until it gets to the end of the script or a delay instruction. When it iterates through a paused script, it looks if the delay is still active or not; if it's still being delayed then it leaves it paused, otherwise it resumes running that script's instructions.

The exact order through which the ACS VM iterates through the script is not really defined by any spec; and indeed ZDoom's VM and vanilla Hexen's VM order them differently. (So ZDoom has had to get a compat hack to run vanilla Hexen maps when one was found which relied on simultaneous scripts being run in a given order.)

02-20-13 18:46 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

gggmork
If you can make any sense of this post, congratulations

Posts: 2379
Registered: 06-07

That seems a lot simpler than the complex code rewrite I was imagining. I guess I was still stuck in more naive "source code" thinking where while loops aren't really broken out of (except break; statements, but they don't remember where they left off.. and goto but I came from python which didn't have that). Simply leaving a particular instruction in a while (and remembering where you left off) and jumping straight to an instruction in another while gives more freedom. Seems that when a script is paused, in addition to the row number being remembered, all the values of the local script variables would have to be remembered. But I guess that's a given automatic because its not like any separate script will change those local values.

Since delay() kinda means pauseThisScriptUntilConditionAndUnpauseNextScriptIfCondition(), I guess that's why delays can't be in functions. But still if a delay is in a function, and that function is used in a script... then the delay kinda is IN the script.

02-20-13 20:14 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Blzut3
Member

Posts: 375
Registered: 06-04

I guess to better explain how the VM works: Here's script 12 from Hexen's map01:

code:script 12 (void)  
{
    int var0;
    int var1;

    mapvar3 = 1;
    while(var1 < 20)
    {
        while(var0 < 4)
        {
            Pillar_BuildAndCrush(40+var0, random(const:8, 32), 0, 20);
            tagwait(40+var0);
            Pillar_Open(40+var0, random(const:8, 32), 0, 0);
            var0++;
        }
        var0 = 0;
        var1++;
    }
}

The VM sees the following only in binary form (there are no rows):

code:Script12:
        pushnumber 1
        assignmapvar 3
BeginOuterLoop:
        pushscriptvar 1
        pushnumber 20
        lt    
        ifnotgoto EndOuterLoop
BeginInnerLoop:
        pushscriptvar 0
        pushnumber 4
        lt   
        ifnotgoto EndInnerLoop
        pushnumber 40 
        pushscriptvar 0
        add  
        randomdirect 8, 32
        pushnumber 0
        pushnumber 20
        lspec4 94
        pushnumber 40
        pushscriptvar 0
        add
        tagwait
        // Script will block here until the tag stops moving
        pushnumber 40
        pushscriptvar 0
        add 
        randomdirect 8, 32
        pushnumber 0
        pushnumber 0
        lspec4 30
        incscriptvar 0
        goto BeginInnerLoop
EndInnerLoop:
        pushnumber 0
        assignscriptvar 0
        incscriptvar 1
        goto BeginOuterLoop
EndOuterLoop:
        terminate

When tagwait is hit, the "thread" is placed on the blocked queue until the tag stops moving. It is then moved to the ready queue and is executed on the next VM pass.

The reason delay can't be used in a function is some VMs (ZDoom and I would assume Hexen), use a global stack which needs to be cleared between each script and consequently each tic. Because of this, when the execution resumes the call stack can not be unwound (so return wouldn't work). IIRC from my discussions with DavidPH, Eternity's VM does save the stack so it would be able to successfully execute a delay in a function.

02-20-13 21:37 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

gggmork
If you can make any sense of this post, congratulations

Posts: 2379
Registered: 06-07

Interesting, thanks for the responses. Kinda reminds me of forth which is a stack based language I read about but never used (how an operation like a plus gets pushed after the 2 numbers to operate on).
Its pretty insane that humans have actually made something as complicated/hierarchical/lifelike as computers.

02-20-13 23:18 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Quasar
Moderator

Posts: 5141
Registered: 08-00

My suggestion for further reading would be to look up "coroutines", as ACS scripts are more or less exactly that. It's a surprisingly complex notion for what appears on the surface to be a toy-like scripting language and is pretty unique in the way it manages to emulate a multi-process / time-sharing system. Not even JavaScript has any true analogue of this feature.

EDIT: I said Python didn't either but apparently they've been working on adding them to the language.

02-22-13 03:32 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

gggmork
If you can make any sense of this post, congratulations

Posts: 2379
Registered: 06-07

Thanks, jargon words like that help home in on interesting information and this is all just out of curiosity.

It seems like the compiler should be able to rewrite/reinterpret all functions as just code blocks nested inside scripts to make the delays work. Just basically copy paste each function into every spot its used in the script and change 'return' to '=' (but I don't really know what I'm ~~talking~~ writing about).

Also I suspect something like floor_waggle is its own script just like any other. Because it does stuff for multiple tics, even using a variable to alter the movement direction repeatedly. If so it might be useful/interesting to put the code for each action special on the zdoom wiki (but that of course takes someone's time/effort).

02-22-13 04:31 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Gez
Why don't I have a custom title by now?!

Posts: 9143
Registered: 07-07

Floor_Waggle and other specials are a different thing entirely. When you call Floor_Waggle from ACS, all the script does is create a "thinker" for the tagged sectors. It's that thinker that will update the sector information every tic.

Thinkers are a fundamental part of the Doom engine; whereas ACS is something that Raven tacked on to get more flexibility. You can make a game without ACS, but nothing would work without thinkers. Everything that changes any property of sectors (floor height, ceiling height, light level, floor texture, ceiling texture, anything!) is a thinker. You couldn't open a door if there were no thinkers.

02-22-13 12:36 #

Profile || Blog || PM || Search || Add Buddy

IP || Edit/Delete || Quote

Quasar
Moderator

Posts: 5141
Registered: 08-00

The relation of thinkers to ACS should be thought of as this: an ordinary thinker is one with its per-tic action implemented as native code. An ACS script is a thinker with its action implemented in ACS. Every running script does indeed have a thinker, which keeps track of its state in the form of the IP, wait data, local variables, etc. It's the thinker loop (originally P_RunThinkers) that implements the cooperative multitasking.

This is why ACS scripts have to call a wait function if they loop forever - the time in which they need to complete their current task is a mere fraction of a single gametic. If they run too long, no other thinkers get a chance to run, and the processing time for a tic will exceed 1/35 sec. ZDoom and EE both implement checks to cap the amount of instructions a script can run, so that the game doesn't lock up permanently.

http://i.imgur.com/jxv9XJGl.png

Last edited by Quasar on 02-22-13 at 13:40

02-22-13 13:26 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Blzut3
Member

Posts: 375
Registered: 06-04

gggmork said:
It seems like the compiler should be able to rewrite/reinterpret all functions as just code blocks nested inside scripts to make the delays work. Just basically copy paste each function into every spot its used in the script and change 'return' to '=' (but I don't really know what I'm ~~talking~~ writing about).

This is called function inlining. However, to handle recursion, circular calls, and whatever else you still need a call stack. It could be solved by allocating a stack in an array, but you'll need a more advanced compiler than ACC to do this. Though if it were really a big issue then it would be something to solve at the VM level.

02-22-13 13:56 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

gggmork
If you can make any sense of this post, congratulations

Posts: 2379
Registered: 06-07

The rabbit hole of complexity continues. The real trick is to find the first turtle because then you know its turtles all the way down:
https://en.wikipedia.org/wiki/Turtles_all_the_way_down

I was wondering if the 500,000 (or whatever) actions per tic cap could be raised, but I guess not as quasar mentioned (if everything is tic based (as opposed to time I guess) it seems like it shouldn't matter and the whole game would simply run slower if something took a long time, merely delaying other stuff until they can be sequentially calculated too, but whatever).

So far, I found ways to get past that limit and no delays in functions though. For example, recently I tagged 160 sectors in a tesselation. I wanted to make the program calculate the neighboring adjacent sectors per sector (because I didn't want to do it by hand). I used a funny trick where for each sector: turn the light off, then for each OTHER sector turn to darkest adjacent. IF it changed dark then you know its adjacent so add it to the list of neighbors for that sector (then turning lights back on).

However I put the above in a function, and it turned out to be maybe quadruple 500,000 actions so made a "runaway script terminated". So I needed a delay and thought, I'll just put a delay(1) after checking each fourth of the sectors (so there will only be 4 delay(1)s and it'll still go fast essentially.
But no delays allowed in functions, so I made functionPart1(), functionPart2() etc part 3/4. then put the delay(1) in the script after every part. Would have been better to just make that neighbor calculating function a script instead so I could put the 4 delays directly inside without redundant mostly identical copy pasted function parts, but whatever.

Another slight hangup is you can only move a floor/ceiling once per tic, so sometimes best to just use a variable representing height so it can change multiple times, then only move actual floor at end of tic.

I didn't think of recursion since I almost never use it. Lol at deSwizzle().

And since there's no defined order for scripts, a seemingly obvious workaround could be put a delay(1/2/3/etc) at the beginning of each script depending on how you want them to sequentially run.

Last edited by gggmork on 02-22-13 at 17:28

02-22-13 17:04 #

Profile || Blog || PM || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote

Quasar
Moderator

Posts: 5141
Registered: 08-00

gggmork said:

I was wondering if the 500,000 (or whatever) actions per tic cap could be raised, but I guess not as quasar mentioned (if everything is tic based (as opposed to time I guess) it seems like it shouldn't matter and the whole game would simply run slower if something took a long time, merely delaying other stuff until they can be sequentially calculated too, but whatever).

It could be raised, to a million or any other arbitrary number. It's just a matter of how much responsiveness you want sacrificed before it gets decided that the script is deadlocking the system (it's impossible to know for sure whether the script will ever terminate or not, as per application of the Church-Turing thesis to the halting problem).

02-22-13 17:30 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

IP || Edit/Delete || Quote