Time Traveling

06-07-2008, 02:55 AM

So I came up with a very abstract idea for a map that I may or may not make, which centers around the idea that you can force time to instantly go back a number of seconds in order to solve puzzles or kill certain enemies. Obviously there would be no point in this if EVERYTHING went back in time and you just did the same actions over again, therefor there would be two interesting aspects:

Hidden information:

So great idea right? Impossible to make, right? Probably. I'm by no means fluent in vjass, but I got to thinking how this would be possible to pull off, and I came up with this very crude and buggy code. Perhaps somebody could help me to come up with a better method, and help smooth it out.

JASS:

library TimeSystem initializer TimeSystemInit needs ObjectCache 


//The variables are arrays because I store each slice of time with its associated 
//data as one array index, and use these indexes as a type of stack where the 
//[0] index is always the newest, and values which fall over the total size of the 
//array are removed.

private struct UnitData  
  //These variables store certain aspects of the unit periodically 
  //(Every 0.1 seconds)
  real array stime[299]
  real array sx[299]
  real array sy[299]
  real array slife[299]
  real array smana[299]
  
  //These variables record any orders issued to the unit, and the 
  //time they were issued at. They are only recorded when an order 
  //is issued: they are not periodically stored.
  real array otime[99]
  integer array oid[99]
  widget array otarget[99]
  real array ox[99]
  real array oy[99]
endstruct


globals
    public trigger OrderImmediateTrigger           = CreateTrigger()
    public trigger OrderPointTrigger               = CreateTrigger()
    public trigger OrderTargetTrigger              = CreateTrigger()
    
    private trigger AddTrigger                      = CreateTrigger()
    private timer Timer                            = CreateTimer()
    private timer Clock                            = CreateTimer()
endglobals




private function OrderConditions takes nothing returns boolean
    return true
endfunction

private function AddConditions takes nothing returns boolean
    return true
endfunction

private function PreloadConditions takes unit u returns boolean
    return true
endfunction

private function PeriodicConditions takes nothing returns boolean
    return true
endfunction

//******************************************************************************
//******************************************************************************


//When a unit is taken back in time, first the game finds the last status entry 
//right before the destination-time. Since the status is recorded every 0.1 
//seconds, the time the unit actually moves back to will be within 0.1 
//seconds of the actual destination time. Obviously this ignores the fact that 
//the unit might have died and needs to be revived, but that can be worked 
//in later.

//Next, after the unit is placed and its status is set, The game finds the 
//most recent order issued to the unit before the destination-time, since this 
//will be the order that the unit was following at the destination-time. I 
//still need to add in some way to detect when a unit finishes its order and 
//begins to idle, so I could store the "stop" command at that point.

function Backtrack takes real time, boolean absolute returns nothing
  local integer i = 0
  local UnitData dat
  local group g = CreateGroup()
  local unit u
  local real r = 0.
    if absolute == false then
        set time = TimerGetElapsed(Clock) - time
    endif
    if time < 0.1 then
        set time = 0.1
    endif
    if time > TimerGetElapsed(Clock) then
        set time = TimerGetElapsed(Clock)
    endif
    if time < TimerGetElapsed(Clock) - 29.9 then
        set time = TimerGetElapsed(Clock) - 29.9
    endif
    
    call GroupEnumUnitsInRect(g, bj_mapInitialPlayableArea, Condition(function PeriodicConditions))
    
    loop
        set u = FirstOfGroup(g)
        exitwhen u == null
        set dat = GetUnitUserData(u)
        
        set i = 0
        loop
            exitwhen dat.stime[i] <= time
            set i = i + 1
        endloop
        
        call SetUnitX(u, dat.sx[i])
        call SetUnitY(u, dat.sy[i])
        call SetWidgetLife(u, dat.slife[i])
        call SetUnitState(u, UNIT_STATE_MANA, dat.smana[i])
        
        
        set i = 0
        loop
            exitwhen dat.otime[i] <= time
            set i = i + 1
        endloop

        if dat.otarget[i] != null then
            call IssueTargetOrderById(u, dat.oid[i], dat.otarget[i])
        elseif dat.ox[i] != 0. then
            call IssuePointOrderById(u, dat.oid[i], dat.ox[i], dat.oy[i])
        else
            call IssueImmediateOrderById(u, dat.oid[i])
        endif
        
        call GroupRemoveUnit(g, u)
    endloop
        
  call DestroyGroup(g)
  set g = null
  set u = null
endfunction

