A Simple Discrete-Event Simulation: Part 37

Today I finished putting together a basic Path component. It mostly works like a queue but it has “physical” dimensions that take time for the entities to traverse. It also draws the path, its endpoints, and any entities in their proper positions.

The Path is component three in the demo. It’ll take a lot of clicks to get through it.

(Click on the “Step” button to advance through the model, refresh the page to run it again.)

Here’s the code for the Path component.

    function PathComponent() {
      setOfComponents.push(this);
      this.componentID = getNewID();
      this.componentName = "Path";
      this.entryTime = "";
      this.entryEntityID = "";
      this.countInQueue = 0;
      this.exitTime = "";
      this.exitEntityID = "";
      this.exitResidenceTime = "";
      this.x1 = 0.0;
      this.y1 = 0.0;
      this.x2 = 0.0;
      this.y2 = 0.0;
      this.pathLength = 0.0;
      this.nextComponent = null;
      this.entityQueue = [];
      this.traverseQueue = [];
      this.endTraverse = 0.0;
      
      this.getComponentID =function() {
        return this.componentID;
      };
      this.getComponentName =function() {
        return this.componentName;
      };
      this.getEntryTime =function() {
        return this.entryTime;
      };
      this.getEntryEntityID =function() {
        return this.entryEntityID;
      };
      this.getExitTime =function() {
        return this.exitTime;
      };
      this.getExitEntityID =function() {
        return this.exitEntityID;
      };
      this.getCountInQueue =function() {
        return this.countInQueue;
      };
      this.getExitResidenceTime =function() {
        return this.exitResidenceTime;
      };
      
      this.setStartPoint = function(x1,y1) {
        this.x1 = x1;
        this.y1 = y1;
      };
      this.setEndPoint = function(x2,y2) {
        this.x2 = x2;
        this.y2 = y2;
      };
      this.setSpeedTime = function(speed, maxRefreshTime) {
        this.speed = speed;
        this.maxRefreshTime = maxRefreshTime;
      };
      this.calcPathLength = function() {
        this.pathLength = Math.sqrt((this.x2-this.x1)*(this.x2-this.x1) +
                                    (this.y2-this.y1)*(this.y2-this.y1));
        this.endTraverse = this.pathLength;
      };
      this.isOpen = function() {
        if (this.entityQueue.length > 0) {
          if (this.traverseQueue[0] < (10 + 2)) {
            return false;
          }
        }
        return true;
      };
      
      this.drawData = function() {
        this.nodeColor = "#FF00FF";
        this.lineColor = "#FFFFFF";
        globalCTX.strokeStyle = this.lineColor;
        globalCTX.beginPath();
        globalCTX.moveTo(this.x1+0.5,this.y1+0.5);
        globalCTX.lineTo(this.x2+0.5,this.y2+0.5);
        globalCTX.stroke();
        drawNode(this.x1+0.5,this.y1+0.5,3,this.nodeColor);
        drawNode(this.x2+0.5,this.y2+0.5,3,this.nodeColor);
        
        var numEntities = this.entityQueue.length;
        if (numEntities > 0) {
          for (var i=0; i<numEntities; i++) {
            this.entityQueue[i].drawEntity();
          }
        }
      };
      this.assignNextComponent = function(next) {
        this.nextComponent = next;
      };
      this.moveEntity = function(entity) {
        //moves entities down path, but keeps them from overlapping
        //for now assumes radius of 5 and clearance of 2
        //start from discharge end of list
        var index = this.entityQueue.length - 1;
        while ((this.entityQueue[index].entityID != entity.entityID) && (index > 0)) {
          index--;
        }
        var distanceIncrement = this.speed * this.maxRefreshTime;
        var dist = distanceIncrement;
        var timeIncrement = this.maxRefreshTime;
        var nextState = "move";
        if (index < this.entityQueue.length - 1) {
          //not the lead entity, check against next entity
          if (this.traverseQueue[index]+distanceIncrement > (this.traverseQueue[index+1] - 10 - 2)) {
            dist = this.traverseQueue[index+1] - 10 - 2 - this.traverseQueue[index];
            if (dist <= 0.0) {
              dist = 0.0;
              timeIncrement = this.maxRefreshTime; //0.5;
            } else {
              timeIncrement *= dist / distanceIncrement;
            }
          }
        } else {
          //this is the lead entity, check against end of path
          if (this.traverseQueue[index]+distanceIncrement > this.pathLength) {
            dist = this.pathLength - this.traverseQueue[index] + 0.001;
            timeIncrement *= dist / distanceIncrement;
            nextState = "forward";
          }
        }  //TODO: also check against endTraverse, which considers possible entity on subsequent path
        this.traverseQueue[index] += dist; //distanceIncrement;
        var frac = this.traverseQueue[index] / this.pathLength;
        var x = this.x1 + (this.x2 - this.x1) * frac;
        var y = this.y1 + (this.y2 - this.y1) * frac;
        entity.setLocation(x,y);
        feq.newItem(globalSimClock+timeIncrement,this,nextState,entity);
        displayProgressText("Path comp. "+this.componentID+" moves entity "+entity.entityID+" at time "+globalSimClock.toFixed(6));
      };
      this.forwardEntity = function() {
        if (this.nextComponent.isOpen()) {
          this.traverseQueue.pop();
          var entity = this.entityQueue.pop();
          if (entity) {
            this.countInQueue--;
            this.exitTime = globalSimClock;
            this.exitEntityID = entity.entityID;
            displayProgressText("Path comp. "+this.componentID+" forwards entity: "+this.exitEntityID+" at time "+globalSimClock.toFixed(6));
            this.nextComponent.receiveEntity(entity);
          }
        }
      };
      this.receiveEntity = function(entity) {
        //receive the entity
        entity.setLocalEntryTime();  //record time entity entered queue
        entity.setLocation(this.x1,this.y1);
        feq.newItem(globalSimClock+this.maxRefreshTime,this,"move",entity);
        this.traverseQueue.unshift(0.0);
        this.entityQueue.unshift(entity);
        this.countInQueue++;
        //display what was done
        this.entryTime = globalSimClock;
        this.entryEntityID = entity.entityID;
        displayProgressText("Path comp. "+this.componentID+" receives entity: "+this.entryEntityID+" at time "+globalSimClock.toFixed(6));
        //if (this.nextComponent.isOpen()) {
        //  this.forwardEntity();
        //}
      };
      this.activate = function(nextState,entity2) {
        if (nextState == "move") {
          this.moveEntity(entity2);
        } else if (nextState == "forward") {
          this.forwardEntity();
        } else {
          errorUndefinedAdvanceState(this.entityID,this.nextState);
        }      
      };  //this.activate
    }  //PathComponent

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

