Spherical forums

Sphere Development => Sphere Support => Topic started by: mezzoEmrys on December 02, 2013, 02:40:40 am

Title: Optimization of "frequency of acting" turn structure
Post by: mezzoEmrys on December 02, 2013, 02:40:40 am
As part of my current project I am giving every entity a "speed" value which determines the frequency of when each entity acts. However, my current implementation involves stepping through a numerical "turn", then seeing if any entity or effect needs to trigger on that turn, currently by iterating through all the entities and effects in play on the map.
However, this process of stepping through the turns becomes visible while playing, with each player turn becoming obviously delayed, even when the player is the only entity on the map.
I suppose my question here would be how could I optimally implement this "frequency of acting" turn structure?
Title: Re: Optimization of "frequency of acting" turn structure
Post by: Radnen on December 02, 2013, 03:33:04 am
How many entities are you stepping through? 2 million?
Title: Re: Optimization of "frequency of acting" turn structure
Post by: Flying Jester on December 02, 2013, 04:01:26 am
Can we see the code?

I've implemented this kind of thing before. Here's the idea of how I did it:

Code: [Select]

function unit(speed){
  this.speed = speed;
  this.time  = 0;
}

for(var i in units){
  units[i].time+=units[i].speed;
  if(units[i].time>MAX_TIME){ //MAX_TIME is some variable, let's say 100 or so, which is greater than the max speed.
    units[i].time%=MAX_TIME;
    units[i].doAction();
  }
}


You could change it so that instead of doing some action, you just flag the unit as having the ability to do an action, and then in an 'action phase' you let every unit that is flagged perform an action, and then unflag them.
If that was too slow, I would consider upping the speeds or lowering MAX_TIME, in case most iterations were just dry-firing and increasing the times, not actually flagging or performing actions. But that would take either a lot of units or an astronomically high MAX_TIME and miniscule speed attribute.
Title: Re: Optimization of "frequency of acting" turn structure
Post by: mezzoEmrys on December 02, 2013, 10:23:03 am
The thing is I'm only checking the one entity. However, the way it's written now, since most of the information is stored in a 2d array, I'm technically stepping through each place in the array, checking to see if it is occupied and, if it is, seeing if what's in that particular spot has anything it needs to do.
So, right now, it has to go through each of n spaces each of x times between each turn.

Having a list of units that actually need to do something would definitely help performance, and iterating through the map only once to fill it seems like a much better plan. And Jester's example still seems better than the plan I came up with last night.

My current plan is a priority queue setup where it will pop the highest priority "turn" that needs to occur next, then subtract that priority from the rest, then push in the next "turn" for that entity that would occur a certain time away. A quick visual example of this:
Code: [Select]

Queue Contents: 2(a), 5(b), 6(c)
queue.pop() - Queue Contents: 5(b), 6(c) -> 3(b), 4(c)
queue.push(a, 2) - Queue Contents: 2(a), 3(b), 4(c)
queue.pop() - Queue Contents: 3(b), 4(c) -> 1(b), 2(c)
queue.push(a, 2) - Queue Contents: 1(b), 2(c), 2(a)
queue.pop() - Queue contents: 2(c), 2(a) -> 1(c), 1(a)
queue.push(b, 5) - Queue contents: 1(c), 1(a), 5(b)


I'll probably get to trying to implement this once I'm actually awake, then see how useful it is to me compared to Jester's much simpler code.
Title: Re: Optimization of "frequency of acting" turn structure
Post by: Fat Cerberus on December 03, 2013, 01:09:41 am
It seems like what you want here is FFX-style (CTB) turn resolution, where a character with higher SPD gets more turns than one with lower SPD, right?  How I did that in Spectacles was, I have my list of units, each of which has a timer that is set according to their AGI stat (higher AGI = smaller timer).  Every cycle I continuously decrement all the timers until one (or more) reaches zero, at which point those at zero can act and have their timers reset, then I start a new cycle, rinse and repeat.