private function Run takes nothing returns nothing
  local group g = CreateGroup()
  local unit u
  local UnitData dat
  local integer i = 0
    call GroupEnumUnitsInRect(g, bj_mapInitialPlayableArea, Condition(function PeriodicConditions))
  
    loop
        set u = FirstOfGroup(g)
        exitwhen u == null
        set dat = GetUnitUserData(u)
        set i = 299
        loop
            exitwhen i == 0
            if dat.stime[i-1] > 0. then
                set dat.stime[i] = dat.stime[i-1]
                set dat.sx[i] = dat.sx[i-1]
                set dat.sy[i] = dat.sy[i-1]
                set dat.slife[i] = dat.slife[i-1]
                set dat.smana[i] = dat.smana[i-1]
            endif
            set i = i - 1
        endloop
        set dat.stime[0] = TimerGetElapsed(Clock)
        set dat.sx[0] = GetUnitX(u)
        set dat.sy[0] = GetUnitY(u)
        set dat.slife[0] = GetWidgetLife(u)
        set dat.smana[0] = GetUnitState(u, UNIT_STATE_MANA)
        call GroupRemoveUnit(g, u)
    endloop

  
  call DestroyGroup(g)
  set g = null
  set u = null
endfunction

private function Load takes nothing returns nothing
  local UnitData dat = UnitData.create()
    call SetUnitUserData(GetEnteringUnit(), dat)
    set dat.otime[0] = 0.1
    set dat.oid[0] = String2OrderIdBJ("stop")
    set dat.ox[0] = 0.
    set dat.oy[0] = 0.
    set dat.otarget[0] = null
endfunction

private function OrderImmediate takes nothing returns nothing
  local UnitData dat = GetUnitUserData(GetOrderedUnit())
  local integer i = 99
    loop
        exitwhen i == 0
        if dat.otime[i-1] > 0. then
            set dat.otime[i] = dat.otime[i-1]
            set dat.oid[i] = dat.oid[i-1]
            set dat.ox[i] = dat.ox[i-1]
            set dat.oy[i] = dat.oy[i-1]
            set dat.otarget[i] = dat.otarget[i-1]
        endif
        set i = i - 1
    endloop
    set dat.otime[0] = TimerGetElapsed(Clock)
    set dat.oid[0] = GetIssuedOrderId()
    set dat.ox[0] = 0.
    set dat.oy[0] = 0.
    set dat.otarget[0] = null
endfunction

private function OrderTarget takes nothing returns nothing
  local UnitData dat = GetUnitUserData(GetOrderedUnit())
  local integer i = 99
    loop
        exitwhen i == 0
        if dat.otime[i-1] > 0. then
            set dat.otime[i] = dat.otime[i-1]
            set dat.oid[i] = dat.oid[i-1]
            set dat.ox[i] = dat.ox[i-1]
            set dat.oy[i] = dat.oy[i-1]
            set dat.otarget[i] = dat.otarget[i-1]
        endif
        set i = i - 1
    endloop
    set dat.otime[0] = TimerGetElapsed(Clock)
    set dat.oid[0] = GetIssuedOrderId()
    set dat.ox[0] = 0.
    set dat.oy[0] = 0.
    set dat.otarget[0] = GetOrderTarget()
endfunction

private function PointTarget takes nothing returns nothing
  local UnitData dat = GetUnitUserData(GetOrderedUnit())
  local integer i = 99
    loop
        exitwhen i == 0
        if dat.otime[i-1] > 0. then
            set dat.otime[i] = dat.otime[i-1]
            set dat.oid[i] = dat.oid[i-1]
            set dat.ox[i] = dat.ox[i-1]
            set dat.oy[i] = dat.oy[i-1]
            set dat.otarget[i] = dat.otarget[i-1]
        endif
        set i = i - 1
    endloop
    set dat.otime[0] = TimerGetElapsed(Clock)
    set dat.oid[0] = GetIssuedOrderId()
    set dat.ox[0] = GetOrderPointX()
    set dat.oy[0] = GetOrderPointY()
    set dat.otarget[0] = null
endfunction

//******************************************************************************
//******************************************************************************

private function PreloadUnits takes nothing returns boolean
  local UnitData dat
    if PreloadConditions(GetFilterUnit()) then
        set dat = UnitData.create()
        call SetUnitUserData(GetFilterUnit(), dat)
        set dat.otime[0] = 0.1
        set dat.oid[0] = String2OrderIdBJ("stop")
        set dat.ox[0] = 0.
        set dat.oy[0] = 0.
        set dat.otarget[0] = null
    endif
    return false
endfunction