function PathComponent() {

setOfComponents.push(this);

this.componentID = getNewID();

this.componentName = "Path";

this.entryTime = "";

this.entryEntityID = "";

this.countInQueue = 0;

this.exitTime = "";

this.exitEntityID = "";

this.exitResidenceTime = "";

this.x1 = 0.0;

this.y1 = 0.0;

this.x2 = 0.0;

this.y2 = 0.0;

this.pathLength = 0.0;

this.nextComponent = null;

this.entityQueue = [];

this.traverseQueue = [];

this.endTraverse = 0.0;

this.getComponentID =function() {

return this.componentID;

};

this.getComponentName =function() {

return this.componentName;

};

this.getEntryTime =function() {

return this.entryTime;

};

this.getEntryEntityID =function() {

return this.entryEntityID;

};

this.getExitTime =function() {

return this.exitTime;

};

this.getExitEntityID =function() {

return this.exitEntityID;

};

this.getCountInQueue =function() {

return this.countInQueue;

};

this.getExitResidenceTime =function() {

return this.exitResidenceTime;

};

this.setStartPoint = function(x1,y1) {

this.x1 = x1;

this.y1 = y1;

};

this.setEndPoint = function(x2,y2) {

this.x2 = x2;

this.y2 = y2;

};

this.setSpeedTime = function(speed, maxRefreshTime) {

this.speed = speed;

this.maxRefreshTime = maxRefreshTime;

};

this.calcPathLength = function() {

this.pathLength = Math.sqrt((this.x2-this.x1)*(this.x2-this.x1) +

(this.y2-this.y1)*(this.y2-this.y1));

this.endTraverse = this.pathLength;

};

this.isOpen = function() {

if (this.entityQueue.length > 0) {

if (this.traverseQueue[0] < (10 + 2)) {

return false;

}

return true;

};

this.drawData = function() {

this.nodeColor = "#FF00FF";

this.lineColor = "#FFFFFF";

globalCTX.strokeStyle = this.lineColor;

globalCTX.beginPath();

globalCTX.moveTo(this.x1+0.5,this.y1+0.5);

globalCTX.lineTo(this.x2+0.5,this.y2+0.5);

globalCTX.stroke();

drawNode(this.x1+0.5,this.y1+0.5,3,this.nodeColor);

drawNode(this.x2+0.5,this.y2+0.5,3,this.nodeColor);

var numEntities = this.entityQueue.length;

if (numEntities > 0) {

for (var i=0; i<numEntities; i++) {

this.entityQueue[i].drawEntity();

}

};

this.assignNextComponent = function(next) {

this.nextComponent = next;

};

this.moveEntity = function(entity) {

//moves entities down path, but keeps them from overlapping

//for now assumes radius of 5 and clearance of 2

//start from discharge end of list

var index = this.entityQueue.length - 1;

while ((this.entityQueue[index].entityID != entity.entityID) && (index > 0)) {

index--;

}

var distanceIncrement = this.speed * this.maxRefreshTime;

var dist = distanceIncrement;

var timeIncrement = this.maxRefreshTime;

var nextState = "move";

if (index < this.entityQueue.length - 1) {

//not the lead entity, check against next entity

if (this.traverseQueue[index]+distanceIncrement > (this.traverseQueue[index+1] - 10 - 2)) {

dist = this.traverseQueue[index+1] - 10 - 2 - this.traverseQueue[index];

if (dist <= 0.0) {

dist = 0.0;

timeIncrement = this.maxRefreshTime; //0.5;

} else {

timeIncrement *= dist / distanceIncrement;

}

} else {

//this is the lead entity, check against end of path

if (this.traverseQueue[index]+distanceIncrement > this.pathLength) {

dist = this.pathLength - this.traverseQueue[index] + 0.001;

timeIncrement *= dist / distanceIncrement;

nextState = "forward";

}

} //TODO: also check against endTraverse, which considers possible entity on subsequent path

this.traverseQueue[index] += dist; //distanceIncrement;

var frac = this.traverseQueue[index] / this.pathLength;

var x = this.x1 + (this.x2 - this.x1) * frac;

var y = this.y1 + (this.y2 - this.y1) * frac;

entity.setLocation(x,y);

feq.newItem(globalSimClock+timeIncrement,this,nextState,entity);

displayProgressText("Path comp. "+this.componentID+" moves entity "+entity.entityID+" at time "+globalSimClock.toFixed(6));

};

this.forwardEntity = function() {

if (this.nextComponent.isOpen()) {

this.traverseQueue.pop();

var entity = this.entityQueue.pop();

if (entity) {

this.countInQueue--;

this.exitTime = globalSimClock;

this.exitEntityID = entity.entityID;

displayProgressText("Path comp. "+this.componentID+" forwards entity: "+this.exitEntityID+" at time "+globalSimClock.toFixed(6));

this.nextComponent.receiveEntity(entity);

}

};

this.receiveEntity = function(entity) {

//receive the entity

entity.setLocalEntryTime(); //record time entity entered queue

entity.setLocation(this.x1,this.y1);

feq.newItem(globalSimClock+this.maxRefreshTime,this,"move",entity);

this.traverseQueue.unshift(0.0);

this.entityQueue.unshift(entity);

this.countInQueue++;

//display what was done

this.entryTime = globalSimClock;

this.entryEntityID = entity.entityID;

displayProgressText("Path comp. "+this.componentID+" receives entity: "+this.entryEntityID+" at time "+globalSimClock.toFixed(6));

//if (this.nextComponent.isOpen()) {

// this.forwardEntity();

//}

};

this.activate = function(nextState,entity2) {

if (nextState == "move") {

this.moveEntity(entity2);

} else if (nextState == "forward") {

this.forwardEntity();

} else {

errorUndefinedAdvanceState(this.entityID,this.nextState);

}

}; //this.activate

} //PathComponent

Here’s how the Path component is instantiated and initialized. In the longer run we want a very generalizable element that can connect anything to anything, including to other Paths. In practice we’ll define nodes independently and then link the paths to pairs of nodes so that completely arbitrary networks can be defined. For now the endpoints are defined directly within the Path component. The Path has an implied direction, and elements can only move along it one way. That said, the path can go in any direction on the screen and the code will handle it naturally.

    //schedule for six hours of arrivals in half-hour blocks
    var arrivalSchedule = [0,0,1,3,4,4,5,6,3,2,1,0]; 
    
    var arrival1 = new ArrivalsComponent(30.0,arrivalSchedule);
    arrival1.defineDataGroup(10,10,80,"#00FFFF","#FF0000","#FFFF00");

    var entry1 = new EntryComponent(2.0);
    entry1.defineDataGroup(175,10,80,"#00FFFF","#FF0000","#FFFF00");
    
    arrival1.assignNextComponent(entry1);
    
    var path1 = new PathComponent();
    path1.setStartPoint(180,73);
    path1.setEndPoint(320,196);
    path1.setSpeedTime(7.5,1.0);
    path1.calcPathLength();
    
    entry1.assignNextComponent(path1);
    
    var exit1 = new ExitComponent(2.0);
    exit1.defineDataGroup(175,196,80,"#00FFFF","#FF0000","#FFFF00");
    exit1.assignPreviousComponent(path1);
    
    path1.assignNextComponent(exit1);

//schedule for six hours of arrivals in half-hour blocks

var arrivalSchedule = [0,0,1,3,4,4,5,6,3,2,1,0];

var arrival1 = new ArrivalsComponent(30.0,arrivalSchedule);

arrival1.defineDataGroup(10,10,80,"#00FFFF","#FF0000","#FFFF00");

var entry1 = new EntryComponent(2.0);

entry1.defineDataGroup(175,10,80,"#00FFFF","#FF0000","#FFFF00");

arrival1.assignNextComponent(entry1);

var path1 = new PathComponent();

path1.setStartPoint(180,73);

path1.setEndPoint(320,196);

path1.setSpeedTime(7.5,1.0);

path1.calcPathLength();

entry1.assignNextComponent(path1);

var exit1 = new ExitComponent(2.0);

exit1.defineDataGroup(175,196,80,"#00FFFF","#FF0000","#FFFF00");

exit1.assignPreviousComponent(path1);

path1.assignNextComponent(exit1);

If entities are moving along the path they are going at the assigned speed; there is no mechanism for accelerating and decelerating. That can be added later if we want. Entities are assumed to have a radius of five and require a clearance of two. For the time being the units of measure are in screen pixels. Later we’ll have to add in the ability to scale the elements, which will add another layer of complexity. If an element cannot move the full distance it “wants” to, because it has to wait for an element in front of it to move out of the way, it pauses for a definable interval (I think one time unit in the demo) and then tries to move again. This is akin to simulating the reaction time of people or vehicles edging forward in queues. They don’t all move in lockstep, they take a certain amount of time to react to the space that opens up in front of them.

I had to add another layer of complexity to the discrete event handling mechanism because we are treating the moving entities as being entirely passive. If an entity within a component needs to be moved according to independent logic that uses the discrete event handling mechanism, then the item that goes into the future events queue has to carry information about the component and the specific entity within the component. Looking at the relevant calls:

        //creating a new event item in the Path component's move method
        //"this" refers to the Path component
        //"entity" refers to the specific item being moved
        feq.newItem(globalSimClock+timeIncrement,this,nextState,entity);
...
        //calls in the main event processing looop
        //note the second parameter added to the activate method
        var itemList = feq.getFirstItem();
        
        if (itemList) {
          feqCurrent = itemList[0];
          feqCurrent.entity.activate(feqCurrent.getNextState(),feqCurrent.entity2);

//creating a new event item in the Path component's move method

//"this" refers to the Path component

//"entity" refers to the specific item being moved

feq.newItem(globalSimClock+timeIncrement,this,nextState,entity);

...

//calls in the main event processing looop

//note the second parameter added to the activate method

var itemList = feq.getFirstItem();

if (itemList) {

feqCurrent = itemList[0];

feqCurrent.entity.activate(feqCurrent.getNextState(),feqCurrent.entity2);

Here’s the updated definition of the newItem method in the FutureEventsQueue object. The only change is that it passes the newly added fourth parameter, the one pointing to the internal entity, to the new FutureEventItem call.

      this.newItem = function(time,entity,nextState,entity2) {
        //create futureEventItem
        var feqItem = new FutureEventItem(time,"absolute",entity,nextState,entity2);
        this.insertTime = feqItem.getActivationTime();
        globalInsertTime = this.insertTime;
        if (this.feqSize == 0) {  
          this.feq[0] = feqItem;
          this.feqSize++;
        } else {
          //find index of feq item to insert before
          //findIndex is a native JavaScript method of the Array object
          var insertIndex = this.feq.findIndex(this.findLaterTime);
          //insert the element
          if (insertIndex < 0) {
            insertIndex = this.feq.length;
          }
          this.feq.splice(insertIndex,0,feqItem);
          this.feqSize++;
        }
      };

this.newItem = function(time,entity,nextState,entity2) {

//create futureEventItem

var feqItem = new FutureEventItem(time,"absolute",entity,nextState,entity2);

this.insertTime = feqItem.getActivationTime();

globalInsertTime = this.insertTime;

if (this.feqSize == 0) {

this.feq[0] = feqItem;

this.feqSize++;

} else {

//find index of feq item to insert before

//findIndex is a native JavaScript method of the Array object

var insertIndex = this.feq.findIndex(this.findLaterTime);

//insert the element

if (insertIndex < 0) {

insertIndex = this.feq.length;

}

this.feq.splice(insertIndex,0,feqItem);

this.feqSize++;

}

};

Here’s the updated code for the FutureEventItem object. All it does is store the extra entity reference.

    //future events queue item
    function FutureEventItem(time,type,entity,nextState,entity2) {
      this.activationTime = 0.0;
      this.nextState = nextState;
      if (type == "advance") {
        this.activationTime = globalSimClock + time;  //activate 'time' from now
      } else if (type == "absolute") {
        if (time >= globalSimClock) {
          this.activationTime = time;                 //activate at specified absolute time, if in future
        } else {
          displayProgressText("Invalid time past time supplied A.  Entity ID: "+entity.entityID+" Current Time: "+globalSimClock+" Specified Time: "+time.toFixed(6));  //alert on invalid time
        }
      }
      this.entity = entity;
      this.entity2 = entity2;
      this.getActivationTime = function() {
        return this.activationTime;
      };
      this.update = function(time,type,nextState) {
        this.nextState = nextState;
        if (type == "advance") {
          this.activationTime = globalSimClock + time;  //activate 'time' from now
        } else if (type == "absolute") {
          if (time >= globalSimClock) {
            this.activationTime = time;                 //activate at specified absolute time, if in future
          } else {
            displayProgressText("Invalid time past time supplied B.  Entity ID: "+this.entity.entityID+" Current Time: "+globalSimClock+" Specified Time: "+time.toFixed(6));  //alert on invalid time
          }
        }
      };
      this.getNextState = function() {
        return this.nextState;
      };
      this.reportItem = function() {
        console.log("Time: "+this.activationTime+" ID: "+this.entity.entityID);
      };
    }  //FutureEventItem

//future events queue item

function FutureEventItem(time,type,entity,nextState,entity2) {

this.activationTime = 0.0;

this.nextState = nextState;

if (type == "advance") {

this.activationTime = globalSimClock + time; //activate 'time' from now

} else if (type == "absolute") {

if (time >= globalSimClock) {

this.activationTime = time; //activate at specified absolute time, if in future

} else {

displayProgressText("Invalid time past time supplied A. Entity ID: "+entity.entityID+" Current Time: "+globalSimClock+" Specified Time: "+time.toFixed(6)); //alert on invalid time

}

this.entity = entity;

this.entity2 = entity2;

this.getActivationTime = function() {

return this.activationTime;

};

this.update = function(time,type,nextState) {

this.nextState = nextState;

if (type == "advance") {

this.activationTime = globalSimClock + time; //activate 'time' from now

} else if (type == "absolute") {

if (time >= globalSimClock) {

this.activationTime = time; //activate at specified absolute time, if in future

} else {

displayProgressText("Invalid time past time supplied B. Entity ID: "+this.entity.entityID+" Current Time: "+globalSimClock+" Specified Time: "+time.toFixed(6)); //alert on invalid time

}

};

this.getNextState = function() {

return this.nextState;

};

this.reportItem = function() {

console.log("Time: "+this.activationTime+" ID: "+this.entity.entityID);

};

} //FutureEventItem

Here’s the working result of all this, in the activate method of the Path component:

      this.activate = function(nextState,entity2) {
        if (nextState == "move") {
          this.moveEntity(entity2);
        } else if (nextState == "forward") {
          this.forwardEntity();
        } else {
          errorUndefinedAdvanceState(this.entityID,this.nextState);
        }      
      };  //this.activate

this.activate = function(nextState,entity2) {

if (nextState == "move") {

this.moveEntity(entity2);

} else if (nextState == "forward") {

this.forwardEntity();

} else {

errorUndefinedAdvanceState(this.entityID,this.nextState);

}

}; //this.activate

JavaScript is bizarre in many ways but one of the nice things about it is that if you choose not to include parameters at the end of the list for function calls, and the relevant variables or parameters are never accessed, then everything goes on working as before. That means that all the other uses of this mechanism that don’t use the extra entity parameter will continue to work without modification. We have to keep track of this kind of thing carefully. JavaScript won’t let you shoot yourself in the foot in the same way that C or C++ will, but it’ll give you a whole new set of creative ways to do it.

There are some other things that bear further description but I’ll get to those shortly.

I want to observe that I do most of my editing in Notepad++ but I occasionally use WebStorm to help me find certain classes of errors I introduce. I typically do this when the debugger in Firefox refuses to display the code, which means it had trouble parsing something, and I can’t find the error quickly. I may then go through the code to follow some of WebStorm’s suggestions about style, through not all of them. I’ve turned off flipping if-else statements and eliminating curly brackets in one-line loops and if statements, for example.

I do not use WebStorm for interactive debugging because it doesn’t have access to the DOM. That’s only accessible to the debugger built into each browser.

A Simple Discrete-Event Simulation: Part 37

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Categories

Meta