I'd post some pseudocode but I'm on my iPhone right now so that would be a pain in the ass. :)
Title: Re: Optimization of "frequency of acting" turn structure
Post by: mezzoEmrys on December 03, 2013, 01:33:03 am
My priority queue works like those timers, except that it jumps straight to the next one that would take an action and cuts out from everyone else's timers the increment that was jumped. It works a lot better, I think I just had to stop and talk out my problem to realize what was actually going on in my code versus what should have been happening.
A quick view of the code:
Code: [Select]
function pQueue(){
var q = new Array();
function qSlot(entity, priority){
this.e = entity;
this.p = priority;
};
qSlot.prototype.toString = function() { return this.p; };
this.add = function(entity, priority){
q.push(new qSlot(entity, priority));
};
this.pop = function(){
q.sort();
var g = q.shift();
var n = q.length;
for(var i = 0; i < n; i++){
q[i].p -= g.p;
}
return g.e;
};
this.get = function(){
return q;
};
}

It takes advantage of a few speedup functions, but the closer to 0 your priority is the faster (relatively) you move. Each entity is responsible for resetting its own timer, and it doesn't account for getting hasted between turns shortening the time until the next turn, but that's fine by me. The important thing is that the visual lag is much less.
Title: Re: Optimization of "frequency of acting" turn structure
Post by: Radnen on December 03, 2013, 01:48:59 am
Hmm, ever thought about implementing a priority queue with a binary heap? You can insert in sorted order, that way you don't need to sort each time. In fact, if you don't want to do that could you just add the sort on the add method? To me it seems in the span of pop, sort does nothing besides sort out entities that had been newly added, but the thing is, if you added entities at the beginning and run successive pops, you are likely sorting an already sorted array. It's hard to tell... Maybe....

Code: (javascript) [Select]

function pQueue(){
var q = new Array();
        var dirty = false;     // change

function qSlot(entity, priority){
this.e = entity;
this.p = priority;
};

qSlot.prototype.toString = function() { return this.p; };

this.add = function(entity, priority){
q.push(new qSlot(entity, priority));
                dirty = true;
};

this.pop = function(){
                if (dirty) { q.sort(); dirty = false; }  // change
var g = q.shift();
var n = q.length;
for(var i = 0; i < n; i++){
q[i].p -= g.p;
}
return g.e;
};

this.get = function(){
return q;
};
}


That way you at least cut out sorting already sorted lists. But I doubt that will be markedly faster. :P
Title: Re: Optimization of "frequency of acting" turn structure
Post by: mezzoEmrys on December 03, 2013, 02:00:35 am
If I knew how to implement a binary heap off the top of my head, I probably would :P
Seriously though, I considered putting it in add instead of in pop, but I couldn't find a good way of adding things in. A binary heap is probably the best plan, so I'll see about writing that in tomorrow. All it'll probably take is a moment with pen and paper to remind myself how they work and a general framework for writing it. For now, I probably will update it to include the dirty/clean just for the small speed increment I'll get.
Nothing gets added to the queue after the map is generated so putting it in add really is the best plan.
Title: Re: Optimization of "frequency of acting" turn structure
Post by: Fat Cerberus on December 03, 2013, 10:25:50 am

My priority queue works like those timers, except that it jumps straight to the next one that would take an action and cuts out from everyone else's timers the increment that was jumped. It works a lot better, I think I just had to stop and talk out my problem to realize what was actually going on in my code versus what should have been happening.
A quick view of the code:
Code: [Select]
function pQueue(){
var q = new Array();
function qSlot(entity, priority){
this.e = entity;
this.p = priority;
};
qSlot.prototype.toString = function() { return this.p; };
this.add = function(entity, priority){
q.push(new qSlot(entity, priority));
};
this.pop = function(){
q.sort();
var g = q.shift();
var n = q.length;
for(var i = 0; i < n; i++){
q[i].p -= g.p;
}
return g.e;
};
this.get = function(){
return q;
};
}

It takes advantage of a few speedup functions, but the closer to 0 your priority is the faster (relatively) you move. Each entity is responsible for resetting its own timer, and it doesn't account for getting hasted between turns shortening the time until the next turn, but that's fine by me. The important thing is that the visual lag is much less.


This is essentially what I do as well, my method is functionally equivalent to finding the unit(s) with the smallest timer, letting those act, and then subtracting that smallest value from all the other unit's timers.  The reason I have it implemented the way I do (decrement in a loop until zero is hit) is for encapsulation purposes, to allow individual units to manage their own timers (the battle engine itself isn't even aware of the timers).  The engine simply calls each unit's tick() method, and tick() returns true if the unit performed an action, which ends the cycle.  This method allows me to get a lot of precision in turn resolution with no noticeable lag, even with large timer values.