private function TimeSystemInit takes nothing returns nothing
    local rect r = GetWorldBounds()
    local region re = CreateRegion()
    local boolexpr b = Condition(function PreloadUnits)
    local group g = CreateGroup()
    local integer i = 0
    
    set OrderImmediateTrigger = CreateTrigger()
    call TriggerAddAction(OrderImmediateTrigger, function OrderImmediate)
    call TriggerAddCondition(OrderImmediateTrigger, Condition(function OrderConditions))
    call TriggerRegisterAnyUnitEventBJ( OrderImmediateTrigger, EVENT_PLAYER_UNIT_ISSUED_ORDER )
    
    set OrderTargetTrigger = CreateTrigger()
    call TriggerAddAction(OrderTargetTrigger, function OrderTarget)
    call TriggerAddCondition(OrderTargetTrigger, Condition(function OrderConditions))
    call TriggerRegisterAnyUnitEventBJ( OrderTargetTrigger, EVENT_PLAYER_UNIT_ISSUED_TARGET_ORDER )
    
    set OrderPointTrigger = CreateTrigger()
    call TriggerAddAction(OrderPointTrigger, function PointTarget)
    call TriggerAddCondition(OrderPointTrigger, Condition(function OrderConditions))
    call TriggerRegisterAnyUnitEventBJ( OrderPointTrigger, EVENT_PLAYER_UNIT_ISSUED_POINT_ORDER )
    
    call GroupEnumUnitsInRect(g, r, b)
    
    set AddTrigger = CreateTrigger()
    call RegionAddRect(re, r)
    call TriggerRegisterEnterRegion(AddTrigger, re, null)
    call TriggerAddAction(AddTrigger, function Load)
    call TriggerAddCondition(AddTrigger, Condition(function AddConditions))
    
    call TimerStart(Timer, 0.1, true, function Run)
    call TimerStart(Clock, 99999., false, null)
    
    call RemoveRect(r)
    call DestroyGroup(g)
    call DestroyBoolExpr(b)
    set re = null
    set g = null
    set b = null
    set r = null
endfunction
endlibrary

The perfect solution to this problem would be a trigger which keeps a timeline of every units' life/mana/position every 0.1 seconds, as well as a timeline of every order issued to the unit. The timelines kept should be complete and go back to the map's initialization, or when the unit was initially created. Certain unit-types would be exempt from the system, as well as units with certain buffs.

06-07-2008, 04:08 AM	#2
Pheonix-IV	Would probably be easier with a 'Save' ability that saves your current location as a ghost. After X seconds, you are reverted to the position, hp, mana ect of the point where you saved and the ghost does what you did in those 20 seconds. That way you can look forward, rather than back, and you don't need to store giant wads of data all the time, which will probably lag like bejeesus.

06-07-2008, 04:24 AM	#3
Malf	Also add a Reload ability for that so you don't have to always wait 20 seconds :D

06-07-2008, 09:36 AM

Themerion

Correct me if I'm wrong, but doesn't the 299-limit mean that you can have maximally 27 units?

Code:

floor( 8120 / 299 ) = (81/3) = 27

I think the method is the way to go, but I see some things in the code which might be improved:

Regarding the groups. Right now, you're asking Warcraft for every unit in the playable map area. You do this every 0.1 seconds. I'm thinking it would perhaps be better to remember all units, and then use call ForGroup(g,function MyEnumFunc)

JASS:

globals
    private group g
endglobals

function RunX takes nothing returns nothing
//    loop
//        set u = FirstOfGroup(g)
//        exitwhen u == null
// The looping is done by ForGroup now, so we don't need the stuff above.
        local unit u=GetEnumUnit()
        local UnitData dat = GetUnitUserData(u)
        set i = 299
        loop
            exitwhen i == 0
            if dat.stime[i-1] > 0. then
                set dat.stime[i] = dat.stime[i-1]
                set dat.sx[i] = dat.sx[i-1]
                set dat.sy[i] = dat.sy[i-1]
                set dat.slife[i] = dat.slife[i-1]
                set dat.smana[i] = dat.smana[i-1]
            endif
            set i = i - 1
        endloop
        set dat.stime[0] = TimerGetElapsed(Clock)
        set dat.sx[0] = GetUnitX(u)
        set dat.sy[0] = GetUnitY(u)
        set dat.slife[0] = GetWidgetLife(u)
        set dat.smana[0] = GetUnitState(u, UNIT_STATE_MANA)
//        call GroupRemoveUnit(g, u)
//    endloop
    set u=null
endfunction

function Run takes nothing returns nothing
//...
// Instead of the FirstOfGroup stuff, we use the ForGroup-native.
// It is supposed to be faster.
    call ForGroup(g, function RunX)
endfunction

function Load/PreloadUnits takes nothing returns nothing/boolean
//...
// When the units are initialized for the system, we add them to the group:
    call GroupAddUnit(g,GetEnteringUnit()/GetFilterUnit())
endfunction

function TimeSystemInit takes nothing returns nothing
//...
set g=CreateGroup()
endfunction

