Module Design - Master Line Object


This object was designed by Tom Walcott.
It was last updated on April 29th, 1998.


Private Data:
Line XLine[]: This is a dynamic array of all line objects with GetAxis()==X.
Line YLine[]: This is a dynamic array of all line objects with GetAxis()==Y.
boolean testedIntersection[][]: This two dimensional array is of size 9x8; large enough to encompass every intersection point on the screen. It is manipulated and traversed by the routine that searches for a feasible path for a link between nodes.

Overview: The Master Line Object is responsible for three things. First, for finding the most efficient path for a link between two given nodes. Second, for invoking the Paint() method on all line objects. Third, maintaining a comprehensive list of all line objects.
public  void PaintAll();
Overview: Paint all the line objects.
Parameters: None.
Pre-conditions: None.
Post-conditions: All lines should be displayed upon the screen in the locations dictated by their respective co-ordinates.
Algorithm: Move through both arrays, invoking the Line::Paint() routines. It is worthy of note that this would be the correct location to invoke the offscreen drawing commands, prior to the invocation. Once these calls to the Line::Paint() routines have completed, the screen should be updated.
Interaction with other objects: Invokes the Paint() method upon every Line Object.
Error conditions: None.
Return value: None.
public  void ClearLine(Line);
Overview: Remove a Line Object from the appropriate array. This method will be called when a Line Object has just set LineCount to 0.
Parameters: A handle to the Line Object.
Pre-conditions: None.
Post-conditions: None.
Algorithm: Move through the array. Find the handle to the appropriate Line Object. Direct that handle to null.
Interaction with other objects: No.
Error conditions: If an existing Line Object does not exist within the Master Line Object, this is Bad. Should such a state occur, and that line attempt to delete itself, there are far more severe problems than can be addressed realistically at this point. Nonetheless, attempting to delete something that is already gone shouldn't return an error, because... well, the Master Line Object will already be in an appropriate state as if the command had completed successfully. In case of such a failed command, throw an exception.
Return value: None.
private  void AddLine(Line)
Overview: Add a Line Object to the appropriate array in the Master Line Object.
Parameters: A handle to the Line Object to be added.
Pre-conditions: None.
Post-conditions: None.
Algorithm: Move through the appropriate array. Find a handle referencing null. Make it point to Line Object. If there isn't a handle referencing null, make the array bigger. Since it's a dynamic array, this shouldn't be a problem.
Interaction with other objects: No.
Error conditions: If for some reason this should prove impossible, we should probably halt execution of the program. It is remotely conceivable that running out of memory could make allocation of array space impossible, in which case the whole program will probably be running into problems in short order. Throw an exception upon such a failure.
Return value: None.
private  int CostRoute(int startX, int startY, int endX, int endY);
Overview: Find the cost of a single line between intersection startX, startY and endX, endY.
Parameters: Two intersection co-ordinates.
Pre-conditions: These intersections must be identical in some orientation.
Post-conditions: None.
Algorithm: We have four possible return values, which correspond to priorities of low, medium, high, and impossible. High priority is in the condition that there are no other lines in that river at any point, and the return value should be 1. Medium priority corresponds to there being at some point up to two other lines in that river, and will return 3. Low indicates that there are over two other lines in that river, and shall return 5. Impossible indicates that a river is at some point full, and shall return 99. Use a brute force search through the line arrays in order to find our answer.
Interaction with other objects: No.
Error conditions: None.
Return value: One of the set {1,3,5,99}.
public  Link MakeLink(Node from, int linkType);
Overview: Create a Link Object which contains a link between node 'from' and node 'to'.
Parameters: We take only one node, and the linkType. It is necessary that SetPrev or SetNext have already been invoked by the master node object, as then the passed in node -- the source of the link -- will have the destination set appropriately, and the linkType will be sufficient information to obtain a handle to the destination node.
Pre-conditions: SetPrev or SetNext must have been already invoked from the master node object.
Post-conditions: None.
Algorithm: I am going to introduce a new notation at this point, in order to describe intersections. Ysi is the Y co-ordinate of the default starting intersection, Ydi for the default destination intersection's Y co-ordinate. The private function FindRoute takes the parameters: Xsi, Ysi, Xdi, Ydi where it is assumed that Xsi, Xdi differ by at most one, and Ysi, Ydi differ by at most one. It should never be the case that both differ by one. This would confuse everyone.

1) Get the locations of both the source and target nodes.

2) Create a new Link object, clear private two dimensional intersection array.

3) Create the first Line Object associated with this link, which shall be the line leading from the source node to the middle of the channel associated with the appropriate side of that node (see linkType).

4) Calculate the minimum displacement for a route to the target node. This calculation is the sum of the differences between each co-ordinate pair, i.e. | Xsi - Xdi | + | Ysi - Ydi |.

5) Determine if a link terminating at the destination node passes through a local intersection ((Xsi, Ysi) or (Xsi, Ysi+1)). Should a link do so, create a line to that location and iterate the count for every line object from that point onwards to the destination. (This determination will be ((Xsi, Ysi) or (Xsi+1, Ysi)) for tree nodes.)

6) Determine a destination node. The destination node will be determined as follows: Generate a list of all intersections which are immediately above and below the destination node, as well as all intersections which contain links with the same destination and (in the case of doubly linked lists) direction (left or right.)

7) Employ Dijkstra's algorithm in order to calculate the best lines to follow. The calculation of line cost will be performed by the FindRoute() function, with an added offset of +2 for any potential line that does not move towards the destination node (i.e., which does not lower the X or Y co-ordinate variance between the source and destination).

8) The first link to reach a node in the destination node list will become the link that we employ. Repeated use of this methodology will establish a list of intersections which lead from a source node to the destination node. Add line segments to the link object that has been created, using the following algorithm to determine the value of the fixed axis:

Examine the line segment to be added. Generate a list of the free river locations for it to occupy. If the next line segment is going to extend the current line segment along the same access, generate a similar list for the next segment, and settle upon the first common element of the list. The free river location list is to have the following prioritization:

Middle of the river, mid-left, mid-right, then left to right, skipping already examined locations. (i.e., if there are 7 channels labelled 1-7, left to right, the possibilities would be examined in the following order: 4, 2, 6, 1, 3, 5, 7.)

The fixed axis value for the next line segment will need to be calculated before the start and end co-ordinates can be designated for the current one -- this is due to the need for right angle intersections. Because of this, if two consecutive line segments share the same fixed axis and can occupy the same value for the fixed axis, it is possible to merge them into a single line object.

Once adequate information for the current line segment has been determined, a fair amount of information for the next line segment will have been mandated. As each line segment is completed, the data is used to construct a new line segment object. As each line segment object is constructed, the Link::AddLine() method will be invoked to add that line segment to the link, and also invokes this::AddLine() to add the line to the local arrays.

Interaction with other objects: Invokes other methods on this object; beyond that, none.
Error conditions: None.
Return value: A Link Object with a collection of valid line objects associated with it. It shall also be the case that the line objects are known by the master line object.

Search engine sitemap created by