Also, you should probably add some cleanup when a unit dies/decays (just use a trigger with one of those events, or add a check in the loop). You have to use UnitData.destroy() if you want to recycle one of your 27 unit-slots. You should of course also remove the unit from the global group (which I mentioned above).

_____ Regarding the looping: _____

The 299=i part doesn't make sense to me. It does seem that you are moving a lot of data though. Wouldn't it be better to just move the pointer to the data?

JASS:

globals
    private integer i=-1
endglobals

// inside the looping-function
if i>=298 then
    set i=0
else
    set i=i+1
endif

set dat.stime[i] = TimerGetElapsed(Clock)
set dat.sx[i] = GetUnitX(u)
set dat.sy[i] = GetUnitY(u)
set dat.slife[i] = GetWidgetLife(u)
set dat.smana[i] = GetUnitState(u, UNIT_STATE_MANA)

Then when you want to retrieve the data, you'll just check where i is.

06-07-2008, 03:20 PM	#5
Szythe	I implemented everything you said, themerion, and I see a tremendous increase in performance. So there's no way to get around the max array size thing, huh? That sucks. I guess I'll have to keep the number of units tracked at one time to a minimum.

06-07-2008, 04:09 PM	#6
grim001	You can use linked lists instead of arrays to have infinite storage size.

06-07-2008, 04:40 PM

Vexorian

Quote:

JASS:

private struct UnitData[400000]
  //These variables store certain aspects of the unit periodically 
  //(Every 0.1 seconds)
  real array stime[299]
  real array sx[299]
  real array sy[299]
  real array slife[299]
  real array smana[299]
  
  //These variables record any orders issued to the unit, and the 
  //time they were issued at. They are only recorded when an order 
  //is issued: they are not periodically stored.
  real array otime[99]
  integer array oid[99]
  widget array otarget[99]
  real array ox[99]
  real array oy[99]
endstruct

Now your instance limit is 1337 (no pun intended)

Yeah linked lists might work better, it is not like you need random access, do you? It won't mean inifinite storage though. I think 299 is too high, I also don't understand why you would have to store all of that per unit.

You could also use gamecache, I think restoring the unit from gamecache should take less time than manually restoring it from some struct that has limits. I think I saw a Darky time travel spell like this.

06-07-2008, 09:29 PM

Szythe

Alright I have something almost-working, but there's one problem. As values are stored to the lists, the game begins to lag more and more. This is because every time I add a value, the game loops through every previous value in the list. The game needs to do more and more work in order to save new values as the game progresses, and the lag begins to build up.

JASS:

function LL_AddListItemInBackOf takes location list, integer listitem, real value returns nothing
  local location loc
  local integer i = 0
  loop
    exitwhen listitem == i
    set list = LL_ly(list)
    set i = i + 1
  endloop
  set loc = Location(value,GetLocationY(list))
  call MoveLocation(list, GetLocationX(list), LL_h2r(loc))

06-07-2008, 11:02 PM	#9
grim001	That's not really the function you want to be using to add new things to the end of a list, you should just have a global location which is marked to be the end of the list, and add something onto that.

06-07-2008, 11:22 PM	#10
Vexorian	I must really say, please, trash that stuff, don't ever use a location based linked list, never, really, it is not worth it. If you really think breaking the limit is that important, use gamecache, at least it is not a location based system list, and you don't need I2H, really, dude, you made me feel as if the dark age was back...

06-08-2008, 12:14 AM	#11
Szythe	I'm worried about performance issues with using gamecache though. I'm storing about 7 values to every unit every 0.1 seconds, and storing 5 values to a unit whenever it is issued an order.

06-08-2008, 03:36 AM	#12
grim001	I guess you could make a linked list out of structs and take advantage of the extended array limit, although slower than normal structs it should still be faster than GC.

06-08-2008, 03:47 AM

#13

Vexorian

Quote:

Originally Posted by Szythe

I'm worried about performance issues with using gamecache though. I'm storing about 7 values to every unit every 0.1 seconds, and storing 5 values to a unit whenever it is issued an order.

You are assuming:
- That performance is worth the risk of greatly breaking your map.
- That the handle count overhead caused by big location linked lists + the large amount of function calls needed for them will cause a lesser hit on performance than gamecache.

06-08-2008, 04:18 AM	#14
grim001	I agree, ditch the location method and go with GC or extended structs.

06-08-2008, 10:45 AM

#15

Themerion

You could use GC, or extended structs (I'd prefer structs over GC).

The real performance gain is when you do this though:

Quote:

Originally Posted by Szythe

I guess I'll have to keep the number of units tracked at one time to a minimum.

I'm not saying you shouldn't have more than 27 units; but you'll definitively save performance if you keep the number low.